3.liste
DESCRIPTION
sdaTRANSCRIPT
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