Structuri dinamice liniare de tip lista

Structuri dinamice liniare de tip lista

Structura a fost introdusa ca fiind o grupa (colectie) ordonata de date care pot fi de tipuri diferite si care au anumite legaturi logice intre ele. Adesea, aceasta grupa de date se repeta de mai multe ori. Se ajunge astfel la notiunea de tablou, ale carui elemente sunt fiecare cate o structura. Tabloul de date definit in acest fel este si el de acest tip nou, pe care il mai numim si tip structurat.

Dupa cum s-a remarcat, in exemplele de pana acum am folosit structuri de tip static. Static se refera la faptul ca tablourile de structuri au dimensiuni predefinite. Termenul structuri de date statice exprima ideea ca putem modifica cu usurinta valorile componentelor dar este foarte dificil sa marim numarul lor peste limita maxima declarata inainte de compilare. Mai mult, prin stergerea unor elemente structura dintr-un tablou de structuri obtinem goluri in tablou, pe care le putem umple numai printr-o gestiune foarte precisa a pozitiilor din tablou. Folosind pointeri la tabloul de structuri, este foarte posibil sa indicam spre un element care a fost sters. Daca dorim o reprezentare contigua in memorie, va trebui sa compactam (sau sa defragmentam) tabloul la fiecare stergere a unui element de tip structura. Mai mult, daca dorim sa schimbam ordinea in care s-au stocat elementele din tablou sau sa inseram intr-o pozitie intermediara un element nou, aceaste operatii devin foarte anevoioase.

Intr-un exemplu anterior am folosit secventa

# define SIZE 100

struct addr addr_info[SIZE];

Rezulta ca am definit un tablou static cu 100 de elemente, cu numele addr_info, la care fiecare element este o structura cu sablonul addr. Daca in aceasta aplicatie, chiar in timpul executiei programului, constatam ca avem nevoie de mai mult de 100 de rezervari de memorie, nu exista nici o posibilitate de a mari tabloul fara a modifica si apoi recompila sursa programului. Tabloul trebuie redeclarat cu o dimansiune mai mare (in cazul nostru prin #define SIZE 200, de exemplu), apoi se recompileaza programul si abia apoi se executa cu succes. Acest lucru prezenta doua inconveniente (vezi [Mocanu, 2001]):

Executia si obtinerea rezultatelor sunt amanate si produc intarzieri pentru modificarea programului sursa, recompilare si reintroducerea datelor care fusesera deja introduse pana in momentul in care s-a constatat necesitatea maririi tabloului.

Este posibil ca programul sursa sa nu fie disponibil.

Eliminarea neajunsurilor prezentate mai sus se face prin implementarea listelor cu ajutorul unor structuri de date dinamice.

Cand apare necesitatea introducerii unui element in lista, se va aloca dinamic spatiu pentru respectivul element, se va crea elementul prin inscrierea informatiilor corespunzatoare si se va lega in lista. Cand un element este scos din lista spatiul de memorie ocupat de acesta va fi eliberat si se vor reface legaturile.

Structurile dinamice se construiesc prin legarea componentelor structurii, numite variabile dinamice. O variabila dinamica ce intra in componenta unor structuri de date dinamice (nod) prezinta in structura sa doua parti:

Partea de informatie (info) ce poate apartine unui tip simplu (int, char, float, double, etc.) conform cu necesitatile problemei.

Partea de legatura (link) ce contine cel putin un pointer de legatura (next) la o alta variabila dinamica, de obicei de acelasi tip, ce realizeaza inlantuirea variabilelor dinamice in structuri de date dinamice.

Dintre structurile de date dinamice, cele mai simple si mai utilizate sunt listele. Lista este o structura liniara, de tipul unui tablou unidimensional (vector), care are un prim element si un ultim element. Celelalte elemente au un predecesor si un succesor. Elementele unei liste se numesc noduri.

La randul lor, listele pot fi grupate in mai multe categorii, cele mai importante fiind listele simplu inlantuite, listele circulare si listele dublu legate.

Principalele operatii care se pot efectua asupra unei liste sunt: crearea listei, adaugare/stergere/modificare au unui element (nod), accesul la un element si stergerea in totalitate a listei.

Lista simplu inlantuita este cel mai simplu tip de lista din punctul de vedere al legarii elementelor: legatura intre elemente este intr-un singur sens, de la primul catre ultimul. Exista un nod pentru care pointerul spre nodul urmator este NULL. Acesta este ultimul nod al listei simplu inlantuite (sau simplu legate). De asemenea, exista un nod spre care nu pointeaza nici un alt nod, acesta fiin primul nod al listei. O lista simplu inlantuita poate fi identificata in mod unic prin primul element al listei. Determinarea ultimului element se poate face prin parcurgerea secventiala a listei pana la intalnirea nodului cu pointerul spre nodul urmator cu valoarea NULL.

Listele circulare sunt un alt tip de liste pentru care relatia de precedenta nu mai este liniara ci ultimul element pointeaza catre primul. Procedurile necesare pentru crearea si utilizarea unei liste circulare sunt extrem de asemanatoare cu cele de la liste liniare, cu singura deosebire ca ultimul element nu are adresa de pointer vid (NULL) ci adresa primului element.

Listele dublu legate sunt utile in rezolvarea unor probleme care necesita parcurgeri frecvente ale structurilor dinamice in ambele sensuri. Ele pot fi privite ca structuri dinamice ce combina doua liste liniare simplu inlantuite ce partajeaza acelasi camp comun info, una fiind imaginea in oglinda a celeilalte.

Pointerul next indica spre urmatorul nod, iar campul previous indica spre campul anterior.

Vom prezenta in continuare modul in care putem proiecta functiile principale care actioneaza asupra unei structuri dinamice. Pentru aceasta vom utiliza doua variabile globale de tip pointer, una care pointeaza spre primul nod al listei iar cealalta spre ultimul nod al listei. Vom denumi aceste variabile first respectiv last. Particularizarile se vor face pe exemplul bazei de date construite anterior.

Tipul unui nod se declara in felul urmator:

Atat la crearea unei liste cat si la inserarea unui nod se va apela functia malloc() pentru a rezerva spatiu de memorie pentru un nod.

Zona alocata prin intermediul functiei malloc() se poate elibera folosind functia free().

Propunem conceperea unui program asemanator cu programul de exploatare a unei baze de date conceput anterior dar care sa foloseasca in locul unui tablou static o lista simplu inlantuita. Programul poate fi extins ulterior pentru structuri dinamice mai complexe, care sa foloseasca liste dublu inlantuite sau circulare.

Programul va avea urmatoarele facilitati:

Crearea unei liste simplu inlantuite in memorie (pentru prima oara).

Exploatarea unei liste simplu inlantuite in memorie:

2.1. Inserarea unor inregistrari (noduri):

a) Inserarea unui nod inaintea primului nod al listei

