Structuri si liste inlantuite

Structuri si liste inlantuite

Tipul structura permite programatorului sa imbine mai multe componente intr-o singura variabila. Componentele structurii au nume distincte si se numesc membrii. Membrii unei structuri pot avea tipuri diferite. Deci, ca si pointerii si sirurile, structurile sunt considerate un tip derivat. Accesarea membrilor unei structuri se face cu '.' sau cu '->' care au cea mai inalta prioritate (ca si () si []).

Declararea structurilor

Se face folosind cuvantul rezervat 'struct'. Iata un exemplu de declarare a cartilor de joc:

Exemplu: Declaratia de mai jos creaza tipul de data 'carte_de_joc':

struct carte_de_joc
;
Astfel cartea 3 de trefla va avea 'numar=3' si 'culoare='t''. Celelalte caractere pentru culorile cartilor sunt (frunza - 'f', caro - 'c', inima - 'i'). Numele structurii poate fi folosit acum pentru declararea variabilelor de acest tip. Abia in acest moment se rezerva loc in memorie pentru aceste variabile:
struct carte_de_joc c1, c2;
Pentru accesarea membrilor lui c1 si c2, folosim operatorul '.'.

Exemplu:

c1.numar = 3;
c1.culoare = 't';
c2.numar = 12;
c2.culoare = 'c';
O constructie de forma
variabila_structura . nume_membru
este folosita ca o variabila in acelasi mod ca o simpla variabila sau ca un element al unui sir. Numele unui membru trebuie sa fie unic intr-o structura specificata. Din moment ce membrii trebuie intotdeauna prefixati de un identificator de variabila de structura
unic, atunci nu vor fi confuzii (ambiguitati) intre doi membri cu acelasi nume, dar din structuri diferite.

Exemplu:

struct fruct


struct leguma


struct fruct a;
struct leguma b;

Putem accesa 'a.calorii', respectiv 'b.calorii' fara ambiguitate. Putem declara variabile de un tip structurat in timpul declararii acestuia.

Exemplu:

struct carte_de_joc
c1, c2, c3[52];
Identificatorul 'carte_de_joc' este numele structurii. Identificatorii 'c1' si 'c2' se declara ca fiind variabile de tip 'struct carte_de_joc', iar identificatorul 'c3' ca fiind un sir de tip 'struct carte_de_joc'. Daca insa lipseste numele structurii, atunci singura data cand se pot declara variabile de tip structura este in momentul declararii acesteia.

Exemplu:

struct
s1, s2, s3;
In aceasta structura se declara trei variabile de tip structura, insa lipsind numele structurii inseamna ca nu se mai pot declara si alte
variabile de acest tip. Daca, de exemplu, scriem
struct student
;
atunci 'student' este numele structurii si nu sunt variabile declarate in acest moment. Acum putem scrie
struct student temp, clasa[100];
si declaram 'temp' si 'clasa' de tip 'struct student'.

Accesarea unui membru

In cele ce urmeaza, prezentam un exemplu de folosire a operatorului de membru '.'.

Exemplu: In fisierul 'cl_info.h' scriem:

#define NR_STUDENTI 100
struct student
;
In alt fisier, scriem
#include 'cl_info.h'
void main()

Putem avea instructiuni de asignare cum ar fi:
temp.medie = 4.00;
temp.nume = 'Ionescu';
temp.nr_student = 1023;
In continuare, scriem o functie care numara studentii cu media 4.00:
int esec(struct student clasa[])

C pune la dispozitie operatorul pointer catre structura -> pentru accesarea membrilor unei structuri relativ la un pointer (Simbolul -> este format din caracterul - (minus) si > (mai mare)). Daca o variabila pointer este asignata cu adresa unei structuri, atunci un membru al structurii poate fi accesat printr-o constructie de forma:
pointer_catre_structura -> nume_membru
Bineinteles, o constructie echivalenta este:
(*pointer_catre_structura).nume_membru
Parantezele sunt necesare deoarece operatorii '.' si '->' au prioritate mare si se asociaza de la stanga la dreapta. Astfel, parantezele sunt obligatorii, deoarece in caz contrar, daca in expresia de mai sus nu ar fi fost paranteze, atunci aceasta ar fi echivalenta cu
*(pointer_catre_structura.nume_membru)

Exemplu: Fie urmatoarele declaratii si asignari:

struct student temp, *p = &temp;
temp.medie = 10.00;
temp.nume = 'Ionescu';
temp.nr_student = 1204;
Atunci obtinem urmatorul tabel:

