Structuri liniare

Structuri liniare

Definitia 3.4

Se numeste lista o secventa finita L = (l₁, l₂, , l_n) de elemente numite componente, secventa care satisface proprietatile:

componentele pot fi date elementare sau structuri de date;

componentele pot fi de tipuri diferite.

Listele au fost introduse din necesitatea realizarii unor structuri de date dinamice, adica structura lor se poate modifica in cursul procesului de calcul.

Definitia 3.5

Se numeste lista liniara o lista L = (l₁, l₂, , l_n) care satisface proprietatile:

exista    o relatie de ordine intre elementele listei L, astfel incat orice element l_i are predecesor pe l_i-1, i = 2, , n si succesor pe l_i , i = 1, , n-1;

elementul l₁ nu are predecesor si este numit element initial al listei;

elementul l_n nu are succesor si este numit element terminal al listei.

Pentru a indica predecesorul sau succesorul unui element al listei liniare se foloseste un indicator numit pointer (care reprezinta o adresa).

Definitia 3.6

Se numeste lista liniara simpla o lista liniara L = (l₁, l₂, , l_n) in care fiecare element l_i este dublet ordonat de forma (d_i, p_i) , unde d_i este o data elementara sau o structura de date, iar p_i este un pointer care indica succesorul elementului l_i din lista.

Observatia 3.1

In cazul elementului terminal l_n al listei L = (l₁, l₂, , l_n), pointerul p_n     are o valoare speciala.

Parcurgerea unei liste liniare simple L = (l₁, l₂, , l_n) se poate face intr-un singur sens de la elementul initial l₁ catre elementul terminal l_n. De aceea o astfel de lista se mai numeste lista liniara asimetrica.

