m6g9gy

O structura este o colectie de una sau mai multe variabile care pot fi de tipuri diferite, grupate impreuna sub un singur nume pentru o manipulare convenabila. (Structurile sint anumite "inregistrari" in unele limbaje, de exemplu in PASCAL.)

Exemplul traditional de structura este inregistrarea personala: un salariat este descris prin citeva atribute ca numele, adresa, salariu etc. Fiecare din atribute la rindul lor pot fi structuri: numele are mai multe componente, adresa de asemenea, salariul de baza s.a.m.d.

Structurile ajuta la organizarea datelor complicate, mai ales in programele de mari dimensiuni, deoarece in multe situatii ele permit ca un grup de variabile inrudite sa fie tratate unitar si nu ca entitati separate. In acest capitol vom incerca sa ilustram cum sint utilizate structurile. Programele pe care le vom folosi in acest scop sint mai mari decit multe altele din manualul acesta, dar inca de dimensiuni modeste.

6.1. Bazele

Sa ne reamintim rutinele de conversie a datei din capitolul 5. O data consista din mai multe parti, precum ziua, luna, anul si probabil ziua din an si numele lunii. Aceste cinci variabile pot fi toate plasate intr-o singura structura ca aceasta: struct date A int day; int month; int yearday; char mon_namea4i;
S

Cuvintul cheie "struct" introduce o structura de date, care este o lista de declartii cuprinsa intre acolade. Un nume optional (eticheta) numit "structure tag", poate sa urmeze cuvintul cheie "struct"(precum date in exemplul de mai sus).
Aceasta eticheta da un nume acestui gen de structura si poate fi referita in continuare ca prescurtare de declaratie detaliata.

Elementele sau variabilele mentionate intr-o structura sint numite
"membri". Un membru al structurii sau o eticheta a unei structuri sau o variabila simpla pot avea acelasi nume fara ambiguitate deoarece se disting prin context. Desigur se va utiliza acelasi nume doar pentru a defini obiecte in strinsa relatie.

Acolada din dreapta care inchide lista membrilor structurii poate fi urmata de o lista de variabile ca in exemplul de mai jos: struct A...S x, y, z; ceea ce este sintactic analog cu: int x, y, z; in sensul ca fiecare declaratie numeste pe x, y, z si z ca variabile de tipul specificat si aloca spatiu pentru fiecare din ele.

O declaratie de structura care nu este urmata de o lista de variabile nu aloca spatiu de memorie ci descrie doar forma sau organizarea structurii. Daca structura este nominalizata, numele poate fi utilizat in program pentru atribuirea de valori structurii. De exemplu: struct date d; defineste o variabila d care are o structura de tip data, si poate fi initializata la un moment dat conform definitiei sale cu o lista ca mai jos: struct date d =A4, 7, 1776, 186, "Jul" S;

Un membru a unei structuri particulare poate fi referit intr-o expresie printr-o constructie de forma:

"numestructura.membru"

Operatorul "." din constructia de mai jos leaga numele membrului de numele structurii. De exemplu pentru a afla un an bisect din structura d se refera la membrul "year" astfel: leap = d.year % 4 == 0 && d.year % 100 != 0 || d.year % 400 == 0;

sau pentru a testa numele liniei din membrul "mon" if (strcmp(d.mon_name, "Aug") == 0) ... sau pentru a converti numele lunii la litere mici d.mon_namea0i = lower(d.mon_namea0i);

O structura poate sa cuprinda structuri, de exemplu: struct person A char nameaNAMESIZEi; char addressaADRSIZEi; long zipcode; long ss-number; double salary; struct date birthdate; struct date hiredate;
S;

Structura "person" contine doua structuri de tip data ("birthdate" si "hiredate"). Daca declaram "p" astfel struct person emp; atunci o constructie emp.birthdate.month se va referi la luna din data nasterii. Operatorul "." asociaza partea stinga cu dreapta.

6.2. Structuri si functii

Exista un numar de restrictii relative la structurile in C.
Regulile esentiale sint ca nu puteti face asupra unei structuri decit operatia de obtinere a adresei cu &, si de accesare a unuia dintre membrii structurii. Acest lucru presupune ca structurile nu pot fi asignate sau copiate ca un tot unitar, si ca nu pot fi nici pasate sau returnate intre functii. (Aceste restrictii vor fi ridicate in versiunile viitoare.) Pointerii la structuri nu se supun insa acestor restricti, si de aceea structurile si functiile coopereaza confortabil. In fine, structurile automate, ca si tablourile automate, nu pot fi initializate; nu pot aceasta decit stucturile statice.

Sa vedem citeva din aceste probleme rescriind functiile de conversie de data din capitolul precedent, folosind structuri.
Deoarece regulile interzic pasarea de structuri direct unei functii, trebuie fie sa pasam componentele separat, fie sa pasam un pointer catre intregul obiect. Prima alternativa se foloseste de day_of_year asa cum am scris in capitolul 5: d.yearday = day_of_year(d.year, d.month, d.day);

Celalalt mod este de a pasa un pointer. Daca am declarat pe hiredate ca: struct date hiredate; si am rescris pe day_of_year, putem apoi spune: hiredate.yearday = day-of-year(&hiredate); deci pointerul lui "hiredate" trece la "day-of-year". Acum functia trebuie sa fie modificata deoarece argumentul sau este un pointer si nu o lista de variabile. day-of-year(pd) /* set day of year from month, day */ struct date *pd;
A 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_tabaleapiaii; return(day);
S

Declaratia "struct date *pd;" spune ca pd este un pointer la o structura de tip data. Notatia "pd->year" este noua. Daca p este pointer la o structura, atunci p->member-of-structure refera un membru particular. (Operatorul -> este un minus urmat de >.) Cu ajutorul pointerului pd poate referit si un membru al structurii, de exemplu membrul "year":

(*pd).year

Deoarece pointerii la structuri sint des utilizati este preferabila folosirea operatorului ->, forma mai scurta. In constructia de mai sus parantezele sint necesare deoarece operatorul "." este prioritar fata de "*". Atit "->" cit si "." se asociaza de la stinga la dreapta astfel: p->q->memb emp.birthdate.month sint

(p->q)->memb
(emp.birthdate).month

Pentru completare dam o alta functie "month-day" rescrisa folosind structurile. month-day(pd) /* set month and day from day of year */ struct date *pd;
A int i, leap; leap = pd->year % 4 == && pd->year % 100 != 0 || pd->year % 400 == 0; pd->day = pd->yearday; for (i = 1; pd->day > day_tabaleapiaii; i++) pd->day -= day_tabaleapiaii; pd->month = i;
S

Operatorii de structura "->" si ". " impreuna cu "()" pentru liste si "ai" pentru indici in ierarhia prioritatilor sint cei mai puternici. De exemplu la declaratia: struct A int x; int *y;
S *p; atunci ++p->x incrementeaza pe x si nu p, deoarece ordinea implicita este ++(p->x). Parantezele pot fi utilizate pentru a modifica prioritatile: (++p)->x incrementeaza p inainte de a accesa x, iar (p++)->x incrementeaza p dupa aceea. (Acest ultim set de paranteze nu este necesar. De ce ?)

In acelasi sens, *p->y aduce ceea ce pointeaza y; *p->y++ incrementeaza y dupa ce se face accesul la ceea ce pointeaza y (la fel cu *s++); (*p->y)++ incrementeaza ceea ce pointeaza y; si *p++->y incrementeaza p dupa accesul la ceea ce pointeaza y.

