5. Tipul abstract "Listă". Liste stivă.
Liste (secvente) de date
Tipul abstract "Listă" are mai multe definitii posibile:
- O colectie liniară de elemente, în care fiecare element este accesibil printr-un indice întreg, care arată pozitia elementului respectiv în listă.
- O secventă de elemente, în care fiecare element are un succesor si, eventual, un predecesor.
Lista nu este o structură de căutare ci doar o structură pentru memorarea temporară a unor date.
Diferentele principale între o listă si o multime sunt:
- Intr-o listă pot fi mai multe elemente egale.
- Intr-o listă nu se fac căutări frecvente după valoarea (continutul) unui element.
Operatiile cu tipul abstract "Listă" pot fi grupate în:
- Operatii comune oricărei colectii : initializare (initL), determinare dimensiune (sizeL), adăugare la sfârsit de listă (addL) s.a.
- Operatii specifice clasei abstracte "List" : citire (getL), modificare (setL), inserare (insL), stergere (removeL), toate într-o pozitie dată (un indice întreg).
Functiile de acces pozitional au rezultat 0 ('fals') dacă indicele "pos" este în afara listei si rezultat 1 ('true') dacă operatia a reus 16416i87q it. Indicele este o variabilă a programului de aplicatie, deci un cursor extern listei. Pot fi mai multe variabile cursor, cu valori diferite, pe o aceeasi listă.
Pentru a realiza operatiile de acces secvential ("first" si "next") se foloseste un cursor intern, deci o variabilă suplimentară de tip întreg sau pointer, functie de implementarea listei.
Implementările principale pentru tipul abstract "Lista" sunt două: vector si listă înlăntuită.
Un vector este recomandat pentru liste cu continut stabil, atunci când este necesar un acces aleator frecvent la elementele listei, ca în operatiile de sortare sau de căutare binară.
O listă înlăntuită se recomandă atunci când dimensiunea listei este greu de estimat, fiind posibile multe adăugări si/sau stergeri din listă, sau atunci când sunt necesare inserări de elemente în interiorul listei. Desi este posibil accesul pozitional, printr-un indice întreg, la elementele unei liste înlăntuite, utilizarea sa frecventă afectează negativ performantele aplicatiei.
Exemple de functii pentru operatii cu o listă abstractă realizată ca listă simplu înlăntuită.
typedef int T ; // tip date aplicatie
typedef struct sn Nod, * Pnod, *List;
// initializare lista
List initL ()
// adaugare la sfarsitul listei
void addL (List lst, T x)
// acces pozitional, pe baza de indice
T getL (List lst, int i)
return p->val;
// dimensiune lista
int sizeL (List lst)
// introducere in lista in pozitia i
void insL (List lst, int i, T x)
n->leg=p; q->leg=n;
// afisare lista, cu acces pozitional
void pprintL (List lst)
printf ("\n");
// creare si afisare lista
void main ()
Căutarea binară, într-o listă ordonată, necesită acces pe bază de indice, la elementul median din listă, dar nu se justifică decât pentru liste implementate prin vectori.
Ca exemplu de prelucrare simplă a unei liste si care necesită accesul aleator (prin indice) la elementele listei vom prezenta o functie care "amestecă" elementele unei liste (operatie inversă ordonării, similară amestecării unui pachet de cărti de joc). Functia "setL" modifică (înlocuieste) valoarea dintr-o pozitie dată a unei liste si este aproape la fel cu functia "getL".
// schimba intre ele valorile din pozitiile i si j
void swap ( List lst, int i, int j)
// amesteca elementele listei
void shuffle (List lst)
void main ()
Liste stivă
O stivă este o listă cu acces la un singur capăt, numit "vârful" stivei. Singurele operatii permise sunt introducere în prima pozitie si extragere din prima pozitie (eventual si citire din prima pozitie). Aceste operatii sunt denumite traditional "push" (pune pe stivă) si "pop" (scoate din stivă) si nu mai specifică pozitia din listă, care este implicită . O stivă mai este numită si listă LIFO ('Last In First Out'), deoarece ultimul element pus este primul care va fi extras din stivă.
Operatiile cu o stivă pot fi privite ca niste cazuri particulare de operatii cu liste oarecare:
// pune x pe stiva
void push ( List lst, T x)
// scoate din stiva in x
T pop ( List lst )
De obicei stiva este abordată direct ca un vector sau ca o listă înlăntuită. Urmează functii pentru operatii cu o stivă realizată ca un vector extensibil, cu adăugare si stergere la sfârsitul vectorului.
#define INC 100 // increment extindere stiva
typedef int T; // tip date puse pe stiva
typedef struct st stiva, *Stack;
// initializare stiva
Stack initS ()
// pune pe stiva o valoare x
void push (Stack s, T x)
s->st [s->sp++]=x;
// scoate valoarea din varful stivei
T (Stack s)
// test stiva goala
int emptyS (Stack s)
Stiva listă înlăntuită, cu adăugare si extragere numai la începutul listei, poate fi o listă cu santinelă. Exemplu de functii pentru operatii cu o stivă listă fără santinelă:
typedef struct s Nod, * stack ;
typedef stack* Stack;
// initializare stiva
Stack initSt ()
// test stiva goala
int emptySt (Stack s)
// pune in stiva un element
void push (Stack s, T x)
// scoate din stiva primul element
T pop (Stack s)
Principalele utilizări pentru o stivă sunt:
- Eliminarea recursivitătii, prin memorarea temporară a unor date (si adrese);
- Inversarea ordinii unui sir de valori (prelucrare în ordine inversă adăugării).
Exemplul următor poate fi privit ca utilizare a stivei pentru afisarea în ordine inversă a resturilor împărtirii prin 2, dar si ca utilizare a stivei pentru eliminarea recursivitătii la conversia în binar.
// afisare numar in binar (nerecursiv)
void binar (int n)
while (! emptySt(st))
// afisare in binar (recursiv)
void binar (int n)
Utilizare stivă pentru eliminarea recursivitătii directe
Functiile recursive cu mai multe apeluri recursive sau cu un singur apel care nu este si ultima instructiune din functie nu pot fi rescrise iterativ fără a utiliza o stivă.
De exemplu, functia nerecursivă pentru afisarea valorilor dintr-un arbore binar foloseste o stivă pentru a memora adresele nodurilor prin care s-a trecut dar care nu au fost afisate, urmând ca la revenirea prin aceste noduri să se afiseze valorile lor. Pentru ca stiva să nu se golească complet se pune initial în stivă o adresă oarecare (diferită de NULL):
// afisare infixata nerecursiva arbore binar
void infix (Nod * r)
else
}
} while ( r!= x));
printf ("\n");
Evolutia stivei 'st' la afisarea infixată a arborelui binar
5 (2 (1,4) , 8 (6,9) )
Oper. Stiva Afisare
push(x) x
push (&5) x,&5
push (&2) x,&5,&2
push (&1) x,&5,&2,&1
pop x,&5,&2 1
pop x,&5 2
push(&4) x,&5,&4
pop x,&5 4
pop x 5
push (&8) x,&8
push (&6) x,&8,&6
pop x, &8 6
pop x 8
push (&9) x,&9
pop x 9
Utilizare stivă pentru trecere la forma postfixată
Intr-o expresie aritmetică ordinea de calcul (de aplicare a operatorilor aritmetici) este în general diferită de ordinea în care operatorii apar în expresie. Exemplu de expresie cu paranteze:
a + (b-c) / (d+e)
Ordinea de evaluare a subexpresiilor este următoarea:
t1=b-c; t2=d+e; t3=t1/t2; t4=a+t3;
Expresiile în care un operator binar apare între cei doi operanzi se numesc si expresii infixate. S-a propus si o altă formă de scriere a expresiilor aritmetice, care nu foloseste paranteze si care tine seama de prioritatea operatorilor- forma postfixată, în care fiecare operator apare după operanzi. Expresia anterioară, în forma postfixată, arată astfel:
abc-de+/+
Trecerea de la forma infixată la forma postfixată a expresiilor aritmetice foloseste o stivă de operatori. Operanzii din sirul infixat sunt trecuti direct în sirul postfixat, iar operatorii trec prin stivă, de unde se scot în functie de rezultatul comparatiei prioritătii operatorului extras din sirul infixat cu prioritatea operatorului din vârful stivei. Algoritmul poate fi descris astfel:
repeta pana la terminarea sirului infixat
extrage urmatorul caracter din sir in ch
daca ch este operand atunci trece ch in sirul postfixat
daca ch este "(" atunci se pune ch in stiva
daca ch este ")" atunci
extrage din stiva pana la "(" (inclusiv) si trece in sirul postfixat
daca ch este operator atunci
repeta cat timp prior(ch) < prior(operator din varful stivei)
scoate din stiva in sirul postfixat
pune ch in stiva
scoate tot ce a ramas in stiva si adauga la sirul postfixat
afiseaza sir postfixat
Program pentru expresii cu operanzi de o singură cifră si cu patru operatori binari si paranteze:
// determina prioritate operator
int pri (char op) ; // tabel operatori
int pr[] =;
for (k=0;k<nop;k++)
if (op==top[k])
return pr[k];
return -1;
// trecere expresii aritmetice la forma postfixata
void main ()
} while (! empty(st));
// afisare sir postfixat
*b=0; // ptr o afisare mai simpla
printf("%s\n",out);
Initial stiva de operatori trebuie să contină un operator de prioritate mică, pentru prima comparatie cu operatorul (paranteza) din sirul infixat. O solutie este adăugarea de paranteze în jurul expresiei initiale, iar o altă solutie este folosirea operatorului de atribuire (prezent în instructiunile aritmetice de atribuire).
Evaluarea unei expresii postfixate se face prin parcurgere de la stânga la dreapta, folosind o stivă pentru operanzi si rezultate intermediare: la întâlnirea unui operator în sirul postfixat se scot cei doi operanzi din vârful stivei, se aplică operatorul si se pune rezultatul operatiei pe stivă.
|