| Expresie | Expresie echivalenta | Valoare conceptuala |

| temp.medie | p -> medie | 10.00 |
| temp.nume | p -> nume | Ionescu |
| temp.nr_student | p -> nr_student | 1204 |
| (*p).nr_student | p -> nr_student | 1204 |


Asociativitatea si precedenta operatorilor (tabelul complet)


Operatori | Asociativitate |

() [] . -> ++ (postfix) -- (postfix) | de la stanga la dreapta |

++ (prefix) -- (prefix) ! ~ sizeof (tip) | de la dreapta |
+ (unar) - (unar) & (adresa) * (dereferentiere) | la stanga |

* / % | de la stanga la dreapta |

+ - | de la stanga la dreapta |

<< >> | de la stanga la dreapta |

< <= > >= | de la stanga la dreapta |

== != | de la stanga la dreapta |

& | de la stanga la dreapta |

^ | de la stanga la dreapta |

| | de la stanga la dreapta |

&& | de la stanga la dreapta |

|| | de la stanga la dreapta |

?: | de la dreapta la stanga |

= += -= *= /= %= >>= <<= &= ^= |= | de la dreapta la stanga |

, (operatorul virgula) | de la stanga la dreapta |

Operatorul ',' are cea mai mica prioritate dintre toti operatorii C. Virgula folosita in declaratii si in lista de argumente ale functiilor nu este operator.

Exemple: Expresia a = 1, b = 2 este o expresie virgula. Intai se evalueaza 'a = 1', apoi 'b = 2', iar valoarea si tipul returnat de ----- ----- ---- expresia virgula sunt cele returnate de 'b = 2', adica valoarea '2' si tipul 'int'.
Un exemplu frecvent unde apare operatorul virgula este 'for'. De exemplu,
for (i = 0, j = 1; i < LIMIT; i += 2, j +=2)

Va amintiti ca operatorul unar 'sizeof' poate fi folosit pentru determinarea numarului de octeti necesar memorarii sale. De exemplu, expresia sizeof(struct carte_de_joc) va intoarce numarul de octeti necesari sistemului pentru memorarea unei variabile de tip 'struct carte_de_joc'. Pe cele mai multe sisteme tipul returnat de expresie este 'unsigned'.

Structuri, functii si asignari

C traditional permite unui pointer catre un tip structura sa fie transmis ca argument al unei functii si returnat ca o valoare. ANSI C
permite chiar unei structuri sa fie trimisa ca argument pentru functii si returnata ca valoare. De exemplu, daca 'a' si 'b' sunt structuri, atunci expresia de asignare 'a = b' este valida. Aceasta implica ca fiecare valoare a unui membru din structura 'a' devine
egala cu valoarea membrului corespunzator din structura 'b'.
In C, structurile, pointerii si vectorii pot fi combinati pentru crearea unor structuri de date complicate.

Exemplu: Baza de date cu studenti

In fisierul 'student.h':

#define NR_STUDENTI 50
#define NR_CURSURI 10

struct student


struct data


struct persoana


struct date_student

Observati ca 'struct date_student' este construita cu structuri imbricate. De exemplu, daca avem declaratia:
struct date_student temp;
atunci expresia:
temp.p.zi_nastere.luna[0]
are ca valoare prima litera a lunii datei de nastere a studentului asociat lui 'temp'.
In continuare, vom scrie o functie 'citeste_date()' pentru a introduce date in variabile de tip 'struct date'. La apelul functiei, trebuie trimisa adresa variabilei ca argument.

Exemplu:

#include 'student.h'

void citeste_date(struct data *z)


Formatul %hd este folosit pentru conversia caracterelor de la tastatura la o valoare de tip 'short'.

Intrebare: De ce 'z -> luna' nu contine operatorul de adresa ?

Functia 'citeste_date()' poate fi folosita pentru citirea informatiei intr-o variabila de tip 'struct date_student' astfel:

struct date_student temp;

citeste_date(&temp.p.zi_nastere);

Initializarea structurilor

Toate variabilele externe si statice, inclusiv variabilele de structura, care nu sunt explicit initializate, sunt automat initializate de catre sistem cu zero. In C traditional, structurile statice si externe pot fi initializate de catre programator. In ANSI C, putem initializa si structuri definite 'auto'. Sintaxa este similara celei folosite la siruri. O variabila structura poate fi urmata de semnul '=' si o lista de constante cuprinse intre acolade. Daca nu sunt suficiente valori pentru asignarea lor, atunci membrii ramasi sunt asignati cu zero implicit.

