Metode evoluate de programare Limbajele c şi C++

9. Liste

9.1. Date structurate definite recursiv

Limbajul C permite definirea de tipuri structurate recursiv (autoreferenţiate). Acest lucru se face cu ajutorul pointerilor, şi anume un element al structurii poate să fie un pointer spre tipul de dată introdus prin structura respectivă:
struct nume

{ declaratii

struct nume *p;

declaratii

};
Un tip definit ca mai sus se spune că este un tip autoreferit sau recursiv. O dată structurată declarată printr-un astfel de tip se spune că este autoreferită sau recursivă. Datele structurate recursive au numeroase aplicaţii în prelucrarea listelor înlănţuite şi arborescente.

Două tipuri structurate t1 şi t2 pot să conţină fiecare un pointer spre celalalt. În acest caz se va proceda ca mai jos:

struct t1; // o declaratie inainte fara de care nu se poate

// declara tipul t2

struct t2

{ declaratii

struct t1 *pt1;

declaratii

};

struct t1

{ declaratii

struct t2 *pt2;

declaratii

};

9.2. Liste înlănţuite

Datele structurate se pot organiza în tablouri sau în structuri recursive introducând în tipul structurat unul sau mai mulţi pointeri spre tipul structurat respectiv. Astfel se stabileşte o relaţie de ordine (uneori chiar mai multe) între elementele mulţimii de date structurate; de asemenea, mulţimea rescpectivă se poate organiza în mod dinamic, adăugând elemente noi sau suprimându-le pe cele care nu mai sunt necesare.

Definiţie O mulţime dinamică de structuri recursive de acelaşi tip şi care satisfac una sau mai multe relaţii de ordine introduse prin pointeri se numeşte listă înlănţuită. Elementele listei se mai numesc noduri.

Cele mai utilizate tipuri de listă sunt:

1. 
   lista simplu înlănţuită;
   
2. 
   lista circulară simplu înlănţuită;
   
3. 
   lista dublu înlănţuită;
   
4. 
   lista circulară dublu înlănţuită;.
   

Cele patru tipuri de liste sunt exemplificate grafic astfel:

capul

listă liniară simplu înlănţuită;

capul

listă liniară circulară simplu înlănţuită;
capul
listă liniară dublu înlănţuită;

capul

listă liniară circulară dublu înlănţuită;

9.3. Lista liniară simplu înlănţuită

O listă simplu înlănţuită; este o listă înlănţuită; ale cărei noduri satisfac o singură relaţie de ordine introdusă prin pointeri.

Tipul unui nod dintr-o listă simplu înlănţuită; se poate declara în două moduri:

1. 
   struct tnod
   

{ declaratii

struct tnod *urmator;

declaratii

};

1. 
   typedef struct tnod
   

{ declaratii

struct tnod *urmator;

declaratii

} TNOD;
Observaţii

1^o. Varianta b) este mai folosită.

2^o. Pointerul următor introduce o relaţie de ordine între nodurile de tip TNOD.

3^o. Ultimul nod al listei va avea pointerul urmator = NULL.

4^o. Pentru nodurile interioare ale listei pointerul urmator va avea valori adrese; dacă urmator din nodul a pointează spre nodul b, spunem că nodul b este succesorul lui a.

Operaţiile ce se pot efectua asupra unei liste simplu înlănţuită;

1. 
   crearea listei;
   
2. 
   accesul la un nod al listei;
   
3. 
   inserarea unui nod înlănţuită;
   
4. 
   ştergerea unui nod dintr-o listă;
   
5. 
   ştergerea unei liste.
   

Memorarea listelor se poate face:

1. 
   dinamic (în memoria internă);
   
2. 
   static (în fişiere).
   

Pentru modul dinamic se va folosi funcţia malloc la crearea listei cât şi la inserarea de noduri, iar la ştergerea de noduri funcţia free.

9.4. Crearea şi afişarea unei liste

Vom crea o listă ce conţine în noduri informaţii despre numere întregi şi pătratele lor. Avem două funcţii: una de creare care întoarce adresa capului listei şi o funcţie de afişare a informaţiei din noduri. Vom comenta instrucţiunile importante din program.

#include

#include

typedef struct nod // definirea tipului NOD

{ int nr;

int patrat;

struct nod* leg;

} NOD;

NOD *creaza(void) // functia de creare, intoarce adresa capului

{ NOD *cap,*p,*pc;

int i,lung;

printf("\n\n\n\ creare lista simplu inlantuita\n\n");

lung = sizeof(NOD);

pc=(NOD *)malloc(lung); // pc este un pointer curent, in el se vor pune adresel noi

cap=pc;

printf("dati informatia elementului : ");

scanf ("%d",&i);

while (i>0) // crearea listei se termina la numar negativ

{ p=pc; // pointer ce pastreaza adresa noua

p->nr=i; // incarcarea informatiei

p->patrat=i*i;

pc=(NOD *)malloc(lung); // se cere o noua adresa de memorie

p->leg=pc; // se leaga pointerul leg la noua adresa

printf("dati informatia elementului : ");

scanf ("%d",&i);

}

p->leg=NULL; // ultimul nod al listei are pointerul leg = NULL

free(pc); // eliberarea ultimei adrese care de fapt nu face parte din lista

return cap; // returneaza adresa capului listei

}
void afisare(NOD *p) // functia de afisare a listei

{

while (p != NULL) // cat timp n-am ajuns la ultimul nod

{ printf ("\n numarul %d si patratul sau %d", p->nr,p->patrat);

p=p->leg; // trecerea la urmatorul nod al listei

}

}
void main (void) // functia principala

{ NOD *capul;

clrscr();

capul=creaza(); // lista e cunoscuta prin adresa capului

afisare(capul);

getch();

}