Punerea în aplicare a unei liste legate de matrice pe baza
Churikov Konstantin, Universitatea Tehnică de Stat Donbass
Determinarea listelor liniare
Listă numit un set ordonat constând dintr-un număr variabil de elemente, care sunt aplicabile într-o operațiune de închidere, excepție. Lista care arată relația dintre elementele cartierului se numește liniar.
Următoarele operații pot fi efectuate cu punerea în aplicare a listelor liniare în limbaje de programare imperative:
să aibă acces la o listă de elemente de verificare și / sau modificarea conținutului câmpurilor sale;
se introduce un nou element imediat înainte sau după un element arbitrar;
ștergerea unui element arbitrar;
asociație într-o listă a două (sau mai multe) liste liniare;
divizare o listă liniară a două (sau mai multe) a listei;
face o copie a unei liste liniare;
determinarea numărului de elemente din listă;
sortarea elementelor din listă;
căuta articole cu o valoare predeterminată.
Într-un program este rareori necesar să se utilizeze toate cele nouă tipuri de operațiuni. În același timp, este destul de dificil de a crea o punere în aplicare uniformă a listelor liniare, în care ar fi efectuate în mod eficient toate aceste operațiuni. Prin urmare, liste liniare pot fi puse în aplicare în mod diferit în funcție de clasa de tranzacții, care sunt cele mai multe ori le-au făcut în program, sau cel mai critic la timpul de execuție.
Reprezentarea internă a listelor liniare
Metodele de bază de stocare a listelor liniare în memoria calculatorului pot fi împărțite în metode secvențiale și depozitare asociate. Lista secvențială a elementelor de stocare aranjate în celule consecutive în memorie, cu un element urmează imediat cealaltă. stocare asociată este o schemă mai flexibilă, în cazul în care fiecare element al listei conține un link către elementul următor, iar pozițiile lor relative în memoria poate fi arbitrară. Fiecare metodă are avantajele și dezavantajele sale. La alegerea unei metode de stocare într-un anumit program ar trebui să ia în considerare orice operațiuni și intensitatea cu care s-ar lua pe o listă liniară, costul de punere în aplicare și cantitatea de memorie necesară pentru a stoca lista.
Această implementare nu apare foarte rar. Pur și simplu, este de multe ori ascunse în spatele diferitelor nume - tablouri index, tablouri de conformitate, etc. În ciuda diferenței de nume, folosind același algoritm. - Ed.
Punerea în aplicare a unei liste legate de matrice pe baza
Luați în considerare această metodă, în exemplul de realizare a unei liste liniare legate. Elementele acestei liste sunt ordonate liniar. În plus față de elementele din lista are un navigator care poate fi în următoarele poziții:
la partea superioară (adică, înainte de primul element al listei);
la sfârșitul listei (de exemplu, ultimul element al listei);
între elementele listei.
Navigator poate fi mutat numai de la începutul până la sfârșitul listei de un element la un moment dat. În plus, se adaugă elemente de listă nu poate fi decât într-o poziție, care se referă la navigatorul. O modificare / ștergere / citire numai elementele care sunt într-o poziție anterioară celei menționate de către navigator, și anume în amonte de mișcarea acesteia.
Ideea principală a acestei implementări este de a separa informații cu privire la conținutul de elemente într-o listă de informații cu privire la ordinea lor. Grafic, această idee este prezentată în figura 1.
Referințe suplimentare vor fi reprezentate prin săgeți, așa cum se arată în figura 2.
În mod firesc, de a lucra cu o listă de numai legăturile dintre elementele care nu este de ajuns - trebuie să știți, de exemplu, în cazul în care primul element din listă, și oferind ultimul element de celelalte (de fapt, nici un element de aceasta nu). În acest scop, am putea introduce două variabile, care ar conține indicii începutul și sfârșitul listei. Noi, cu toate acestea, nu va face acest lucru, și de a folosi recepția de „rulare în ring“ - „întoarce“ lista prin introducerea unui element special imaginar NULL, care va fi întotdeauna plasat în elementul cu indexul NullElem (având o valoare de la 0) de matrice utilizat pentru a stoca trimiterea la elemente de listă (numite Refs). Figura 3 prezintă o reprezentare grafică a modelului.
listă goală corespunde unei situații în care în ring orice elemente, altele decât NullElem, nu, adică, indicele de referință matrice de celule NullElem se referă la sine.
Navigator este situat între elementele, astfel încât vinde sub forma a două variabile înainte și după, după care conține indexul pentru trecut și înainte de - elementul index nu a fost încă trecut. Regulamentul Navigator din partea de sus, corespunde, astfel, într-un caz când egal după NullElem, iar poziția finală - atunci când valoarea conținută în înainte de.
Acum, o listă legată este simulat complet. Rămâne neclar, numai următoarele întrebări:
Cum se determină prezența sau absența spațiului în elementele de matrice (numite Elems)?
Cum de a găsi elementul liber în elementele de matrice în simulare adăuga un element la lista?
Nu este de a ghici ce elemente Elems sunt gratuite și care sunt ocupate, să ia o decizie, să păstreze în plus față de lista de elemente utilizate ca lista liberă. Elementele listei vor fi conectate într-un inel, pornind de la elementul de serviciu stocat în elementul cu NullFreeSpace index (egal cu unu) o serie de legături (refs). O reprezentare grafică a modelului rezultat este prezentat în figura 4.
Astfel, pentru a determina dacă există o listă de spațiu liber, este necesar să se examineze valoarea elementului Refs (NullFreeSpace). Dacă această valoare este NullFreeSpace (și anume îndreptat către el însuși), spațiul liber acolo. În caz contrar, această valoare de puncte la primul element liber al elementelor de matrice. Atunci când adăugați un element la lista pe care doriți să excludeți indicele acestui element din lista liberă și include în lista principală. Atunci când ștergeți un element, trebuie să efectuați operațiunea inversă.
Figura 4 negru marcat implicit o listă legată, și roșu - lista articolelor disponibile.
Într-o implementare de software, indicele de referință de atribuire lista valorilor virtualIndex realIndex disponibile într-o rutină separată. În plus, rutine individuale aloca toate acțiunile asociate cu funcționarea spațiului liber.
Cu toate punerea în aplicare remarcile menționate mai sus conectate pur și simplu listă liniară pentru Visual Basic 6.0 poate avea forma prezentată mai jos.