LISTA - Exemple de liste, stergerea si adaugarea in lista

Lista

Exemple de liste se intalnesc destul de des in practica prelucrarii datelor pe calculator. Iata cateva: lista studentilor dintr-o grupa si a notelor primite la un examen, lista cartilor dintr-o biblioteca, lista clientilor unei banci, lista cadrelor didactice dintr-o catedra etc.

Putem defini lista ca o colectie omogena, secventiala de date.

In continuare vom prezenta cele doua variante de implementare a listelor in calculator: varianta statica si varianta dinamica.

Varianta statica presupune memorarea elementelor listei intr-un tablou; ordinea elementelor listei este data de ordinea elementelor tabloului.

//Static_Lista

# include 'stdio.h'

# include 'conio.h'

const max_aloc=20;

int lista[max_aloc];

int i,n,k;

char ch;

int x;

int Creare()

return 1;

}

int InsertEl(int k,int x)

else

return 0;

int StergEl(int k)

else

return 0;

void Listare()

void main(void)

while (n<0);

if (Creare())

Listare();

else

printf('nDimensiune alocare lista insuficienta');

break;

case 'I':

do

while ((k<1)&&(k>n+1));

printf('nDati valoare care se va insera=');

scanf('%d',&x);

if (InsertEl(k,x))

printf('nS-a inserat elementul %d pe pozitia %d',x,k);

else

break;

case 'S':

if (n>0)

while ((k<1)&&(k>n));

if (StergEl(k))

printf('nA fost sters elemetul de pe pozitia %d',k);

}

else

printf('nLista este vida!');

break;

case 'L':

Listare();

getch();

break;

case 'E':

break;

default:

printf('nIntroduceti alta litera!');

getch();

}

clrscr();

}

while (ch!='E');

Se observa ca operatiile de insertie/stergere ale unui element in/din lista implica deplasari cu o pozitie spre dreapta/stanga a subsirului intre pozitiile k si n. Grafic, lucrurile se prezinta astfel:

(a)

(b)

Operatii de insertie (a), stergere (b)

Aceste deplasari (care consuma timp calculator) precum si necesitatea de a alege o dimensiune optima de alocare, diminueaza principalul avantaj oferit de implementarea statica a listei: evidentierea naturala a succesiunii elementelor sale.

Varianta dinamica presupune memorarea elementelor listei in spatii de memorie gestionate cu ajutorul pointerilor. Astfel, un element din lista se va reprezenta intr-o structura (celula) cu mai multe campuri: o parte din camp contine informatia propriu-zisa (partea utila), iar cealalta parte adresa elementului urmator sau/si a elementului precedent din lista. Daca lista este organizata intr-o singura directie (de exemplu, stanga-dreapta) spunem ca lista este simplu inlantuita. Grafic, o lista simplu inlantuita cu patru elemente se poate reprezenta sub forma:

Lista simplu inlantuita

l reprezinta adresa primului element din lista, sagetile sugereaza pointerul spre urmatoarea celula, punctul din ultima celula specifica sfarsitul listei (valoarea nil-pointer spre orice tip de date).

Prin meniul programului se activeaza cele patru proceduri care au acelasi nume si aceleasi functii ca si in cazul static.

//Dinamic_Lista

# include 'stdio.h'

# include 'conio.h'

# include 'alloc.h'

const max_aloc=50;

struct pstruct

;

typedef struct pstruct PSTRUCT;

PSTRUCT *l,*p,*q;

int i,n,k;

char ch;

int x;

int Creare()

return 1;

}

int InsertEl(int k,int x)

else //adaugare la inceput

p->util=x;

n++;

return 1;

}

else

return 0;

int StergEl(int k)

else//stergere orice element diferit de primul

free(p);

n--;

return 1;

void Listare()

void main(void)

while (n<0);

if (Creare())

Listare();

else

printf('nDimensiune alocare lista insuficienta');

break;

case 'I':

do

while ((k<0)&&(k>n));

printf('nDati valoare care se va insera=');

scanf('%d',&x);

if (InsertEl(k,x))