6.3. Tablouri de structuri

Structurile sint in special utile pentru manevrarea tablourilor de variabile inrudite. Pentru exemplificare sa consideram un program pentru a numara fiecare aparitie a cuvintului cheie C.
Avem nevoie de un tablou de siruri de caractere pentru a pastra numele si un tablou de intregi pentru contoare. O posibilitate este folosirea in paralel a doua tablouri unul pentru cuvinte cheie si unul pentru contoare, astfel char *keywordaNKEYSi; int keycountaNKEYSi;

Dar insasi faptul ca se folosesc doua tablouri paralele indica posibilitatea unei alte organizari. Fiecare acces de cuvint cheie este de fapt o pereche: char *keywordd int keycount ceea ce de fapt este un tablou de perechi. Urmatoarea declaratie de structura: struct key A char *keyword; int keycount;
S keytabaNKEYSi; defineste un tablou "keytab" de structuri de acest tip si ii aloca memorie.
Fiecare element al tabloului este o structura. Aceasta se mai poate scrie: struct key A char *keyword; int keycount;
S; struct key keytabaNKEYSi;

De fapt structura "keytab" contine un set constant de nume care cel mai usor se poate initializa o singura data cind este definita. Initializarea structurii este analoaga cu initializarile prezentate mai devreme -definitia este urmata de o lista de initializatori cuprinsi intre acolade: struct key A char *keyword; int keytab;
S keytabai =A
"break", 0,
"case", 0,
"char", 0,
"continue", 0,
"default", 0,
/*...*/
"unsigned", 0,
"while", 0
S;

Initializatorii sint listati in perechi corespunzind membrilor structurii. Ar fi mai precis ca initializatorii pentru fiecare "sir" sau structura sa fie cuprinsi intre acolade:

A"break", 0S,
A"case", 0S,
... dar acoladele in interior nu sint necesare atunci cind initializatorii sint simple variabile sau siruri de caractere si cind toate sint prezente. Ca de obicei compilatorul va calcula numarul de intrari in tabloul "keytab" daca initializatorii sint prezenti iar "ai" este lasat gol.

Programul de numarare a cuvintelor cheie incepe prin definirea lui "keytab". Rutina principala citeste intrarea prin apeluri repetate a functiei "getword" care la o apelare citeste un cuvint. Fiecare cuvint este cautat in "keytab" cu ajutorul unei versiuni a functiei de cautare linia ra descrisa in capitolul 3.
(Bineinteles lista de cuvinte cheie trebuie sa fie in ordine crescatoare pentru ca treaba sa mearga).

