Extras din curs
1. Introducere
Lista este o multime dinamica, întelegând prin aceasta faptul ca ea are un numar variabil de
elemente.
La început lista este o multime vida. În procesul executiei programului se pot adauga elemente noi
listei si totodata pot fi eliminate diferite elemente din lista.
* Elementele unei liste sunt date de acelasi tip. Tipul comun elementelor unei liste este un tip utilizator. =>
Elementele unei liste sunt structuri de acelasi tip.
* De multe ori listele sunt organizate sub forma de tablou. Acest lucru nu este eficient deoarece listele sunt
dinamice, iar tablourile din limbajul C nu sunt dinamice.
* Exista situatii în care este dificil de a evalua numarul maxim al elementelor unei liste, precum si cazuri cand
numarul lor difera de la executie la executie. => Apare problema de a organi-za o astfel de multime de tip
lista.
Ordonarea elementelor unei liste se face cu ajutorul pointerilor care intra in compunerea elementelor
listei. Datorita acestor pointeri, elementele listei devin structuri recursive. Listele organizate in acest fel
se numesc liste inlantuite.
Prin definitie, o multime dinamica de structuri recursive de acelasi tip, pentru care sunt definite
una sau mai multe relatii de ordine cu ajutorul unor pointeri din compunerea structurilor respective,
se numeste lista inlantuita.
Elementele unei liste se numesc noduri.
Daca intre nodurile unei liste exista o singura relatie de ordine, atunci lista se numeste simplu
inlantuita. In mod analog, lista este dublu inlantuita daca intre nodurile ei sunt definite doua relatii de ordine.
O lista este n-inlantuita daca intre nodurile ei sunt defi-nite n relatii de ordine.
Operatii ce tin de o lista inlantuita:
a) crearea listei inlantuite;
b) accesul la un nod oarecare al listei;
c) inserarea unui nod intr-o lista inlantuita;
d) stergerea unui nod dintr-o lista inlantuita;
e) stergerea unei liste inlantuite.
STRUCTURI DE DATE SI ALGORITMI LABORATOR 1
- 2 -
2. Lista simplu inlantuita
Intre nodurile listei simplu inlantuite avem
o singura relatie de ordonare. Exista un singur
nod care nu mai are succe-sor si un singur nod
care nu mai are predecesor. Aceste noduri
formeaza capetele listei.
Vom utiliza doi pointeri spre cele doua
capete pe care ii notam cu:
prim - pointerul spre nodul care
nu are predecesor
ultim - pointerul spre nodul care
nu are succesor.
Pointerul urm defineste relatia de succesor
pentru nodurile listei. Pentru fiecare nod, el
are ca valoare adresa nodului urmator din lista.
Exceptie face nodul spre care pointeaza varia-bila
ultim (pentru care urm ia valoarea zero).
3. Lista dublu inlantuita
Intr-o astfel de lista fiecare nod contine
doi pointeri: unul spre nodul urmator si unul spre
nodul precedent. Astfel fiecare nod al listei are un
nod precedent definit prin pointerul prec si un nod
urmator definit prin pointerul urm.
<- ultim
DATE
urm
DATE
urm
DATE
prim
0 urm
0
urm
prec
prim -->
urm
prec
urm
prec
0 urm
prec
ultim -->
STRUCTURI DE DATE SI ALGORITMI LABORATOR 1
- 3 -
4. Crearea unei liste simplu inlantuite
La crearea unei liste simplu inlantuite se realizeaza urma-toarele:
a) Se initializeaza pointerii prim si ultim cu valoarea zero, deoarece la inceput lista este vida.
b) Se rezerva zona de memorie in memoria heap pentru nodul cu-rent.
c) Se incarca nodul curent cu datele curente, daca exista si apoi se trece la pasul d). Altfel lista este creata si
se revine din functie.
Preview document
Conținut arhivă zip
- Liste
- SDA_L1 - lista.pdf
- SDA_L1_Sch_Log_corectat.bmp