b) Inserarea unui nod inainte/dupa un nod intern al listei

c) Inserarea unui nod dupa ultimul nod al listei (adaugare la coada listei)

1.2. Stergerea unor inregistrari

a)      Stergerea primului nod al listei

b)      Stergerea unui nod intern al listei

c)      Stergerea ultimului nod al listei

Salvarea din memorie pe disc a unei liste simplu inlantuite

Citirea de pe disc in memorie a bazei de date salvate anterior

Afisarea pe ecran, inregistrare cu inregistrare, a bazei de date continute in lista dinamica.

Programul este prevazut cu o intefata simpla prin care utilizatorul poate alege dintre optiunile pe care le are la dispozitie. Interfata este sub forma unui meniu din care, prin tastarea initialelor comenzilor, acestea se lanseaza in executie.

Vom descrie pe rand functiile care indeplinesc sarcinile enumerate mai sus. Pentru o mai buna proiectare a programului, vom folosi atat modularizarea interna prin construirea mai multor functii cat si o modularizare externa prin izolarea programului principal de restul functiilor care se folosesc.

Exemplu:

Programul principal bd_main.c

# include 'local.h'

void main() }}

Fisierul header local.h este:

# include <stdio.h>

# include <ctype.h>

# include <string.h>

# include <stdlib.h>

typedef struct addr TNOD;

TNOD *first, *last;

FILE *fp;

extern int create_list();

extern char menu();

extern void display_list(), insert(), erase();

extern int loadf_list(), savef_list();

extern TNOD *add_nod();

Cu ajutorul acestui fisier header se realizeaza definirea sablonului structurii addr si apoi, prin comanda typedef, se defineste un nou tip de date numit TNOD. First si last sunt pointeri la structuri de acest tip iar fp este pointer la fisier (file pointer).

Cu extern se definesc prototipurile unor functii care nu se gasesc in fisierul bd_main.c ci in fisierul bd_bib.c unde sunt colectate toate functiile pe care le folosim. Acest fisier are la randul sau un fisier header numit local1.h care contine:

# include <stdio.h>

# include <ctype.h>

# include <string.h>

# include <stdlib.h>

extern FILE *fp;

typedef struct addr TNOD;

extern TNOD *first, *last;

Prin cele doua fisiere header cele doua fisiere sursa bd_main.c si bd_bib.c se pot compila impreuna, rezultand un singur fisier executabil.

Interfata cu utilizatorul

Aceasta consta intr-un meniu principal, care permite accesarea functiilor principale, si din doua submeniuri pentru operatiile de stergere si inserare de inregistrari.

/* Functia menu() principala */

