CAPITOLUL 1 Structuri elementare de date.
În capitolul 1, introductiv, recapitulăm câteva din noţiunile introduse la ‘algoritmică’ şi anume:
- structuri liniare vectori, matrici, stive, cozi
- alocarea stucturilor liniare
- secvenţială
- înlănţuită
Am folosit, până acum structuri foarte simple de date cum ar fi :
- variabile simple (dintre care unele aveau domeniul de valori formate doar din două valori).
- vectori cu componentele sortate sau nesortate (aşa cum sunt folosiţi în matematică).
- matrici considerate ca vectori de vectori sau ca masive biortogonale.
Vom studia acum alte structuri ceva mai complicate.
1.1 Structuri liniare.
O structură liniară este o mulţime de n 0 componente x(1),x(2),…,x(n) cu proprietăţile:
a) Cand n=0 spunem ca structura este vidă.
b) Daca n > 0 atunci x(1) este primul element iar x(n) este ultimul element.
c) Oricare ar fi x(k) unde k{2,…,n-1} există un predecesor x(k-1) şi un succesor x(k+1).
Ne va interesa să executăm cu aceste structuri urmatoarele operaţii:
-adăugarea unui element
-extragerea unui element
-accesarea unui element x(k) din structură
-combinarea a două sau mai multe structuri într-una singură
-“ ruperea “ unei structuri ăn mai multe structuri
-sortarea elementelor unei structuri
-căutarea unui element al structurii care are anumite proprietăţi etc…
1.2 Stive.
Una din cele mai folosite structuri liniare este stiva.O stivă este caracterizată de disciplina de intrare şi ieşire din stivă.
Să considerăm o mulţime de cărţi puse una peste alta ; există o primă carte care se poate lua foarte şor (TOP) şi o carte care se poate lua numai dacă deplasez toate celelalte carţi (BOTTOM).
Disciplina unei stive este “ ultimul intrat - primul ieşit “ (disciplină care nu v-ar place să fie respectată când staţi la rând la lapte ! ) ( Last in, first out - prescurtarea acestei reguli este LIFO).
Care ar fi diferenţele fată de un vector :
-un vector are o lungime fixă, non zero cunoscută aprioric
-o stivă poate fi vidă
-stiva are un numar variabil de elemente în timpul execuţiei unui algoritm
Se pune problema reprezentării concrete a unei stive în memoria unui calculator. Putem aloca o stivă în două moduri :
I ) Secvenţial
II ) Înlănţuit
I ) Alocarea secvenţială a stivei.
Folosim vectorul ca fiind structura cea mai apropiată de structura reală a memoriei. În vectorul (x (i) ) i=1,n
| x(1) | x(2) | x(3) | … | x(k) | … | x(n) |
Bottom Top
-din n componente ale unui vector doar ‘k’ elemente fac parte din stivă.
Algoritmul de intrare în stivă va fi :
a STIVA
Daca k = n atunci DEPASIRE
altfel
k = k + 1
x(k) = a
Sdaca
Return
Algoritmul de ieşire din stivă va fi :
aSTIVA
Daca k = 0 atunci STIVA VIDA
altfel
a = x( k )
- k = k – 1
Sdaca
Return
II ) Alocarea înlanţuită a stivei
În alocarea înlănţuită fiecare element al structurii este însoţit de adresa la care se afla precedentul element. Vom avea vârful pus în evidenţă (ancorat) în INC şi un semn special “” în loc de adresa bazei ca în figura următoare :
| INFO | LEG |
INC | || x(k) | ||x(k-1) | |…|x(2) | ||x(1) | |
(Ordinea 1,2,…,k este ordinea intrării în stivă).
În acest caz intrarea în stivă va folosi stiva de locuri libere (această stivă se numeşte LIBERE) pentru a obţine locuri la introducerea în stivă.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
