Liste dinamice-Pascal Pascal - Pascal - Programare - Articole Director

Structuri de date dinamice (aproximativ pot fi găsite pe forum)

Obiectul de date are o structură dinamică în cazul în care dimensiunea sa variază în timpul execuției programului sau este potențial infinit.

Clasificarea structurilor de date

Folosit pentru a programa datele pot fi împărțite în două grupe majore:

Aceste structuri statice - aceste date, pozițiile relative și relațiile de elemente care rămân întotdeauna constantă.

Structura de date dinamice - aceste date, a cărui structură internă este formată dintr-o lege, dar numărul de elemente și relația lor relativă poate fi modificată în mod dinamic în timpul execuției programului, conform legii formării.

Structura de date dinamice:

Prin structura dinamică a fișierelor de date includ, date dinamice care nu au legătură și conexe.

Rețineți că fișierele din clasificarea atribuită structurilor de date dinamice. Acest lucru este realizat pe baza definiției de mai sus. Deși eliminarea și elemente în mijlocul fișierului inserarea nu este permisă, dar lungimea fișierului în program se pot schimba - crește sau descrește la zero. Și aceasta este proprietățile dinamice ale fișierului ca o structură de date.

Variabilele statice și dinamice în Pascal

Memoria dinamică (DP) - un PC de memorie furnizat de program în timpul funcționării sale, mai puțin segmentul de date (64K), stiva (16 Kb) și corpul propriu-zis al programului. dimensiunea memoriei dinamice pot fi variate. Implicit DP - toate memoria disponibilă a PC-ului.

DP - este de fapt singura posibilitate de a procesa matrici mari de date de dimensiuni. Multe probleme practice sunt dificil sau imposibil de rezolvat fără a utiliza DP. De exemplu, în dezvoltarea de alocare de memorie statică CAD este imposibilă, deoarece dimensiunea modelelor matematice în diferite proiecte pot varia în mod semnificativ.

Pentru a lucra cu variabile dinamice în cadrul programului trebuie urmate următoarele etape:

• alocare de memorie pentru variabila dinamică;
• Inițializa indicatorul;
• Ușurării memoriei după folosind o variabilă dinamică.

Programatorul însuși trebuie să rezerve un loc, pentru a determina valoarea indicatorului, eliberați DP.

În schimb, puteți utiliza orice dinamică variabilă statică, dar fără o nevoie reală de acest lucru nu este în valoare de a face.

Pointer asociat cu un anumit tip de date specifice, numit un pointer tastat. Descrierea lui este după cum urmează:

Un indicator care nu este asociat cu un anumit tip de date se numește un indicator netipizat. Pentru a descrie indicii în Pascal există fără tip este un tip standard de pointer. Descrierea indicatorului este după cum urmează:

Folosind indicii care este netipizat aloca dinamic structura de date și tipul care variază în timpul execuției programului.

Ar fi de așteptat ca valoarea indicatorului poate fi trecut la alta. De fapt, puteți transmite valori doar între indicii asociate cu un singur tip de date. Pointeri la diferitele tipuri de date sunt de diferite tipuri, și aceste tipuri nu sunt compatibile.

Cu toate acestea, această restricție nu se aplică în cazul unui indicator netipizat. Programul include următoarele acțiuni vor fi permise:

Alocarea și eliberarea memoriei dinamice

Toate DP este considerat ca un șir de octeți continuu, care este numit un morman.

Locație heap în memoria PC-ului.

• Heaporg - începutul haldei;
• Heapend - sfârșitul haldei;
• Heapptr - limita actuală a neocupat DP.

Alocarea memoriei este realizată în conformitate cu procedura de variabilă dinamică:

Grafic, noile proceduri de acțiune pot fi reprezentate după cum urmează:

Eliberarea procedura heap se efectuează:

Procedura Exemplu fragment de program se elimina

Rețineți că aplicarea repetată a procedurilor de eliminare în mod liber indicatorul poate duce la erori.

Procedura Evacuați eliberează memoria luată de variabila dinamică. În acest caz, indicatorul este nedefinit.

Orice acțiune a indicatorului în program sunt situate între noile proceduri și evacuez.