char menu() while (!strrchr('clsdieq',ch));

return tolower(ch); }

//meniu functia de stergere

char menu_del() while (!strrchr('efliq',ch));

return tolower(ch); }

//meniu functia de inserare

char menu_insert() while (!strrchr('fliq',ch));

return tolower(ch); }

Incarcarea bazei de date de pe disc

Baza de date este inregistrata pe disc in fisierul maillist.dat care se creaza la prima salvare a listei dinamice din memorie. Functia loadf_nod() citeste o inregistrare (record) din fisier, returnand 1 in caz de reusita, -1 daca se ajunge la sfarsitul fisierului si 0 in cazul in care exista o eroare de citire de pe disc.

/* Functia loadf_nod() from file*/

int loadf_nod(TNOD *p)

else }

/* Functia loadf_list() from file */

int loadf_list()

while (((p=(TNOD *)malloc(n))!=NULL)&&((i=loadf_nod(p))==1))

if (first==NULL)

else

if (p==NULL)

free(p);return i;}

Functia loadf_list() aloca fiecare inregistrare citita de pe disc unui nod al listei dinamice construite in memorie. In pointerii first si last se stocheaza in permanenta adresele primei si ultimei inregistrari (nod sau structura).

Salvarea bazei de date pe disc

Reprezinta operatiunea inversa celei de citire. Lista simplu inlantuita din memorie se salveaza in intregime pe disc in fisierul maillist.dat. Spre deosebire de functia loadf_list() care apela la functia loadf_nod(), functia savef_list() nu face nici un apel la o alta functie definita de utilizator:

/* Functia savef_list() */

int savef_list()

p=first;

do

p=p->next;} while (p!=NULL);

fclose (fp);return 1;}

Crearea unei liste simple inlantuite

La inceput variabilele first si last au valoarea NULL, lista fiind vida. Crearea unei liste se face prin functia create_list. Ea returneaza 0 pentru eroare si 1 daca operatia reuseste. Prin aceasta functie se initializeaza o lista dinamica in memorie, fara a face o citire a unei baze de date create anterior. Aceasta este prima functie care se apeleaza cand construim o baza de date noua.

/* Functia create_list() new */

void create_list()

else

printf ('Exit? (x): ');

if ((ch=getchar())=='x') break;}

if (p==NULL)}

Afisarea listei dinamice din memorie

Prin aceasta operatie, realizata de functia display_list(), se afiseaza secvential toate inregistrarile continute in nodurile listei pornind de la prima si terminand cu ultima.

// functie de afisare antet

void disp_antet()

// afisare o singura inregistrare (nod)

void disp_nod(TNOD *p)

/* Functia display_list() */

void display_list() while (p!=NULL);

else printf('Lista vida !n');}

Functia display_list() apeleaza la functia disp_nod() care afiseza o singura inregistrare. Daca este nevoie de afisarea unui cap de tabel (antet) se apeleaza la functia disp_antet().

Inserarea unor noduri in lista dinamica

Aceasta operatie presupune introducerea unor noduri (inregistrari) fie la inceputul listei inaintea primului nod, fie la sfarsitul sau (adaugare) dupa ultimul nod, fie intre doua noduri vecine nesituate la extremitati. Functiile listate mai jos realizeaza aceste sarcini.

// functia de inserare

void insert() break;}}

/* Functia insert_last() */

void ins_last() }

/* Functia insert_first() */

void ins_first() }

// inserare dupa inregistrarea afisata

void ins_int()

pi=(TNOD *)malloc(sizeof(TNOD));

pi=add_nod(pi);

pi->next=p->next;

p->next=pi;}

La inserarea unui nod, este nevoie ca acesta sa fie legat de cele intre care se introduce cu ajutorul pointerilor next. Daca se doreste ca nodul inserat sa fie primul sau ultimul din lista, este nevoie sa modificam pointerii globali first si last.

Stergerea unor noduri din lista dinamica

Nodurile pe care dorim sa le stergem pot fi interioare sau se pot afla la extremitati. In acest caz, este nevoie sa modificam pointerii first si last . In toate cazurile este nevoie sa refacem legaturile distruse dupa disparitia prin stergere a unor noduri. tergerea nu este efectiva, ci numai se refac legaturile si se elibereaza cu functia free() zona de memorie alocata in prealabil (prin inserare sau creare) cu functia malloc().

Mai mult, avem optiunea de a sterge intreaga lista din memorie in scopul inlocuirii in totalitate a datelor continute in inregistrari.

// functia de stergere

void erase() break;}}

// se sterge intreaga lista si se elibereaza memoria

void del_list()

first=NULL;last=NULL;}

// sterge prima inregistrare

void del_first() }

// stergere ultima inregistrare

void del_last() }

// stergere inregistrare intermediara

void del_int()

else }}