Lista simplu inlantuita

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

Nota. Ca structura si elemente de baza, programul Dublu_Lista este asemanator programului Dinamic_Lista.

//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.