LISTE SIMPLU ÎNLĂNŢUITE
Continutul lucrarii
În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si particularitatile stivelor si cozilor.
Consideratii teoretice
Lista este o multime finita si ordonata de elemente de acelasi tip. Elementele listei se numesc noduri.
Listele pot fi organizate sub forma statica, de tablou, caz în care ordinea este implicit data de tipul tablou unidimensional, sau cel mai des, sub forma de liste dinamice, în care ordinea nodurilor este stabilita prin pointeri. Nodurile listelor dinamice sunt alocate în memoria heap. Listele dinamice se numesc liste înlantuite, putând fi simplu sau dublu înlantuite.
În continuare se vor prezenta principalele operatii asupra listelor simplu înlan 434d36e tuite.
Structura unui nod este urmatoarea:
typedef struct tip_nod TIP_NOD;
Modelul listei simplu înlantuite este prezentat în fig. 2.1.
Fig. 2.1. Model de lista simplu
înlantuita
Pointerii prim si ultim vor fi declarati astfel:
TIP_NOD *prim, *ultim;
Crearea unei liste simplu înlantuite
Crearea unei liste simplu înlantuite se va face astfel:
a) Initial lista este vida:
prim = 0; ultim = 0;
b) Se genereaza nodul de introdus:
n=sizeof(TIP_NOD);
p=(TIP_NOD *)malloc(n); /* rezervare spatiu de memorie în heap*/
citire date în nodul de adresa p;
c) Se fac legaturile corespunzatoare:
p->urm = 0; /*nodul este ultimul în lista */
if(ultim != 0) ultim->urm = p; /* lista nu este vida */
else prim = p;
/* nodul p este primul introdus în lista */
ultim=p;
Accesul la un nod al unei liste simplu înlantuite
În functie de cerinte, nodurile listei pot fi accesate secvential, extragând informatia utila din ele. O problema mai deosebita este gasirea unui nod de o cheie data si apoi extragerea informatiei din nodul respectiv. Cautarea nodului dupa cheie se face liniar, el putând fi prezent sau nu în lista.
O functie de cautare a unui nod de cheie "key" va contine secventa de program de mai jos; ea returneaza adresa nodului respectiv în caz de gasire sau pointerul NULL în caz contrar:
TIP_NOD *p;
p=prim;
while( p != 0 ) if (p->cheie == key)
else p=p->urm;
return 0; /* nu exista nod de cheie = key */
Inserarea unui nod într-o lista simplu înlantuita
Nodul de inserat va fi generat ca la paragraful 2.1; se presupune ca are pointerul p.
Daca lista este vida, acest nod va fi singur în lista:
if (prim == 0)
Daca lista nu este vida, inserarea se poate face astfel:
a) înaintea primului nod
if(prim != 0)
b) dupa ultimul nod:
if (ultim != 0)
c) înaintea unui nod precizat printr-o cheie "key":
se cauta nodul de cheie "key":
TIP_NOD *q, *q1;
q1=0; q=prim;
while(q!=0)
se insereaza nodul de pointer p, facând legaturile corespunzatoare:
if(q!=0)
else
d) dupa un nod precizat printr-o cheie "key":
se cauta nodul având cheia "key":
TIP_NOD *q;
q=prim;
while(q!=0)
se insereaza nodul de adresa p, facând legaturile corespunzatoare:
if (q !=)0)
stergerea unui nod dintr-o lista simplu înlantuita
La stergerea unui nod se vor avea în vedere urmatoarele probleme: lista poate fi vida, lista poate contine un singur nod sau lista poate contine mai multe noduri.
De asemenea se poate cere stergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie "key".
a) stergerea primului nod
TIP_NOD *p;
if(prim!=0)
b) stergerea ultimului nod
TIP_NOD *q, *q1;
q1=0; q=prim;
if(q!=0)
if(q==prim)
else
elib_nod(q);
c) stergerea unui nod de cheie "key"
TIP_NOD *q, *q1;
/* cautare nod */
q1=0; q=prim;
while (q!=0)
if(q != 0)
else
stergerea unei liste simplu înlantuite
În acest caz, se sterge în mod secvential fiecare nod:
TIP_NOD *p;
while( prim != 0)
ultim=0;
Stive
Stiva este o lista simplu înlantuita
bazata pe algoritmul LIFO (Last In First Out), adica ultimul nod
introdus este primul scos. Modelul stivei, care va fi avut în vedere în
continuare, este prezentat în fig.2.6.1.
Fig. 2.6.1. Model de stiva
Fiind o structura particulara a unei liste simplu înlantuite, operatiile principale asupra unei stive sunt:
- push - pune un element pe stiva; functia se realizeaza conform paragrafului 2.3.a., adica prin inserarea unui nod înaintea primului;
- pop - scoate elementul din vârful stivei; functia se realizeaza conform paragrafului 2.4.a., adica prin stergerea primului nod;
- clear - stergerea stivei; functia se realizeaza conform paragrafului 2.5.
În concluzie, accesul la o stiva se face numai pe la un capat al sau.
Cozi
Coada este o lista simplu înlantuita, bazata pe algoritmul FIFO (First In First Out), adica primul element introdus este primul scos. Modelul cozii care va fi avut în vedere în consideratiile
urmatoare, este prezentat în
fig.2.7.1.
Fig.2.7.1. Model de coada
Deci coada are doua capete, pe la unul se introduce un element, iar de la celalalt capat se scoate un element.
Operatiile importante sunt:
introducerea unui element în coada - functia se realizeaza prin inserarea dupa ultimul nod, conform celor prezentate la paragraful 2.3.b.;
scoaterea unui element din coada - functia se realizeaza prin stergerea primului nod, conform celor prezentate la paragraful 2.4.a.;
stergerea cozii - functia se realizeaza conform paragrafului 2.5.
Mersul lucrarii
3.1.Sa se defineasca si sa se implementeze functiile pentru structura de date
typedef stuct LISTA;
având modelul din fig.3.1.
3.2.Sa se implementeze o lista ca un tablou static ce
contine pointeri la nodurile de informatie din heap, conform
modelului din fig.3.2.
3.3. De la tastatura se citesc cuvinte. Sa se creeze o lista simplu înlantuita ordonata alfabetic, care contine în noduri cuvintele distincte si frecventa lor de aparitie. Se va afisa continutul listei în ordine alfabetica .
3.4. Se considera un depou de locomotive cu o singura intrare si cu o singura linie de cale ferata, care poate cuprinde oricâte locomotive. Sa se scrie programul care realizeaza dispecerizarea locomotivelor din depou.
Programul prelucreaza comenzi de intrare în depou a unei locomotive, de iesire din depou a unei locomotive si de afisare a locomotivelor din depou.
Aceeasi problema 3.4, cu deosebirea ca depoul are intrarea la un capat si iesirea la capatul opus.
Sortarea topologica.
Elementele unei multimi M sunt notate cu litere mici din alfabet. Se citesc perechi de elemente x, y (x, y apartin multimii M) cu semnificatia ca elementul x precede elementul y. Sa se afiseze elementele multimii M într-o anumita ordine, încât pentru orice elemente x, y cu proprietatea ca x precede pe y, elementul x sa fie afisat înaintea lui y.
3.7.Sa se scrie programul care creeaza doua liste ordonate crescator dupa o cheie numerica si apoi le interclaseaza.
3.8.Sa se conceapa o stuctura dinamica eficienta pentru reprezentarea matricelor rare. Sa se scrie operatii de calcul a sumei si produsului a doua matrice rare. Afisarea se va face in forma naturala.
3.9.Sa se conceapa o structura dinamica eficienta pentru reprezentarea în memorie a polinoamelor. Se vor scrie functii de calcul a sumei, diferentei, produsului si împartirii a doua polinoame.
3.10. Se citeste de la tastatura o expresie postfixata corecta sintactic. Sa se scrie programul de evaluare a sa. Expresia contine variabile formate dintr-o litera si operatorii binari +, -, *, /.
|
