Lucrarea de laborator nr

Liste1. Coninutul lucrriin lucrare sunt prezentate operaiile importante asupra listelor simplu nlnuite si listelor circulare simplu nlnuite.2. Consideraii teoreticeLista este o mulime finit i ordonat de elemente de acelai tip. Elementele listei se numesc noduri.

Listele pot fi organizate sub form static, de tablou, caz n care ordinea este implicit dat de tipul tablou unidimensional, sau cel mai des, sub form de liste dinamice, n care ordinea nodurilor este stabilit prin pointeri. Nodurile listelor dinamice sunt alocate n memoria heap. Listele dinamice se numesc liste nlnuite, putnd fi simplu sau dublu nlnuite.

n continuare se vor prezenta principalele operaii asupra listelor simplu nlnuite.

Structura unui nod este urmtoarea:

typedef struct tip_nod {

int cheie; /* cmp neobligatoriu */

alte cmpuri de date utile;

struct tip_nod urm;/* legtura spre urmtorul nod */

} TIP_NOD;

Modelul listei simplu nlnuite este prezentat n fig. 2.1.

Fig. 2.1. Model de list simplu nlnuit

Pointerii prim i ultim vor fi declarai astfel:

TIP_NOD *prim, *ultim;

2.1 Crearea unei liste simplu nlnuite

Crearea unei liste simplu nlnuite se va face astfel:

a) Iniial lista este vid:

prim = 0; ultim = 0;

b) Se genereaz nodul de introdus:

n=sizeof(TIP_NOD);

p=(TIP_NOD *)malloc(n);/* rezervare spaiu de memorie n heap*/

citire date n nodul de adres p;c) Se fac legturile corespunztoare:

p->urm = 0; /*nodul este ultimul n list */

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

else prim = p; /* nodul p este primul introdus n list */

ultim=p;

2.2 Accesul la un nod al unei liste simplu nlnuite

n funcie de cerine, nodurile listei pot fi accesate secvenial, extrgnd informaia util din ele. O problem mai deosebit este gsirea unui nod de o cheie dat i apoi extragerea informaiei din nodul respectiv. Cutarea nodului dup cheie se face liniar, el putnd fi prezent sau nu n list.

O funcie de cutare a unui nod de cheie key va conine secvena de program de mai jos; ea returneaz adresa nodului respectiv n caz de gsire sau pointerul NULL n caz contrar:

TIP_NOD *p;

p=prim;

while( p != 0 ) if (p->cheie == key)

{

/* s-a gsit nodul de cheie dat */

/* el are adresa p */

return p;

}

else p=p->urm;

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

2.3 Inserarea unui nod ntr-o list simplu nlnuit

Nodul de inserat va fi generat ca la paragraful 2.1; se presupune c are pointerul p.

Dac lista este vid, acest nod va fi singur n list:

if (prim == 0) {

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

}

Dac lista nu este vid, inserarea se poate face astfel:

a) naintea primului nod

if(prim != 0) {

p->urm = prim; prim = p;

}

b) dup ultimul nod:

if (ultim != 0) {

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

}

c) naintea unui nod precizat printr-o cheie key:

-se caut 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 insereaz nodul de pointer p, fcnd legturile corespunztoare:

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) dup un nod precizat printr-o cheie key:

-se caut nodul avnd cheia key:

TIP_NOD *q;

q=prim;

while(q!=0) {

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

q=q->urm;

}

-se insereaz nodul de adres p, fcnd legturile corespunztoare:

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

p -> urm = q -> urm;

q -> urm=p;

if (q == ultim) ultim = p;

}

2.4 tergerea unui nod dintr-o list simplu nlnuit

La tergerea unui nod se vor avea n vedere urmtoarele probleme: lista poate fi vid, lista poate conine un singur nod sau lista poate conine mai multe noduri.

De asemenea se poate cere tergerea primului nod, a ultimului nod sau a unui nod dat printr-o cheie key.

a) tergerea primului nod

TIP_NOD *p;

if(prim!=0) {/* lista nu este vid */

p=prim; prim=prim->urm;

elib_nod(p); /*eliberarea spaiului de memorie */

if(prim==0) ultim=0; /* lista a devenit vid */

}

b) tergerea ultimului nod

TIP_NOD *q, *q1;

q1=0; q=prim;

if(q!=0) { /* lista nu este vid */

while(q!=ultim)

{

q1=q; q=q->urm;

}

if(q==prim) {

prim=0; ultim=0;

}

else {

q1->urm=0; ultim=q1;

}

elib_nod(q);

}

c) tergerea unui nod de cheie key

TIP_NOD *q, *q1;

/* cutare nod */

q1=0; q=prim;

while (q!=0)

{

if(q->cheie == key) break; /* s-a gsit nodul */

q1=q; q=q->urm;

}

if(q != 0) { /* exist un nod de cheie key */

if (q == prim) {

prim=prim_>urm;

elib_nod(q); /*eliberare spaiu */

if( prim==0) ultim=0;

}

else {

q1->urm=q->urm;

if(q==ultim) ultim=q1;

elib_nod(q); /* eliberare spaiu */

}

2.5 tergerea unei liste simplu nlnuite

n acest caz, se terge n mod secvenial fiecare nod:

TIP_NOD *p;

while( prim != 0) {

p=prim; prim=prim->ultim;

elib_nod(p); /*eliberare spaiu de memorie */

}

ultim=0;

2.6. Liste circulare simplu nlnuiteLista circular simplu nlnuit este lista simplu nlnuit a crei ultim element este legat de primul element; adic ultim -> urm = prim.

n cadrul listei circulare simplu nlnuite nu exist capete. Pentru gestionarea ei se va folosi un pointer ptr_nod, care adreseaz un nod oarecare al listei, mai precis ultimul introdus (fig.2.6.1.).

Ca i la lista simplu nlnuit, principalele operaii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

tergerea unui nod,

tergerea listei.

Structura unui nod este urmtoarea:

typedef struct tip_nod {

int cheie; /* nu este obligatoriu acest cmp */

cmpuri;

struct tip_nod *urm;

} TIP_NOD;3. Mersul lucrrii

3.1. De la tastatur se citesc cuvinte. S se creeze o list simplu nlnuit ordonat alfabetic, care conine n noduri cuvintele distincte i frecvena lor de apariie. Se va afia coninutul listei n ordine alfabetic.

3.2. S se conceap o structur dinamic eficient pentru reprezentarea n memorie a polinoamelor. Se vor scrie funcii de calcul a sumei, diferenei, produsului i mpririi a dou polinoame.

3.3. S se conceap o structur dinamic eficient pentru reprezentarea matricelor rare. S se scrie operaii de calcul a sumei i produsului a dou matrici rare. Afiarea se va face n form natural.

3.4. De la tastatur se citete numrul n i numele a n copii. S se simuleze urmtorul joc: cei n copii stau ntr-un cerc. ncepnd cu un anumit copil, se numr copiii n sensul acelor de ceasornic. Fiecare al n-lea copil iese din cerc .Ctig ultimul copil rmas n joc.

EMBED PBrush

EMBED PBrush

EMBED Word.Picture.8

_1486802130.doc

simplu nlnuite

Fig. 2.6.1 Modelul listei circulare