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