Standard C ++ biblioteca include o mulțime de structuri de date de bază. Printre care veți găsi liste, stive, cozi, seturi și altele. Dar, pentru a le utiliza în mod eficient, aveți o bună înțelegere a particularităților muncii lor. Problema va fi de aproximativ una dintre structurile de bază: lista legată.
Listele singulara legate în teorie
Pentru a înțelege cum de a construi o listă legată, imaginați-vă un lanț. În lanțul are un început și un sfârșit, precum și link-uri, care sunt conectate succesiv unul cu celălalt. Puteți merge cu ușurință de la începutul până la sfârșitul unui lanț, care trece succesiv de la un link către altul:
Este pur și simplu conectat și liste de lucru. partea de sus a listei se numește elementul părinte, și link-uri - noduri. Lista este determinată de un nod special (NULL). Astfel, fiecare nod „închide“, ceea ce înseamnă că structura să fie folositoare:
O listă avantaj legat este faptul că introducerea și eliminarea nodurilor efectuate relativ cu ușurință oriunde în listă. Cu toate acestea, structura listei restricționează accesul la site-urile sale asupra indicelui. Lista nu poate fi indexat ca o matrice. Pentru a ajunge la o listă de nod conectat, trebuie să mergeți în mod constant tot drumul de la elementul cap la locul dorit.
interfață de clasa listă legată
Izolat lista inlantuita este utilizat pentru a stoca un set ordonat de elemente identice. Pentru a nu fi stabilită pentru fiecare tip de date listă, definiți șablonul de clasă:
Clasa noastră va menține nodul listă legat adăugând la început, ștergerea ultimul nod și valorile elementelor capului de recepție. În plus, vom pune în aplicare lista de by-pass cu iteratori, precum și adăugați o funcție de membru pentru a calcula lungimea listei.
Nod nod este determinat prin structura. care conține două domenii: m_t - valoare legat de un nod, și m_next - pointer la nodul următor.
Inițial, lista este goală, astfel încât punctele elementului părinte la NULL:
Adăugarea unui element la lista legată
Adăugarea unui nod la lista legată implementată la început. nod Adăugat în sine va deveni noul element principal al listei:
Eliminarea unui element dintr-o listă legată
Când eliminați un nod din lista legată este trunchiat elementul părinte. Dacă lista nodurile încă, noul element este nodul părinte, ca urmare a elementului mamă, sau este NULL:
Lista este o structură dinamică. La adăugarea unui nou nod este alocat de memorie din grămada care trebuie să fie liber să nu creeze pierderi de memorie. Având o funcție de eliminarea elementelor pentru al realiza nu este lista dificilă legată de destructor:
Lista legată Iterator
Funcționalitate pentru a adăuga / șterge noduri în listă este mai bine să nu se amestece cu sarcina de eludare. În acest scop, sunt iteratori. Iteratorul a crea o listă legată în C ++ stil. Să revenim la definiția sa, care a ratat anterior:
Ca un iterator la începutul și sfârșitul listei următoarele afirmații este adevărată:
Acum lista poate obține cu ușurință în jurul valorii de la început până la sfârșit. Dar nu uitați despre funcția pentru a calcula lungimea. Noi folosim mecanismul de iteratori pentru a simplifica sarcina:
concluzie
Rețineți că exemplul de mai sus este doar o scurtă demonstrație a principiilor unei liste legate în C ++. În programe reale, aproape întotdeauna mai bine să utilizeze implementarea biblioteca standard a listei, precum și orice altă structură de date. Atunci nu va fi nevoie doar pentru a face mai puțin de lucru, dar va primi, la dispoziția unei versiuni bine pus la punct și optimizat, care va fi capabil de a utiliza în condiții de siguranță.