#define MAXWORD 20 main() /* count c keywords */
A int n, t; char wordaMAXWORDi;
while ((t = getword(word, MAXWORD)) != EOF) if (t == LETTER) if ((n = binary(word, keytab<NKEYS)) >= 0) keytabani.keycount++; for (n = 0; n < NKEYS; n++) if (keytabani, keycount > 0) printf("%4d %s\n", keytabani.keycount, keytabani.keyword);
S binary(word, tab, n) /* find word in taba0i...taban-1i */ char *word; struct key tabai; int n;
A int low, high, mid, cond; low = 0 high = n - 1
while (low <= high) A mid = (low + high) / 2; if ((cond = strcmp(word, tabamidi.keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return(mid);
S return(-1);
S

In curind vom prezenta si functia "getword"; pentru moment este suficient sa spunem ca ea returneaza LETTER de atitea ori cind gaseste un cuvint si copiaza cuvintul in primul ei argument.

Cantitatea NKEYS este numarul de cuvinte cheie din "keytab".
Desi am putea sa numaram acestea manual, este mult mai usor si mai sigur sa facem aceasta cu ajutorul masinii in special daca lista este subiectul unei posibile schimbari. O posibilitatea ar fi sa incheiem lista de initializatori cu un pointer nul si apoi sa buclam in "keytab" pina este detectat sfirsitul.

Dar aceasta este mai mult decit este necesar, deoarece dimensiunea tabloului este complect determinata in momentul compilarii. Numarul de intrari este: dimensiunea lui keytab/dimensiunea lui struct key

C obtine un timp de compilare operator unar numit "sizeof" care poate fi folosit la calcularea dimensiunii oricarui obiect.
Expresia sizeof(object) livreaza un intreg egal cu dimensiunea obiectului specificat
Dimensiunea este data in unitati nespecificate numite "bytes", care au aceeasi dimensiune ca si "char") Obiectul poate o variabila actuala sau tablou sau structura, ori numele unui tip de baza ca "int" sau "double" ori numele unui tip derivat ca o structura. In cazul nostru numarul de cuvinte cheie se obtine prin impartirea dimensiunii tabloului la dimensiunea unui element detablou. Acest calcul se face uzind o declaratie
"#define" setind valoarea in NKEYS:

#define NKEYS (sizeof(keytab) / sizeof(struct key))

Si acum asupra functiei "getword". De fapt noi am scris un
"getword" mai complicat decit era necesar pentru acest program, dar nu mult mai complicat. "getword" returneaza urmatorul
"word" de la intrare, unde "word" este fie un sir de litere si cifre incepind cu o litera fie un un singur caracter. Tipul obiectului este returnat ca o valoare a unei functii; aceasta este LETTER daca e vorba de un cuvint, EOF daca este sfirsitul fisierului si este caracterul insusi daca este un caracter non alfabetic. getword(w, lim) /* get next word from input */ char *w; int lim;
A int c, t; if (type(c = *w++ =getch()) != LETTER) A
*w = '\0'; return(c);
S
while (--lim > 0) A t = type(c = *w++ = getch()); if (t != LETTER && t != DIGIT) A ungetch(c); break;
S
S
*(w-1) = '\0'; return(LETTER);
S

"getword" utilizeaza rutinele "getch" si "ungetch" despre care am scris in capitolul 4: cind colectia de caractere alfabetice se termina, "getword" a depasit deja cu un caracter sirul. Apelarea lui "ungetch" repune un caracter inapoi la intrare pentru urmatorul acces.

"getword" apeleaza "type" pentru a determina tipul fiecarui caracter de la intrare. Iata o versiune numai pentru alfabetul
ASCII. type(c) /* return type of ascii character */ int c;
A if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') return(LETTER); else if (c >= '0' && c <= '9') return(DIGIT); else return(c);

Constantele simbolice LETTER si DIGIT pot avea orice valori care nu sint in conflict cu caracterele nonalfabetice si EOF;
ALegerile evidente sint:

#define LETTER 'a'
#define DIGIT0'

"getword" poate fi mai rapid daca apelurile la functia "type" sint in locuite cu apeluri corespunzatoare tablourilor, typeai.
Biblioteca standard C contine macrouri numite "isalpha" si
"isdigit" care opereaza de aceasta maniera.

Exercitiul 6.1. Faceti aceste modificari la "getword" si determinati modificarile de viteza ale programului.

Exercitiul 6.2. Scrieti o versiune de "type" care este independenta de setul de caractere.

Exercitiul 6.3. Scrieti o versiune a programului de numarare a cuvinte care nu numara aparitiile continute intre apostrofi.

6.4. Pointeri la structuri

Pentru a ilustra citeva din consideratiile referitoare la pointeri si tablouri de structuri sa rescriem programul de contorizare a cuvintelor cheie, de data aceasta folosind pointerii in loc de indici.

Declaratia externa "keytab" nu necesita modificari, dar
"main" si "binary" necesita. main() /* count keywords; pointer version */
A int t; char wordaMAXWORDi; 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 struct key *binary(word, tab, n) /* find word */ char *word; /* in taba0i...taban-1i */ struct key tabai; int n;
A int cond; struct key *low = detaba0i; struct key *high = ftaban-1i; struct key *mid;
while (low <= high) A 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);
S return(NULL);
S
Aici sint mai multe chestiuni de notat. Prima, declaratia
"binary" trebuie sa indice ca e returneaza un pointer structurii tip "key" in locul unui intreg. Acesta este declarat in "main" cit si in "binary". Daca "binary" gaseste cuvintul, returneaza un pointer; daca acesta lipseste, returneaza NULL.

A doua, orice acces la elementele lui "keytab" sint facute prin pointeri. Aceasta determina o schimbare semnificativa in
"binary calculul poate fi simplu. mid = (low + high) / 2 deoarece adunarea a doi pointeri nu va produce nici un fel de raspuns utilizabil si de fapt este ilegala. Aceasta trebuie schimbata in mid = low + (high - low) / 2 care seteaza "mid" in punctul de la jumatatea intre "low" si
"high".

Ar trebui sa studiati si initializatorii pentru "low" si "high"
Este posibil sa se initializeze un pointer la adresa unui obiect definit dinainte; aceasta am facut noi aici.

In "main" am scris: for (p = keytab; p < keytab + NKEYS; p++)

Daca p este un pointer la structura, orice operatie aritmentica asupra lui p tine cont de dimnesiunea actuala a structurii, astfel p++ incrementeaza p cu cantitatea corecta pentru a obtine urmatorul element al tabloului de structuri. Dar sa nu credeti ca dimensiunea structurii este suma dimensiunilor membrilor sai deoarece aliniamentul cerut pentru diferiti membri pot determina aparitia de "gauri" in structura.

Si in final o consideratie asupra formatului programului.
Cind o functie f returneaza un tip complicat ca in: struct key *binary(word, tab, n) numele functiei este dificil de vazut si de gasit cu un editor de texte De aceea un alt stil este citeodata folosit. struct key * binary(word, tab, n)

Aceasta este mai mult o chestiune de gust personal; luati forma pe care o doriti si tineti-va de ea.

6.5 Structuri cu autoreferire

Sa presupunem ca vrem sa tratam problema numararii aparitiei cuvintelor in modul cel mmai general adica sa numaram fiecare aparitie a fiecarui cuvint la o intrare. Deoarece lista de cuvinte nu este cunoscuta in avans nu putem sa o sortam convenabil si sa folosim o cautare liniara. Inca nu putem sa efectuam o cautare liniara pentru fiecare cuvint in momentul cind soseste pentru a vedea daca a mai aparut deoarece perogramul ar dura foarte mult. (Mai precis, timpul de rulare ar creste cu patratul numarului de cuvinte introduse. ) Cum putem organiza datele pentru a face fata in mod eficient cu o lista de cuvinte arbitrare?

O solutie ar fi sa pastram setul de cuvinte sortat in orice moment plasind fiecare cuvint in pozitia adecvata in momentul sosirii lui. Aceasta n-ar terebui facut prin mutarea cuvintelor intr-un tablou linear deoarece si aceasta ia un timp prea lung. In loc vom utiliza o structura de date numita "binary tree" adica arborele binar.

Arborele contine un "node" pentru fiecare cuvint distinct; fiecare nod contine: un pointer la textul cuvintului un contor al numarului de aparitii un pointer la nodul-copil din stinga un pointer la nodul-copil din dreapta

Nici un nod nu poate avea mai mult de doi copii. Ar trebui sa aiba numai zero sau unu.

Nodurile sint astfel mentinute incit subarborele din stinga contine numai cuvinte care sint mai mici decit cuvintele din nodul considerat, iar subarborele din dreapta numai cuvinte care sint mai mari. Pentru a afla daca un nou cuvint se afla in arbore se incepe comparatia de la nodul radacina. Daca ele sint egale chestiunea este rezolvata Daca noul cuvint este mai mic decit cuvintul din nodul radacina cercetarea continua la nodul copil din stinga; altfel este investigat nodul copil din dreapta. Daca nu gasete nici un copil cu un continut egal noului cuvint, inseamna ca noul cuvint nu se afla in vreun nod al arborelui si deci trebuie creat unul. Procesul de cautare este inerent recursiv deoa rece cautarea din orice nod este legata de cautarea din unul din nodurile copii. In consecinta rrutinele pentru insertie si tiparire vor fi cele mai naturale.

Intorcindu-ne la descrierea unui nod, este clar o structura cu patru componente: struct tnode A /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */
S;

In general este ilegal ca o structura sa contina o parte a ei insusi, dar struct tnode *left; declara "left" ca fiind un pointer al nodului si nu nodul insusi.

Codul pentru intregul program este surprinzator de scurt si foloseste o multime de rutine ajutatoare pe care deja le-am scris. Acestea sint 'getword' pentru a aduce fiecare cuvint de la intrare si 'alloc' pentru a obinte spatiu pentru cuvinte in avans.

Rutina principala citeste cuvinte cu ajutorullui 'getword' si le instaleaza in arbore cu ajutorul lui 'tree'.

#define MAXWORD 20 main() /* word frequency count */
A struct tnode *root, *tree(); char wordaMAXWORDi; int t; root = NULL;
while ((t = getword(word, MAXWORD)) != EOF) if (t == LETTER) root = tree(root, word); treeprint(root);
S

Un cuvint este prezentat de catre rutina "main" la nivelul cel mai de sus(radacina) arborelui. La fiecare nivel cuvintul este comparat cu cuvintul aflat deja in nod si apoi este coborit in arbore fi e in subarborele din dreapta fie in cel din stinga printr-o apelare recursiva la "tree". Cuvintul nou fie are deja un corespondent in arbore in care caz contorul este incrementat, fie se ajunge la un pointer nul ceea ce indica necesitatea creearii unui nou nod in arbore. Daca este creat un nou nod "tree" returneaza un pointer care este instalatin nodul parinte. struct tnode *tree(p, w) /* install w at or below p */ struct tnode *p; char *w;
A struct tnode *talloc(); char *strsave(); int cond if (p == NULL) A /* a new word has arrived */ p = talloc(); /* make a new node */ p->word = strsave(w); p->count = 1; p->left = p->right = NULL;
S else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* repeated word */ else if (cond < 0) /* lower goes into left subtree */ p->left = tree(p->left, w); else /* greater into right subtree */ p->right = tree(p->right, w); return(p);
S

Memoria pentru noul nod este obtinuta de rutina "talloc" care este o adaptare a rutinei "alloc" scrisa mai devreme. Aceasta returneaza un pointer a unui spatiu liber utilizabil pentru un nod. ANoul cuvint este copiat in locul pregatit de catre
"strsave", contorul este initializat si cei doi copii sint facuti nuli. Aceasta parte a programului este executata numai la
"marginea" copacului cind un nou nod este de adaugat. Am omis intentionat controlul erorilor la valorile returnate de rutinele
"strsave" si "talloc".

Rutina "treprint" tipareste arborele incepind in ordine cu subarborele din stinga; in fiecare nod tipareste subarborele sting (toate cuvintele mai mici decit cel actual ), apoi cuvintul actual, apoi subarborele drept (toate cuvintele mai mari). Daca va simtiti cam nesiguri pe recursiune imaginativa singuri un arbore si tipariti-l cu "tree print"; este una dintre cele mai pure rutine recursive pe care o puteti gasi. treeprint(p) /* prnt tree p recursinely */ struct tnode *p;
A if (p != NULL) A treeprint(p->left); printf("%4d %s\n", p->count, p->word); treeprint(p->right);
S
S

O observatie practica; daca arborele devine dezechilibrat din cauza cuvintelor care nu sosesc intr-o ordine aleatoare, timpul de rulare al progarmului poate sa creeasca prea repede. In cel mai rau caz, daca cuvtele sosesc deja sortate acest program devinnnnn o alternativa neeconomicoasa a cautarii lineare. Exista generalizari ale arborelui care nu sufera de acest neajuns, dar pe care nu le putem descrie aici.

Inainte de a parasi acest exemplu merita o scurta digresiune asupra problemelor legate de alocarea de memorie. Clar, este dezirabil ca intr-un program sa fie folosit un singur alocator de memorie chiar daca aloca diferite feluri de obiecte. Dar daca un alocator trebuie sa satisfaca cereri pentru pointeri de caractere "char" sau de "struct tnode", daca se pun intrebari.
Prima, cum se satisface cerinta celor mai multe masini reale ca obiectele de diferite tipuri sa fie aliniate la adrese satisfacatoare(de exemplu intregii adesea trebuie aliniati pare)?
A doua, ce declaratii pot satisface faptul ca "alloc" in mod necesar returneaza diferite tipuri de pointeri ?

Cererile de aliniament pot fi usor satisfacute, cu pretul unor spatii neutilizate, asigurindu-ne ca alocatorul intodeauna returneaza pointeri care intrunesc toate restrictiile de aliniament. De exemplu pentru PDP-11 este suficient ca
"alloc" intodeauna sa returneze un "even" point, din moment ce orice tip de obiect poate fi memorat la o adresa "even". Masuri asemanatoare se iau pe alte masini. Astfel implementarea unui "alloc" poate sa nu fie portabila) dar usajul este.
"Alloc"-ul din capitolul 5 nu garanteaza nici un aliniament particular. In capitolul 8 vom prezenta modul de a face corect.

