Structura dinamică a listelor de date

În articolele anterioare am uitat la programarea asociată cu procesarea datelor numai statice. Variabilele statice sunt cele care sunt alocate la compilare și se menține pe tot parcursul programului.

În limbaje de programare (Pascal, C, și colab.), Există o altă metodă de alocare de memorie pentru date, care se numește dinamică. În acest caz, memoria pentru valoarea atribuită în timpul rulării. Aceste valori vor fi numite dinamice. Memoria CATEGORIE care urmează să fie alocate static, numită memorie statică; alocă în mod dinamic secțiune de memorie numită o memorie dinamică (memorie heap).

Utilizarea cantități dinamice oferă programatorului o serie de caracteristici suplimentare. În primul rând, conexiunea de memorie dinamică poate crește cantitatea de date care sunt prelucrate. În al doilea rând, în cazul în care nevoia de date eliminate înainte de sfârșitul programului, memoria ocupată de acestea pot fi eliberate pentru alte informații. În al treilea rând, utilizarea memoriei dinamice vă permite să creați structuri de date de dimensiuni variabile.

Lucrul cu valori dinamice asociate cu utilizarea unui alt tip de date - tipul de referință. Variabilele cu un tip de referință, numit indicii.

În continuare vom discuta în detaliu mai multe indicii și acțiuni cu ei în limbajul Pascal, exemple vor duce la Pascal și C.

Amploarea tipului de referință (pointer) este descris în secțiunea care descrie variabilele după cum urmează:

Iată câteva exemple de descrieri ale semnelor:

Aici P1 - un pointer la valoarea dinamică a tipului întreg; P2 - pointer la valoarea dinamică a tip string; Pm - un pointer la matrice dinamic de tipul specificat în secțiunea Tip.

cantitățile dinamice Sami nu are nevoie de o descriere a programului, deoarece în timpul memoriei de compilare pentru ei este alocat. La momentul compilării, memoria este alocată doar o valoare statică. Pointerii - o valoare statică, astfel încât ele necesită o descriere.

Cum, atunci, apare sub valoarea de alocare dinamică a memoriei? Memorie pentru valoarea dinamică asociată cu indicatorul este eliberat prin efectuarea procedurii standard de NOU. Formatul de a recurge la această procedură:

Se crede că după această afirmație creează o valoare dinamică a cărei nume este după cum urmează:

Lăsați programul, care are descrierea de mai sus, există următoarele afirmații:

După executarea lor este dedicat spațiu pentru trei valori (doi scalare și o matrice), care au identificatori într-o memorie dinamică:

De exemplu, P1 ^ simbol poate fi decodat astfel: o variabilă dinamică care se face referire prin indicatorul P1.

Mai multe de lucru cu variabilele dinamice este exact la fel ca și variabilele statice ale tipurilor corespunzătoare. Ele pot fi atribuite valori, acestea pot fi folosite ca operanzi în expresii, parametri, rutine și așa mai departe. De exemplu, în cazul în care P1 variabila ^ doriți să atribuiți numărul 25, P2 variabila ^ atribuie o valoare „scrie“ simbol, și o serie de Pm ^ umple numerele intregi de ordine de la 1 la 100, se face după cum urmează:

În plus față de noua procedură valoarea indicatorului poate fi determinată de către operatorul de atribuire:

Ca referință, puteți utiliza expresia

• pointer;
• o funcție de referință (adică o funcție a cărei valoare este un pointer);
• constant Nil.

Nil - este rezervat constantă, ceea ce indică o legătură goală, adică, link-ul, care nu nimic puncte. Când atribuiți tipurile de bază de expresii de referință pentru cursor și trebuie să fie aceleași. Constant Nil poate atribui un pointer la orice tip de bază.

Înainte de a atribui o valoare a variabilei de referință (folosind operatorul de atribuire sau o nouă procedură) este incertă.

De intrare și de ieșire indicii nu sunt permise.

Să considerăm un exemplu. Să programul descris în următoarele indicatoare:

Apoi, operatorii de atribuire sunt valabile ca principiu de tip respectate ca. Operatorul K: = D eronată deoarece tipuri de bază de la partea dreaptă și stângă sunt diferite.

Dacă valoarea dinamică pierde indicatorul său, atunci acesta devine un „gunoi.“ În programare, acest cuvânt se referă la informații care are memorie, dar nu mai este necesară.

