LISTE

LISTE

9.1. DATE STRUCTURATE DEFINITE RECURSIV

Limbajul C permite definirea de tipuri structurate recursiv (autoreferentiate). Acest lucru se face cu ajutorul pointerilor, si anume un element al structurii poate sa fie un pointer spre tipul de data introdus prin structura respectiva:

struct nume

;

Un tip definit ca mai sus se spune ca este un tip autoreferit sau recursiv. O data structurata declarata printr-un astfel de tip se spune ca este autoreferita sau recursiva. Datele structurate recursive au numeroase aplicatii în prelucrarea listelor înlantuite si arborescente.

Doua tipuri structurate t1 si t2 pot sa contina 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

;

struct t1

;

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 multi pointeri spre tipul structurat respectiv. Astfel se stabileste o relatie de ordine (uneori chiar mai multe) între elementele multimii de date structurate; de asemenea, multimea rescpectiva se poate organiza în mod dinamic, adaugând elemente noi sau suprimându-le pe cele care nu mai sunt necesare.

Definitie O multime dinamica de structuri recursive de acelasi tip si care satisfac una sau mai multe relatii de ordine introduse prin pointeri se numeste lista înlantuita. Elementele listei se mai numesc noduri.

Cele mai utilizate tipuri de lista sunt:

lista simplu înlantuita;

lista circulara simplu înlantuita;

lista dublu înlantuita;

lista circulara dublu înlantuita;.

Cele patru tipuri de liste sunt exemplificate grafic astfel:

capul

lista liniara simplu înlantuita;

capul

lista liniara circulara simplu înlantuita;

capul

lista liniara dublu înlantuita;

capul

lista liniara circulara dublu înlantuita;

9.3. LISTA LINIARĂ SIMPLU ÎNLĂNŢUITĂ

O lista simplu înlantuita; este o lista înlantuita; ale carei noduri satisfac o singura relatie de ordine introdusa prin pointeri.

Tipul unui nod dintr-o lista simplu înlantuita; se poate declara în doua moduri:

struct tnod

typedef struct tnod

TNOD;

Observatii

1^o. Varianta b) este mai folosita.

2^o. Pointerul urmator introduce o relatie 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; daca urmator din nodul a pointeaza spre nodul b, spunem ca nodul b este succesorul lui a.

Operatiile ce se pot efectua asupra unei liste simplu înlantuita;

crearea listei;

accesul la un nod al listei;

inserarea unui nod înlantuita;

stergerea unui nod dintr-o lista;

stergerea unei liste.

Memorarea listelor se poate face:

dinamic (în memoria interna);

static (în fisiere).

Pentru modul dinamic se va folosi functia malloc la crearea listei cât si la inserarea de noduri, iar la stergerea de noduri functia free.

9.4. CREAREA sI AFIsAREA UNEI LISTE

Vom crea o lista ce contine în noduri informatii despre numere întregi si patratele lor. Avem doua functii: una de creare care întoarce adresa capului listei si o functie de afisare a informatiei din noduri. Vom comenta instructiunile importante din program.

#include <stdio.h>

#include <alloc.h>

typedef struct nod // definirea tipului NOD

NOD;

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

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

void main (void) // functia principala