In legatura cu intrebarea asupra declaratiei tipului pentru
"alloc"; i"c" cea mai buna metoda este aceea de a dlara ca
"alloc" returneaza un pointer la "char" si apoi sa se converteasca ppoinerul in tipul dorit. Daca p este declarat astfel: char *p; atunci

(struct tnode *)p il converteste intr-unn "tnode" pointer dintr-o exepresie.

Astfel "talloc" devine: struct tnode *talloc()
A char *alloc(); return((struct tnode *) alloc(sizeof(strusct tnode)));
S

Aceasta este mai mult decit este nevoie pentru compilarile curente dar reprezinta cel mai sigur mod pentru viitor.

Exercitiul 6.4. Scrieti un program care citeste un program "c" si tipareste in ordine alfabetica fiecare grup al numelor de variaile care sint identice in primele 7 caractere dar diferite dupa aceea. (Asigurativa ca 7 este un parametru).

Exercitiul 6.5. Scrieti un porogram care tipareste o lista a tuturor cuvintelor dintr-un text si pentru fiecare cuvint o lista cu numerele liniei in care apar.

Exercitiul 6.6. Scrieti un program care tipareste cuvintele distincte, care sint introdues, in ordinea frecventei lor de aparitie. Fiecare cuvint sa fie precedat de numarul de aparitii.

6.6 Cautare in tabele

In aceasta sectiune vom da continutul unui pachet de cautare in tabel ca o ilustrare a mai multor aspecte legate de structuri. Amcest pachet este tipic pentru modul de explorare a unui tabel de simboluri pentru rutinele de management ale unui macroprocesor. De exemplu sa consideram declaratia din C,
"#define". Cind o linie ca

#define YES 1 este luata in considerare, numele YES si textul corespunzator 1 sint memorate intr-un tabel. Mai tirziu, cind numele YES apare intr- declaratie ca inword = YES; trebuie inlocuit cu 1.

Exista doua rutine majore care manipuleaza numele si textele de inlocuire corespunzatoare. "install(s, t)" inregistreaza numele "s" si textul de inlocuire "t" intr-o tabela; "s" si"t" sint siruri de caractere. "lookup(s)" cauta numele "s" intr-o tabela si returneaza un pointer la locul unde afost gasit ori NULL daca nu a fost gasit.

Algoritmul care se utilizeaza se bazeaza pe o cautare fragmentara "hash" un nume care se introduce este convertit intr-un intreg pozitiv care apoi este utilizat ca index intr-un tabloude pointeri. Un element al tablului pointeaza pe inceputul unui lant de balncuri care descriiu avind respectiva valoare de fragment ("hash"). Acesta este NULL daca nici un nume nu corespunde acestei valori.

Un bloc din lant este o structura care contine: pointeri, la nume, textul de inlocuire si urmatorul bloc din lant. Daca pointerul pentru urmatorul bloc este nul marcheaza sfirsitul lantului de blocuri. struct nlist A /* basic table entry */ char *name; char *def; struct nlist *next; /* next entry in chain */
S;

Tabloul de poiunteri este:

#define HASHSIZE 100 static struct nlist *hashtabaHASHSIZEi; /* pointer table */

Functia de fragmentare ("hashing"), care este utilizata de ambele rutine "lookup" si "install", aduna valorile carcterelor din sirul nume si formeaza restul modulo dimensiunea tabloului.
(Aceasta nu este cel mai bun algoritm posibil, darare meritul simplitatii. ) hash(s) /* form hash value for string s */ char *s;
A int hashval; for (hashval = 0; *s != '0';) hashval += *s++; return(hashval % HASHSIZE);
S

Procesul de fragmentare ("hashing") produce un index de cautare in "hashtab"; sirul de carctere cautat se va gasi intr-un bloc din sirul de blocuri a carui inceput este pointat de elementul din tabelul "hashtab". Cautarea este efectuata de rutina
"lookup". Dca "lookup" gaseste in "hashtab" intrarea deja prezenta, returneaza un pointer; daca nu, returneaza NULL. struct nlist *lookup(s) /* look for s in hashtab */ char *s
A struct nlist *up for (up = hashtabahash(s)i; up != NULL; up = up->next) if (strcmp(s, up->name) == 0) return(up); /*found it */ return(NULL); /* not found */