Pentru reprezentarea grafica a unei liste liniare simple L = ((d₁, p₁), , (d_n, p_n)) se poate folosi un digraf (graf orientat) G = (N, A), N = , A = , p_i = (d_i, d_i

Exemplul 3.2

Lista L = ((d₁, p₁), (d₂, p₂), (d₃, p₃), (d₄, p₄), (d₅, p₅)) este reprezentata grafic prin digraful din figura 3.1

Figura 3.1

Definitia 3.7

Se numeste lista liniara dublu inlantuita o lista L = (l₁, l₂, , l_n) in care fiecare element l_i este un triplet ordonat de forma (d_i, p_i , p_i) unde d_i este o data elementara sau o structura de date, p_i este un pointer spre predecesor si p_i este un pointer spre succesor.

Observatia 3.2

In cazul elementului initial l₁ si al elementului terminal l_n ale listei liniare dublu inlantuite L = (l₁, l₂, , l_n) pointerul p₁ si respectiv pointerul p_n au valori speciale;

Parcurgerea unei liste liniare dublu inlantuita se poate face in ambele sensuri. De aceea o astfel de lista se mai numeste lista liniara simetrica.

Pentru reprezentarea grafica a unei liste liniare dublu inlantuita L = ((d₁, p₁ , p₁), , (d_n, p_n , p_n)) se poate folosi un digraf (graf orientat) G = (N, A), N = , A = , p_i = (d_i, d_i-1), p_i = (d_i, d_i

Exemplul 3.3

Lista L = ((d₁, p₁ , p₁), , (d₅, p₅ , p₅)) este reprezentata grafic prin digraful din figura 3.2.

Figura 3.2

Definitia 3.8

Se numeste lista liniara circulara o lista liniara L = (l₁, l₂, , l_n) in care elementul initial l₁ este succesorul elementului terminal l_n.

Observatia 3.3

O lista liniara circulara poate fi simpla sau dublu inlantuita dupa cum elementele listei sunt dublete sau triplete, adica contin un pointer sau doi pointeri.

Memorarea listelor liniare se poate face in mai multe moduri, in continuare prezentandu-se doua dintre ele:

alocarea secventiala;

alocarea inlantuita.

Alocarea secventiala consta in a memora elementele listei in locatii succesive de memorie, conform ordinii acestor elemente in lista; in acelasi timp se memoreaza adresa de baza (adresa primului element al listei). Pointerii nu se reprezinta, iar ordinea logica a elementelor in lista este identica cu ordinea fizica pe suport. In acest caz, in general, elementele listei sunt memorate intr-un vector, adresa de baza fiind adresa primului element al vectorului.

Alocarea inlantuita consta in a memora fiecare element al listei intr-o locatie de memorie. Fiecare locatie are doua sau trei campuri, un camp pentru data si unul sau doua campuri pentru pointeri dupa cum lista este simplu sau dublu inlantuita. Trebuie memorata si adresa de baza. Deci, in acest caz pointerii se reprezinta efectiv, ei fiind adresele locatiilor unde se afla predecesorii sau succesorii elementelor. Astfel se asigura o independenta a ordinii logice a elementelor in lista in raport cu ordinea fizica pe suport si, de aceea elementele listei se pot memora in diverse zone de memorie.

Alocarea inlantuita cere mai multa memorie decat alocarea secventiala, dar are avantajul ca elimina necesitatea deplasarii de elemente pentru operatiile de introducere si de extragere din lista.

Asupra unei liste de date se pot efectua o multime de operatii care se refera la datele elementelor sau la structura. Aceste operatii sunt:

- creare(L) care consta in memorarea listei L in forma initiala;

- card(L) care consta in determinarea numarului elementelor listei L;

- sortare(L) care consta in ordonarea elementelor listei L dupa un criteriu;

- suprimare(L) care consta in stergerea listei L de pe suport;

- introducere(L, l) care consta in adaugarea la lista L a elementului l;

- consultare(L, l) care consta in accesul in lista L la elementul l;

- extragere(L, l) care consta in stergerea din lista L a elementului l;

- actualizare(L, l) care consta in actualizarea in lista L a valorii elementului l;

- inserare(L, l) care consta in adaugarea la lista L a elementului l intr-un anumit loc din lista;

- descompunere(L; L₁, , L_m) care consta in descompunerea listei L in listele L₁, , L_m;

- concatenare(L₁, , L_m; L) care consta in obtinerea listei L din concatenarea listelor L₁, , L_m;

- salvare(L₁, L₂) care consta in copierea listei L₁ in lista L₂, in general, pe un alt suport.

In cazul in care se impun anumite restrictii asupra operatiilor de introducere si extragere a elementelor unei liste liniare, se obtin cateva tipuri particulare de liste folosite frecvent in practica.

Definitia 3.9

Se numeste stiva o lista liniara cu proprietatea ca operatiile de introducere si stergere din lista se fac la un singur capat al listei numit varful stivei.

Observatia 3.4

O stiva mai poarta numele de stack, pila, lista LIFO (Last-In, First-Out) sau lista push-down.

Definitie 3.10

Se numeste coada o lista liniara cu proprietatea ca operatia de introducere se efectueaza la un capat al listei numit baza cozii si operatia de extragere se efectueaza la celalalt capat al listei numit varful cozii.

Observatia 3.5

O coada mai poarta si numele de queue, sir de asteptare sau lista FIFO (First-In, First-Out).

In reprezentarea secventiala, elementele stivei vor fi memorate intr-un vector s cu n componente, n fiind capacitatea maxima a stivei. O stiva fara nici un element se numeste stiva vida. O stiva cu n elemente se numeste stiva plina.

Fie k numarul efectiv de elemente din stiva; ca urmare elementul s_k apare in varful stivei. Operatia de introducere in stiva se realizeaza asa cum se arata in procedura SIN:

PROCEDURE SIN(s, n, k, x);

ARRAY s(n);

IF k ≥ n THEN

WRITE 'STIVA PLINA';

STOP;

ENDIF

k := k + 1;

s(k) := x;

RETURN

END.

Operatia de extragere din stiva se realizeaza asa cum se arata in procedura SOUT:

PROCEDURE SOUT(s,n,k,x);

ARRAY s(n);

IF k ≤ 0 THEN

WRITE 'STIVA VIDA';

STOP;

ENDIF

x := s(k);

k := k - 1;

RETURN

END.

In reprezentarea inlantuita, adresa de baza va fi adresa varfului stivei, legaturile mergand de la ultimul spre primul element al stivei.

In alocarea secventiala vom folosi pentru o coada un vector c cu n componente in care, daca elementele cozii sunt memorate in c_i+1, c_i+2, , c_k (unde c_i+1 este varful cozii, iar c_k este baza cozii), atunci p = i si u = k. Introducerea variabilelor p si u este necesara pentru a putea testa daca o coada este vida, caz in care p = u. Scoaterea, respectiv introducerea unui element in coada conduce la marirea lui p, respectiv u cu o unitate. Dar operatiile de introducere si extragere din coada produc o deplasare spre dreapta a elementelor. Astfel se poate ajunge la situatia p = u = n, cand coada esta vida, dar nu putem introduce nici un element in coada. Pentru a elimina acest neajuns se va considera ca lista coada este o lista circulara, adica dupa c_n urmeaza c₁. In acest caz relatia p = u este valabila atat pentru o coada vida cat si pentru una plina. Pentru a deosebi cele coua cazuri se poate folosi una din metodele:

introducerea unei variabile b care sa ia valoarea 0 in cazul unei cozi vide si 1 in rest;

utilizarea a n-1 componente ale vectorului c; in aceasta situatie coada vida este identificata prin p = u, iar coada plina prin u + 1 = p (mod n).

Convenim ca la initializarea cozii punem p := n, u := n.

Operatia de introducere in coada se realizeaza asa cum se arata in procedura CIN:

PROCEDURE CIN(c, n, p, u, x);

ARRAY c(n);

u := u + 1;

IF u > n THEN

u := 1;

ENDIF

IF p = u THEN

WRITE 'COADA PLINA';

STOP;

ENDIF

c(u) := x;

RETURN

END.

Operatia de extragere din coada se realizeaza asa cum se arata in procedura COUT:

PROCEDURE COUT(c, n, p, u, x);

ARRAY c(n);

IF p = u THEN

WRITE 'COADA VIDA';

STOP;

ENDIF;

IF p = n THEN

p := 0;

ENDIF

p := p + 1;

x := c(p);

RETURN

END.

Reprezentarea inlantuita a cozilor se realizeaza analog ca pentru stive, cu deosebirea ca se memoreaza doua adrese p si u pentru varful, respectiv baza cozii.