O structura de date presupune un mod de organizare a datelor (in tablouri, structuri, etc), si definirea operatiilor acceptate. Deci, o structura de date reprezinta o colectie organizata de date si un set de operatii definite.
Si notiunea de tip de date presupune: |--- reprezentare
|--- operatii acceptate
De exemplu, pentru tipul int 858j99i : |--- reprezentare: pe doi octeti: cod
| complementar
|---operatii acceptate: +, -, *, /, &, |, etc.
Daca pentru un tip de date nu intereseaza reprezentarea, ci doar operatiile acceptate,inseamna ca tipul de date este abstract.
Tabloul este o colectie de date in care fiecare element poate fi identificat pe baza unui index, colectia asigurand timp de acces constant pentru fiecare element. Prin reprezentarea tabloului se intelege plasarea elementelor in locatii succesive de memorie:
Locatiile de memorie pot fi numerotate, putand accesa direct orice element. Timpul de accesare al elementului numar, de exemplu, fiind acelasi cu timpul de accesare al elementului n.
O lista este o multime de obiecte, numite atomi, pentru care este definita o ordine:
Operatiile principale care se pot se face in cadrul listei:
inserare: introducerea unui nou element intr-o anumita pozitie;
stergere: scoaterea unui element dintr-o anumita pozitie;
consultare: accesul asupra fiecarui element din lista;
parcurgere.
Tipuri speciale de liste
O stiva este o lista in care operatiile de inserare, stergere si consultare se efectueaza asupra unui capat al listei. Stiva se poate asemana cu un recipient in care se pun si se pot scoate diferite obiecte. Operatia care pune obiectele in stiva se numeste push, iar cea care scoate obiecte din stiva se numeste pop. Capatul accesibil pentru stiva se numeste varful stivei:
Asadar:
push insereaza un element in varful stivei;
pop sterge un element din varful stivei;
top consulta (citeste) elementul din varful stivei;
top(S) citeste varful stivei.
O coada este o lista in care inserarea se face la un capat (la sfarsit), iar stergerea se face de la celalalt capat al cozii (de la inceput). Partea din fata a cozii (a primului element) se numeste front, iar partea din spate (a ultimului element) se numeste end.
Operatia de inserare in coada add (put)
Operatia de stergere din coada
O lista poate fi realizata ca: lista ordonata sau
lista inlantuita
Lista ordonata tine cont de o ordine a pozitiilor elementelor listei, nu de continutul elementelor.
Inserarea intr-o lista de forma:
se face cu deplasare de o pozitie la stanga din punctul in care dorim sa inseram (pentru a face acest loc noului element).
Deplasarea se face inspre zona de memorie libera (cea hasurata) presupunem ca dorim sa inseram pe a in pozitia i):
Presupunand acum hasurat corpul de elemente din lista si nehasurata zona de memorie libera, inserarea s-ar putea figura astfel:
Stergerea: deplasarea cu o pozitie la stanga din acel punct.
Intr-o lista inlantuita, ordinea din memorie nu mai corespunde cu ordinea din lista. Fiecare element al listei inlantuite va avea urmatoarea structura:
(a(i) , succesor(a(i)))
unde a(i) este atomul listei inlantuite, iar informatia succesor(a(i)) ne permite sa identificam un nou element de lista inlantuita. Ordinea din memorie a elementelor listei nu conteaza. Informatia care indica primul element al listei se numeste 'capul' listei. Informatiei succesor(a(i)) i se potriveste notiunea de pointer (identificator), pointer-ul fiind o variabila care pastreaza o adresa din memorie. El indica pozitia elementului urmator. Cand informatiile de inlantuire sunt pointeri, putem utiliza urmatoarea reprezentare:
Capul de lista este un pointer separat care duce la primul element din lista, iar 0 este pointer-ul nul (NULL) cu valoare zero. La implementarea listei inlantuite concentrarea se face la fluxul instructiunilor, nu la declaratiile de variabile.
In programe vom utiliza urmatoarele notatii:
x adresa unui element din lista, deci un pointer;
data(x) atomul memorat in elementul de lista indicat de x;
link(x) informatia de legatura memorata in elementul de lista indicat de x, adica adresa elementului urmator;
y = get_sp() y (de acelasi tip cu x) primeste adresa unei zone de memorie in care se poate memora un element din lista (get space sau alocare de memorie cand este vorba de pointer);
ret_sp(x) elibereza memoria ocupata de elementul de lista indicat de x (din momentul respectiv acolo se poate memora altceva).
Un element de lista va fi o astfel de structura:
struct Element ;
Se va scrie:
tipul lui x ----- ----- ------ Element* x
data(x) ----- ----- ------ x data
link(x) ----- ----- ------ x link
y = get_sp() ----- ----- ------ y = new Element
ret_sp() ----- ----- ------ delete x
Deoarece lucram cu conceptul de lista vom face declaratia :
typedef Element* Lista;
Un pointer la un element de lista considerat aproximeaza lista ce porneste cu elementul indicat.
Inserarea
Inserarea se face: in fata, sau
in interior (la mijloc ori la sfarsit)
a) Inserarea in fata
1 - Prima atribuire: link(x) = l
2 - A doua atribuire: l = x
Observatie: daca lista este vida, l are valoarea 0 (capatul listei) iar atribuirile de mai sus raman valabile:
b) Inserarea la mijloc
Analog pentru inserarea la sfarsit.
1 - Prima atribuire: link(x) = link(y)
2 - A doua atribuire: link(y) = x
2.a) Stergerea (stergerea din fata):
1 - Prima atribuire: p = l
2 - A doua atribuire: l = link(l)
3 - ret_sp(p)
Sau, stergerea din fata s-ar mai putea reprezenta astfel:
Situatia initiala:
Situatia finala:
(1) p = cap;
(2) cap = cap link;
delete p ; // Elibereaza zona de memorie
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).
Varibila q va indica elementul din fata celui care va fi sters.
Situatia initiala:
Situatia finala:
(1) p = q link;
(2) q link = p link; // sau q link = q link link;
delete p;
Observatii:
Atunci cand 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.
|
