Capitolul 6.3. Tablouri de structuri

Vezi subiectul anterior Vezi subiectul urmator In jos

Capitolul 6.3. Tablouri de structuri

Mesaj  zooky la data de Mier Mar 18, 2009 1:53 pm

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 *keyword[NKEYS];
int keycount[NKEYS];

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 {
char *keyword;
int keycount;
} keytab[NKEYS];

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 {
char *keyword;
int keycount;
};
struct key keytab[NKEYS];

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 {
char *keyword;
int keytab;
} keytab[] ={
"break", 0,
"case", 0,
"char", 0,
"continue", 0,
"default", 0,
/*...*/
"unsigned", 0,
"while", 0
};

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

{"break", 0},
{"case", 0},
...

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 "[]" 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 */
{
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);
}
binary(word, tab, n) /* find word in tab[0]...tab[n-1] */
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);
}

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;
{
int c, t;
if (type(c = *w++ =getch()) != LETTER) {
*w = '\0';
return(c);
}
while (--lim > 0) {
t = type(c = *w++ = getch());
if (t != LETTER && t != DIGIT) {
ungetch(c);
break;
}
}
*(w-1) = '\0';
return(LETTER);
}

"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;
{
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, type[]. 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.
avatar
zooky
Moderator
Moderator

Numarul mesajelor : 147
Data de inscriere : 15/03/2009
Varsta : 24
Localizare : Cernatesti City

Vezi profilul utilizatorului http://e-learning.forumhit.ro

Sus In jos

Vezi subiectul anterior Vezi subiectul urmator Sus


 
Permisiunile acestui forum:
Nu puteti raspunde la subiectele acestui forum