Curs TP

iÎn multe situaţii datele ce urmează a fi prelucrate pot fi organizate sub forma unor liste, de exemplu lista produselor dintr-o firmă, lista blocurilor dintr-un cartier, lista studenţilor de la un examen etc.

i Pentru a întelege conceptul de listă şi diversele tipuri particulare de liste se dă o definiţie mai exactă a noţiunii de listă. Se consideră o multime finită:

L L= {l1, l2,...ln);

aale carei elemente se numesc componente.

Se numeste listă liniară o mulţime finită L care satisface următoarele proprietăţi:

- -există o relaţie de ordine între elementele mulţimii L, astfel încât orice element li are ca predecesor pe li-1 si ca succesor pe li+1;

- -există un element în listă, ln care nu are predecesor şi este numit capul listei;

- -există un element în listă, l1 care nu are succesor şi care este numit element terminal (baza) listei.

Se consideră că elementele unei liste liniare sunt perechi ordonate de forma (d,p) unde d este o dată elementară sau structurată, iar p este un pointer ce indică succesorul elementului în listă. O astfel de listă este numită listă liniară simplă sau asimetrică deoarece parcurgerea ei nu se poate face decât într-un singur sens. Timpul de parcurgere este proporţional cu numarul elementelor listei.

Alocarea de memorie se face pentru un singur element din lista. Acest element poate fi conţinut într-o structura mai mare care conţine pe lânga elementul din listă şi un pointer care permite “legarea” la un alt element din lista. Ansamblul format din elementul propriu-zis şi pointer se numeste nod. Structura listei este obtinuta legând între ele nodurile din listă.

În concluzie, fieacare nod contine o câmp “data” şi un câmp pointer “urm”; data memorează informaţia dorită iar pointerul este utilizat pentru a lega doua noduri din listă.

Dacă elementele listei sunt formate din triplete de forma (d, pd, ps) unde d este o dată elementară sau structurată, pd este un pointer spre elementul predecesor, iar ps este un pointer spre elementul succesor, atunci lista este liniară dublu inlanţuită sau simetrică deoarece poate fi parcursă in ambele sensuri.

În plus dacă relaţia de ordine este astfel definită încat ultimul element al listei are ca succesor primul element al listei, lista astfel definita este o lista circulară. O astfel de listă circulară poate fi asimetrică sau simetrică.

a) lista liniară simplă

b) lista liniară dublu înlanţuită

c) lista liniară circulară

d) lista liniară dublu înlanţuită circulară

Operaţiile principale ce pot fi efectuate asupra unei liste sunt:

- crearea listei;

- adaugarea de noi elemente la sfârsitul listei;

- inserarea de noi elemente în orice loc din lista;

- ştergerea de elemente din orice poziţie a listei;

- modificarea unui element dintr-o poziţie dată.

În cazul lisei studenţilor dintr-o grupă, un element poate conţine informaţiile: numar curent, nume-prenume, grupa, notele obţinute, media lor.

Oricare din aceste informaţii poate reprezenta o cheie ce poate fi folosită pentru diverse operaţii. De exemplu, luând drept cheie media, se poate face un tabel cu studenţii grupei în ordinea descrescatoare a mediei, în vederea obţinerii unei burse, sau dacă luam drept cheie numele şi prenumele studenţilor pentru clasificarea lor în ordine alfabetică.

Operaţiile specificate mai sus modifică conţinutul listei. Alte operaţii nu modifică structura şi continutul listei, oferind informaţii despre aceasta, cum ar fi:

- determinarea lungimii listei (numărul de elemente);

- localizarea elementului din lista care îndeplineşte o anumită condiţie;

- afişarea conţinutului elementelor listei.

Asupra listelor se pot efectua şi operaţii complexe, cum ar fi:

- separarea unei liste în două sau mai multe subliste după anumite criterii;

- crearea unei liste din două sau mai multe liste prin concatenarea (alipire) sau interclasare conform unui criteriu;

- crearea unei liste ordonate după valorile unei chei

- selecţia elementelor dintr-o lista, care satisfac anumite criterii, într-o nouă listă.

Elementele listelor sunt în general înregistrări având structura specifică aplicaţiilor considerate.

Listele pot fi reprezentate prin structuri statice – tablouri sau prin structuri dinamice (liste inlantuite). Modul de reprezentare al listelor poate fi transparent pentru utilizator dacă sunt definite sub forma unor subprograme şi toate prelucrările se fac prin intermediul acestora.

În cazul reprezentării listelor prin tablouri elementele vecine din lista ocupa poziţii alaturate în memorie. În acest caz accesul la un element din listă, parcurgerea listei, sau adaugarea unui element la sfârşitul listei se fac uşor, pe când inserarea şi ştergerea de elemente din interiorul listei de fac prin deplasarea unor elemente.

În cazul alocării dinamice a memoriei, elementele listei sunt dispersate în întreaga memorie disponibilă. Legarea elementelor aceleaşi liste între ele se face prin pointeri, care se adaugă informaţiei utile din elemente.

Pentru ca operaţiile de inserare şi ştergere să se facă la fel pentru orice element din listă, se folosesc doua elemente false, denumite santinele plasate la începutul şi la sfârşitul listei (prim şi ultim). În acest mod fiecare element din şir are atât un predecesor cât şi un succesor.