Laborator SDA

LISTE SIMPLU ÎNLANTUITE

1. Continutul lucrarii

În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si particularitatile stivelor si cozilor.

2. 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 înlantuite.

Structura unui nod este urmatoarea:

typedef struct tip_nod {

int cheie; /* câmp neobligatoriu */

alte câmpuri de date utile;

struct tip_nod urm; /* legatura spre urmatorul 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;

2.1 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;

2.2 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)

{

/* s-a gasit nodul de cheie data */

/* el are adresa p */

return p;

}

else p=p->urm;

return 0; /* nu exista nod de cheie = key */

2.3 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) {

prim=p; ultim=p; p->urm=0;

}

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

a) înaintea primului nod

if(prim != 0) {

p->urm = prim; prim = p;

}

b) dupa ultimul nod:

if (ultim != 0) {

p -> urm = 0; ultim -> urm = p; ultim = p;

}

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)

{

if(q->cheie==key) break;

q1=q; q=q->urm;

}

- se insereaza nodul de pointer p, facând legaturile corespunzatoare:

if(q!=0) { /*nodul de cheie “key” are adresa q */

if (q==prim) {

p->urm=prim; prim=p;

}

else {

q1->urm=p; p->urm=q;

}

}

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

- se cauta nodul având cheia “key”:

TIP_NOD *q;

q=prim;

while(q!=0) {

if(q->cheie==key) break;

q=q->urm;

}

- se insereaza nodul de adresa p, facând legaturile corespunzatoare:

if (q !=)0) { /* nodul de cheie “key” are adresa q */

p -> urm = q -> urm;

q -> urm=p;

if (q == ultim) ultim = p;

}

2.4 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) { /* lista nu este vida */

p=prim; prim=prim->urm;

elib_nod(p);

/*eliberarea spatiului de memorie */

if(prim==0) ultim=0;

/* lista a devenit vida */

}