Crearea unei liste
----- ----- -------------
Vom prezenta o varianta recursiva a acestei operatii, si anume vom crea o
lista pornind de la un string. Functia va returna un pointer catre primul element al listei.
#include "list.h"
LISTA creare(char s[])
}
----- ----- ----------------
Numarare si cautare
----- ----- ----------------
Functia recursiva "numara()" numara elementele unei liste
parcurgand fiecare element pana intalneste pointerul NULL. Daca lista este vida, atunci se intoarce 0, altfel numarul de elemente
al listei.
#include "list.h"
int numara(LISTA
head)
Functia recursiva "cauta()" cauta intr-o lista un element. Daca
este gasit acel element, atunci se intoarce un pointer
catre acesta,
altfel se intoarce pointerul NULL.
#include "list.h"
LISTA cauta(DATA c, LISTA
head)
----- ----- ---------------
Inserare si stergere
----- ----- ---------------
Pictural, asta ar arata cam asa (inainte de inserare):
p1
--|
p2--|
|
|
V
V
----- ----- ---- ----- ----- ----
... --->| A | ---|--->|
C | ---|---> ...
----- ----- ---- ----- ----- ----
----- ----- -------
q --->| B | NULL |
----- ----- -------
Dupa inserare, obtinem:
----- ----- ---- ----- ----- ----
... --->| A | |
| | C | ---|--->
...
----------|--- ----- ----- ----
|
^
->----------|----
q --->| B | | |
----- ----- -----
Functia care face acest lucru este:
#include "list.h"
void insert(LISTA p1, LISTA
p2, LISTA q)
Stergerea unui element intr-o lista liniar inlantuita este foarte simpla.
Pictural, avem:
p--|
|
V
----- ----- ----
----- ----- ---- ----- ----- ----
... --->| A
| ---|--->| B
| ---|--->| C
| ---|--> ...
----- ----- ----
----- ----- ---- ----- ----- ----
Instructiunea
q = p -> next;
va implica pointarea lui q catre obiectul care trebuie sters. Obtinem:
p--|
q--|
|
|
V
V
----- ----- ----
----- ----- ---- ----- ----- ----
... --->| A |
---|--->| B | ---|--->| C
| ---|--> ...
----- ----- ----
----- ----- ---- ----- ----- ----
Considerand instructiunea
p -> next = q -> next;
se obtine in memorie
p--|
q--|
|
|
V
V
----- ----- ---- ----- ----- ----
----- ----- ----
... --->| A | |
| | B |
---|--->| C | ---|--> ...
---------|---- ----- ----- -----
----- ----- ----
|
^
|
|
----- ----- --------- ----- -------
Se observa ca elementul B este inaccesibil (adica nu mai apartine
listei), deci nu mai este folosit. Acesta se mai numeste
"garbage" (gunoi). Evident ca ar fi bine
pentru sistem daca s-ar putea elibera aceasta locatie de memorie pentru a putea
fi refolosita. Eliberarea zonei de memorie se face cu functia "free()" din biblioteca standard. Deci,
"free(q)" face disponibila pentru sistem locatia de memorie catre
care pointeaza "q" care a fost alocata mai inainte cu
"malloc()" (sau "calloc()"). Cum "free()" are ca
argument de tip pointer catre "void", rezulta ca "q" poate
fi de orice tip.
In continuare, vom scrie o functie care sterge si elibereaza toate
elementele unei liste.
#include "list.h"
void sterge_lista(LISTA
head)
}
