Link.RO
11.3. Lista circulara simplu inlantuita (LCSI)
2020/03/02 in Programare in C
In paragraful 11.1. s-a definit lista simplu inlantuita ca o multime ordonata de noduri, fiecare nod continand un pointer spre un alt nod al listei, numit urmatorul nodului respectiv, exceptand un singur nod, care nu mai are urmator. Acest nod, care nu mai are urmator, constituie un capat al listei simplu inlantuite. Tot acolo, am convenit ca spre acest nod sa pointeze variabila ultim. De asemenea, lista simplu inlantuita contine un nod care nu mai este urmatorul niciunui alt nod al ei. Acest nod constituie celalalt capat al listei si spre el pointeaza variabila prim.
Pointerul prezent in fiecare nod al listei care defineste ordinea nodurilor a fost numit urm.
Conform celor spuse mai sus, ultim -> urm = 0.
Daca intr-o LSI schimbam valoarea expresiei in modul urmator: ultim -> urm = prim, atunci LSI devine o
lista simplu inlantuita circulara (LCSI).
Procesul de transformare a LSI in LCSI este shematizat in figura de mai jos:
Intr-o LCSI toate nodurile sunt echivalente - fiecare nod are un urmator si fiecare nod este urmatorul unui nod. Intr-o astfel de lista nu mai sunt capete si de aceea nu mai sunt necesare variabilele prim si ultim. Gestiunea nodurilor LCSI se realizeaza folosind o variabila globala care pointeaza spre un nod oarecare al listei. Numim ptrnod aceasta variabila. Ea se declara astfel:
TNOD *ptrnod;unde:
| TNOD | este tipul comun nodurilor listei. |
Asupra LCSI se definesc aceleasi operatii ca si asupra LSI.
LCSI au o serie de aplicatii, printre care amintim:
- operatii cu numere intregi care au un numar mare de cifre;
- operatii asupra polinoamelor de una sau mai multe variabile;
- alocarea dinamica a memoriei.
Important:
Trebuie mentionat ca functiile malloc, free precum si celelalte utilizate la gestiunea dinamica a memoriei utilizeaza o zona de memorie organizata ca o LCSI.
Memoria libera este o lista circulara de noduri, fiecare cu o zona de memorie libera. Un nod contine:
- dimennsiunea lui;
- un pointer spre nodul urmator din lista;
- spatiul liber care se pune la dispozitia utilizatorului.
Alocarea se face astfel:
La un apel al lui malloc se parcurg nodurile listei pana cand se gaseste o zona de memorie de dimensiune cel putin egala cu cea ceruta la apel. Daca zona este mai mare, atunci ea se divide si partea neutilizata se inlantuie cu celelalte blocuri ale listei. Cand nu se gaseste o zona de memorie corespunzatoare, atunci se incearca obtinerea ei printr-un apel la sistemul de operare.
Eliberarea unei zone de memorie prin intermediul functiei free va inlantui zona respectiva in lista circulara. Daca doua noduri cu zone de memorie libere ocupa zone contigue, atunci ele se concateneaza formand o singura zona libera de dimensiune egala cu suma dimensiunilor lor. De aceea, se recomanda utilizarea functiei free pentru a elibera zone de memorie de indata ce nu mai este nevoie de ele. In felul acesta se poate preintampina divizarea excesiva a zonei gestionata dinamic prin functiile de felul malloc si free.
In continuare sunt definite functii pentru a realiza operatiile de baza asupra LCSI.