Limbajul de Programare C - Liste

Liste

O lista este o colectie de elemente de informatie (noduri) aranjate intr-o anumita ordine. Lungimea unei liste este numarul de noduri din lista. Structura corespunzatoare de date trebuie sa ne permita sa determinam efficient care este primul/ultimul nod in structura si care este predecesorul/succesorul (daca exista) unui nod dat. Limbaju C ofera posibilitati de implementare a acestor structure atat static cat si dinamic.

Operatiile curente care se fac in liste sunt: inserarea unui nod, stergerea (extragerea) unui nod, concatenarea unor liste, numararea elementelor unei liste etc.

Implementarea unei liste se poate face in principal in doua moduri:

• Implementarea secventiala, in locatii successive de memorie, conform ordinii nodurilor in lista. Avantajele acestei tehnici sunt accesul rapid la predecesorul/succesorul unui nod si gasirea rapida a primului/ultimului nod. Dezavantajele sunt ca nu se foloseste intreaga memorie alocata listei.

• Implementarea inlantuita. Fiecare nod contine doua parti: informatia propriu-zisa si adresa nodului succesor. Alocarea memoriei fiecarui nod se poate face in mod dinamic, in timpul rularii programului. Accesul la un nod necesita parcurgerea tuturor predecesorilor sai, ceea ce poate lua ceva mai mult timp. Inserarea/stergerea unui nod este, in schimb, foarte rapida.

Listele se pot clasifica dupa numarul de legaturi in:

• liste simple

• liste duble

• liste circulare

O lista simpla are o singura legatura, legatura ultimului element este adresa NIL/NULL. Pentru a accesa lista avem nevoie de o variabila care sa pastreze adresa primului element (cap sau prim). O lista dubla are doua legaturi: legatura de tip urmator si legatura de tip precedent sau anterior. O lista circular este o lista in care, dupa ultimul nod, urmeaza primul, deci fiecare nod are succesor si predecessor.

Listele se pot clasifica dupa locul in care se fac operatiile de adaugare/eliminare astfel:

• stive

• cozi

Liste dublu inlantuite in Limbajul C.

O lista dublu inlantuita, spre deosebire de lista simplu inlantuita, presupune realizarea inlantuirii componentelor sale in ambele sensuri, de la prima component spre ultima si invers, de la ultima component spre prima component. In acest sens, in fiecare component, trebuie prevazute doua adrese de inlantuire (2 pointeri), una care sa precizeze adresa urmatoarei component din lista, si alta care sa precizeze adresa componentei anterioare, ca in exemplul urmator:

struct tipstudent

{

int matricol;

char nume[15]

char prenume[15];

float nota1;

float nota2;

float media;

struct tipstudent *urmator;

struct tipstudent *anterior;

}

var_student, primul_student, ultimul_student;

Tipul de date de mai sus declara structure recursive, in ambele sensuri, datorita campurilor “urmator” si “anterior”, care furnizeaza adresa urmatoarei component (nod), respective adresa componentei anterioare, si care nu sunt altceva decat pointeri spre structure de date de tipul celei din care fac parte insusi campurile respective (“urmator” si “anterior”).

In cazul listelor dublu inlantuite campul “urmator”, pentru ultimul nod, are valoarea nula NULL iar campul “anterior” pentru primul nod are, de asemenea, valoarea nula NULL.