Liste simplu inlantuite

LISTE SIMPLU INLANTUITE

Continutul lucrarii

In lucrare sunt prezentate operatiile importante asupra listelor simplu inlantuite 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 in care ordinea este implicit data de tipul tablou unidimensional, sau cel mai des, sub forma de liste dinamice, in care ordinea nodurilor este stabilita prin pointeri. Nodurile listelor dinamice sunt alocate in memoria heap. Listele dinamice se numesc liste inlantuite, putand fi simplu sau dublu inlantuite.

In continuare se vor prezenta principalele operatii asupra listelor simplu inlantuite.

Structura unui nod este urmatoarea:

typedef struct tip_nod TIP_NOD;

Modelul listei simplu inlantuite este prezentat in fig. 2.1.

Fig. 2.1. Model de lista simplu inlantuita

Pointerii prim si ultim vor fi declarati astfel:

TIP_NOD *prim, *ultim;

Crearea unei liste simplu inlantuite

Crearea unei liste simplu inlantuite 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 in heap*/

citire date in nodul de adresa p;

c) Se fac legaturile corespunzatoare:

p->urm = 0;  /*nodul este ultimul in lista */

if(ultim != 0) ultim->urm = p;  /* lista nu este vida */

else prim = p;

/* nodul p este primul introdus in lista */

ultim=p;

Accesul la un nod al unei liste simplu inlantuite

In functie de cerinte, nodurile listei pot fi accesate secvential, extragand 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 putand fi prezent sau nu in lista.

O functie de cautare a unui nod de cheie "key" va contine secventa de program de mai jos; ea returneaza adresa nodului respectiv in caz de gasire sau pointerul NULL in 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 intr-o lista simplu inlantuita

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 in lista:

if (prim == 0)

Daca lista nu este vida, inserarea se poate face astfel:

a) inaintea primului nod

if(prim != 0)

b) dupa ultimul nod:

if (ultim != 0)

c)   inaintea 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, facand legaturile corespunzatoare:

if(q!=0)

else

d)   dupa un nod precizat printr-o cheie "key":

se cauta nodul avand cheia "key":

TIP_NOD *q;

q=prim;

while(q!=0)

se insereaza nodul de adresa p, facand legaturile corespunzatoare:

if (q !=)0)

Stergerea unui nod dintr-o lista simplu inlantuita

La stergerea unui nod se vor avea in 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 inlantuite

In acest caz, se sterge in mod secvential fiecare nod:

TIP_NOD *p;

while( prim != 0) 

ultim=0;

Stive

Stiva este o lista simplu inlantuita bazata pe algoritmul LIFO (Last In First Out), adica ultimul nod introdus este primul scos. Modelul stivei, care va fi avut in vedere in continuare, este prezentat in fig.2.6.1.

Fig. 2.6.1. Model de stiva

Fiind o structura particulara a unei liste simplu inlantuite, 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 inaintea primului;

- pop     - scoate elementul din varful stivei; functia se realizeaza conform paragrafului 2.4.a., adica prin stergerea primului nod;

- clear - stergerea stivei; functia se realizeaza conform paragrafului 2.5.

In concluzie, accesul la o stiva se face numai pe la un capat al sau.

Cozi

Coada este o lista simplu inlantuita, bazata pe algoritmul FIFO (First In First Out), adica primul element introdus este primul scos. Modelul cozii  care va fi avut in vedere in consideratiile

urmatoare, este prezentat in 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 in 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;

avand 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 inlantuita ordonata alfabetic, care contine in noduri cuvintele distincte si frecventa lor de aparitie. Se va afisa continutul listei in 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 oricate locomotive. Sa se scrie programul care realizeaza dispecerizarea locomotivelor din depou.

Programul prelucreaza comenzi de intrare in 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 intr-o anumita ordine, incat pentru orice elemente x, y cu proprietatea ca x precede pe y, elementul x sa fie afisat inaintea 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 in memorie a polinoamelor. Se vor scrie functii de calcul a sumei, diferentei, produsului si impartirii 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 +, -, *, /.