Noi te platim pentru timpul acordat , o postare , like , vizualizare subiect , sau creare subiect , insemna castig.
Suntem comunitatea unica din Romania care plateste pentru efortul depus . Ideile ,opiniile tale conteaza si sunt platite doar la noi.

Structuri şi reuniuni

Structuri şi reuniuni

Solus

Membru
Staff member
Fondator BitArena
Moderator
Utilizator
Joined
Jul 6, 2018
Messages
523
Reaction score
94
Points
26
Location
Bucuresti
Website
www.bitarena.eu

Reputation:

O structură este o colecţie de una sau mai multe variabile, de acelaşi tip sau de tipuri diferite, grupate împreună sub un singur nume pentru a putea fi tratate împreună (în alte limbaje, structurile se numesc articole).
Structurile ajută la organizarea datelor complicate, în special în programele mari, deoarece permit unui grup de variabile legate să fie tratate ca o singură entitate. Vom ilustra în acest capitol modul de utilizare a structurilor.

Elemente de bază

Să revenim asupra rutinei de conversie a datei prezentată în capitolul 9.
O dată constă din zi, lună şi an, eventual numărul zilei din an şi numele lunii. Aceste cinci variabile pot fi grupate într-o singură structură astfel:

struct date {
int day;
int month;
int year;
int yearday;
char mon_name[4];
};

Cuvîntul cheie struct introduce o declaraţie de structură care este o listă de declaraţii închise în acolade.
Cuvîntul struct poate fi urmat opţional de un nume, numit marcaj de structură sau etichetă de structură, cum este în exemplul nostru numele date. Acest marcaj denumeşte acest tip de structură şi poate fi folosit în continuare ca o prescurtare pentru declaraţia de structură detaliată căreia îi este asociat.
Elementele sau variabilele menţionate într-o structură se numesc membri ai structurii. Un membru al structurii sau o etichetă şi o variabilă oarecare, nemembru, pot avea acelaşi nume fără a genera conflicte, deoarece ele vor fi întotdeauna deosebite una de alta din context.
Acolada dreaptă care încheie o listă de membri ai unei structuri poate fi urmată de o listă de variabile, la fel ca şi în cazul tipurilor de bază. De exemplu:
struct {. . .} x,y,z;
este din punct de vedere sintactic analog cu:
int x,y,z;
în sensul că fiecare declaraţie declară pe x, y şi z ca variabile de tipul numit (structură în primul caz şi întreg în al doilea) şi cauzează alocarea de spaţiu pentru ele.
O declaraţie de structură care nu este urmată de o listă de variabile nu alocă memorie; ea descrie numai un şablon, o formă de structură. Dacă structura este marcată sau etichetată, atunci marcajul ei poate fi folosit mai tîrziu pentru definirea unor alte variabile de tip structură, cu acelaşi şablon ca structura marcată. De exemplu, fiind dată declaraţia:
struct date d;
ea defineşte variabila d, ca o structură de acelaşi fel (şablon) ca structura date.
O structură externă sau statică poate fi iniţializată, ataşînd după definiţia ei o listă de iniţializatori pentru componente, de exemplu:
struct date d = {4,7,1984,185,"iulie"};
Un membru al unei structuri este referit printr-o expresie de forma:
nume-structură.membru
în care operatorul membru de structură ’.’ leagă numele membrului de numele structurii. Ca exemplu fie atribuirea:

leap = (d.year%4==0) && (d.year%100!=0)
|| (d.year%400==0);

sau verificarea numelui lunii:
if (strcmp(d.mon_name,"august")==0) ...

Structurile pot fi imbricate; o înregistrare de stat de plată, de exemplu, poate fi de următoarea formă:

struct person {
char name[NAMESIZE];
char address[ADRSIZE];
long zipcode;
long ss_number;
double salary;
struct date birthdate;
struct date hiredate;
};

Structura person conţine două structuri de şablon date. Declaraţia:
struct person emp;
defineşte şi alocă o structură cu numele emp de acelaşi şablon ca şi person. Atunci:
emp.birthdate.month
se referă la luna de naştere. Operatorul de membru de structură ’.’ este asociativ de la stînga la dreapta.

Structuri şi funcţii

Există un număr de restricţii asupra structurilor în limbajul C. Singurele operaţii care se pot aplica unei structuri sînt accesul la un membru al structurii şi considerarea adresei ei cu ajutorul operatorului &. Acest lucru implică faptul că structurile nu pot fi atribuite sau copiate ca entităţi şi că ele nu pot fi transmise ca argumente la funcţii şi nici returnate din funcţii. Structurile de clasă automatic, ca şi masivele de aceeaşi clasă, nu pot fi iniţializate; pot fi iniţializate numai structurile externe şi statice, regulile de iniţializare fiind aceleaşi ca pentru masive.
Pointerii la structuri nu se supun însă acestor restricţii, motiv pentru care structurile şi funcţiile pot coexista şi conlucra prin intermediul pointerilor.
Ca un exemplu, să rescriem programul de conversie a datei, care calculează ziua anului, din lună şi zi.

day_of_year(struct date *pd) {
/* calculul zilei anului */
int i, day, leap;
day = pd->day;
leap = (pd->year%4==0) &&
(pd->year%100!==0) ||
(pd->year%400==0);
for (i=1; i<pd->month; i++)
day += day_tab[leap];
return day;
}


