RECAPITULAREA PRINCIPALELOR STRUCTURI DE DATE
LISTE
Liste Inlantuite
Introducere
O lista este o colectie de elemente intre care este specificata o anumita ordine. Pentru o lista inlantuita ordinea elementelor este specificata explicit printr-un cimp de informatie care face parte din fiecare element, specificind elementul urmator.
Deci fiecare element de lista inlantuita are urmatoarea structura:
Informatie utila Informatie de inlantuire
+----- ----- --------- ----- -------+
| | |
+----- ----- --------- ----- -------+
data link
Pe baza informatiei de inlantuire (pastrata in cimpul link) trebuie sa poata fi identificat urmatorul element din lista.
Lista inlantuita statica
Consideram urmatoarele declaratii:
struct Element ;
Element V[8];
Pentru elementele vectorului V exista o ordine naturala data de aranjarea in memorie a elemetelor sale: V[0], V[1], ... V[7]. Vom reperezenta memoria ocupata de vectorul V astfel incit fiecare element sa fie reprezentat vertical, in felul urmator:
0 1 2 3 4 5 6 7
+----- ----- -------------+
data | | | | | | | | |
| | | | | | | | |
+--+--+--+--+--+--+--+--|
link | | | | | | | | |
+----- ----- -------------+
Completind cimpul link pentru fiecare element al vectorului putem obtine o lista inlantuita. Valoarea cimpului link va fi index in vector al urmatorului element din lista.
Vectorul V:
V[0] V[1] V[2] V[3] V[4] V[5] V[6] V[7]
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
|+---+|+---+|+---+|+---+|+---+| |+---+|+---+|
|| 1 ||| 2 ||| 4 ||| 6 ||| 5 || -1 || 7 ||| 0 ||
|+---+|+---+|+---+|+---+|+---+| |+---+|+---+|
| +-»-+ +-»-+ | | | +-»-+ | +-»-+ |
| | +-»-+----»------+ |
| +----»----+ |
+----- ----- -----------«----- ----- -----------+
Pe baza inlantuirii stabilita de valorile din figura de mai sus se obtine ordinea: V[3], V[6], V[7], V[0], V[1], V[2], V[4], V[5].
Este necesar sa cunoastem care este primul element din inlantuire, pentru aceasta retinem intr-o variabila:
int cap;
indexul primului element
cap=3.
Parcurgerea in ordine a elemntelor listei se face in felul urmator:
int crt;
.................
crt = cap;
while (crt!=-1)
Indiferent de modul cum se materializeaza informatiile de legatura pentru a reprezenta o lista inlantuita vom folosi urmatoarea reprezentare:
data link data link
+----- ----- ------+ +----- ----- ------+
| | | | | | |
+-------------+--+ +--->+----- ----- ------+
+-------+
Sageata care porneste din cimpul link arata faptul valoarea memorata aici indica elementul la care duce sageata.
Structuri autoreferite in C si C++
Pentru rolul pe care il joaca informatiile de legatura in structurile inlantuite, cel mai potrivit este tipul pointer. Tipul cimpului link va fi "pointer la element de lista". Iata cum arata declaratiile tipului "element de lista" in C++:
struct Element ;
In C va trebui sa scriem:
typedef struct _Element Element;
Avind declaratiile de mai sus (una din forme), si
Element* p; // un pointer la Element
in urma unei operatii:
p = (Element*) malloc( sizeof(Element) ); // in C
sau, simplu
p = new Element; // in C++
p a fost initializat cu adresa unei variabile de tip Element alocata in zona de alocare dinamica:
*p
+----- ----- ---------+
data link
p +----- ----- ---------+
+----+ | | |
| |-+----->+----- ----- ---------+
+----+ p->data p->link
Atunci, aceasta din urma va fi identificata prin expresia *p iar cimpurile sale prin expresiile p->data si respectiv p->link .
Pentru a manevra o lista avem nevoie doar de un pointer la primul element al listei. Pentru a indica o lista vida acest pointer va primi valoarea 0.
Operatii in liste inlantuite
Consideram declaratiile de tipuri de mai sus si variabilele:
Element* cap; // pointer la primul element al unei liste
Element* p;
Element* q;
Operatiile primitive pentru acces la o lista inlantuita sint:
1 Inserarea unui element in lista
Consideram: cap - contine adresa primului element din lista;
p - contine adresa unui element izolat care dorim sa fie inserat in lista.
[A] Inserarea in fata
Situatia initiala:
cap
+---+ +----------+ +----------+ +----------+
| |-+------->| | |-+-->| | |-+-->| | 0 |
+---+ +----------+ +----------+ +----------+
p +----------+
+---+ | | |
| |-+--->+----------+
+---+
Situatia finala:
cap
+---+ +----------+ +----------+ +----------+
| | | +->| | |-+-->| | |-+-->| | 0 |
+-+-+ | +----------+ +----------+ +----------+
| +-------+
|2 |1
p +---+ +--------+-+
+---+ +->| | | |
| |-+--->+----------+
+---+
Fiecare sageata nou creeata insemna o atribuire: se atribuie varibilei in care sageata nou creata isi are originea, valoarea luata dintr-o variabila in care se afla originea unei sageti cu aceeasi destinatie.
In cazul nostru avem atribuirile (fiecare atribuire corespunde sagetii cu acelasi numar din figura):
(1) p->link = cap;
(2) cap = p;
Sa detaliem: Prima atribuire
p->link = cap;
leaga elementul de inserat de restul listei. In urma acestei atribuiri, cap si p->link vor indica ambii inceputul listei initiale (vezi figura de mai jos).
cap
+---+ +----------+ +----------+ +----------+
||||+------->| | |-+-->| | |-+-->| | 0 |
+---+ +->+----------+ +----------+ +----------+
1|
+-------+
p +--------|-+
+---+ | |||||
| |-+--->+----------+
+---+ p->link
A doua atribuire:
cap = p;
pune in pointerul cap adresa elementului inserat in fata listei.
cap
+---+ +----------+ +----------+ +----------+
||||| | | |-+-->| | |-+-->| | 0 |
+-|-+ +->+----------+ +----------+ +----------+
+---+ +-------+
p 2| +--------|-+
+---+ +->| | | |
||||+--->+----------+
+---+
Observatie:
Daca pointerul cap este initial nul, (ceea ce inseamna inserarea intr-o lista vida) atribuirile de mai sus functioneaza corect rezultind o lista cu un singur element.
p->link = cap; // de fapt p->link = 0;
cap = p;
+---+ +---+
| 0 | cap| |-+-+
+---+ +----------+ +---+ | +----------+
+---+ | | | +---+ +->| | 0 |
| |-+--->+----------+ p | |-+--->+----------+
+---+ +---+ p->link
[B] Inserarea la mijloc sau la sfirsit
Varibila q va indica elementul dupa care se face inserarea.
Situatia initiala:
cap +----------+ +----------+ +----------+
+---+ | | |-+----->| | |-+------>| | 0 |
| |-+--->+----------+ +->+----------+ +----------+
+---+ +---+ |
q| |-+-+ +----------+
+---+ +---+ | | |
p| |-+--->+----------+
+---+
Situatia finala: q->link
cap +----------+ +----------+ +----------+
+---+ | | |-+----->| | | | +->| | 0 |
| |-+--->+----------+ +->+--------+-+ | +----------+
+---+ +---+ | +--+ +-----+
q| |-+-+ | +----------+ |
+---+ +---+ +->| | |-+-+
p| |-+--->+----------+
+---+ p->link
(1) p->link = q->link;
(2) q->link = p;
Observatii:
Atunci cind q indica ultimul element dintr-o lista, atribuirile de mai sus functioneaza corect si adauga elementul indicat de p la sfirsitul listei.
Nu se poate face inserarea in fata unui element dat (prin q) fara a parcurge lista de la capat.
2 Stergerea unui element din lista
Consideram: cap - contine adresa primului element din lista.
[A] Stergerea din fata
Prin operatia de stergere se intelege scoaterea unui element din inlantuire. Elementul care a fost izolat de lista trebuie sa fie procesat in continuare, cel putin pentru a fi eliberata zona de memorie pe care o ocupa, de aceea adresa lui trebuie salvata (sa zicem in variabila pointer p).
Situatia initiala:
cap +----------+ +----------+ +----------+
+---+ | | |-+-->| | |-+-->| | 0 |
| |-+--->+----------+ +----------+ +----------+
+---+
Situatia finala:
p
+---+
| |-+-+1
+---+ |
cap | +----------+ +----------+ +----------+
+---+ +->| | |-+-->| | |-+-->| | 0 |
| | | +----------++->+----------+ +----------+
+-+-+ |
+----- ----- --------+2
(1) p = cap;
(2) cap = cap->link;
delete p ; // Elibereaza zona de memorie
[B] Stergerea din mijloc sau de la sfirsit
Varibila q va indica elementul din fata celui care va fi sters.
Situatia initiala:
------+ +----------+ +----------+ +---|
| |-+----->| | |-+------>| | |-+------>|
------+ +>+----------+ +----------+ +---|
+---+ |
q| |-+-+
+---+
p
Situatia finala: +---+
| | |
+-+-+
------+ +----------+ | +----------+ +---|
| |-+----->| | | | +->| | |-+------>|
------+ +>+--------+-+ +----------+ +->+---|
+---+ | +----- ----- ---------------+
q| |-+-+
+---+
(1) p = q->link;
(2) q->link = p->link; // sau q->link = q->link->link;
delete p;
Observatii:
Atunci cind q indica penultimul element dintr-o lista, atribuirile de mai sus functioneaza corect si sterg ultimul element din lista.
Nu se poate face stergerea elementului indicat de q fara parcurgerea listei de la capat.
3 Parcurgerea listei
Consideram: cap - contine adresa primului element din lista.
O parcurgere inseamna prelucrarea pe rind a tuturor elementelor listei, in ordinea in care acestea apar in lista. Vom avea o variabila pointer p care va indica pe rind fiecare element al listei:
p = cap; |
while (p!=0)
} |
Un caz special apare atunci cind dorim sa facem o parcurgere care sa se opreasca in fata unui element care sa indeplineasca o conditie (ca in cazul cind inseram un element intr-o pozitie data printr-o conditie, sau stergem un elemen care indeplineste o conditie).
Presupunem ca lista are cel putin un element.
p = cap;
while (p->link!=0 && !conditie(p->link))
p = p->link;
Bucla while se poate opri pe conditia "p->link==0", ceea ce insemna ca nici un element din lista nu indeplineste conditia iar poinertul p indica ultimul element din lista, sau pe conditia "conditie(p->link)" , ceea ce insemna ca pointerul p va contine adresa elementului din fata primului element care indeplineste conditia.
Cozi
Introducere
O coada este o lista in care operatiile de acces sint restrictionate la inserarea la un capat si stergerea de la celalat capat.
Coada
PUT -------- ----- ------ ----- ----- ---- GET
----- ----- ----> ¦ ¦ ¦ ¦ ¦ ¦ ----- ----- ------->
-------- ----- ------ ----- ----- ----
Ultimul Primul
Pricipalele operatii de acces sint:
PUT(Coada, Atom) --> Coada
Adauga un element la coada.
GET(Coada) --> Coada, Atom
Scoate un Atom din coada. Returneaza atomul scos.
Implementari ale conceptului de coada
[A] Coada liniara
Coada poate fi organizata pe un spatiu de memorare de tip tablou (vector).
¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦ ¦
+------+ +------+
¦ head ¦ ¦ tail ¦
+------+ +------+
Sint necesari doi indicatori:
head - indica: primul element care urmeaza sa fie scos.
tail - indica: locul unde va fi pus urmatorul element adaugat la coada.
Conditia "coada vida" este echivalenta cu: head = tail
Initial indicatorii vor fi initializati astfel incit sa indice ambii primul element din vector.
Operatia PUT inseamna:
- V[tail] primeste Atomul adaugat
- incrementeaza tail
Operatia GET inseamna:
- intoarce V[head]
- incrementeaza head
Se observa ca adaugari si stergeri repetate in coada deplaseaza continutul cozii la dreapta, fata de inceputul vectorului. Pentru a evita acest lucru ar trebui ca operatia GET sa deplaseze la stinga continutul cozii cu o pozitie. Primul element
care urmeaza sa fie scos va fi intotdeauna in prima pozitie, indicatorul head pierzindu-si utilitatea. Dezavantajul acestei solutii consta in faptul ca operatia GET necesita o parcurgere a continutului cozii.
[B] Coada circulara
Pentru a obtine o coada circulara vom porni de la o coada liniara simpla (cu doi indicatori) si vom face in asa fel incit la incrementarea indicatorilor head si tail, cind acestia ating ultima pozitie din vector sa se continue cu prima pozitie din vector.
Functia urmatoare poate realizeaza aceasta cerinta:
int nextPoz(int index)
unde DIMVECTOR este dimensiunea vectorului in care se memoreaza elementele cozii.
Continutul cozii va arata asa:
¦ ¦1¦2¦3¦4¦5¦6¦7¦8¦ ¦
¦ ¦
+------+ +------+
¦ head ¦ ¦ tail ¦
+------+ +------+
sau asa:
¦5¦6¦7¦8¦9¦ ¦1¦2¦3¦4¦
¦ ¦
+------+ +------+
¦ tail ¦ ¦ head ¦
+------+ +------+
¦ Conditia "coada vida" ramine echivalenta cu: head = tail
¦ Coada va fi plina daca: head=1 si tail=DIMVECTOR
+-------- ----- ------ ----- ----- ----+
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ ¦
+-------- ----- ------ ----- ----- ----+
¦ ¦
+------+ +------+
¦ head ¦ ¦ tail ¦
+------+ +------+
sau daca: tail+1 = head
+-------- ----- ------ ----- ----- ----+
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
+-------- ----- ------ ----- ----- ----+
¦ ¦
+------+¦ ¦+------+
¦ tail ++ +¦ head ¦
+------+ +------+
Ambele situatii sint continute in conditia:
nextPoz(tail) = head // conditia "coada plina"
[C] Coada inlantuita
O coada poate fi implementata printr-o lista inlantuita la care operatiile de acces sint restrictionate corespunzator.
+----------+ +----------+ +----------+
¦ ¦ ¦-+-->¦ ¦ ¦-+-->¦ ¦nil¦
+->+----------+ +----------+ +>+----------+
head ¦ tail ¦
+---+ ¦ +---+ ¦
¦ ¦-+-+ ¦ ¦-+-+
+---+ +---+
Este nevoie de doi indicatori (pointeri):
head - indica primul element din coada (primul care va fi
scos);
tail - indica ultimul element din coada (ultimul introdus).
O coada vida va avea head=tail=nil
In mod obisnuit adaugarea unui element in coada modifica numai tail iar stergerea unui element numai head. Intr-un mod special trebuie sa fie tratate cazurile:
- adaugare intr-o coada vida:
Initial: head=tail=nil
Final: Coada cu un elememnt:
+----------+
+->¦ ¦nil¦
¦+>+----------+
head ¦¦ tail
+---+ ¦¦ +---+
¦ ¦-+-++--+-¦ ¦
+---+ +---+
- stergere dintr-o coada cu un element:
Initial: Coada cu un element
Final: head=tail=nil
In aceste cazuri se modifica atit head cit si tail.
[D] Coada inlantuita circulara
Daca reprezentam coada printr-o structura inlantuita circulara va fi nevoie de un singur pointer prin intermediul caruia se pot face ambele operatii de adaugare si stergere din coada:
+-------- ----- ------ ----- ----- --------+
¦ primul ultimul ¦
¦ +----------+ +----------+ +----------+ ¦
+->¦ ¦ ¦-+-····--->¦ ¦ ¦-+-->¦ ¦ ¦-+-+
+----------+ +----------+ +>+----------+
tail ¦
+---+ ¦
¦ ¦-+--+
+---+
Liste generalizate
Reprezentarea in C++
Un element al unei liste generalizate poate fi un atom sau o lista. Reprezentarea trebuie sa asigure un mijloc de a discrimina intre cele doua situatii. Solutia directa este de a memora in fiecare nod tipul lui (Atom sau Lista). Astfel, un element va avea urmatoarea structura:
tag data link
+-------- ----- ------ +
| | | |
+-------- ----- ------ +
unde: tag - eticheta discriminatoare;
data - informatia utila: un Atom sau o Lista;
link - informatia de inlantuire.
De exemplu, lista (a, (b, c), (d)) va avea reprezentarea:
+-------------+ +-------------+ +-------------+
|A| a | |--+-->|L| | | |--+-->|L| | | |
+-------------+ +----+--------+ +----+--------+
+----- ----- ---------+ |
| +-------------+ +-------------+ | +-------------+
+->|A| b | |--+->|A| c | | +->|A| d | |
+-------------+ +-------------+ +-------------+
Cimpul data poate contine un Atom sau o lista. Deci pentru structura de date care memoreaza un element de lista exista doua variante:
+-------------+ Un element de lista generalizata care
|A| val | |--+-> contine un Atom avind valoarea val .
+-------------+ Cimpul "data" contine valoarea atomului.
+-------------+ Un element de lista generalizata care
|L| | | |--+-> contine o Lista.
+----+--------+ Cimpul "data" contine pointer la primul element
+-> dintr-o lista.
Acest lucru se exprima in C++ cu ajutorul unei uniuni (union):
typedef char Atom;
enum ;
struct GElement; // declaratie simpla
typedef GElement* GLista; // o lista generalizata este un
// pointer la primul element
struct GElement data;
GElement* link; // legatura
};
Daca p este un pointer care contine adresa unui GElement, atunci in
memorie vom avea:
+----- ----- ----------------+
|p->tag| p->data | p->link |
+--------->+----- ----- ----------------+
| p->data.A - cimpul data considerat Atom
+---+---+ p->data.L - cimpul data considerat lista
| ||| |
+-------+
p
Parcurgerea unei liste generalizate
Definitia unei liste generalizate este o definitie recursiva (O «lista» este colectie ordonata de atomi si «liste». In consecinta operatiile de prelucrare a listelor generalizate vor fi realizate prin proceduri recursive. Iata procedura de afisare a unei liste generalizate:
void afisare(GLista L)
}
Se observa scheletul parcurgerii unei liste inlantuite simple, in care prelucrarea elementelor se face diferentiat in functie de tipul acestora: Atom sau Lista. Prelucrarea sublistelor se face prin apeluri recursive la aceeasi procedura.
Sa scriem o functie care calculeaza numarul de atomi aflati in total intr-o lista si in toate listele continute de aceasta.
Pornim de la urmatoarea definitie recursiva:
NrAtomi(L) = Na(L) + NrAtomi(Li)
unde: - NrAtomi - numarul total de atomi din lista L;
- Na(L) - numarul elementelor listei L care sint atomi;
- Li - elementele listei L care sint subliste.
int NrAtomi(GLista L)
return nr; }
|