Exemple: struct carte_de_joc c = ;
----------- struct complex
m[3][3] =



Se observa imediat ca linia 'm[2][]' este initializata cu 0.

Folosirea lui 'typedef'

Facilitatea 'typedef' este deseori folosita pentru redenumirea unui tip structura.

Exemple:

typedef char * string;
typedef int lungime;
typedef float vector[10];
typedef double (*PFD)(double);
Dupa aceste redenumiri, putem face declaratiile:
lungime l1, l2;
string s1 = 'abc', s2 = 'xyz';
vector x;
Aceste declaratii sunt echivalente cu:
int l1, l2;
char * s1 = 'abc', s2 = 'xyz';
float x[10]; /* Atentie ! Se inlocuieste vector cu x */
La fel, declaratia
PFD f;
este echivalenta cu
double (*f)(double);
Este vorba mai sus de un pointer la o functie ce returneaza tipul 'double'.

Structuri recursive (self-referential)

O structura este recursiva daca un membru pointer se refera la tipul structurii initiale (recursie de ordinul 1, exista si ordine mai
mari). De obicei, structurile recursive necesita rutine explicite pentru rezervarea si eliberarea de memorie.

Exemplu:

struct lista

Fiecare variabila de tip 'struct lista' are doi membri, 'data' si 'urmator'. Pictural, asta arata cam asa (in memorie):
----- ----- ----
| | ----|-->
----- ----- ----
data urmator
Variabila pointer 'urmator' contine o adresa a unei locatii de memorie a unui element succesor 'struct lista' sau valoarea speciala
NULL, definita in ca avand valoarea constanta 0. Valoarea NULL este folosita pentru notarea sfarsitului listei.
Presupunem ca avem declaratiile
struct lista a, b, c;
Vrem sa creeam o lista inlantuita formata din aceste trei variabile. Mai intai, facem asignarile:
a.data = 1;
b.data = 2;
c.data = 3;
a.urmator = b.urmator = c.urmator = NULL;
Dupa aceste instructiuni, obtinem in memorie:
a b c

| 1 | NULL | | 2 | NULL | | 3 | NULL |

data urmator data urmator data urmator
Acum putem 'lega' cele trei structuri, astfel:
a.urmator = &b;
b.urmator = &c;
Obtinem:
a b c

| 1 | ---|---->| 2 | ---|---->| 3 | NULL |

data urmator data urmator data urmator

Liste liniar inlantuite

O lista liniar inlantuita este o structura de date ce are elementele legate secvential. Exista un pointer catre primul element al listei,
fiecare element al listei pointeaza catre urmatorul element al listei, avand ultimul element pointand catre NULL. De obicei, o lista
inlantuita se creaza dinamic.
Scriem in fisierul 'header' intitulat 'list.h' urmatoarele declaratii:
#include
typedef char DATA;

struct lista_inlantuita
;

typedef struct lista_inlantuita ELEMENT;
typedef ELEMENT * LISTA;
Relativ la alocarea dinamica, va reamintim ca functia 'malloc()' are un singur argument de tip 'size_t' si intoarce un pointer catre
'void' care pointeaza catre adresa de baza a spatiului de memorie alocat (evident, cauta spatiu suficient pentru un obiect). Astfel,
daca 'head' este o variabila de tip 'LISTA', atunci
head = (LISTA) malloc(sizeof(ELEMENT));
va produce o bucata din memorie menita sa memoreze un ELEMENT asignand adresa de baza pointerului 'head'.

Exemplu:

Presupunem ca vrem sa creeam dinamic o lista liniar inlantuita pentru memorarea a trei caractere 'n', 'e' si 'w'. Considerand
head = (LISTA) malloc(sizeof(ELEMENT));
head -> d = 'n';
head -> next = NULL;
obtinem un memorie ceva de genul:
----- ----- ------
head --->| 'n' | NULL |

d next
Al doilea element este adaugat de instructiunile:
head -> next = (LISTA) malloc(sizeof(ELEMENT));
head -> next -> d = 'e';
head -> next -> next = NULL;
In memorie avem:
------------ ----- ----- -----
head--->| 'n' | ---|--->| 'e' | NULL |
------------ ----- ----- -----
d next d next
In sfarsit, adaugam si al treilea element:
head -> next -> next = malloc(sizeof(ELEMENT));
head -> next -> next -> d = 'w';
head -> next -> next -> next = NULL;
In memorie avem:
----- ----- ---- ----- ----- ---- ----- ----- ------
head--->| 'n' | ---|--->| 'e' | ---|--->| 'w' | NULL |
----- ----- ---- ----- ----- ---- ----- ----- ------
d next d next d next