Declaraţia:
struct date * pd;
indică faptul că pd este un pointer la o structură de şablonul lui date. Notaţia:
pd->year
indică faptul că se referă membrul "year" al acestei structuri. În general, dacă p este un pointer la o structură p->membru-structură se referă la un membru particular (operatorul ’->’ se formează din semnul minus urmat de semnul mai mare).
Deoarece pd este pointer la o structură, membrul year poate fi de asemenea referit prin:
(*pd).year
Notaţia "->" se impune ca un mod convenabil de prescurtare. În notaţia (*pd).year, parantezele sînt necesare deoarece precedenţa operatorului membru de structură ’.’ este mai mare decît cea a operatorului *.
Ambii operatori ’.’ şi ’->’ sînt asociativi de la stînga la dreapta, astfel încît:
p->q->membru
emp.birthdate.month
sînt de fapt:
(p->q)->membru
(emp.birthdate).month
Operatorii ’->’ şi ’.’ ai structurilor, împreună cu () pentru listele de argumente şi [] pentru indexare se găsesc în vîrful listei de precedenţă (vezi secţiunea 4.16), fiind din acest punct de vedere foarte apropiaţi. Astfel, fiind dată declaraţia:
struct {
int x;
int *y;} *p;
unde p este un pointer la o structură, atunci expresia:
++p->x
incrementează pe x, nu pointerul p, deoarece operatorul ’->’ are o precedenţă mai mare decît ’++’. Parantezele pot fi folosite pentru a modifica ordinea operatorilor dată de precedenţa. Astfel:
(++p)->x
incrementează mai întîi pe p şi apoi accesează elementul x, din structura nou pointată.
În expresia (p++)->x se accesează mai întîi x, apoi se incrementează pointerul p.
În mod analog, *p->y indică conţinutul adresei pe care o indică y. Expresia *p->y++ accesează mai întîi ceea ce indică y şi apoi incrementează pe y. Expresia (*p->y)++ incrementează ceea ce indică y. Expresia *p++->y accesează ceea ce indică y şi apoi incrementează pointerul p.


Masive de structuri

Structurile sînt în mod special utile pentru tratarea masivelor de variabile legate prin context. Pentru exemplificare vom considera un program care numără intrările fiecărui cuvînt cheie dintr-un text. Pentru aceasta avem nevoie de un masiv de şiruri de caractere, pentru păstrarea numelor cuvintelor cheie şi un masiv de întregi pentru a memora numărul apariţiilor. O posibilitate este de a folosi două masive paralele keyword şi keycount declarate prin:
char *keyword[NKEYS];
int keycount[NKEYS];
respectiv unul de pointeri la şiruri de caractere şi celălalt de întregi. Fiecărui cuvînt cheie îi corespunde perechea:
char *keyword;
int keycount;
astfel încît putem considera cele două masive ca fiind un masiv de perechi. Atunci, declaraţia de structură:


struct key {
char *keyword;
int keycount;
} keytab[NKEYS];


defineşte un masiv keytab de structuri de acest tip şi alocă memorie pentru ele. Fiecare element al masivului keytab este o structură de acelaşi şablon ca şi structura key.
Definiţia masivului keytab poate fi scrisă şi sub forma:


struct key {
char *keyword;
int keycount;
};
struct key keytab[NKEYS];


Deoarece masivul de structuri keytab conţine, în cazul nostru, o mulţime constantă de cuvinte cheie, este mai uşor de iniţializat o dată pentru totdeauna chiar în locul unde este definit. Iniţializarea structurilor este o operaţie analoagă cu iniţializarea unui masiv în sensul că definiţia este urmată de o listă de iniţializatori închişi în acolade.
Atunci iniţializarea masivului de structuri keytab va fi următoarea:


struct key {
char * keyword;
int keycount;
} keytab[] = {
"break",0,
"case",0,
"char",0,
/* ... */
"while",0};


Iniţializatorii sînt perechi care corespund la membrii structurii. Iniţializarea ar putea fi făcută şi incluzînd iniţializatorii fiecărei structuri din masiv în acolade ca în:
{"break",0},{"case",0}....
dar parantezele interioare nu sînt necesare dacă iniţializatorii sînt variabile simple sau şiruri de caractere şi dacă toţi iniţializatorii sînt prezenţi.
Compilatorul va calcula, pe baza iniţializatorilor, dimensiunea masivului de structuri keytab motiv pentru care, la iniţializare, nu este necesară indicarea dimensiunii masivului.
Programul de numărare a cuvintelor cheie începe cu definirea masivului de structuri keytab. Rutina principală main citeşte textul de la intrare prin apel repetat la o funcţie getword, care extrage din intrare cîte un cuvînt la un apel. Fiecare cuvînt este apoi căutat în tabelul keytab cu ajutorul unei funcţii de căutare binary, descrisă în secţiunea 7.5. Lista cuvintelor cheie trebuie să fie în ordine crescătoare pentru ca funcţia binary să lucreze corect. Dacă cuvîntul cercetat este un cuvînt cheie atunci funcţia binary returnează numărul de ordine al cuvîntului în tabelul cuvintelor cheie, altfel returnează -1.


#define MAXWORD 20

binary(char *word, struct key tab[],
int n) {
int low,high,mid,cond;
low = 0;
high = n - 1;
while (low<=high) {
mid =(low + high) / 2;
if (
(cond=strcmp(word,tab[mid].keyword))
<0)
high = mid - 1;
else
if (cond>0) low = mid + 1;
else
return mid;
}
return -1;
}


main() { /* numără cuvintele cheie */
int n,t;
char word[MAXWORD];
while ((t=getword(word,MAXWORD))!=EOF)
if (t==LETTER)
if (
(n=binary(word,keytab,NKEYS))
>=0)
keytab[n].keycount++;
for (n=0; n<NKEYS; n++)
if (keytab[n].keycount>0)
printf("%4d %s\n",
keytab[n].keycount,
keytab[n].keyword);
}