Rutina "install" foloseste "lookup" pentru a determina care dintre numele de instalat sint deja prezente; daca nu, o noua definire trebuie sa succeada uneia vechi. Altfel spus, o intrare complect noua este creeata. "install" returneza NULL daca dintr-un motiv oarecare nu mai este loc pentru o noua intrare. struct nlist *install(name, def) /*put(name, def) */ char *name, *def; /* in hashtab */
A struct nlist *np, *lookup(); char *strsave(), *alloc(); int hashval; if ((np = lookup(name)) == NULL) A /* not found */ np = (struct nlist *) alloc(sizeof(*np)); if (np == NULL) return(NULL); if ((np->name = strsave(name)) == NULL) return(NULL); hashval = hash(np->name); np->next = hashtabahashvali; hashtabahashvali = np;
S else /* already there */ free(np->def); /*free previous definition */ if ((np->def = strsave(def)) == NULL return(NULL); return(np);
S

"strsave" copiaza sirul furnizat de catre argumentul sasu intr_un loc obtinut cu un apel la functia "alloc". Am prezentat codul in capitolul 5 Deoarece apelurile la "alloc" si
"free" pot sa apara in orice ordine si deoarece aici aliniamentul conteaza, versiunea simpla a "alloc" de la capitolul 5, nu este adecvata aici vedeti capitolele 7 si 8.

Exercitiul 6.7. Scrieti o rutina care sa scoata un nume si definitia dintr-o tabela mentinuta cu "lookup" si "install".

Exercitiul 6.8. Implementati o versiune simpla a procesorului "#define" utilizabila in programe C, folosind rutinele din aceasta sectiune. Puteti gasi de ajutor si "getch" si
"ungetch".

6.7 Cimpuri

Atunci cind spatiul de memorare estre la mare pret, poate fi necesar ca mai multe obiecte sa fie impachetate intr-un singur cuvint masina; un caz adesea folosit este compactarea fanioanelor de un singur bit necesare in aplicatii catabelele de simboluri ale compilatoarelor. Formatele externe impuse de interfetele cu diversele echipamente externe, adesea impun compactrea datelor pe un cuvint.

Sa ne imaginam un fragment dintr-un compilator care manipuleaza o tabela de simboluri. Fiecare identificator dintr un program are anumite informatii asociate, de exemplu, este sau nu un cuvint cheie, e este sau nu extern si/sau static, s. a. m. d. Cel mai compact mod de a coda astfel de informatii este un set de fanioane de un bit cuprinse intr-un "char" sau "int".

Modul cel mai uzual este de a defini un set de masti corespunzatoare pozitiilor cu biti semnificativi, ca in

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

(Numele trebuie sa fie puteri ale lui doi.) Apoi accesul la biti devine un soi de "bitareala" cu operatori de permutare, mascare si complementare, care au foat descrisi in capitolul 2.

Anumite idioame apar frecvent: flags != EXTERNAL ! STATIC; valideaza bitii EXTERNAL si STATIC ca fanioane, in timp ce flags &= (EXTERNAL ! STATIC); ii invalideaza.

Desi aceste idioame sint cu usurinta manevrate, limbajul C, mai degraba ofera capacitatea preferabila de adefini si accesa cimpuri Un cimp este un set de biti adiacenti cuprinsi intr-un singur "int". Sintaxa de definire si accesul cimpurilor este bazata pe structuri. De exemplu tabela de simboluri definita mai sus ar putea fi inlocuita printr-o definire a trei cimpuri. struct A unsigned is_keyword: 1; unsigned is_extern: 1; unsigned is_static: 1;
Sflags;

Este astfel definita o variabila numita "flags" care contine trei cimpuri de cite un bit. Numarul de dupa ":" reprezinta lungimea cimpului in biti. Cimpurile sint declarate fara semn (unsigned) tocmai pentru a accentua ca sint cantitati fara semn.

Cimpurile individuale sint referite ca "flags.is_keyword",
"flags.is_extern", etc, la fel ca oricare alti me, bri ai structurii. Cimpurile se comporta ca niste mici intregi fara semn si pot participa in expresii aritmetice la fel ca oricare alti intregi. Exemplele de mai sus pot fi rescrise mai natural astfel flags.is_extern = flags.is_static = 1; pozitioneaza bitii pe unu; flags.is_extern = flags.is_static = 0; pozitioneaza bitii pe zero; if (flags.is_extern == 0 && flags.is_static == 0) ... pentru a-i testa.

Un cimp poate sa nu corespunda cu limitelke unui "int"; in acest caz cimpul este alinial la urmatoarea margine 'int".
Cimpurile nu trebuie sa aibe un nume; cimpurile fara nume(doua puncte si lungimea numai) sint folosite ca umplutura. Lungimea speciala 0 poate fi folosita pentru alinierea la urmatoarea
"int" margine.

Exista un numar de reguli de aplicat cimpurilor. Dintre cele mai importante, cipurile sint asignate de la stinga la dreapta in unele masini si de la dreapta la stinga in altele ceea ce reflecta natura diferita a hardwareului inseamna ca, desi cipurile sint utilizabile de preferinta pentru a intretine structurile de adte interne, chestiunea carui sfirsit vine primul trebuie considerata cu grija pentru prelucrarea datelor definite extern.

Alte restrictii care trebuie avute in minte: cimpurile sint fara semn ele pot fi memorate numai in "int"(sau echivalentul
"unsigned"); ele nu sint tablouri; ele nu au adrese, astfel ca operatorul "&" nu le poate fi aplicat.

6.8 Uniuni

O uniune este o varaibila care poate pastra (la momente diferite) obiecte de diferite tipuri si dimensiuni, iar compilatorul tine seama de cerintele de dimensiune si aliniament. Uniunile permit sa se manipuleze diferite feluri de date intr-o singura zona de memorie, fara sa se includa in program nici un fel de informatii dependente de masina.

Ca de exemplu, sa consideram din nou o tabela de simboluri a unui compilator. Sa presupunem ca constantekle pot fi "int",
"float" sau pointeri de caractere. Valoarea unei constante particulare trebuie memorata intr-o variabila de tipul corespunzator, dar este cel mai convenabil pentru organizarea tabelei daca valoarea ocupa aceasi dimensiune de memorie si acelasi loc in memorie in functie de tipul ei. Aceasta este scopul unei uniuni -sa permita ca o singura variabila care poate sa contina oricare din mai multe tipuri. La fel ca la cimpuri, sintaxa se bazeaza pe structuri. union u-tagA int ival; float fval; char *pval;
S uval;

O variabila "uval" va fi suficient de mare ca sa pastreze oricare din cele trei tipuri, iar privitor la masina, codul generat de compilator este indiferent de caracteristicile hard. Oricare din aceste tipuri poate fi asignat la "uval" si apoi utilizat in expresii, atita vreme cit uzajul este considerat, adica tipul utilizat trebuie sa fie cel mai recent memorat. Este responsabilitatea programatorului sa tina seama de tipul de data curent memorat intr-o uniune; rezultatele sint dependente de masina daca ceva este memorat ca un tip si este extras ca altul.

Sintactic, membri unei uniuni sint accesati ca union-name.member sau union-pointer->member la fel cu structurile. Daca variabila "utype" este folosita pentru a tine seama de tipul curent al marimii memorate in "uval", poate scrie un cod, astfel: 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("bad type %d in utype\n", utype);

Uniunile pot sa se gaseasca in structuri si tablouri si viceversa. Notatia pentru a accesa un membru a unei uniuni dintr-o structura(sau viceversa) este identica cu aceea pentru structurile in cuiburi. De exemplu in structura definita prin struct A char *name; int flags; int utype; union A int ival; float fval; char *pval;
S uval;
S symtabaNSYMi; variabila "ival" este referita astfel symtabaii.uval.ival iar primul caracter al sirului "pval" prin

*symtabaii.uval.pval

In fond, o uniune este o structura in care toti membri au deplasamentul zero, structura este suficient de mare ca sa cuprinda cel mai mare membru, iar aliniamentul este potrivit pentru toate tipurile din uniune Ca si la structuri singurele operatii admise cu uniunile sint de a accesa un membru si obtinerea adresei lui;uniunile nu pot fi asignate, nu se pot aplica functii asupra lor, Pointeri la uniuni pot fi utilizati de o maniera identica pinterilor la structuri.

In capitolul 8 se arata cum alocatorul de memorie prin intermediul unei uniuni de memorie prin intermediul unei uniuni forteaza o variabila sa se alinieze la orice fel de particularitati de memorare.

6.9. Typedef

C admite o facilitate numita typedef pentru a crea nume pentru noi tipuri de date. De exemplu declaratia: typedef int LENGTH; face numele LENGTH sinonim pentru "int". Tipul LENGTH poate fi utilizat in declaratii exact la fel ca int:

LENGTH len, maxlen;
LENGTH *lengthsai;

Similar, declaratia: typedef char*STRING; face ca STRING sa fie sinonim cu char* sau pointerul unui caracter, care poate fi utilizat in declaratii ca:

STRING p, lineptraLINESi, alloc();

Observati ca tipul fiind declarat printr-un typedef apare in pozitia unui nume de variabila. Sintactic, typedef este ca o clasa de memorie, extern, static, etc. In cazul de mai sus am utilizat litere pentru a accentua numele.

Ca de exemplu mai complicat putem folosi typedef pentru nodurile copacului prezentat mai inainte in acest capitol: typedef struct tnode A /* the basic node */ char *word; /* points to the text */ int count; /* number of occurrences */ struct tnode *left; /* left child */ struct tnode *right; /* right child */
S TREENODE, *TREEPTR;

Aceasta creeaza doua noi tipuri de cuvinte cheie numite TREENODE
(o structura) si TREEPTR (un pointer la structura), dupa care rutina "talloc" poate deveni:

TREEPTR talloc()
A char *alloc(); return((TREEPTR) alloc(sizeofTREENODE)));

