1

III. STRUCTURI DE DATE

21. LISTE

O lista liniara este o structura de date omogena si secventiala (o secventa de articole)

realizata din elementele unei multimi specifice unei aplicatii. Cea mai utilizata forma de

reprezentare este lista simplu inlantuita.

Exemplu. Se considera lista formata din elementele a1, a2, a3, a4, a5 (in aceasta ordine).

Reprezentarea elementelor sub forma unei liste simplu inlantuite:

START

Lista poate fi accesata numai cu primul element indicat de START (inceputul listei). Fiecare element

al listei are doua componente: informatia utila ak (cheia) si legatura catre elementul urmator.

Ultimul element, in campul legatura contine o informatie speciala pentru sfarsit de lista.

Cu listele se pot realiza operatii, cele mai comune fiind:

-adaugarea unui nou element intr-o lista;

-stergerea unui element dintr-o lista;

-modificarea unui element (modificarea informatiei utile);

-determinarea lungimii unei liste;

-cautarea unui element care indeplineste un anumit criteriu;

-concatenarea si interclasarea a doua liste intr-o singura noua lista;

-separarea unei liste in doua subliste pe baza unui anumit criteriu.

Exista doua mari categorii de solutii pentru implementarea listelor: implementari statice si

implementari dinamice.

Implementare statica

O solutie statica de implementare a unei liste simplu inlantuite utilizeaza doi vectori: un

vector pentru memorarea informatiei utile (CHEIA) si un vector pentru memorarea legaturilor dintre

elemente (LEGATURA). Pentru exemplul precedent de lista simplu inlantuita formata din cinci

elemente cei doi vectori au urmatorul continut:

CHEIA LEGATURA

Elementul de tablou CHEIA[0] nu are nicio semnificatie, dar LEGATURA[0] are ca valoare indicele

de tablou unde se gaseste primul element al listei a1 (deci rolul variabilei START), in cazul

exemplului, 2. CHEIA[2] contine informatia utila pentru primul element al listei, iar

LEGATURA[2] indica locatia unde se gaseste elementul urmator al listei, a2, etc. Pentru ultimul

element, a5 din locatia 4, LEGATURA[4] are o valoare speciala, 0, deoarece acesta este ultimul

element al listei.

0 - 2

1 a3 3

2 a1 5

3 a4 4

4 a5 0

5 a2 1

a1 a2 a3 a4 a5 ·

2

In continuare se prezinta pentru aceasta solutie statica de implementare a unei liste doua

operatii de baza: inserarea unui nou element in lista si eliminarea unui element. Aceste doua operatii

se realizeaza in legatura cu un vector de locatii libere, LIBER, in care se pastreaza indicii

elementelor neutilizate din cei doi vectori CHEIA si LEGATURA. Parcurgerea informatiilor din

vectorul LIBER se face cu variabila INDLIB: la inserarea unui nou element in lista se consuma un

element din vectorul LIBER, din pozitia indicata de INDLIB, care apoi se decrementeaza, respectiv

la stergerea unui element din lista se elibereaza cate o locatie din cei doi vectori CHEIA si

LEGATURA, indicele locatiei fiind memorat in vectorul LIBER in pozitia obtinuta prin

incrementarea variabilei INDLIB.

Algoritmii de inserare si stergere sunt prezentati in pseudocod. In cadrul algoritmului de

inserare, inserarea noului element ELEM se face dupa elementul din pozitia POZ.

functia inserare (ELEM, POZ)

daca (INDLIB ≥ 0)

CHEIA[LIBER[INDLIB]]=ELEM

LEGATURA[LIBER[INDLIB]]=LEGATURA[POZ]

LEGATURA[POZ]=LIBER[INDLIB]

INDLIB=INDLIB-1

intoarce adevarat // succes

altfel

intoarce fals // esec

Algoritmul de eliminare elimina elementul urmator dupa elementul din locatia I.

functia eliminare (I)

INDLIB=INDLIB+1

LIBER[INDLIB]=LEGATURA[I]

LEGATURA[I]=LEGATURA[LEGATURA[I]]

O alta solutie statica de implementare a unei liste simplu inlantuite utilizeaza variabile

dinamice si pointeri. Gestionarea listei se face cu trei variabile intregi continand indicii locatiilor de

inceput, curent si sfarsit. Lista propriu zisa este reprezentata printr-un tablou de pointeri, in ordinea

normala din lista. Fiecare pointer indica cate o variabila dinamica continand informatia utila cu

structura corespunzatoare aplicatiei.

informatia utila

inceput curent sfarsit

elementele listei

3