Înainte de a scrie funcţia getword este suficient să spunem că ea returnează constanta simbolică LETTER de fiecare dată cînd găseşte un cuvînt în textul de intrare şi copiază cuvîntul în primul ei argument.
Cantitatea NKEYS este numărul cuvintelor cheie din keytab (dimensiunea masivului de structuri). Deşi putem calcula acest număr manual, este mai simplu şi mai sigur s-o facem cu calculatorul, mai ales dacă lista cuvintelor cheie este supusă modificărilor. O posibilitate de a calcula NKEYS cu calculatorul este de a termina lista iniţializatorilor cu un pointer NULL şi apoi prin ciclare pe keytab să detectăm sfîrşitul lui. Acest lucru este mai mult decît necesar deoarece dimensiunea masivului de structuri este perfect determinată în momentul compilării. Numărul de intrări se determină împărţind dimensiunea masivului la dimensiunea structurii key.
Operatorul sizeof descris în secţiunea 4.2 furnizează dimensiunea în octeţi a argumentului său.
În cazul nostru, numărul cuvintelor cheie este dimensiunea masivului keytab împărţită la dimensiunea unui element de masiv. Acest calcul este făcut într-o linie #define pentru a da o valoare identificatorului NKEYS:
#define NKEYS (sizeof(keytab) /
sizeof(struct key))
Să revenim acum la funcţia getword. Programul pe care-l vom da pentru această funcţie este mai general decît este necesar în aplicaţia noastră, dar nu este mult mai complicat.
Funcţia getword citeşte cuvîntul următor din textul de intrare, printr-un cuvînt înţelegîndu-se fie un şir de litere şi cifre, cu primul caracter literă, fie un singur caracter. Funcţia returnează constanta simbolică LETTER dacă a găsit un cuvînt, EOF dacă a detectat sfîrşitul fişierului sau caracterul însuşi, dacă el nu a fost alfabetic.


getword(char *w, int lim) { /* citeşte un cuvînt */
int t;
while (--lim>0) {
t = type(*w++=getchar());
if (t==EOF)
return EOF;
if (t!=LETTER && t!=DIGIT)
break;
}
*(w-1) = '\0';
return LETTER;
}


Funcţia getword apelează funcţia type pentru identificarea tipului fiecărui caracter citit la intrare cu ajutorul funcţiei getchar. Versiunea funcţiei type pentru caractere ASCII este:

type(int c) { /* returnează tipul caracterului */
if (c>='a' && c<='z' || c>='A' && c<='Z')
return LETTER;
if (c>='0' && c<='9')
return DIGIT;
return c;
}


Constantele simbolice LETTER şi DIGIT pot avea orice valoare care nu vine în contradicţie cu caracterele nealfabetice şi EOF. Valori posibile pot fi:
#define LETTER 'a'
#define DIGIT '0'


Pointeri la structuri

Pentru a ilustra modul de corelare dintre pointeri şi masivele de structuri, să rescriem programul de numărare a cuvintelor cheie dintr-un text, de data aceasta folosind pointeri, în loc de indici de masiv.
Declaraţia externă a masivului de structuri keytab nu necesită modificări, în timp ce funcţiile main şi binary da. Prezentăm, în continuare, aceste funcţii modificate.


#define MAXWORD 20

struct key *binary(char *word, struct key
tab[], int n) {
/* caută cuvînt */
int cond;
struct key * low;
struct key *high;
struct key *mid;
low = &tab[0];
high = &tab[n-1];
while (low<=high) {
mid = low + (high-low) / 2;
if ((cond=strcmp(word,mid->keyword))<0)
high = mid - 1;
else if (cond>0)
low = mid + 1;
else return mid;
}
return NULL;
}


main() { /* numără cuvintele cheie, versiune cu pointeri */
int t;
char word[MAXWORD];
struct key *binary(), *p;
while ((t=getword(word.MAXWORD))!=EOF)
if (t==LETTER)
if ((p=binary(word,keytab,NKEYS))
!= NULL)
p->keycount++;
for (p=keytab; p<keytab+NKEYS; p++)
if (p->keycount>0)
printf("%4d %s\n",p->keycount,
p->keyword);
}


Să observăm cîteva lucruri importante în acest exemplu. În primul rînd, declaraţia funcţiei binary trebuie să indice că ea returnează un pointer la o structură de acelaşi şablon cu structura key, în loc de un întreg. Acest lucru este declarat atît în funcţia principală main cît şi în funcţia binary. Dacă binary găseşte un cuvînt în structura key, atunci returnează un pointer la el; dacă nu-1 găseşte, returnează NULL. În funcţie de aceste două valori returnate, funcţia main semnalează găsirea cuvîntului prin incrementarea cîmpului keycount corespunzător cuvîntului sau citeşte următorul cuvînt.
În al doilea rînd, toate operaţiile de acces la elementele masivului de structuri keytab se fac prin intermediul pointerilor. Acest lucru determină o modificare semnificativă în funcţia binary. Calculul elementului mijlociu nu se mai poate face simplu prin:
mid = (low + high) / 2
deoarece adunarea a doi pointeri este o operaţie ilegală, nedefinită. Această instrucţiune trebuie modificată în:
mid = low + (high-low) / 2
care face ca mid să pointeze elementul de la jumătatea distanţei dintre low şi high.
Să mai observăm iniţializarea pointerilor low şi high, care este perfect legală, deoarece este posibilă iniţializarea unui pointer cu o adresă a unui element deja definit.
În funcţia main avem următorul ciclu:
for(p=keytab; p<keytab+NKEYS; p++)...
Dacă p este un pointer la un masiv de structuri, orice operaţie asupra lui p ţine cont de dimensiunea unei structuri, astfel încît p++ incrementează pointerul p la următoarea structură din masiv, adunînd la pdimensiunea corespunzătoare a unei structuri. Acest lucru nu înseamnă că dimensiunea structurii este egală cu suma dimensiunilor membrilor ei deoarece din cerinţe de aliniere a unor membri se pot genera „goluri” într-o structură.
În sfîrşit, cînd o funcţie returnează un tip complicat şi are o listă complicată de argumente, ca în:
struct key *binary(char *word, struct key
tab, int n)
funcţia poate fi mai greu vizibilă şi detectabilă cu un editor de texte. Din acest motiv, se poate opta şi pentru următoarea formă:
struct key *binary(word,tab,n)
char *word; struct key tab; int n;
unde înainte de acolada de deschidere se precizează tipul fiecărui parametru.
Alegeţi forma care vă convine şi care vi se pare mai sugestivă.


Structuri auto-referite