Trebuie sa specificam ca un typedef nu creaza noi tipuri; mai degraba renumeste tipurile existente. Variabilele astfel declarate au exact aceleasi proprietati ca si variabilele a caror declaratii sint explicite. In fond, typedef este ca un
#define, exceptind ca, de cind este interpretat de copilator el face fata cu substitutiile in text care sint dincolo de capacitatile C macro procesorului. De exemplu: typedef int (*PFI) (); creaza tipul PFI, care poate fi utilizat intr-un context ca

PFI strcmpp, numcmp, swap; din programul de sort din capitolul 5.

Exista doua motive mai importante pentru a utiliza declaratiile t9pedef. Primul este de a parametrizaun program alaturi de problemele de portabilitate. Daca pse utilizeza typedef pentru diferite tipuri de date care pot fi dependente de masina, numai typedef necesita modificari daca programul este mutat pe alta masina. O situatie obisnuita este de a folosi typedef pentru cantitati intregi variate, cind se alcatuieste un set adecvat de
"short", "int" si "long" pentru fiecare masina.

Un al doilea scop a lui typedef este de a da mai mare claritate unui program numit TREEPTR este mai usor de inteles decit unul declarat ca un simplu pointer la o structura complicata.

In final, exista deja posibilitatea ca in viitor, compilatorul sau * un alt program ca "lint" sa faca uz de informatia continuta in typedef ca sa execute niste controale in plus asupra programului.

CAPITOLUL 6.STRUCTURI

O structura este o colectie de una sau mai multe variabile care pot fi de tipuri diferite, grupate impreuna sub un singur nume pentru o manipulare convenabila. (Structurile sint anumite "inregistrari" in unele limbaje, de exemplu in PASCAL.)

Exemplul traditional de structura este inregistrarea personala: un salariat este descris prin citeva atribute ca numele, adresa, salariu etc. Fiecare din atribute la rindul lor pot fi structuri: numele are mai multe componente, adresa de asemenea, salariul de baza s.a.m.d.

Structurile ajuta la organizarea datelor complicate, mai ales in programele de mari dimensiuni, deoarece in multe situatii ele permit ca un grup de variabile inrudite sa fie tratate unitar si nu ca entitati separate. In acest capitol vom incerca sa ilustram cum sint utilizate structurile. Programele pe care le vom folosi in acest scop sint mai mari decit multe altele din manualul acesta, dar inca de dimensiuni modeste.

6.1. Bazele

Sa ne reamintim rutinele de conversie a datei din capitolul 5. O data consista din mai multe parti, precum ziua, luna, anul si probabil ziua din an si numele lunii. Aceste cinci variabile pot fi toate plasate intr-o singura structura ca aceasta: struct date A int day; int month; int yearday; char mon_namea4i;
S

Cuvintul cheie "struct" introduce o structura de date, care este o lista de declartii cuprinsa intre acolade. Un nume optional (eticheta) numit "structure tag", poate sa urmeze cuvintul cheie "struct"(precum date in exemplul de mai sus).
Aceasta eticheta da un nume acestui gen de structura si poate fi referita in continuare ca prescurtare de declaratie detaliata.

Elementele sau variabilele mentionate intr-o structura sint numite
"membri". Un membru al structurii sau o eticheta a unei structuri sau o variabila simpla pot avea acelasi nume fara ambiguitate deoarece se disting prin context. Desigur se va utiliza acelasi nume doar pentru a defini obiecte in strinsa relatie.

Acolada din dreapta care inchide lista membrilor structurii poate fi urmata de o lista de variabile ca in exemplul de mai jos: struct A...S x, y, z; ceea ce este sintactic analog cu: int x, y, z; in sensul ca fiecare declaratie numeste pe x, y, z si z ca variabile de tipul specificat si aloca spatiu pentru fiecare din ele.

O declaratie de structura care nu este urmata de o lista de variabile nu aloca spatiu de memorie ci descrie doar forma sau organizarea structurii. Daca structura este nominalizata, numele poate fi utilizat in program pentru atribuirea de valori structurii. De exemplu: struct date d; defineste o variabila d care are o structura de tip data, si poate fi initializata la un moment dat conform definitiei sale cu o lista ca mai jos: struct date d =A4, 7, 1776, 186, "Jul" S;

Un membru a unei structuri particulare poate fi referit intr-o expresie printr-o constructie de forma:

"numestructura.membru"

Operatorul "." din constructia de mai jos leaga numele membrului de numele structurii. De exemplu pentru a afla un an bisect din structura d se refera la membrul "year" astfel: leap = d.year % 4 == 0 && d.year % 100 != 0 || d.year % 400 == 0;

sau pentru a testa numele liniei din membrul "mon" if (strcmp(d.mon_name, "Aug") == 0) ... sau pentru a converti numele lunii la litere mici d.mon_namea0i = lower(d.mon_namea0i);

O structura poate sa cuprinda structuri, de exemplu: struct person A char nameaNAMESIZEi; char addressaADRSIZEi; long zipcode; long ss-number; double salary; struct date birthdate; struct date hiredate;
S;

Structura "person" contine doua structuri de tip data ("birthdate" si "hiredate"). Daca declaram "p" astfel struct person emp; atunci o constructie emp.birthdate.month se va referi la luna din data nasterii. Operatorul "." asociaza partea stinga cu dreapta.

6.2. Structuri si functii

Exista un numar de restrictii relative la structurile in C.
Regulile esentiale sint ca nu puteti face asupra unei structuri decit operatia de obtinere a adresei cu &, si de accesare a unuia dintre membrii structurii. Acest lucru presupune ca structurile nu pot fi asignate sau copiate ca un tot unitar, si ca nu pot fi nici pasate sau returnate intre functii. (Aceste restrictii vor fi ridicate in versiunile viitoare.) Pointerii la structuri nu se supun insa acestor restricti, si de aceea structurile si functiile coopereaza confortabil. In fine, structurile automate, ca si tablourile automate, nu pot fi initializate; nu pot aceasta decit stucturile statice.

