Liste
Def 17: Lista sau lista liniara este un sir , eventual vid de elemente apartinind unei multimi date.
Cele doua capete ale unei liste se numesc baza , respectiv virf.
Prima referire la o lista trebuie sa fie initializ 252i83c area ei ca lista vida. Asupra listelor se efectueaza urmatoarele operatii:
Ø accesul la un anumit element identificat prin numarul de ordine in lista sau prin valoarea sa
Ø inserarea unui element intr-un anumit loc in lista
Ø stergerea (eliminarea) unui element dintr-o lista
Ø concatenarea listelor
Ø reordonarea elementelor unei liste conform unui anumit criteriu
Ø descompunerea unei liste in mai multe liste.
Memorarea listelor liniare se poate face in urmatoarele moduri:
Alocarea secventiala consta in memorarea elementelor listei in locatii succesive de memorie, conform ordinii acestor elemente in lista; in acelasi timp se memoreaza adresa de baza (adresa primului element).
Alocarea inlantuita presupune ca fiecare element al listei este inlocuit cu o celula formata din doua parti de informatie corespunzatoare elementului si o parte de legatura ce contine adresa celulei corespunzatoare urmatorului element. Ca si la alocarea secventiala, mai trebuie memorata o adresa de baza. Celulele vor fi reprezentate sub forma:
 |
Legaturile
vor fi precizate fie numeric, fie prin sageti. Exemplu :
Alocarea inlantuita necesita mai multa memorie decit cea secventiala si elimina necesitatea deplasarii de elmente pentru operatiile de introducere si de scoatere din lista.
O lista liniara poate fi transformata in lista circulara daca in partea de legatura a ultimului element al listei se pune adresa primului element al listei.
|