Să considerăm problema mai generală, a numărului apariţiilor tuturor cuvintelor dintr-un text de intrare. Deoarece lista cuvintelor nu este cunoscută dinainte, n-o putem sorta folosind algoritmul de căutare binară, ca în paragraful precedent. Nu putem utiliza nici o căutare liniară pentru fiecare cuvînt, pe măsura apariţiei lui pentru a vedea dacă a mai fost prezent sau nu, pentru că timpul de execuţie al programelor ar creşte pătratic cu numărul cuvintelor de la intrare.
Un mod de a organiza datele pentru a lucra eficient cu o listă de cuvinte arbitrare este de a păstra mulţimea de cuvinte, tot timpul sortată, plasînd fiecare nou cuvînt din intrare pe o poziţie corespunzătoare, relativ la intrările anterioare. Dacă am realiza acest lucru prin deplasarea cuvintelor într-un masiv liniar, programul ar dura, de asemenea, foarte mult. De aceea, pentru rezolvarea eficientă a acestei probleme vom folosi o structură de date numită arbore binar.
Fiecare nod al arborelui va reprezenta un cuvînt distinct din intrare şi va conţine următoarea informaţie:
- un pointer la cuvînt;
- un contor pentru numărul de apariţii;
- un pointer la descendentul stîng al cuvîntului;
- un pointer la descendentul drept al cuvîntului. Nici un nod al arborelui nu va avea mai mult decît doi descendenţi dar poate avea un descendent sau chiar nici unul.
Arborele se construieşte astfel încît pentru orice nod, sub-arborele stîng al său conţine numai cuvintele care sînt mai mici decît cuvîntul din nod, iar sub-arborele drept conţine numai cuvinte, care sînt mai mari decît cuvîntul din nod, compararea făcîndu-se din punct de vedere lexicografic.
Pentru a şti dacă un cuvînt nou din intrare există deja în arbore se porneşte de la nodul rădăcină şi se compară noul cuvînt cu cuvîntul memorat în nodul rădăcină. Dacă ele coincid se incrementează contorul de numărare a apariţiilor pentru nodul rădăcină şi se va citi un nou cuvînt din intrare.
Dacă noul cuvînt din intrare este mai mic decît cuvîntul memorat în nodul rădăcină, căutarea continuă cu descendentul stîng, altfel se investighează descendentul drept. Dacă nu există nici un descendent pe direcţia cerută, noul cuvînt nu există în arbore şi va fi inserat pe poziţia descendentului corespunzător. Se observă că acest proces de căutare este recursiv, deoarece căutarea din fiecare nod utilizează o căutare într-unul dintre descendenţii săi.
Prin urmare se impune de la sine ca rutinele de inserare în arbore şi de imprimare să fie recursive.
Revenind la descrierea unui nod, el apare ca fiind o structură cu patru componente:


struct tnode { /* nodul de bază */
char *word; /* pointer la cuvînt */
int count; /* numărător de apariţii */
struct tnode *left; /* descendent stîng */
struct tnode *right; /* descendent drept */
};


Această declaraţie „recursivă” a unui nod este perfect legală, deoarece o structură nu poate conţine ca şi componentă o intrare a ei însăşi dar poate conţine un pointer la o structură de acelaşi şablon cu ea.
Declaraţia:
struct tnode *left;
declară pe left ca fiind un pointer la structură (nod) şi nu o structură însăşi.
În program vom folosi rutinele getword, pentru citirea unui cuvînt din intrare, alloc pentru rezervarea de spaţiu necesar memorării unui cuvînt şi alte cîteva rutine pe care le cunoaştem deja. Rutina principală main citeşte prin intermediul rutinei getword un cuvînt, şi îl plasează în arbore prin rutina tree.


#define MAXWORD 20

main() { /* contorizare apariţii cuvinte */
struct tnode *root, *tree();
char word[MAXWORD];
int t;
root = NULL;
while ((t=getword(word,MAXWORD))!=EOF)
if (t==LETTER)
root = tree(root,word);
treeprint(root);
}


Rutina main gestionează fiecare cuvînt din intrare începînd cu cel mai înalt nivel al arborelui (rădăcina). La fiecare pas, cuvîntul din intrare este comparat cu cuvîntul asociat rădăcinii şi este apoi transmis în jos, fie descendentului stîng, fie celui drept, printr-un apel recursiv la rutina tree. În acest proces, cuvîntul fie există deja, undeva în arbore, caz în care contorul lui de numărare a apariţiilor se incrementează, fie căutarea continuă pînă la întîlnirea unui pointer NULL, caz în care nodul trebuie creat şi adăugat arborelui. Cînd se creează un nod nou, rutina tree returnează un pointer la el, care apoi este introdus în nodul de origine (adică în nodul al cărui descendent este noul nod) în cîmpul left sau right după cum noul cuvînt este mai mic sau mai mare faţă de cuvîntul origine. Rutina tree, care returnează un pointer la o structură de şablon tnode are următorul cod:

struct tnode *tree(struct tnode *p,
char *w) { /* introduce cuvîntul w în nodul p */
struct tnode *talloc(int n);
char *strsav(char *s);
int cond;
if (p==NULL) { /* a sosit un nou cuvînt */
p = talloc(); /* creează un nod nou */
p->word = strsav(w);
p->count = 1;
p->left = p->right = NULL;
}
else
if ((cond=strcmp(w,p->word))==0)
p->count++;
else
if (cond<0) /* noul cuvînt mai mic */
p->left = tree(p->left,w);
else /* noul cuvînt mai mare */
p->right = tree(p->right,w);
return p;
}