Imaginați-vă că în program, în care există indicii în secțiunea de mai sus declarații scrise cu următorul text:

Astfel, o variabilă dinamică egală cu 5, a pierdut indicatorul său și a devenit inaccesibile. Cu toate acestea, spațiul de memorie pe care îl ocupă. Acesta este un exemplu al apariției „gunoi“. Această diagramă arată ce sa întâmplat ca urmare a operatorului P: = D.

În Pascal, există o procedură standard care vă permite să eliberați memorie pe datele, necesitatea care a dispărut. Formatul său este:

De exemplu, în cazul în care nu mai este nevoie de variabila dinamică P ^, operatorul

scoateți-l din memorie. După aceea, valoarea indicatorului P devine incertă. În special efectul devine economii semnificative de memorie atunci când eliminarea matrice mari.

In versiunile Turbo Pascal, care rulează sub sistemul de operare MS DOS, 64 kilobytes de memorie este alocată pentru un program (sau, să fie precise, 65,520 bytes). Aceasta este o zonă de memorie statică. Dacă este necesar, lucra cu matrice mari de informații care nu poate fi suficient. dimensiunea memoriei - mult mai mari (sute de kilobytes). Prin urmare, utilizarea memoriei dinamice poate crește în mod semnificativ cantitatea de informații care sunt prelucrate.

Trebuie înțeles în mod clar că lucrul cu date dinamice încetinește executarea programului, deoarece accesul la valoarea are loc în două etape: în primul rând, un pointer se solicită, apoi - valoarea. Așa cum se întâmplă adesea, acționează „legea conservării de probleme“: un câștig în memorie este compensat de o pierdere de timp.

Exemplu. 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.

Vom discuta problema modului haldei, puteți crea o structură de date de dimensiuni variabile.

Să considerăm următorul exemplu. În cursul experimentului fizic, citirile sunt luate de mai multe ori (de exemplu, un termometru) și înregistrate în memoria unui calculator pentru prelucrare ulterioară. Nu se știe cât de multe vor fi făcute măsurători.

În cazul în care prelucrarea acestor date nu utilizează memorie externă (fișiere), este rezonabil să le plaseze într-o grămadă. În primul rând, memoria dinamică vă permite să stocați o cantitate mai mare de informații decât statice. Și în al doilea rând, în memoria dinamică, aceste numere pot fi aranjate într-o listă legată, care nu necesită pre-specificat numarul de numere, cum ar fi matrice. Ce este o „listă legată“? Schematic, se pare ca acest lucru:

aici Inf # 151; informații link-ul listei (valoarea oricărui tip simplu sau structurat, cu excepția fișierului), Next # 151; un pointer la link-ul următor din listă; în primul rând # 151; un pointer la link-ul de lista din titlu.

Prin definiție, o listă se află în grămadă, un link pointer la titlul este stocat în memoria statică. Structura, în contrast cu matrice, este cu adevărat dinamică: unități create și șterse după cum este necesar în timpul execuției programului.

Acolo BT # 151; un anumit tip de bază de elemente din listă.

Dacă indicatorul se referă numai la următoarea legătură din listă (așa cum se arată în structura de mai sus declarată), atunci o astfel de listă numită unidirecțional. În cazul în care link-urile următoare și anterioară # 151; lista bidirecțională. În cazul în care indicatorul la ultimul link-ul nu este instalat în Nil, iar titlul se referă la lista de link-ul, această listă se numește un inel. Inelul poate fi liste unidirecționale și bidirecționale.

O privire mai atentă la lucrul cu liste legate de un exemplu de listă unidirecționale non-inelar.

Distingem operațiunile tipice pe liste:

• adăugând un link în partea de sus a listei;
• eliminarea din lista de link-ul început;
• adăugarea unui link către o listă de locație arbitrară, alta decât de la început (de exemplu, după indicatorul legătură care este specificat);
• scoaterea din lista link de o locație arbitrară alta decât la început (de exemplu, după indicatorul legătură care este setat);
• a verifica dacă lista este goală;
• Ștergerea listei;
• lista de imprimare.

Punerea în aplicare a unui set dedicat de operații într-un modul. Prin conectarea acestui modul, este posibil să se rezolve cele mai comune sarcini privind prelucrarea listă. Să lista este declarată așa cum este descris mai sus. Primele patru etape, în primul rând vinde separat, oferindu-le cu ilustrații.

1. Adăugarea unui link către partea de sus a listei