In unele aplicatii se utilizeaza si liste dublu inlantuite, care pot fi parcurse in ambele sensuri,

fie inainte, incepand cu primul element, fie inapoi, incepand cu ultimul element.

Exemplu. Se considera lista formata din elementele a1, a2, a3, a4, a5 (in aceasta ordine).

Reprezentarea elementelor sub forma unei liste dublu inlantuite:

START

STOP

Lista poate fi parcursa inainte incepand cu primul element indicat de START (inceputul listei).

Fiecare element al listei are trei campuri: informatia utila (CHEIA), legatura inainte (URMATOR) si

legatura inapoi (PRECEDENT). Ultimul element, in campul legatura inainte contine o informatie

speciala pentru sfarsit de lista. Lista poate fi parcursa inapoi incepand cu ultimul element indicat de

STOP. Cei trei vectori utilizati pentru implementarea statica a acestei liste duble inlantuite au

urmatorul continut:

CHEIA URMATOR PRECEDENT

Implementare dinamica

Solutiile de implementare dinamica utilizeaza variabile dinamice si pointeri:

inceput curent sfarsit

legat

pinf

informatia

utila

Lista este gestionata cu ajutorul a trei pointeri indicand primul element, elementul curent si

ultimul element (acest pointer poate sa lipseasca). Fiecare element al listei contine doua campuri: un

pointer catre elementul urmator (legat) si un pointer catre informatia utila (pinf). Informatia utila

este reprezentata printr-un set de variabile dinamice cu o structura specifica aplicatiei.

0 - 2 4

1 a3 3 5

2 a1 5 0

3 a4 4 1

4 a5 0 3

5 a2 1 2

a1 a2 a3 a4 a5 · ·

·

4

Aplicatie. Lista simplu inlantuita implementata dinamic, reprezentand un sir de numere

intregi ordonate crescator. S-a optat pentru urmatoarea solutie de implementare dinamica: start

legat

cheia

Fiecare element al listei contine doua campuri: informatia utila cheia (un numar intreg) si un pointer

legat pentru legatura la elementul urmator.

#include <iostream.h>

#include <conio.h>

typedef struct element{

int cheia;

struct element *legat;

} ;

element *start;

void inser (int e) {

element *s, *t, *u;

u=new element;

u->cheia=e;

if(start==NULL) {

u->legat=NULL; //inserare in lista vida

start=u;

}

else

if (e<=start->cheia) {

u->legat=start; //inserare in I pozitie

start=u;

}

else {

t=start;

while ((e>t->cheia)&&(t->legat!=NULL)) {

s=t;

t=t->legat;

}

if ((e>t->cheia)&&(t->legat==NULL)) {

u->legat=NULL; //inserare pe ultima pozitie

t->legat=u;

}

else {

s->legat=u; //inserare pe o pozitie oarecare

u->legat=t;

}

}

}

void elimin (int e) {

element *s, *t;

t=start;

if (t==NULL)

cout<<"Nu se poate elimina din lista vida!\n";

else

if (e==t->cheia) {

·

5

start=t->legat; //elimina primul element

delete t;

}

else {

while ((e!=t->cheia)&&(t->legat!=NULL)){

s=t;

t=s->legat;

}

if (e==t->cheia) {

s->legat=t->legat; //elimina element oarecare

delete t; //sau elimina ultimul element

}

else

cout<<e<<" nu exista in sir"<<endl;

}

}

void main (void) {

int n,i,e1;

element *p;

char cda;

cout<<"Introduceti numarul initial de elemente:";

cin>>n;

for (i=1; i<=n; i++) {

cout<<"Elementul "<<i<<':';

cin>>e1;

inser(e1);

}

do {

cout<<"\nSirul este:\n";

p=start;

while (p!=NULL){

cout<<p->cheia<<' ';

p=p->legat;

}

cout<<"\nIntroduceti comanda (i/e/g):";

cda=getche();

switch (cda) {

case 'i':

cout<<"\nIntroduceti elementul de inserat:";

cin>>e1;

inser(e1);

break;

case 'e':

cout<<"\nIntroduceti elementul de eliminat:";

cin>>e1;

elimin(e1);

}

}

while(cda!='g');

}

O solutie de implementare dinamica a unei liste dublu inlantuite este prezentata in figura

urmatoare:

6

inceput curent sfarsit

urm

prec

pinf

informatia utila

Un caz particular de lista inlantuita este lista circulara in care este realizata legatura intre

primul si ultimul element. Un exemplu de lista circulara dublu inlantuita este prezentat in figura

urmatoare:

inceput curent

urm

prec

pinf

informatia utila

·

·