Când se utilizează variabilele alocate dinamic apare adesea o problemă generală numită scurgere de memorie dinamică. scurgere de memorie - este o situație în care spațiul este alocat în grămadă, iar apoi a pierdut - pentru un motiv oarecare, indicatorul nu indică mai mult decât suprafața alocată, astfel încât să nu se poate elibera spațiu. O cauza frecventa de pierderi de memorie este rebindings variabile dinamice fără precedent de presă. Cel mai simplu caz este urmatoarea:

fragment de program EXEMPLU

var IntPointer: ^ Integer;
începe
Noi (IntPointer);
Noi (IntPointer);
end.

Primul apel din nou heap alocat 2 octeți, și au pus IntPointer indicatorul. Al doilea apel noi scoate în evidență alte 2 octeți, și IntPointer instalat pe ele. Acum, nu aveți un indicator ce indică spre primele 2 octeți, astfel încât să nu le pot elibera. Programul acestor octeți vor fi pierdute.

Atribuirea la indicatorul

Pentru a inițializa indicii există mai multe posibilități.

operațiune indicatorul

Pentru indicii sunt definite numai operatorul de atribuire și de verificare pentru egalitate sau inegalitate. În Pascal interzice orice operații aritmetice pe indicii, lor de intrare-ieșire și comparație cu mai mult mai puțin.

Încă o dată regulile de atribuire indicatoare:

• Puteți atribui orice indice zero constantă standard, ceea ce înseamnă că indicele nu se referă la orice celulă de memorie special;
• standard, indicii de tip pointer pointer compatibile cu orice tip;
• un pointer la un anumit tip de date poate fi atribuit numai valoarea indicatorului de același tip de date sau standard.

Pointerii pot fi comparate pentru egalitate sau de inegalitate, de exemplu:

Dacă p1 = p2 atunci ... ..
În cazul în care p1<>p2 apoi ... ..

funcții standard sunt definite în Pascal pentru indicii:

Atribuirea de valori variabilelor dinamice

Date de alocare dinamică pot fi folosite oriunde în program, ceea ce a permis utilizarea unor tipuri adecvate de expresii.

R ^: = sqr (R ^) + I ^ -17;
q ^: = 2; inc (q ^); writeln (q ^)

Este inadmisibil de a utiliza expresii cum ar fi următoarele:

Luați în considerare exemplul de lucru cu indicii:

structuri dinamice

Listele liniare (chain one-way).

Lista este o structură de date, în cazul în care fiecare element printr-un pointer asociat cu elementul următor.

Fiecare element al listei legate, în primul rând, păstrează unele informații, și în al doilea rând indică elementul următor. Deoarece elementul listă stochează diferite tipuri de (informații stocate și un pointer), atunci este firesc să reprezinte o înregistrare în care câmpul este situat într-un singur obiect, iar celălalt - un pointer la următoarea înregistrare de același tip. Această înregistrare se numește un link. și structura acestor intrări se numește o listă, sau un lanț.

Numai la primul element din listă (cap), un indice separat. Ultimul element din listă nu va indica.

Descriere lista

Descrierea EXEMPLU Lista

Type = ^ S Vezi;
S = înregistrare
Inf: integer;
Următor: Vezi;
End;

În Pascal există o regulă de bază care trebuie să fie descris înainte de utilizarea oricărui obiect. O excepție se face numai pentru indicii care pot referire la tipul nu a fost încă declarată.

Crearea unei liste

Pentru lista a existat, este necesar să se definească un pointer la începutul său.

Descrierea EXEMPLU Lista

Type = ^ S Vezi;
S = înregistrare
Inf: integer;
Următor: Vezi;
End;

Să creeze primul element listă:

Vom continua pentru a crea o listă. Pentru a face acest lucru, adăugați un element la fiecare capăt al listei, sau în cap.

A) Adăugați elemente la cap de listă. Pentru a face acest lucru, trebuie să efectuați o secvență de acțiuni:

• obține memorie pentru noul element;
• pune din nou informațiile;
• atașați elementul de la capul listei.