Operatii pentru liste

Operatiile de baza pentru liste liniar inlantuite includ urmatoarele:
1. Crearea unei liste
2. Numararea elementelor unei liste
3. Cautarea unui element
4. Inserarea unui element
5. Stergerea unui element

Crearea unei liste

Vom prezenta o varianta recursiva a acestei operatii, si anume vom crea o lista pornind de la un string. Functia va returna un pointer catre primul element al listei.
#include 'list.h'

LISTA creare(char s[])



Numarare si cautare

Functia recursiva 'numara()' numara elementele unei liste parcurgand fiecare element pana intalneste pointerul NULL. Daca lista este vida, atunci se intoarce 0, altfel numarul de elemente al listei.
#include 'list.h'

int numara(LISTA head)

Functia recursiva 'cauta()' cauta intr-o lista un element. Daca este gasit acel element, atunci se intoarce un pointer catre acesta,
altfel se intoarce pointerul NULL.
#include 'list.h'

LISTA cauta(DATA c, LISTA head)


Inserare si stergere

Pictural, asta ar arata cam asa (inainte de inserare):

p1 --| p2--|
| |
V V
----- ----- ---- ----- ----- ----
--->| A | ---|--->| C | ---|--->
----- ----- ---- ----- ----- ----
----- ----- -------
q --->| B | NULL |

Dupa inserare, obtinem:

--->| A | | | | C | ---|--->

| ^
->----------|----
q --->| B | | |
----- ----- -----
Functia care face acest lucru este:
#include 'list.h'
void insert(LISTA p1, LISTA p2, LISTA q)

Stergerea unui element intr-o lista liniar inlantuita este foarte simpla. Pictural, avem:
p--|

V
----- ----- ---- ----- ----- ---- ----- ----- ----
--->| A | ---|--->| B | ---|--->| C | ---|-->
----- ----- ---- ----- ----- ---- ----- ----- ----
Instructiunea
q = p -> next;
va implica pointarea lui q catre obiectul care trebuie sters. Obtinem:
p--| q--|
| |
V V

--->| A | ---|--->| B | ---|--->| C | ---|-->

Considerand instructiunea
p -> next = q -> next;
se obtine in memorie
p--| q--|

V V

--->| A | | | | B | ---|--->| C | ---|-->


| |

Se observa ca elementul B este inaccesibil (adica nu mai apartine listei), deci nu mai este folosit. Acesta se mai numeste 'garbage' (gunoi). Evident ca ar fi bine pentru sistem daca s-ar putea elibera aceasta locatie de memorie pentru a putea fi refolosita. Eliberarea zonei de memorie se face cu functia 'free()' din biblioteca standard. Deci, 'free(q)' face disponibila pentru sistem locatia de memorie catre care pointeaza 'q' care a fost alocata mai inainte cu 'malloc()' (sau 'calloc()'). Cum 'free()' are ca argument de tip pointer catre 'void', rezulta ca 'q' poate fi de orice tip.
In continuare, vom scrie o functie care sterge si elibereaza toate elementele unei liste.
#include 'list.h'
void sterge_lista(LISTA head)



Exercitii propuse spre implementare

1. Scrieti un program C pentru simularea unui joc de carti. Sa se faca o amestecare si o impartire a cartilor la cei n jucatori.
2. Folosind 'typedef', sa se scrie trei functii C care sa calculeze suma a doi vectori, produsul scalar a doi vectori si inmultirea
matricelor.
3. (Operatii cu liste)
a) Concatenarea a doua liste;
b) Determinarea unei subliste ce contine primele k elemente dintr-o lista, cu eliberarea zonelor de memorie ale restului elementelor.
4. Sa se oglindeasca o lista liniara inlantuita cu numar constant de variabile suplimentare fara a folosi recursie.
5. Sa se sorteze n numere folosind liste liniar inlantuite si metoda interclasarii.
6. Scrieti un program C in care sa descrieti urmatoarele operatii pentru arbori binari: creare, numarare, cautare, stergere, inserare, parcurgere (preordine, inordine, postordine).
7. Scrieti un program C in care sa descrieti aceleasi operatii de mai sus, dar pentru arbori generali (idee: folositi legaturi de tip fiu-frate).