Structuri elementare de date
În capitolul 1, introductiv, recapitulam câteva din notiunile introduse la 'algoritmica' si anume:
alocarea stucturilor liniare
secventiala
înlantuita
Am folosit, pâna acum structuri foarte simple de date cum ar fi :
variabile simple (dintre care unele aveau domeniul de valori formate doar din doua valori).
vectori cu componentele sortate sau nesortate (asa cum sunt folositi în matematica).
matrici considerate ca vectori de vectori sau ca masive biortogonale.
Vom studia acum alte structuri ceva mai complicate.
1.1 Structuri liniare
O structura liniara este o multime de n 0 componente x(1),x(2),.,x(n) cu proprietatile:
a) Cand n=0 spunem ca structura este vida.
b) Daca n > 0 atunci x(1) este primul element iar x(n) este ultimul element.
c) Oricare ar fi x(k) unde k exista un predecesor x(k-1) si un succesor x(k+1).
Ne va interesa sa executam cu aceste structuri urmatoarele operatii:
-adaugarea unui element
-extragerea unui element
-accesarea unui element x(k) din structura
-combinarea a doua sau mai multe structuri într-una singura
-" ruperea " unei structuri an mai multe structuri
-sortarea elementelor unei structuri
-cautarea unui element al structurii care are anumite proprietati etc.
1.2 Stive.
Una din cele mai folosite structuri liniare este stiva.O stiva este caracterizata de disciplina de intrare si iesire din stiva.
Sa consideram o multime de carti puse una peste alta ; exista o prima carte care se poate lua foarte sor (TOP) si o carte care se poate lua numai daca deplasez toate celelalte carti (BOTTOM).
Disciplina unei stive este " ultimul intrat - primul iesit " (disciplina care nu v-ar place sa fie respectata când stati la rând la lapte ! ) ( Last in, first out - prescurtarea acestei reguli este LIFO).
Care ar fi diferentele fata de un vector :
-un vector are o lungime fixa, non zero cunoscuta aprioric
-o stiva poate fi vida
-stiva are un numar variabil de elemente în timpul executiei unui algoritm
Se pune problema reprezentarii concrete a unei stive în memoria unui calculator. Putem aloca o stiva în doua moduri :
I ) Secvential
II ) Înlantuit
I ) Alocarea secventiala a stivei.
Folosim vectorul ca fiind structura cea mai apropiata de structura reala 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 stiva.
Algoritmul de intrare în stiva va fi :
a STIVA
Daca k = n atunci DEPASIRE
altfel
k = k + 1
x(k) = a
Sdaca
Return
Algoritmul de iesire din stiva va fi :
a STIVA
Daca k = 0 atunci STIVA VIDA
altfel
a = x( k )
k = k - 1
Sdaca
Return
II ) Alocarea înlantuita a stivei
În alocarea înlantuita fiecare element al structurii este însotit de adresa la care se afla precedentul element. Vom avea vârful pus în evidenta (ancorat) în INC si un semn special " " în loc de adresa bazei ca în figura urmatoare :
| INFO | LEG |
INC | | | x(k) | |x(k-1) | | |x(2) | | |x(1) |
(Ordinea 1,2,.,k este ordinea intrarii în stiva).
În acest caz intrarea în stiva va folosi stiva de locuri libere (aceasta stiva se numeste LIBERE) pentru a obtine locuri la introducerea în stiva.
Vom prezenta în continuare algoritmii de intrare-iesire dintr-o stiva în cazul în care alocarea ei a fost înlantuita :
Algoritmul de intrare in stiva va fi :
a STIVA
y LIBERE
INFO(y) = a ; LEG(y)=INC ; INC = y
Return
Algoritmul de iesire din stiva va fi :
a STIVA
Daca INC= ' ' atunci 'STIVA VIDA'
Altfel
INC LIBERE
a=INFO(INC)
INC=LEG(INC)
Sdaca
Return
1.3 Coada.
O alta structura liniara utilizata în conceperea algoritmilor este coada. O coada este caracterizata si ea de o disciplina de intrare-iesire, bineinteles diferita de cea a stivei. De aceasta data puteti sa va gânditi la coada la lapte: primul care s-a asezat la coada va fi primul servit, adica primul care iese din coada.
Disciplina unei cozi este "primul venit, primul plecat" ( "first in, first out " având prescurtarea FIFO).
O coada poate fi vida si are si ea un numar variabil de elemente în timpul executiei unui algoritm.
I ) Alocarea secventiala a cozii.
Coada alocata secvential îsi va gasi locul tot într-un vector (x(i)),i=1,n.
| x(1) | x(2) | . | x(f) | . | x(s) | . | x(n) |
FAŢĂ SFÂRsIT
Din cele 'n' componente ale vectorului doar componentele x(f) . x(s) fac parte din coada.
Algoritmul de intrare în coada va fi :
a COADA
Daca S = n atunci 'DEPASIRE'
Altfel
S = S + 1
x(S) = a
Sdaca
Return
Algoritmul de iesire din coada va fi :
a COADA
Daca F> S atunci COADA VIDA
Altfel
a=x(F);F=F+1
Sdaca
Return
Se poate imagina usor ca procedând în acest fel (scotând din fata si introducând la sfârsit) coada "migreaza" spre dreapta si poate sa ajunga în situatia DEPASIRE când de fapt mai exista mult loc gol (în vectorul x) pe primele pozitii. Apare astfel ideea de a folosi elementele vectorului ca si cum ar fi dispuse circular:
FATA
| x(F) |
| x(2) |
| x(1) |
| x(n) | | x(S) | SFARSIT
Este locul ca cititorul sa faca primul efort de a scrie algoritmii de intrare-iesire din coada circulara.
Exercitiul 1 si 2.
II ) Alocarea înlantuita a cozii.
Se face în mod similar cu alocarea înlantuita a stivei în noduri de tipul:
| INFO | LEG |
| x(F) | | | | | x(S) |
FAŢĂ SFÂRsIT
Algoritmul de intrare în coada va fi :
a COADA
y LIBERE
INFO(y) = a ; LEG(SFARSIT)=y
Return
Algoritmul de iesire din coada va fi :
a COADA
Daca FATA= ' ' atunci COADA VIDA
Altfel
a=INFO(FATA)
FATA LIBERE
FATA=LEG(FATA)
Sdaca
Return
Întrebari si exercitii la capitolul 1.
Exercitiile 1 si 2 se refera la coada circulara si sunt cuprinse în text.
Exercitiul 3.
Considerati doua stive alocate în acelasi vector.
a. care va fi disciplina de umplere? Faceti un desen.
b. scrieti algoritmii de intrare-iesire pentru stiva 1.
c. scrieti algoritmii de intrare-iesire pentru stiva 2.
Exercitiul 4
Considerati o matrice patratica de ordinul n în care toate elementele deasupra diagonalei principale sunt egale cu 0.
a) câte elemente pot fi diferite de 0?
b) aranjati, pe linii, elementele acestea (de pe diagonala principala si de sub ea) într-un vector. Faceti un desen.
c) Daca matricea este A si vectorul este B, A(i,j) se va duce în B(k). Dati formula pentru calculul lui k în functie de i si j.
d) Dati si formula invers: i si j în functie de k.
e) Scrieti algoritmul care citeste matricea A si trece elementele de pe diagonala principala si de sub ea în vectorul B.
f) Scrieti algoritmul care, pornind de la doi vetori B1 si B2, obtinuti ca la punctul e) din matricile A1 si A2 calculeaza imaginea MB a matricii produs A1xA2. (Aratati, mai întâi, ca produsul este o matrice de aceeasi forma.)
|
