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ã.
|
