III. STRUCTURI DE DATE - Facultatea de Stiinte Aplicate · PDF file1 III. STRUCTURI DE DATE...
Click here to load reader
Transcript of III. STRUCTURI DE DATE - Facultatea de Stiinte Aplicate · PDF file1 III. STRUCTURI DE DATE...
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
·
·