printf('nS-a inserat elementul %d pe pozitia %d',x,k);

else

break;

case 'S':

if (n>0)

while ((k<1)&&(k>n));

if (StergEl(k))

printf('nA fost sters elemetul de pe pozitia %d',k);

}

else

printf('nLista este vida!');

break;

case 'L':

Listare();

getch();

break;

case 'E':

break;

default:

printf('nIntroduceti alta litera!');

getch();

}

clrscr();

}

while (ch!='E');

Operatiile de insertie si stergere presupun evidentierea distincta a urmatoarelor cazuri: adaugare la inceput, insertie propriu-zisa sau adaugare la sfarsit (insertie); stergere prim element, stegere orice element din lista diferit de primul (stergere).

Operatii de insertie:

adaugare la inceput:

Insertie (adaugare la inceput)

insertie propriu-zisa sau adaugare la sfarsit:

Insertie propriu-zisa sau adaugare la sfarsit

Operatii de stergere:

stergere prim element;

Stergerea primului element din lista

stergere orice element din lista diferit de primul:

Stergerea oricarui element din lista diferit de primul

In cazul listelor simplu inlantuite cunoscand adresa unei celule putem cunoaste adresa celulei imediat urmatoare, in timp ce adresa celulei precedente nu este accesibila cu aceeasi rapiditate. Se poate obtine aceeasi rapiditate in parcurgerea unei liste la stanga sau la dreapta unui element adaugand fiecarei celule inca un camp de legatura; acest camp va contine adresa celulei precedente, cand exista, iar in caz contrar valoarea NIL. Se obtine astfel o lista dublu inlantuita. Grafic, o astfel de lista cu trei elemente se poate reprezenta ca mai jos:

Lista dublu inlantuita

//Dublu_Lista

# include 'stdio.h'

# include 'conio.h'

# include 'alloc.h'

const max_aloc=50;

struct pstruct

;

typedef struct pstruct PSTRUCT;

PSTRUCT *l,*p,*q;

int i,n,k;

char ch;

int x;

int Creare()

if (l!=NULL)

l->prec=NULL;

return 1;

}

int InsertEl(int k,int x)

else

if (k==0) //adaugarea la inceput

else //insertie propriu-zisa sau adaugare la sfarsit

p->util=x;

n++;

return 1;

}

else

return 0;

int StergEl(int k)

else

else

}

}

free(p);

n--;

return 1;

void Listare()

getch();

void main(void)

while (n<0);

if (Creare())

Listare();

else

printf('nDimensiune alocare lista insuficienta');

break;

case 'I':

do

while ((k<0)&&(k>n));

printf('nDati valoare care se va insera=');

scanf('%d',&x);

if (InsertEl(k,x)==1)

else

break;

case 'S':

if (n>0)

while ((k<1)&&(k>n));

if (StergEl(k))

}

else

break;

case 'L':

Listare();

break;

case 'E':

break;

default:

printf('nIntroduceti alta litera!');

getch();

}

clrscr();

}

while (ch!='E');

Operatiile de insertie si stergere presupun evidentierea distincta a urmatoarelor cazuri: adaugare in lista vida, nevida (insertie); stergere unic element, prim element, ultim element, orice element aflat in interiorul listei (stergere).

Operatii de insertie:

adaugare in lista vida:

Adaugare in lista vida

adaugare in lista nevida:

adaugare la inceput:

Adaugare la inceput

insertie propriu-zisa sau adaugare la sfarsit:

Insertie propriu-zisa

Adaugare la sfarsit

Operatii de stergere:

stergere unic element din lista;

Stergere unic element

stergere prim element din lista;

Stergere prim element

stergere ultim element din lista;

Stergere ultim element

stergere orice element aflat in interiorul listei.

Stergere orice element

Usurinta cu care se realizeaza in variantele de implementare dinamica operatiile de adaugare si stergere este evidenta. De altfel, acest lucru reprezinta principalul avantaj al implementarii dinamice a listei; pretul platit consta in necesarul suplimentar de memorie pentru reprezentarea legaturilor dintre elementele sale.7