In timp ce u<> nil do
începe
Writeln (u ^ .inf);
u: = u ^ .Etapele;>
se încheie;

Eliminarea unui element din listă

A) Eliminarea primului element. În acest scop, în indexul secundar va aminti primul element, un pointer la capul listei pentru a trece la următorul element din listă și pentru a elibera zona haldei, ceea ce indică faptul subindex.

x: = u;
în timp ce (x<> nil) și (x ^. inf<> cifre) fac
începe
dx: = x;
x: = x ^ .Etapele;
se încheie;
dx: = x ^ .Etapele:
dispune (x);

B) îndepărtarea de la sfârșitul listei. Pentru a face acest lucru, aveți nevoie pentru a găsi elementul penultimul.

x: = u; dx: = u;
în timp ce x ^ .Etapele<> nil do
începe
dx: = x; x: = x ^ .Etapele;
se încheie;
dx ^ .Etapele: = zero;
dispune (x);

Trecerea listei. Este important să fie capabil de a sorta elementele din listă, efectuați orice operație. Să presupunem că vrem să găsim suma unei liste de articole.

summa: = 0;
x: = u;
în timp ce x<> nil do
începe
summa: = summa + x ^ .inf;
x: = x ^ .Etapele;
se încheie;

obiecte dinamice ale structurii complexe

Utilizarea listelor unidirecționale poate provoca unele dificultăți în rezolvarea unui număr de probleme. Faptul că lista de purtător se poate deplasa numai într-o singură direcție, de la capul listei la ultimul link. În același timp adesea necesar să se facă o operație cu elementul care precede elementul cu proprietățile dorite. Cu toate acestea, după ce a constatat elementul cu o anumită proprietate într-o listă unidirecțional, nu avem nici o modalitate de a obține rapid și convenabil de a avea acces la elementul anterior.

Type = ^ S Vezi;
S = înregistrare
Inf: integer;
Următor: Vezi;
Pred: Vezi;
End;

Structura dinamică formată din unități de tip numit lista bidirecțională. care poate fi reprezentată schematic după cum urmează:

În programare, liste de două ori legate sunt adesea generalizate după cum urmează: ca valoare domeniu de ultima verigă Următoarea ia o trimitere la elementul din titlu, și ca valoare de câmp Pred link-ul din titlu - un link către ultimul link:

Există diferite metode de utilizare liste dinamice:

• Stiva - un tip special de listă, la care accesul este doar un pointer la primul element. Dacă doriți să adăugați la elementul stivă, acesta se adaugă în fața primului element, indicatorul în partea de sus a stivei este comutată la noul element. Algoritmul stivei este caracterizat de regula „ultima in - first out“.
• Coadă - o vizualizare listă, având două indicii la primul și ultimul element al lanțului. Elemente noi sunt scrise după ultima, iar componentele probei este primul. Algoritmul de „primul venit - primul ieșit“.
• Posibilitatea de a organiza liste de acces aleatoriu la elementele. În acest caz, aveți nevoie de un indicator suplimentar pentru elementul curent.

Având în vedere un fișier text, nu mai mare de 64 Kb cuprinzând numere reale, câte unul în fiecare rând. Suprascrieți conținutul unui fișier într-o matrice, plasându-l într-o grămadă. Se calculează valoarea medie a elementelor de matrice. heap clară. Creați o întreagă gamă de dimensiuni 10000, umple-l cu numere întregi aleatoare în intervalul de -100 până la 100, și se calculează valoarea medie a acestuia.