Sa vedem citeva din aceste probleme rescriind functiile de conversie de data din capitolul precedent, folosind structuri.
Deoarece regulile interzic pasarea de structuri direct unei functii, trebuie fie sa pasam componentele separat, fie sa pasam un pointer catre intregul obiect. Prima alternativa se foloseste de day_of_year asa cum am scris in capitolul 5: d.yearday = day_of_year(d.year, d.month, d.day);

Celalalt mod este de a pasa un pointer. Daca am declarat pe hiredate ca: struct date hiredate; si am rescris pe day_of_year, putem apoi spune: hiredate.yearday = day-of-year(&hiredate); deci pointerul lui "hiredate" trece la "day-of-year". Acum functia trebuie sa fie modificata deoarece argumentul sau este un pointer si nu o lista de variabile. day-of-year(pd) /* set day of year from month, day */ struct date *pd;
A 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_tabaleapiaii; return(day);

S

Declaratia "struct date *pd;" spune ca pd este un pointer la o structura de tip data. Notatia "pd->year" este noua. Daca p este pointer la o structura, atunci p->member-of-structure refera un membru particular. (Operatorul -> este un minus urmat de >.) Cu ajutorul pointerului pd poate referit si un membru al structurii, de exemplu membrul "year":

(*pd).year

Deoarece pointerii la structuri sint des utilizati este preferabila folosirea operatorului ->, forma mai scurta. In constructia de mai sus parantezele sint necesare deoarece operatorul "." este prioritar fata de "*". Atit "->" cit si "." se asociaza de la stinga la dreapta astfel: p->q->memb emp.birthdate.month sint

(p->q)->memb
(emp.birthdate).month

Pentru completare dam o alta functie "month-day" rescrisa folosind structurile. month-day(pd) /* set month and day from day of year */ struct date *pd;
A int i, leap; leap = pd->year % 4 == && pd->year % 100 != 0 || pd->year % 400 == 0; pd->day = pd->yearday; for (i = 1; pd->day > day_tabaleapiaii; i++) pd->day -= day_tabaleapiaii; pd->month = i;
S

Operatorii de structura "->" si ". " impreuna cu "()" pentru liste si "ai" pentru indici in ierarhia prioritatilor sint cei mai puternici. De exemplu la declaratia: struct A int x; int *y;
S *p; atunci ++p->x incrementeaza pe x si nu p, deoarece ordinea implicita este ++(p->x). Parantezele pot fi utilizate pentru a modifica prioritatile: (++p)->x incrementeaza p inainte de a accesa x, iar (p++)->x incrementeaza p dupa aceea. (Acest ultim set de paranteze nu este necesar. De ce ?)

In acelasi sens, *p->y aduce ceea ce pointeaza y; *p->y++ incrementeaza y dupa ce se face accesul la ceea ce pointeaza y (la fel cu *s++); (*p->y)++ incrementeaza ceea ce pointeaza y; si *p++->y incrementeaza p dupa accesul la ceea ce pointeaza y.

6.3. Tablouri de structuri

Structurile sint in special utile pentru manevrarea tablourilor de variabile inrudite. Pentru exemplificare sa consideram un program pentru a numara fiecare aparitie a cuvintului cheie C.
Avem nevoie de un tablou de siruri de caractere pentru a pastra numele si un tablou de intregi pentru contoare. O posibilitate este folosirea in paralel a doua tablouri unul pentru cuvinte cheie si unul pentru contoare, astfel char *keywordaNKEYSi; int keycountaNKEYSi;

Dar insasi faptul ca se folosesc doua tablouri paralele indica posibilitatea unei alte organizari. Fiecare acces de cuvint cheie este de fapt o pereche: char *keywordd int keycount ceea ce de fapt este un tablou de perechi. Urmatoarea declaratie de structura: struct key A char *keyword; int keycount;
S keytabaNKEYSi; defineste un tablou "keytab" de structuri de acest tip si ii aloca memorie.
Fiecare element al tabloului este o structura. Aceasta se mai poate scrie: struct key A char *keyword; int keycount;
S; struct key keytabaNKEYSi;

De fapt structura "keytab" contine un set constant de nume care cel mai usor se poate initializa o singura data cind este definita. Initializarea structurii este analoaga cu initializarile prezentate mai devreme -definitia este urmata de o lista de initializatori cuprinsi intre acolade: struct key A char *keyword; int keytab;
S keytabai =A
"break", 0,
"case", 0,
"char", 0,
"continue", 0,
"default", 0,
/*...*/
"unsigned", 0,
"while", 0
S;

Initializatorii sint listati in perechi corespunzind membrilor structurii. Ar fi mai precis ca initializatorii pentru fiecare "sir" sau structura sa fie cuprinsi intre acolade:

A"break", 0S,
A"case", 0S,
... dar acoladele in interior nu sint necesare atunci cind initializatorii sint simple variabile sau siruri de caractere si cind toate sint prezente. Ca de obicei compilatorul va calcula numarul de intrari in tabloul "keytab" daca initializatorii sint prezenti iar "ai" este lasat gol.

Programul de numarare a cuvintelor cheie incepe prin definirea lui "keytab". Rutina principala citeste intrarea prin apeluri repetate a functiei "getword" care la o apelare citeste un cuvint. Fiecare cuvint este cautat in "keytab" cu ajutorul unei versiuni a functiei de cautare linia ra descrisa in capitolul 3.
(Bineinteles lista de cuvinte cheie trebuie sa fie in ordine crescatoare pentru ca treaba sa mearga).

