Într-o listă legată, fiecare element de informație conține un link la următorul articol din listă. Fiecare element de date este de obicei o structură care constă din informații și comunicare câmp pointer. Lista Conceptual legate arata ca acest lucru, așa cum se arată în Fig. 22.2.
Fig. 22.2 lista individual legată
Există două modalități principale de construire a unei liste legate. Primul mod - a pus noile elemente în partea de jos a listei [1]. Al doilea - pentru a insera elemente într-o anumită poziție din listă, de exemplu, în ordine crescătoare. Metoda de construire membru adăugarea dependentă de funcția de listă algoritm. Să începem cu un mod simplu de a crea o listă de elemente prin plasarea în cele din urmă.
Funcția slstore () de mai jos creează o listă legată prin plasarea fiecărei următorului element al listei. Ca parametri sunt trecut un pointer la o structură de tip adresă. conține o intrare nouă, și un pointer la ultimul element din listă. Dacă lista este goală, un pointer la ultimul element trebuie să fie zero.
Deși creat de către o listă de funcții slstore () pot fi sortate într-o operație separată, după crearea sa, este mai ușor doar pentru a crea o lista ordonata, inserarea fiecare element nou în poziția dorită în secvența. În plus, în cazul în care lista este deja sortate, are sens să sprijine rânduială sa, introducerea de noi elemente în pozițiile corespunzătoare. Pentru a insera un element în acest fel necesită o viziune consistentă o listă atâta timp cât nu există nici un loc găsit un element nou, apoi se introduce un nou record în poziția găsit și reinstalați-uri.
Când inserați un element dintr-o listă legată poate fi una dintre cele trei situații: elementul devine este introdus primul element între celelalte două, devine ultimul element. Fig. 22.3 arată schimbarea circuitului în fiecare caz, referința.
Fig. 22.3. Se introduce un nou element lista inlantuita (în care info - date de câmp)
Următoarea funcție, sls_store (). introduce adresa de tip structură pentru o listă de corespondență, prin care se dispune l ascendent în valoarea câmpului de nume. Funcția ia un pointer la un pointer la primul și ultimele elemente ale listei, precum și un pointer la elementul de inserție. Deoarece primul și ultimele elemente ale listei se pot schimba, funcția sls_store (), dacă este necesar, actualizează automat indicatoarele la începutul și sfârșitul listei. Primul apel la această funcție, primul și ultimul indicii trebuie să fie egal cu zero.
Du-te prin elementele listei legate este foarte simplu: pentru a începe de la început și urmați semnele. De obicei, fragment de cod busting este atât de mic încât este introdus într-o altă procedură - de exemplu, o funcție de căutare, șterge sau afișa conținutul. Astfel, funcția de mai jos afiseaza toate numele din lista de adrese:
Când se apelează funcțiile de afișare () parametrul de pornire trebuie să fie un pointer la prima structură din listă. După aceea, funcția trece la elementul următor, ceea ce indică un câmp indicator următor. Procesul se oprește atunci când următorul zero.
Pentru a obține un element din listă trebuie să treacă prin link-urile de lanț. Mai jos este un exemplu de o funcție de căutare cu privire la conținutul de numele câmpului.
Deoarece funcția de căutare () returnează un pointer la intrarea din listă care conține numele dorit, tipul de retur este descris ca un pointer la structura de adrese. In absenta unui nul (NULL) returnează lista de celule adecvate.
Eliminarea unui element dintr-o listă legată este simplă. La fel ca și în insert, există trei cazuri posibile: eliminarea primului element, elementul deleție în mijlocul, eliminarea ultimului element. Fig. 22.4 arată toate cele trei operații.
Fig. 22.4. Eliminarea unui element dintr-o listă legată
Mai jos este o funcție care elimină elementul specificat din lista structurilor de adrese.
sldelete () funcție trebuie să treacă indicatoare către un element detașabil care precede șterse și, de asemenea, primele și ultimele elemente. La ștergerea unui pointer la primul element care precede elementul să fie egală cu zero (NULL). Această caracteristică se actualizează automat indexurile începe și ultima. în cazul în care una dintre ele se referă la intrarea care urmează să fie eliminate.
Într-o listă legată, există un mare dezavantaj: este imposibil de a citi lista legată în direcția inversă. Din acest motiv, utilizate în mod obișnuit liste dublu-legate.
[1] Nu uitați că lista legate, cum ar fi coarda, cele două capete: începutul și sfârșitul.