Liste

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.