#define MAXWORD 20 main() /* count c keywords */
A int n, t; char wordaMAXWORDi;
while ((t = getword(word, MAXWORD)) != EOF) if (t == LETTER) if ((n = binary(word, keytab<NKEYS)) >= 0) keytabani.keycount++; for (n = 0; n < NKEYS; n++) if (keytabani, keycount > 0) printf("%4d %s\n", keytabani.keycount, keytabani.keyword);
S binary(word, tab, n) /* find word in taba0i...taban-1i */ char *word; struct key tabai; int n;
A int low, high, mid, cond; low = 0 high = n - 1
while (low <= high) A mid = (low + high) / 2; if ((cond = strcmp(word, tabamidi.keyword)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return(mid);
S return(-1);
S

In curind vom prezenta si functia "getword"; pentru moment este suficient sa spunem ca ea returneaza LETTER de atitea ori cind gaseste un cuvint si copiaza cuvintul in primul ei argument.

Cantitatea NKEYS este numarul de cuvinte cheie din "keytab".
Desi am putea sa numaram acestea manual, este mult mai usor si mai sigur sa facem aceasta cu ajutorul masinii in special daca lista este subiectul unei posibile schimbari. O posibilitatea ar fi sa incheiem lista de initializatori cu un pointer nul si apoi sa buclam in "keytab" pina este detectat sfirsitul.

Dar aceasta este mai mult decit este necesar, deoarece dimensiunea tabloului este complect determinata in momentul compilarii. Numarul de intrari este: dimensiunea lui keytab/dimensiunea lui struct key

C obtine un timp de compilare operator unar numit "sizeof" care poate fi folosit la calcularea dimensiunii oricarui obiect.
Expresia sizeof(object) livreaza un intreg egal cu dimensiunea obiectului specificat
Dimensiunea este data in unitati nespecificate numite "bytes", care au aceeasi dimensiune ca si "char") Obiectul poate o variabila actuala sau tablou sau structura, ori numele unui tip de baza ca "int" sau "double" ori numele unui tip derivat ca o structura. In cazul nostru numarul de cuvinte cheie se obtine prin impartirea dimensiunii tabloului la dimensiunea unui element detablou. Acest calcul se face uzind o declaratie
"#define" setind valoarea in NKEYS:

#define NKEYS (sizeof(keytab) / sizeof(struct key))

Si acum asupra functiei "getword". De fapt noi am scris un
"getword" mai complicat decit era necesar pentru acest program, dar nu mult mai complicat. "getword" returneaza urmatorul
"word" de la intrare, unde "word" este fie un sir de litere si cifre incepind cu o litera fie un un singur caracter. Tipul obiectului este returnat ca o valoare a unei functii; aceasta este LETTER daca e vorba de un cuvint, EOF daca este sfirsitul fisierului si este caracterul insusi daca este un caracter non alfabetic. getword(w, lim) /* get next word from input */ char *w; int lim;
A int c, t; if (type(c = *w++ =getch()) != LETTER) A
*w = '\0'; return(c);
S
while (--lim > 0) A t = type(c = *w++ = getch()); if (t != LETTER && t != DIGIT) A ungetch(c); break;
S
S
*(w-1) = '\0'; return(LETTER);
S

"getword" utilizeaza rutinele "getch" si "ungetch" despre care am scris in capitolul 4: cind colectia de caractere alfabetice se termina, "getword" a depasit deja cu un caracter sirul. Apelarea lui "ungetch" repune un caracter inapoi la intrare pentru urmatorul acces.

"getword" apeleaza "type" pentru a determina tipul fiecarui caracter de la intrare. Iata o versiune numai pentru alfabetul
ASCII. type(c) /* return type of ascii character */ int c;
A if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') return(LETTER); else if (c >= '0' && c <= '9') return(DIGIT); else return(c);

Constantele simbolice LETTER si DIGIT pot avea orice valori care nu sint in conflict cu caracterele nonalfabetice si EOF;
ALegerile evidente sint:

#define LETTER 'a'
#define DIGIT0'

"getword" poate fi mai rapid daca apelurile la functia "type" sint in locuite cu apeluri corespunzatoare tablourilor, typeai.
Biblioteca standard C contine macrouri numite "isalpha" si
"isdigit" care opereaza de aceasta maniera.

Exercitiul 6.1. Faceti aceste modificari la "getword" si determinati modificarile de viteza ale programului.

Exercitiul 6.2. Scrieti o versiune de "type" care este independenta de setul de caractere.

Exercitiul 6.3. Scrieti o versiune a programului de numarare a cuvinte care nu numara aparitiile continute intre apostrofi.

6.4. Pointeri la structuri

Pentru a ilustra citeva din consideratiile referitoare la pointeri si tablouri de structuri sa rescriem programul de contorizare a cuvintelor cheie, de data aceasta folosind pointerii in loc de indici.

Declaratia externa "keytab" nu necesita modificari, dar
"main" si "binary" necesita. main() /* count keywords; pointer version */
A int t; char wordaMAXWORDi; 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 struct key *binary(word, tab, n) /* find word */ char *word; /* in taba0i...taban-1i */ struct key tabai; int n;
A int cond; struct key *low = detaba0i; struct key *high = ftaban-1i; struct key *mid;
while (low <= high) A 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);
S return(NULL);
S
Aici sint mai multe chestiuni de notat. Prima, declaratia
"binary" trebuie sa indice ca e returneaza un pointer structurii tip "key" in locul unui intreg. Acesta este declarat in "main" cit si in "binary". Daca "binary" gaseste cuvintul, returneaza un pointer; daca acesta lipseste, returneaza NULL.

A doua, orice acces la elementele lui "keytab" sint facute prin pointeri. Aceasta determina o schimbare semnificativa in
"binary calculul poate fi simplu. mid = (low + high) / 2 deoarece adunarea a doi pointeri nu va produce nici un fel de raspuns utilizabil si de fapt este ilegala. Aceasta trebuie schimbata in mid = low + (high - low) / 2 care seteaza "mid" in punctul de la jumatatea intre "low" si
"high".

Ar trebui sa studiati si initializatorii pentru "low" si "high"
Este posibil sa se initializeze un pointer la adresa unui obiect definit dinainte; aceasta am facut noi aici.

In "main" am scris: for (p = keytab; p < keytab + NKEYS; p++)

Daca p este un pointer la structura, orice operatie aritmentica asupra lui p tine cont de dimnesiunea actuala a structurii, astfel p++ incrementeaza p cu cantitatea corecta pentru a obtine urmatorul element al tabloului de structuri. Dar sa nu credeti ca dimensiunea structurii este suma dimensiunilor membrilor sai deoarece aliniamentul cerut pentru diferiti membri pot determina aparitia de "gauri" in structura.

Si in final o consideratie asupra formatului programului.
Cind o functie f returneaza un tip complicat ca in: struct key *binary(word, tab, n) numele functiei este dificil de vazut si de gasit cu un editor de texte De aceea un alt stil este citeodata folosit. struct key * binary(word, tab, n)

Aceasta este mai mult o chestiune de gust personal; luati forma pe care o doriti si tineti-va de ea.

6.5 Structuri cu autoreferire

Sa presupunem ca vrem sa tratam problema numararii aparitiei cuvintelor in modul cel mmai general adica sa numaram fiecare aparitie a fiecarui cuvint la o intrare. Deoarece lista de cuvinte nu este cunoscuta in avans nu putem sa o sortam convenabil si sa folosim o cautare liniara. Inca nu putem sa efectuam o cautare liniara pentru fiecare cuvint in momentul cind soseste pentru a vedea daca a mai aparut deoarece perogramul ar dura foarte mult. (Mai precis, timpul de rulare ar creste cu patratul numarului de cuvinte introduse. ) Cum putem organiza datele pentru a face fata in mod eficient cu o lista de cuvinte arbitrare?

O solutie ar fi sa pastram setul de cuvinte sortat in orice moment plasind fiecare cuvint in pozitia adecvata in momentul sosirii lui. Aceasta n-ar terebui facut prin mutarea cuvintelor intr-un tablou linear deoarece si aceasta ia un timp prea lung. In loc vom utiliza o structura de date numita "binary tree" adica arborele binar.

Arborele contine un "node" pentru fiecare cuvint distinct; fiecare nod contine: un pointer la textul cuvintului un contor al numarului de aparitii un pointer la nodul-copil din stinga un pointer la nodul-copil din dreapta

Nici un nod nu poate avea mai mult de doi copii. Ar trebui sa aiba numai zero sau unu.

Nodurile sint astfel mentinute incit subarborele din stinga contine numai cuvinte care sint mai mici decit cuvintele din nodul considerat, iar subarborele din dreapta numai cuvinte care sint mai mari. Pentru a afla daca un nou cuvint se afla in arbore se incepe comparatia de la nodul radacina. Daca ele sint egale chestiunea este rezolvata Daca noul cuvint este mai mic decit cuvintul din nodul radacina cercetarea continua la nodul copil din stinga; altfel este investigat nodu