>> Inapoi <<
=========
Capitolul 13
=========
====================
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
{
int numar;
char culoare;
};
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
{
char nume[15];
int calorii;
}
struct leguma
{
char nume[15];
int calorii;
}
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
{
int numar;
char culoare;
} 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
{
char *nume;
int nr_student;
float medie;
} 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
{
char *nume;
int nr_student;
float medie;
};
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
{
char *nume;
int nr_student;
float medie;
};
In alt fisier, scriem
#include "cl_info.h"
void main()
{
struct student temp, clasa[NR_STUDENTI];
. . . . .
}
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[])
{
int i, contor = 0;
for (i = 0; i < NR_STUDENTI; ++i)
contor += clasa[i].medie == 4.00;
return contor;
}
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
{
char *nume;
int nr_student;
float medie;
};
struct data
{
short zi;
char luna[10];
short an;
};
struct persoana
{
char nume[20];
struct data zi_nastere;
};
struct date_student
{
struct persoana p;
int nr_student;
float medie[NR_CURSURI];
};
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)
{
printf("Dati ziua(int) luna(string) an(int): ");
scanf("%hd%s%hd", &z -> zi, z -> luna, &z -> an);
}
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 = {12, 't'};
----------- struct complex
{
double real;
double imaginar;
} m[3][3] =
{
{{1.0, -0.5}, {2.5, 1.0}, {0.7, 0.7}},
{{7.0, -6.5}, {-0.5,1.5},{45.7,8.0}},
};
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
{
int data;
struct lista *urmator;
}
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
&ls;stdio.h> 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
{
DATA d;
struct lista_inlantuita *next;
};
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[])
{
LISTA head;
if (s[0] == '\0')
return NULL;
else
{
head = (LISTA) malloc(sizeof(ELEMENT));
head -> d = s[0];
head -> next = creare(s + 1);
return head;
}
}
--------------------------
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)
{
if (head == NULL)
return 0
else
return (1 + numara(head -> next));
}
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)
{
if (head == NULL)
return NULL;
else
if (c == head -> d)
return head;
else
return (cauta(c, head -> next));
}
-------------------------
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)
{
p1 -> next = q;
q -> next = p2;
}
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)
{
if (head != NULL)
{
sterge_lista(head -> next);
free(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).