Memoria pentru noul nod se alocă de către rutina talloc, care este o adaptare a rutinei alloc, pe care am văzut-o deja. Ea returnează un pointer la un spaţiu liber, în care se poate înscrie noul nod al arborelui. Vom discuta rutina talloc mai tîrziu. Noul cuvînt se copiază în acest spaţiu cu ajutorul rutinei strsav, care returnează un pointer la începutul cuvîntului, contorul de apariţii se iniţializează la 1 şi pointerii către cei doi descendenţi se fac NULL. Această parte de cod se execută numai cînd se adaugă un nou nod.
Rutina treeprint tipăreşte arborele astfel încît pentru fiecare nod se imprimă sub-arborele lui stîng, adică toate cuvintele mai mici decît cuvîntul curent, apoi cuvîntul curent şi la sfîrşit sub-arborele drept, adică toate cuvintele mai mari decît cuvîntul curent. Rutina treeprint este una din cele mai tipice rutine recursive.


treeprint(struct tnode *p) {
/* tipăreşte arborele p recursiv */
if (p!=NULL) {
treeprint(p->left);
printf("%5d %s\n",p->count,p->word);
treeprint(p->right);
}
}


Este important de reţinut faptul că în algoritmul de căutare în arbore, pentru a ajunge la un anumit nod, se parcurg toate nodurile precedente, pe ramura respectivă (stîngă sau dreaptă), începînd întotdeauna cu nodul rădăcină. După fiecare ieşire din rutina tree, din cauza recursivităţii, se parcurge acelaşi drum, de data aceasta de la nodul găsit spre rădăcina arborelui, refăcîndu-se toţi pointerii drumului parcurs.
Dacă consideraţi ca nu aţi înţeles suficient de bine recursivitatea, desenaţi-vă un arbore şi imprimaţi-l cu ajutorul rutinei treeprint, avînd grijă să memoraţi fiecare ieşire din tree şi treeprint.
O observaţie legată de acest exemplu: dacă arborele este „nebalansat“, adică cuvintele nu sosesc în ordine aleatoare din punct de vedere lexicografic, atunci timpul de execuţie al programului poate deveni foarte mare. Cazul limită în acest sens este acela în care cuvintele de la intrare sînt deja în ordine, (crescătoare sau descrescătoare), caz în care programul nostru simulează o căutare liniară într-un mod destul de costisitor.
Să ne oprim puţin asupra alocării de memorie. Cu toate că se alocă diferite tipuri de obiecte, este de preferat să existe un singur alocator de memorie într-un program. Relativ la acest alocator de memorie se pun doua probleme: în primul rînd cum poate satisface el condiţiile de aliniere ale obiectelor de un anumit tip (de exemplu întregii trebuie alocaţi la adrese pare); în al doilea rînd cum se poate declara că alocatorul returnează pointeri la tipuri diferite de obiecte.
Cerinţele de aliniere pot fi în general rezolvate cu uşurinţă pe seama unui spaţiu care se pierde, dar care este nesemnificativ ca dimensiune. De exemplu, alocatorul alloc returnează totdeauna un pointer la o adresă pară. În cazul în care cererea de alocare poate fi satisfăcută şi de o adresă impară (pentru şiruri de caractere, de exemplu) se pierde un caracter.
În ceea ce priveşte declararea tipului alocatorului alloc (adică a tipului de obiect pe care îl indică pointerul returnat de alloc), un foarte bun procedeu în limbajul C este de a declara că funcţia alloc returnează un pointer la char şi apoi să convertim explicit acest pointer la tipul dorit printr-un cast. Astfel dacă p este declarat în forma:
char *p;
atunci:
(struct tnode *)p;
converteşte pe p dintr-un pointer la char într-un pointer la o structură de şablon tnode, dacă el apare într-o expresie. Şi atunci, o versiune a alocatorului talloc poate fi următoarea:


struct tnode *talloc() {
char *alloc();
return (struct tnode *) alloc
(sizeof(struct tnode));
}
Căutare în tabele


O altă problemă legată de definirea şi utilizarea structurilor este căutarea în tabele. Cînd se întîlneşte de exemplu, o linie de forma:
#define YES 1
simbolul YES şi textul de substituţie 1 se memorează într-o tabelă. Mai tîrziu, ori de cîte ori textul YES va apărea în instrucţiuni, el se va înlocui cu constanta 1.
Crearea şi gestionarea tabelelor de simboluri este o problemă de bază în procesul de compilare. Există două rutine principale care gestionează simbolurile şi textele lor de substituţie. Prima, install(s,t)înregistrează simbolul s şi textul de substituţie t într-o tabelă, s şi t fiind şiruri de caractere. A doua, lookup(s) caută şirul s în tabelă şi returnează fie un pointer la locul unde a fost găsit, fie NULL dacă şirul s nu figurează în tabel.
Algoritmul folosit pentru crearea şi gestionarea tabelei de simboluri este o căutare pe bază de hashing. Fiecărui simbol i se calculează un cod hash astfel: se adună codurile ASCII ale caracterelor simbolului şi se ia restul provenit din împărţirea numărului obţinut din adunare şi dimensiunea tabelului. Astfel, fiecărui simbol i se asociază un cod hash H care verifică relaţia:
0<=H<0x100 (în hexazecimal)
Codul hash astfel obţinut va fi folosit apoi ca un indice într-o tabelă de pointeri. Un element al acestei tabele (masiv) indică începutul unui lanţ de blocuri care descriu simboluri cu acelaşi cod hash. Dacă un element al tabelei este NULL înseamnă că nici un simbol nu are valoarea respectivă de hashing.
Un bloc dintr-un lanţ indicat de un element al tabelei este o structură care conţine un pointer la simbol, un pointer la textul de substituţie şi un pointer la următorul bloc din lanţ. Un pointer NULL la următorul bloc din lanţ indică sfîrşitul lanţului.
Şablonul unei structuri (nod) este următorul:


struct nlist {
char *name;
char *def;
struct nlist *next;/ * următoarea intrare în lanţ */
};


Tabelul de pointeri care indică începuturile lanţului de blocuri ce descriu simboluri de acelaşi cod hash este:

#define HASHSIZE 0x100
static struct nlist *hashtab[HASHSIZE];


Algoritmul de hashing pe care-l prezentăm nu este cel mai bun posibil, dar are meritul de a fi extrem de simplu:

hash(char *s) {
/* formează valoarea hash pentru şirul s */
int hashval;
for (hashval=0; *s!='\0';)
hashval += *s++;
return hashval % HASHSIZE;
}


Algoritmul de hashing produce un indice în masivul de pointeri hashtab. În procesul de căutare a unui simbol, dacă el există, el trebuie să fie în lanţul de blocuri care începe la adresa conţinută de elementul din hashtab cu indicele respectiv.
Căutarea în tabela de simboluri hashtab se realizează cu funcţia lookup. Dacă simbolul căutat este prezent undeva în lanţ, funcţia returnează un pointer la el; altfel returnează NULL.


struct nlist *lookup(char *s) {
/* caută şirul s în hashtab */
struct nlist *np;
for (np=hashtab[hash(s)]; np!=NULL;
np=np->next)
if (strcmp(s,np->name)==0)
return np; /* s-a găsit s */
return NULL; /* nu s-a găsit s */
}


Rutina install foloseşte funcţia lookup pentru a determina dacă simbolul nou care trebuie introdus în lanţ este deja prezent sau nu. Dacă mai există o definiţie anterioară pentru acest simbol, ea trebuie înlocuită cu definiţia nouă. Altfel, se creează o intrare nouă pentru acest simbol, care se introduce la începutul lanţului. Funcţia install returnează NULL, dacă din anumite motive nu există suficient spaţiu pentru crearea unui bloc unu.