? 200 '200px': '' + (this.scrollHeight + 5) + 'px'); „>
Programul Srednee;
Const NMax = 10000;
Type Diapazon = 1..NMax;
MasInt = Array # 91; Diapazon] Din Integer;
MasReal = Array # 91; Diapazon] Real;
Var PIint. ^ MasInt; PReal. ^ MasReal;
Eu, Midint. longInt; MidReal. Real; T. text; string S.;
începe
Scrie ( 'Introduceți numele fișierului:' # 41 ;; readln (S # 41 ;;
Asociați (T, S # 41 ;; Reset (T # 41 ;; MidReal: = 0; MidInt: = 0;
Randomizează;
NEW (PReal # 41 ;;

Deși nu EOF (T # 41; Do
Inceput readln (T, PReal ^ # 91; I] # 41 ;; MidReal: = MidReal + PReal ^ # 91; I] End;
DISPUNE (PReal # 41 ;;
NEW (Pint # 41 ;;

Pentru I: = 1 până la NMAX Do
Inceput pint ^ # 91; I]: = -100 + aleatoare (41 # 201 ;; MidInt: = MidInt + pint ^ # 91; I] End;

WriteLn ( 'întreg mediu egal cu:', MidInt Div NMax # 41 ;;
WriteLn ( 'mediu real bine:'., (MidReal / NMAX # 41; 10. 6 Nr 41;
Sfârșit.

// limbajul C ++
#include
#include
#include
#include
#define NMAX 10000
MasInt int typedef;
typedef float MasReal;
MasInt * pint; MasReal * PReal;
int I, n, MidInt; float MidReal; char S # 91; 255];
FILE T *; char * endptr;
void main (# 41;
> S;
t = fopen (S, "r" # 41 ;;
MidReal = 0; MidInt = 0;
randomizarea (# 41 ;; I = 0;
/ * Aloca memorie pentru matrice reale * /
PReal = (MasReal * # 41; malloc (sizeof (MasReal # 41; # 41 ;;
/ * Intrare și însumării matrice reale * /
în timp ce (feof (t # 41;! # 41;
PReal # 91; I] = strtod (S, endptr # 41 ;; // converti șirul de intrare la un număr real
MidReal + = PReal # 91; I]; I ++;>
n = I + 1;
liber (PReal # 41 ;; / * Ștergere matrice reale * /
Pint = (MasInt * # 41; malloc (sizeof (MasInt # 41; # 41 ;; / * Aloca memorie array sub un * /
/ * Calculati suma întregii matrice * /
pentru (I = 0; I MidInt + = pint # 91; I];>
/ * Afișarea valorilor medii * /
cout <<"\nсреднее целое равно " < cout <<"среднее вещественное равно: " < fclose (t # 41 ;;
>

Creați un program care, pe baza unei liste predeterminate formează alte două, plasând primul dintre ele pozitive, iar al doilea - elemente negative, lista originală.

? 200 '200px': '' + (this.scrollHeight + 5) + 'px'); „>
Programul Ex_sp_1;
Folosește Spisok;
Var S1, S2, S3, V1, V2, V3. U; A. BT; I, N. Byte;
începe
Randomizează;
N: = 1 + random (20 # 41 ;;
S1: = Nil; A: = -100 + aleatoare (41 # 201 ;;
V_Nachalo (S1, A # 41 ;; V1: = S1;
Pentru I: = 2 până la N Do
Inceput A: = -100 + aleatoare (41 # 201 ;; V_Spisok (V1, A # 41 ;; V1: = V1 ^ .Etapele End;
WriteLn ( 'lista de declanșare' # 41 ;; Print (S1 # 41 ;;
s1 =;: V1 S2: = Nil; S3: = Nil;
În timp ce V1 <> nil Do
începe
Dacă V1 ^ .inf> 0
Apoi, dacă S2 = Nil
Apoi Începe V_Nachalo (S2, V1 ^ .inf # 41 ;; V2: = S2 End
Începe Else V_Spisok (V2, V1 ^ .inf # 41 ;; V2: = V2 ^ .Etapele End;
Dacă V1 ^ .inf <0
Apoi, dacă S3 = Nil
Apoi a începe V_Nachalo (s3, V1 ^ .inf # 41 ;; V3: = S3 End
Începe Else V_Spisok (V3, V1 ^ .inf # 41 ;; V3: = V3 ^ .Etapele End;
V1: = V1 ^ .Etapele
End;
WriteLn ( 'Lista rezultată de elemente pozitive:' # 41 ;; Print (S2 # 41 ;;
WriteLn ( 'Lista rezultată a elementelor negative:' # 41 ;; Print (S3 # 41 ;;
Ochistka (S1 # 41 ;; Ochistka (S2 # 41 ;; Ochistka (S3 # 41 ;;
Sfârșit.