struct nlist *install(char *name, char
*def) { /* scrie (nume, def) în htab */
struct nlist *np, *lookup();
char *strsav(), *alloc();
int hashval;
if ((np=lookup(name))==NULL) { /* nu s-a găsit */
np = (struct nlist*)alloc(sizeof(*np));
if (np==NULL)
return NULL; /* nu există spaţiu */
if ((np->name=strsav(name))==NULL)
return NULL;
hashval = hash(np->name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
}
else /* nodul există deja */
free(np->def); /* eliberează definiţia veche */
if ((np->def=strsav(def))==NULL)
return NULL;
return np;
}


Deoarece apelurile la funcţiile alloc şi free pot apărea în orice ordine şi deoarece alinierea contează, versiunea simplă a funcţiei alloc, prezentată în capitolul 9 nu este adecvată aici. În biblioteca standard există funcţii de alocare fără restricţii, care se apelează implicit sau explicit de către utilizator dintr-un program scris în C pentru a obţine spaţiul de memorie necesar. Deoarece şi alte acţiuni dintr-un program pot cere spaţiu de memorie într-o manieră asincronă, spaţiul de memorie gestionat de funcţia alloc poate să fie necontiguu. Astfel, spaţiul liber de memorie este păstrat sub forma unui lanţ de blocuri libere, fiecare bloc conţinînd o dimensiune, un pointer la următorul bloc şi spaţiul liber propriu-zis. Blocurile sînt păstrate în ordinea crescătoare a adreselor iar, ultimul bloc, de adresa cea mai mare, indică primul bloc, prin pointerul lui la blocul următor din lanţ, astfel încît lanţul este circular.
Cînd se lansează o cerere, se examinează lista spaţiului liber, pînă se găseşte un bloc suficient de mare pentru cererea respectivă. Dacă blocul are exact dimensiunea cerută, el se eliberează din lanţul blocurilor libere şi este returnat utilizatorului. Dacă blocul este mai mare se descompune, astfel încît partea cerută se transmite utilizatorului, iar partea rămasă se introduce înapoi în lista de spaţiu liber. Dacă nu se găseşte un bloc suficient de mare pentru cererea lansată se caută un alt bloc de memorie.
Eliberarea unei zone de memorie prin intermediul rutinei free cauzează, de asemenea, o căutare în lista de spaţiu liber, pentru a găsi locul corespunzător de inserare a blocului de memorie eliberat. Dacă blocul de memorie eliberat este adiacent cu un bloc din lista de spaţiu liber la orice parte a sa, el este alipit la acel bloc, creîndu-se un bloc mai mare, astfel ca memoria să nu devină prea fragmentată. Determinarea adiacenţei este uşurată de faptul că lista de spaţiu liber se păstrează în ordinea crescătoare a adreselor de memorie.
Exemplul de utilizare a acestor funcţii iniţializează elementele masivului hashtab cu NULL. În continuare se aşteaptă de la tastatură introducerea unui nume şi a unei definiţii pentru acest nume. Dacă numele introdus nu există în lista hashtab atunci se afişează un mesaj corespunzător, altfel se afişează vechea definiţie care este apoi înlocuită de noua definiţie introdusă.


main() {
char num[30],def[30];
int i;
struct nlist *np;
for (i=0; i<HASHSIZE; i++)
hashtab = NULL;
do {
getword(num); getword(def);
if ((np=lookup(num))==NULL)
printf("New name\n");
else
printf("Old definition: %s\n",
np->def);
install(num,def);
} while (1);
}


Cîmpuri

Un cîmp se defineşte ca fiind o mulţime de biţi consecutivi dintr-un cuvînt sau întreg. Adică din motive de economie a spaţiului de memorie, este utilă împachetarea unor obiecte într-un singur cuvînt maşină. Un caz frecvent de acest tip este utilizarea unui set de flaguri, fiecare pe un bit, pentru tabela de simboluri a unui compilator.
Fiecare simbol dintr-un program are anumite informaţii asociate lui, cum sînt de exemplu, clasa de memorie, tipul, dacă este sau nu cuvînt cheie ş.a.m.d. Cel mai compact mod de a codifica aceste informaţii este folosirea unui set de flaguri, de cîte un bit, într-un singur întreg sau caracter.
Modul cel mai uzual pentru a face acest lucru este de a defini un set de măşti, fiecare mască fiind corespunzătoare poziţiei bitului m interiorul caracterului sau cuvîntului. De exemplu:


#define KEYWORD 01
#define EXTERNAL 02
#define STATIC 04


definesc măştile KEYWORD, EXTERNAL şi STATIC care se referă la biţii 0, 1 şi respectiv 2 din caracter sau cuvînt. Atunci accesarea acestor biţi se realizează cu ajutorul operaţiilor de deplasare, mascare şi complementare, descrişi într-un capitol anterior. Numerele trebuie să fie puteri ale lui 2.

Expresii de forma:
flags | = EXTERNAL | STATIC;
apar frecvent şi ele setează biţii 1 şi 2 din caracterul sau întregul flags (în exemplul nostru)


în timp ce expresia:
flags &= (EXTERNAL | STATIC);
selectează biţii 1 şi 2 din flags.


Expresia:
if (flags & (EXTERNAL | STATIC)) ...
este adevărată cînd cel puţin unul din biţii 1 sau 2 din flags este unu.


Expresia:
if (!(flags & (EXTERNAL | STATIC))) ...
este adevărată cînd biţii 1 şi 2 din flags sînt ambii zero.


Limbajul C oferă aceste expresii, ca o alternativă, pentru posibilitatea de a defini şi de a accesa biţii dintr-un cuvînt, în mod direct, folosind operatorii logici pe biţi.
Sintaxa definiţiei cîmpului şi a accesului la el se bazează pe structuri. De exemplu construcţiile #define din exemplul de mai sus pot fi înlocuite prin definirea a trei cîmpuri:


struct {
unsigned is_keyword: 1;
unsigned is_external:1;
unsigned is_static: 1;
} flags;


Această construcţie defineşte variabila flags care conţine 3 cîmpuri, fiecare de cîte un bit. Numărul care urmează după ’:’ reprezintă lungimea cîmpului în biţi. Cîmpurile sînt declarate unsigned pentru a sublinia că ele sînt cantităţi fără semn. Pentru a ne referi la un cîmp individual din variabila flags folosim o notaţie similară cu notaţia folosită pentru membrii structurilor.
flags.is_keyword
flags.is_static
Cîmpurile se comportă ca nişte întregi mici fără semn şi pot participa în expresii aritmetice ca orice alţi întregi. Astfel, expresiile anterioare pot fi scrise mai natural sub forma următoare:
flags.is_extern = flags.is_static = 1;
pentru setarea biţilor 1 şi 2 din variabila flags,
flags.is_extern = flags.is_static = 0;
pentru ştergerea biţilor, iar:


if (flags.is_extern==0 &&
flags.is_static==0)


pentru testarea lor.
Un cîmp nu trebuie să depăşească limitele unui cuvînt. În caz contrar, cîmpul se aliniază la limita următorului cuvînt. Cîmpurile nu necesită să fie denumite. Un cîmp fără nume, descris numai prin caracterul ’:’ şi lungimea lui în biţi este folosit pentru a rezerva spaţiu în vederea alinierii următorului cîmp. Lungimea zero a unui cîmp poate fi folosită pentru forţarea alinierii următorului cîmp la limita unui nou cuvînt, el fiind presupus a conţine tot cîmpuri şi nu un membru obişnuit al structuri, deoarece în acest ultim caz, alinierea se face în mod automat. Nici un cîmp nu poate fi mai lung decît un cuvînt. Cîmpurile se atribuie de la dreapta la stînga.
Cîmpurile nu pot constitui masive, nu au adrese, astfel încît operatorul '&' nu se poate aplica asupra lor.


Reuniuni

O reuniune este o variabilă care poate conţine, la momente diferite, obiecte de diferite tipuri şi dimensiuni; compilatorul este cel care ţine evidenţa dimensiunilor şi aliniamentului.
Reuniunile oferă posibilitatea ca mai multe tipuri diferite de date să fie tratate într-o singură zonă de memorie, fără a folosi în program vreo informaţie dependentă de maşină.
Să reluăm exemplul tabelei de simboluri a unui compilator, presupunînd că constantele pot fi de tip int, float sau şiruri de caractere.
Valoarea unei constante particulare trebuie memorată într-o variabilă de tip corespunzător, cu toate că este mai convenabil, pentru gestiunea tabelei de simboluri, ca valoarea să fie memorată în aceeaşi zonă de memorie, indiferent de tipul ei şi să ocupe aceeaşi cantitate de memorie. Acesta este scopul unei reuniuni: de a furniza o singură variabilă care să poată conţine oricare dintre valorile unor tipuri de date. Ca şi în cazul cîmpurilor, sintaxa definiţiei şi accesului la o reuniune se bazează pe structuri. Fie definiţia:


union u_tag. { int ival;
float fval;
char *pval;
} uval;


Variabila uval va fi suficient de mare ca să poată păstra pe cea mai mare dintre cele trei tipuri de componente. Oricare dintre tipurile de mai sus poate fi atribuit variabilei uval şi apoi folosit în expresii în mod corespunzător, adică tipul în uval este tipul ultim atribuit. Utilizatorul este cel care ţine evidenţa tipului curent memorat într-o reuniune.
Sintactic, membrii unei reuniuni sînt accesibili printr-o construcţie de forma:
nume-reuniune. membru
sau
pointer-la-reuniune->membru
Dacă variabila utype este utilizată pentru a ţine evidenţa tipului curent memorat în uval, atunci fie următorul cod:


if (utype==INT)
printf ("%d\n",uval.ival);
else if (utype== FLOAT)
printf("%f\n",uval.fval);
else if (utype==STRING)
printf("%s\n",uval.pval);
else
printf("tip incorect %d in utype\n",
utype);


Reuniunile pot apărea în structuri şi masive şi invers. Sintaxa pentru accesarea unui membru al unei reuniuni, dintr-o structură, sau invers este identică cu cea pentru structurile imbricate. Pe exemplu, în masivul de structuri symtab[NSYM] definit de:

struct {
char * name;
int flags;
int utype;
union {
int ival;
float fval;
char *pval;
} uval;
} symtab[NSYM];


variabila ival se referă prin:
symtab.uval.ival
iar primul caracter al şirului pointat de pval prin:
*symtab.uval.pval
De fapt, o reuniune este o structură în care toţi membrii au deplasamentul zero, structura fiind suficient de mare pentru a putea păstra pe cel mai mare membru. Alinierea este corespunzătoare pentru toate tipurile reuniunii. Ca şi la structuri, singurele operaţii permise cu reuniuni sînt accesul la un membru al reuniunii şi considerarea adresei ei.
Reuniunile nu pot fi atribuite, transmise la funcţii sau returnate de către acestea. Pointerii la reuniuni pot fi folosiţi în mod similar cu pointerii la structuri.


Declaraţii de structuri, reuniuni şi cîmpuri

Deoarece specificatorii de structuri, reuniuni şi cîmpuri au aceeaşi formă vom prezenta sintaxa lor generală în acest paragraf.

Specificator-structură-sau-reuniune:
struct-sau-union { lista-declaraţiilor }
struct-sau-union identificator { lista-declaraţiilor }
struct-sau-union identificator
Struct-sau-union:
struct
union


Lista-declaraţiilor este o secvenţă de declaraţii pentru membrii structurii sau reuniunii.

Lista-declaraţiilor:
declaraţie-structură
declaraţie-structură, lista-declaraţiilor
Declaraţie-structură:
specificator-tip, lista-declarator;
Lista-declarator:
declarator-structură
declarator-structură, lista-declarator


În mod obişnuit, un declarator-structură este chiar un declarator pentru un membru al structurii sau reuniunii. Un membru al structurii poate fi constituit dintr-un număr specificat de biţi, caz în care avem de-a face cu un cîmp. Lungimea lui se separă de nume prin caracterul ’:’ Atunci:

Declarator-structură:
declarator
declarator : expresie-constantă
: expresie-constantă


Într-o structură fiecare membru care nu este un cîmp începe la o adresă corespunzătoare tipului său. Astfel într-o structură pot exista zone fără nume neutilizate, rezultate din motive de aliniere.
Limbajul C nu introduce restricţii privind tipurile obiectelor care pot fi declarate cîmpuri.
Un specificator-structură-sau-reuniune de forma a doua declară un identificator ca fiind eticheta (marcajul) structurii sau reuniunii. Atunci o declaraţie ulterioară poate folosi forma a treia a unui specificator-structură-sau-reuniune.
Etichetele de structuri permit definirea structurilor auto-referite; de asemenea permit ca partea de declaraţie a corpului structurii să fie dată o singură dată şi folosită de mai multe ori. Este interzisă declararea recursivă a unei structuri sau reuniuni, dar o structură sau o reuniune poate conţine un pointer la ea.
Două structuri pot partaja o secvenţă iniţială comună de membri; adică acelaşi membru poate apărea în două structuri diferite dacă el are acelaşi tip în ambele structuri şi dacă toţi membri precedenţi lui sînt identici în cele două structuri.


Typedef

Limbajul C oferă o facilitate numită typedef pentru a crea noi nume de tipuri de date. Specificatorul de tip typedef-nume are sintaxa:
typedef-nume:
declarator


Într-o declaraţie implicînd typedef fiecare identificator care apare ca parte a unui declarator devine sintactic echivalent cu cuvîntul cheie rezervat pentru tipul asociat cu identificatorul. De exemplu, declaraţia:
typedef int LENGTH;
îl face pe LENGTH sinonim cu int. „Tipul” LENGTH poate fi folosit ulterior în declaraţii în acelaşi mod ca şi tipul int.
LENGTH len, maxlen;
LENGTH *length[];
În mod similar, declaraţia:
typedef char *STRING;
îl face pe STRING sinonim cu char*, adică pointer la caracter, care apoi poate fi utilizat în declaraţii de tipul:
STRING p, lineptr[LINES], alloc();
Se observă că tipul care se declară prin typedef apare pe poziţia numelui de variabilă nu imediat după cuvîntul rezervat typedef. Sintactic typedef este sinonim cu clasele de memorie extern, static etc, dar nu rezervă memorie pentru variabilele respective.
Ca un exemplu mai complicat să reluăm declaraţia unui nod al unui arbore, de data aceasta folosind typedef pentru a crea un nou nume pentru un tip structură (vezi secţiunea 10.5).


typedef struct tnode {
char *word; /* pointer la text */
int count; /* număr apariţii */
struct tnode *left; /* descendent stîng */
struct tnode *right; /* descendent drept */
} TREENODE, *TREEPTR;


Această declaraţie creează două nume noi de tipuri, numite TREENODE, care este o structură şi TREEPTR, care este un pointer la o structură. Atunci rutina talloc poate fi scrisă sub forma:

TREEPTR talloc() {
char *alloc();
return (TREEPTR)alloc(sizeof(TREENODE)));
}


Trebuie subliniat faptul că declaraţia typedef nu creează noi tipuri în nici un caz; ea adaugă doar sinonime pentru anumite tipuri de date, deja existente. Variabilele declarate în acest fel au exact aceleaşi proprietăţi ca şi cele declarate explicit. De fapt, typedef se aseamănă cu #define, cu excepţia faptului că în timp ce #define este tratat de preprocesor, typedef este tratat de către compilator. De exemplu:
typedef int(*PFI)();
creează numele PFI pentru „pointer la o funcţie care returnează un întreg”, tip care poate fi folosit ulterior într-un context de tipul:
PFI strcmp, numcmp, swap;
în programul de sortare din capitolul 9.
Există două motive principale care impun folosirea declaraţiilor typedef. Primul este legat de problemele de portabilitate. Cînd se folosesc declaraţii typedef pentru tipuri de date care sînt dependente de maşină, atunci pentru o compilare pe un alt sistem de calcul este necesară modificarea doar a acestor declaraţii nu şi a datelor din program.
Al doilea constă în faptul că prin crearea de noi nume de tipuri se oferă posibilitatea folosirii unor nume mai sugestive în program, deci o mai rapidă înţelegere a programului.
 
Top