.pl 60 .po 12 .mt 2 .mb 2 .pn 103 KAPITOLA 6. STRUKTURY ---------------------- S t r u k t u r a je sestava jedne nebo vice promennych stejneho nebo ruzneho typu. Je oznacena jednim jmenem, aby se s ni dalo dobre zachazet. /Struktury jsou nekdy nazyvany "rekordy" napr. v PASCALU./ Klasickym prikladem jsou osobni data zamestnancu na vy- platni listine. "Zamestnanec" je popsan mnozinou atributu, jako je jmeno, adresa, rodne cislo, plat atd. Nektere z polo- zek mohou byt opet struktury: jmeno ma vice slozek, adresa a plat take. Struktury pomahaji organizovat slozita data speci- alne v rozsahlych programech, protoze v mnoha situacich umoznu- ji, aby s celou soustavou dat bylo nakladano jako s jednou promennou. V teto kapitole popiseme, jak se pouzivaji struktury. Programy budou vetsi nez ty, ktere jsme dosud poznali, ale budou jeste stale v rozumne velikosti. 6.1 Zaklady ------------- Podivejme se znova na program z kapitoly 5 zabyvajici se datem. Datum je slozeno z ruznych casti: den, mesic, rok a den v roce a popr. jmeno mesice. Techto pet udaju muze byt ulozeno do jedne struktury: struct date { int day; int month; int year; int yearday; char mon_name [4]; }; Klicove slovo struct uvadi deklaraci struktury, ktera je seznamem deklaraci, vlozenych do zavorek. Nepovinnym para- matrem muze byt jmeno, nazyvane oznaceni struktury /tag/. Je uveden za slovem struct. V nasem prikladu je to jmeno date. Oznaceni struktury oznacuje strukturu a muze byt pouzito jako zkratka pro podobnou deklaraci. Prvky nebo promenne uvedene ve strukture jsou nazyvany jejimi c l e n y . Clen struktury nebo jeji oznaceni muze byt shodne se jmenem obycejne promenne, protoze muze byt vzdy odliseno podle kontextu. Ovsem vhodne je pouzivat shodne nazvy pouze pro uzce svazane veliciny. Prava zavorka ukoncuje seznam clenu a za ni muze nasle- dovat seznam obycejnych promennych. Tj. struct (...) x, y, z; je z hlediska syntaxe identicke s int x, y, z; Deklarace struktury, za kterou nenasleduje seznam clenu, Š.po 3 nealokuje zadnou pamet. Popisuje pouze "sablonu" struktury. Jestlize je struktura oznacena jmenem, tak jmeno muze byt pouzito pro definici aktualnich objektu struktury. Napr. mame-li danu deklaraci struktury date, potom struct date d; definuje promennou d, ktera je strukturou typu date. Struk- tura typu static nebo external muze byt inicializovane. struct date d = {4,7,1776,186,"Jul"}; Clen struktury muze byt dosazen takto: oznaceni struktury. jmeno Operator clenu struktury "." spojuje jmeno struktury s jejim clenem. Napr. nastaveni promenne leap z data struktury muze byt provedeno takto: leap = d.year % 4 == 0 && d.year % 100 != 0 || d.year % 400 == 0; Kontrola nazvu mesice if (strcmp(d.mon_name, "Aug") == 0) ... nebo konvertovani prvniho znaku mesice na male pismeno d.mon_name [0] = lower (d.mon_name[0]; Struktury mohou byt vkladany do sebe. Data zamestnance mohou vypadat takto struct person { char name [NAMESIZE]; char address [ADRSIZE]; long zipcode; long ss number; double salary; struct date birthdate; struct date hiredate; }; Struktura person obsahuje dva datumy. Jestlize budeme deklaro- vat emp jako struct person emp; potom emp.birthdate.month udava mesic narozeni. Operator "." pracuje zleva doprava. Š.po 12 6.2 Struktury a funkce ----------------------- V jazyku C existuji omezeni pro struktury. Zakladnim pravi- dlem je to, ze jedine operace, ktere muzeme se strukturami provadet, je zjisteni adresy operatorem & a pristup k jejim clenum. Z toho plyne, ze struktury nemohou byt prirazovany nebo kopirovany jako obycejne promenne a nemohou byt predavany jako parametry. /Tato omezeni budou v dalsi verzi jazyka C odstraneny./ Pointry na struktury nemaji tato omezeni, takze struktury a funkce mohou dobre spolupracovat. Automaticke struktury stejne jako automaticka pole nemohou byt inicializo- vany. Nektere z techto zaveru si overime pri prepsani funkce pro konverzi data z predchozi kapitoly. Protoze neni mozne predavat struktury funkcim primo, musime bud predavat jedno- tlive prvky nebo pointry na struktury. Prvni varianta pouziva funkci day_of_year z kapitoly 5: d.yearday = day_of_year(d.year, d.month, d.day); Druhy zpusob je predani pointru. Jestlize jsme deklarovali hiredate jako struct date hiredate; a prepsali funkci day_of_year, muzeme napsat hiredate.yearday = day_of_year (&hiredate); Funkce musi byt modifikovana, protoze jejim argumentem je nyni pointr a ne seznam promennych day_of_year(pd) /*vypocet dne roku z mesice a dne*/ struct date *pd; { 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] [i]; return (day); } Deklarace struct date *pd urcuje, ze pd je pointr na strukturu typu date. Notace pd -> year je novinkou. Jestlize p je pointr struktury potom p -> clen struktury Š.po 3 ukazuje na urcity clen. Operator sestava ze znamenka minus a >. Protoze pd je pointr na strukturu, tak clen year muze byt dosazen take takto (*pd).year Pointry na struktury jsou casto pouzivany a tak operator -> je vyhodnou zkratkou. Ve vyrazu (*pd).year jsou zavorky nezbytne, protoze operator "." ma vyssi prioritu nez *. -> a . pracuji zleva doprava p -> q -> memb je emp.birthdate.month (p -> q) -> memb je (emp.birthdate).month month_day (pd) /*vypocet mesice a dne ze dne roku*/ struct date *pd; { int i, leap; leap = pd -> year % 4 == 0 && pd -> year % 100 != 0 || pd -> year % 400 == 0; pd -> day = pd -> yearday; for (i = 1; pd -> day_tab[leap] [i]; i++) pd -> day -= day_tab[leap] [i]; pd -> month = i; } Operator -> a ., spolu s () pro seznam argumentu a [] pro indexy maji ze vsech operatoru nejvyssi prioritu. Napr. mame-li danu deklaraci struct { int x; int *y; }*p; potom ++p -> x zvetsuje x a ne p, protoze prikaz je vykonan takto: ++(p -> x). Pro zmenu priority mohou byt pouzity zavorky: (++p) -> x zvetsuje p pred dosazenim x a (p++) -> x zvetsuje p potom. /Tyto posledni zavorky jsou zbytecne. Proc?/ Stejnym zpusobem *p -> y vybira to, na co ukazuje y: *p -> y++ zvetsuje y po dosazeni objektu /prave tak jako *s++/. (*p -> y)++ zvesuje to, na co ukazuje y. *p++ -> y zvetsuje p po dosazeni toho, na co ukazuje y. .pa Š.po 12 6.3 Pole struktur ----------------- Struktury jsou vyhodne hlavne pro operace s poli pro- mennych. Napr. uvazujme program, ktery zjistuje vyskyt klico- vych slov jazyka C. Potrebujeme pole znakovych retezcu, ktera budou obsahovat jmena a pole cisel int, kde bude ukladan pocet. Jednou z moznosti je pouziti dvou paralelnich poli - keyword a keycount: char *keyword [NKEYS]; int keycount [NKEYS]; Prave fakt, ze jsou pole paralelni indikuje to, ze by byla mozna jina organizace. Kazdy prvek je vlastne par: char *keyword; int keycount; Deklarace struktury struct key { char *keyword; int keycount; } keytab [NKEYS]; Pole keytab alokuje pamet. Kazdy prvek pole je strukturou. To muze byt napsano takto struct key { char *keyword; int keycount; }; struct key keytab [NKEYS]; Protoze struktura keytab obsahuje ve skutecnosti konstan- tni soubor jmen, je usnadnena inicializace. Inicializace struktury je podobna predchozim - definici nasleduje seznam vlozeny do zavorek: struct key { char *keyword; int keycount; } keytab [] = { "break", 0, "case", 0, "char", 0, "continue", 0, "default", 0, /* ... */ Š.po 3 "unsigned", 0, "while", 0 }; Inicializace je provedena pary odpovidajicimi strukture clenu. Bylo by presnejsi vkladat patricne pary do zavorek ("break", 0) ("case", 0) ... ale neni nutne, protoze v nasem pripade jsou to jednoduche promenne a znakove retezce. Jako obvykle prekladac zjisti pocet clenu z inicializace a zavorky [] mohou zustat prazdne. Program pro zjistovani poctu klicovych slov zacina deklaraci keytab. Hlavni program cte vstup opakovanym volanim funkce getword, ktera nacita ze vstupu vzdy jedno slovo. Pro kazde slovo je prohledana tabulka keytab pomoci funkce pro binarni hledani, kterou jsme uvedli v kapitole 3. /Sez- nam klicovych slov muze byt usporadan vzestupne./ #define MAXWORD 20 main() /* pocitej klicova slova */ { 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) /*najdi slovo v 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); Š.po 12 } Na chvili se zastavime u funkce getword. Pro zacatek staci rici, ze vraci LETTER pokazde, kdyz nalezne slovo. Toto slovo kopiruje do prvniho argumentu. NKEYS udava pocet klicovych slov v tabulce keytab. Prestoze bychom ho mohli snadno zjistit sami, je lepsi to ne- chat na pocitaci, zvlaste bude-li se program jeste menit. Rozsah pole je uz znam v dobe prekladu. Pocet prvku je rozmer keytab /rozmer struct key Existuje unarni operator sizeof, ktery muze byt pouzit pro urceni delky objektu. Vyraz sizeof (objekt) je cele cislo, ktere je rovno velikosti specifikovaneho objektu /delka je udana v "bytech", ktere maji stejnou velikost jako char/. Objekt muze byt obycejna promenna, pole, struktura, jmeno typu int nebo double, nebo jmeno odvozene od struct jako v nasem pripade. Tohoto vypoctu je pouzito pri vypoctu NKEYS: #define NKEYS (sizeof(keytab)/ sizeof(struct key)) Nyni k funkci getword. Jiz jsme napsali obecnejsi funkci getword, nez je v nasem priklade potreba. getword vraci "slovo" ze vstupu. Jmeno je bud retezcem znaku a cisel zacinajici pismenem, nebo jeden znak. Typ objektu je urcen hodnotou, kterou funkce vraci: LETTER bylo-li nacteno slovo, EOF pro konec souboru nebo nacteny nealfanumericky znak. Funkce getword pouziva funkce getch a ungetch, ktere jsme napsali v kapitole 4. Funkce getword vola type pro urceni typu znaku ze vstupu. Nasledujici verze je pouze pro ASCII znaky. type (c) int c; { if(c >= 'a' && c <= 'z' || c >= 'A'&& c <= 'Z') return(LETTER); else if(c >= '0' && c <= '9') return(DIGIT); else return(c); } Symbolicke konstanty LETTER a DIGIT mohou mit libovolnou hodnotu, ktera neni v rozporu s nealfanumerickymi znaky a EOF. Obvykle se voli #define LETTER 'a' #define DIGIT '0' Š.po 3 Funkce getword by mohla byt rychlejsi, kdyby bylo vola- ni funkce type nahrazeno odkazem na odpovidajici pole type[]. Standardni knihovna jazyka C obsahuje makro nazvane isalpha a isdigit, ktere funguje timto zpusobem. C v i c e n i 6-1. Provedte tyto zmeny v getword a zmerte rozdil v rychlosti. C v i c e n i 6-2. Napiste funkci type, ktera je nezavisla na souboru znaku. C v i c e n i 6-3. Napiste verzi programu pro pocitani kli- covych slov, ktery nepocita vyskyt v retezcich v uvozovkach. 6. 4. Pointry na struktury -------------------------- Abychom ilustrovali nektere vlastnosti pointru a poli struktur, napisme znovu program pro zjisteni poctu vyskytu jednotlivych klicovych slov. Pouzijme ale pointry a ne indexy pole. Deklarace extern pole keytab muze zustat nezmenena. Musime zmenit main a binary. main() /*pocitej klicova slova, verze s pointry*/ { 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); } struct key *binary(word, tab, n) /*najdi slovo*/ char *word;, struct key tab[]; int n; { int cond; struct key *low = &tab [0]; struct key *high = &tab[n-1]; struct key *mid; 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; Š.po 12 else return (mid); } return (NULL); } Za zminku zde stoji vice veci. Za prve deklarace funkce binary musi indikovat, ze funkce vraci pointr na strukturu typu key. To musi byt deklarovano jak v jednotce main, tak ve funkci binary. Jestlize funkce binary slovo najde, tak vraci pointr na nej. Kdyz slovo nenajde vraci NULL. Za druhe - pristup k prvkum pole keytab je pres pointry. Proto musime zmenit funkci binary. Prostredni prvek nemuze uz byt jednoduse zjistovan vyrazem mid = (low + high) / 2 protoze soucet pointru produkuje nesmyslny vysledek /dokonce i kdyz je vydelen 2/. To musi byt zmeneno na mid = low + (high - low) / 2 coz nastavuje mid na prvek na polovine cesty mezi low a high. Vsimnete si rovnez inicializace low a high. Je mozne totiz inicializovat pointr na adresu drive definovanoho objektu. V main jsme napsali for (p = keytab; p > keytab + NKEYS; p++) p je pointr na strukturu a tak kazda operace s p bere v potaz rovnez struktury. p++ zvetsuje p odpovidajicim zpusobem na dalsi pole struktur. Nepredpokladejte ale, ze rozmer struktu- ry je dan pouze souctem rozmeru jejich clenu. Nakonec se podivejme na format programu. Jestlize funkce vraci komplikovany typ jako struct key *binary(word, tab, n) tak muzeme v deklaraci jmeno funkce prehlednout. Proto nekdy pouzivame zapis ve tvaru struct key * binary(word, tab, n) To je veci vkusu programatora. Vyberte si jeden zpusob a drzte se ho. 6. 5. Struktury odkazujici se samy na sebe ------------------------------------------- Predpokladejme, ze chceme resit obecnejsi problem: pocitat mnozstvi vyskytu v s e c h slov ze vstupu. Protoze ale seznam slov neni na zacatku znam, nemuzeme pouzit binarniho prohleda- vani. Ani linearniho prohledavani nemuzeme pouzit, protoze by program spotrebovaval mnoho casu /pozadovany cas by rostl kva- Š.po 3 draticky s mnozstvim nactenych slov/. Jak tedy musime organi- zovat data? Jednim z reseni je neustale nacitana slova tridit. To zna- mena ukladat prave nactene slovo tam, kam patri. To ale nemu- zeme delat v linearnim poli, protoze to by rovnez trvalo dlou- ho. Misto toho pouzijeme datovou strukturu nazyvanou b i n a r n i s t r o m. Tento strom obsahuje vzdy jeden uzel pro kazde slovo. Kazdy uzel obsahuje: pointr na dalsi slovo pocet vyskytu daneho slova pointer na levy poduzel pointer na pravy poduzel. Zadny uzel nemuze mit vic nez dva poduzly; muze mit jeden nebo nemusi mit zadny. Uzly jsou usporadany tak, ze levy podstrom obsahuje slova, ktera jsou mensi nez slovo v danem uzlu, a pravy podstrom ob- sahuje slova vetsi. Abychom zjistili, zda je prave nactene slovo ve stromu, zacneme u korenu a porovname nactene slovo se slovem v uzlu. Jestlize slovo souhlasi, jsme hotovi. Jestlize je nactene slovo mensi nez slovo v uzlu, pokracujeme do leveho poduzlu; je-li vetsi, tak pokracujeme vpravo. Jestlize ale jiz v danem smeru neni zadny uzel, znamena to, ze nactene slovo neni ve stromu obsazeno a misto pro ne je prave chybejici uzel. Proces vyhledavani je rekurzivni, protoze se pri prohledavani z jednoho uzlu se vyuziva prohledavani z jednoho poduzlu. Ob- dobne proces ukladani a tisku je rekurzivni. Vratme se zpet k popisu uzlu. Je to struktura se ctyrmi polozkami: struct tnode /*zakladni uzel*/ { char *word; /*pointr na text*/ int count; /*pocet vyskytu*/ struct tnode *left; /*levy poduzel*/ struct tnode *right; /*pravy poduzel*/ }; "Rekurzivni" definice uzlu muze vypadat zmatene, ale je uplne spravna. Je zakazano, aby struktura obsahovala sebe samu jako polozku, ale struct tnode *left; deklaruje text jako p o i n t r na uzel a neobsahuje uzel. Text programu je velice kratky a vyuziva funkce, ktere jsme napsali drive. Je to getword pro nactena slova ze vstupu, alloc, ktera zajistuje misto v pameti pro jednotliva slova. Hlavni program jednoduse cte slova a uklada je do stromu tree #define MAXWORD 20 main() /*pocitani frekvence slov*/ { struct tnode *root, *tree (); char word [MAXWORD]; int t; Š.po 12 root = NULL; while ((t = getword( word, MAXWORD)) != EOF) if (t == LETTER) root = tree (root,word); treeprint (root); } Funkce tree je jednoducha. Slovo word je ulozeno na vrcho- lek stromu (root). V kazde fazi je porovnano se slovem uloze- nym v uzlu. Potom se pokracuje do leveho nebo praveho poduzlu rekurzivnim volanim funkce tree. Slovo je bud ve stromu nale- zeno (a je prictena jednicka k mnozstvi vyskytu), nebo je vy- sledkem nulovy pointr, ktery indikuje, ze uzel musi byt ve stromu vytvoren. Jestlize je vytvoren novy uzel, tak tree vra- ci pointr na nej a tento pointr je zarazen do vyssiho uzlu. struct tnode *tree (p,w) /*ulozeni do p nebo nize*/ struct tnode *p; char *w; { struct tnode *talloc (); char *strsave(); int cond; if (p == NULL) /*nove slovo*/ { p = talloc(); /*vytvoreni noveho uzlu*/ p -> word = strsave (w); p -> count = 1; p -> left = p -> right = NULL; } else if ((cond = strcmp(w,p -> word)) == 0) p -> count ++ ; /*opakovane slovo*/ else if (cond < 0) /*je mensi*/ p -> left = tree (p -> left,w); else /*je vetsi*/ p -> right = tree (p -> right, w); return (p); } Pamet pro novy uzel je pridelovana funkci talloc, ktera je obdobou funkce alloc, kterou jsme napsali drive. Vraci pointr na volne misto pro uzel stromu. /Za chvili se k tomu vratime./ Nove slovo je kopirovano kamsi v pameti funkci strsave, je ini- cializovan pocet vyskytu a poduzly jsou vynulovany. Tato cast programu je vykonavana pouze tehdy, vytvari-li se novy uzel. Vynechali jsme testovani chyby po navratu z funkci strsave a talloc, coz neni prilis moudre. treeprint tiskne strom levym podstromem pocinajic. V kazdem uzlu tiskne levy podstrom /coz jsou vsechna slova mensi nez slovo v uzlu/, potom slovo samo, a nakonec pravy podstrom /vsechna vetsi slova/. Pokuste se sami si vypsat strom uzitim funkce treeprint; je to jedna z nejjasnejsich rekurzivnich fun- kci, na kterou jste kdy narazili. Š.po 3 treeprint (p) /*tiskni p rekurzivne*/ { if (p != NULL) { treprint (p -> left); print ("%4d % s\n",p -> count, p -> word); treeprint (p -> right); } } Prakticka poznamka: jestlize strom neni vyvazen, protoze slova neprichazeji nahodne, cas vypoctu roste prilis rychle. Nejhor- sim pripadem je, prichazeji-li slova jiz usporadana. Program vlastne potom provadi linearni prohledavani. Existuje zobecneni linearnich stromu: stromy typu 2-3 a AVL, ktere jsou vyhodnejsi ale my se o nich zde nebudeme zminovat. Predtim, nez opustime tento priklad, vratme se jeste k pro- blemu pridelovani pameti. Idealne by mel v programu existovat jenom jeden alokacni podprogram a mel by pridelovat pamet ruz- nym objektum. Ale kdyz ma jeden alokacni podprogram pridelit pamet pro pointr na char a pointr na tnode struktury, tak vy- vstavaji dve otazky. Za prve jak je splnena podminka mnoha po- citacu pro zarovnani adresy /napr. int. musi byt umisteno na sude adrese/. Za druhe jak nalozime s tim, ze podprogram vraci pokazde jiny druh pointru? Pozadavky na zarovnani mohou byt snadno splneny za predpo- kladu urciteho plytvani pameti. Alokacni podprogram bude vzdy vracet pointr, ktery splnuje v s e c h n y pozadavky na srovnani pameti. Napr. na PDP-11 mohou byt objekty ulozeny na sudych adresach. Jedinou cenou za to je jeden zbytecny znak na liche adrese. Obdobne je tomu na jinych pocitacich. Proto funkce alloc neni prenosna, ale jeji pouziti je univerzalni. Nase funkce z kapitoly 5 nesplnuje zakladni pozadavky na zarov- navani. V kapitole 8 tuto funkci napiseme spravne. Otazka zpusobu deklarace funkce alloc je klicova pro vsechny jazyky, kde je provadeno kontrolovani typu seriozne. V jazyce C je nejlepsim zpusobem deklarovat, ze alloc vraci pointr na char a potom upravit pointr na pozadovany tvar. Jestlize je p dekla- rovano jako char *p; potom (struct tnode*)p jej konvertuje na pointr typu tnode. Proto je talloc napsana takto: struct tnode *talloc() { char *alloc(); return((struct tnode*)alloc(sizeof(struct tnode))); } Š.po 12 Je to vice nez pozaduji soucasne prekladace, ale predstavu- je to nejbezpecnejsi pristup k budoucim prekladacum. C v i c e n i 6-4 Napiste program, ktery cte program v jazy- ku C a tiskne podle abecedy skupiny nazvu promennych, ktere jsou shodne v prvnich sedmi znacich a v ostatich se lisi. C v i c e n i 6-5 Napiste jednoduchy program pro krizove re- ference. Program ma tisknout vsechna slova ze vstupu a ke kaz- demu slovu uvest cisla radek, ve kterych se vyskytuje. C v i c e n i 6-6 Napiste program, ktery tiskne rozdilna slo- va ze vstupu setridena sestupne podle frekvence vystupu. Pred kazde slovo vytisknete pocet vyskytu. 6.6 Prohledavani tabulky ------------------------- Dalsi vlastnosti struktur budeme ilustrovat souborem progra- mu pro prohledavani tabulek. Tyto programy byvaji soucast pod- programu pro rozvijeni maker a pro ukladani parametru do tabu- lek. Napr. uvazujeme prikaz #define v jazyku C. Jestlize je na radce text #define YES 1 tak jmeno YES i jeho hodnota 1 jsou ulozeny v tabulce. Pozdeji, kdyz se objevi jmeno YES v prikazu inword = YES tak musi byt nahrazeno jednickou. Pro operace s nazvy a jejich nahradami existuji dve zakladni funkce. install(s,t) uklada jmeno s a nahrazujici retezec t do tabulky. s a t jsou znakove retezce. Funkce lookup prohledava tabulku a vraci pointr na misto, kde byl nalezen text, nebo NULL nebyl-li text nalezen. V techto funkcich je pouzito kli- covaciho algoritmu: jmena jsou konvertovana na mala kladna cisla, ktera jsou potom pouzita jako indexy do pole pointru. Prvek tohoto pole ukazuje na zacatek retezce bloku popisuji- cich jmena, ktera maji tuto hodnotu. Vraci NULL, nejsou-li zadna takova jmena. Blok v retezci je strukturou obsahujici pointr na jmena, nahrazujici text a odkaz na dalsi blok v retezci. Nulovy pointr oznacuje konec retezce. struct nlist /*zakladni polozka*/ { char *name; char *def; struct nlist *next; /*dalsi vstup v retezci*/ }; Pole pointru vypada takto: #define HASHSIZE 100 static struct nlist *hashtab[HASHSIZE]; /*tabulka pointru*/ Š.po 3 Transformacni funkce, ktere je pouzito ve funkcich lookup a install scita hodnoty znaku v retezci a vrati zbytek po de- leni delkou hashovaci tabulky. /Neni to algoritmus nejlepsi, ale je jednoduchy/. hash(s) /*transformace retezce s*/ char *s; { int hashval; for(hashval = 0; *s != '\0';) hashval += *s++; return(hasval % HASHSIZE); } Tento proces produkuje zacatecni index pole hashtab. At uz byl retezec nalezen kdekoliv, bude ulozen v retezci bloku zaci- najicich zde. Funkce lookup realizuje prohledavani. Jestlize jmeno jiz existuje, vraci pointr na nej. Jestlize ale neexistu- je, vraci NULL. struct nlist *lookup(s) /*prohledavani*/ char *s; { struct nlist *np; for(np = hashtab[ hash(s)];np == NULL;np=np -> next) if (strcmp(s,np -> name) == 0 ) return(np); /*nalezeno*/ return(NULL); /*nenalezeno*/ } Funkce install pouziva lookup pro zjisteni, zda je jmeno jiz ulozeno. Jestlize je ulozeno, tak nova definice musi nahradit starou. Jinak je ulozeno nove jmeno. Install vraci nulu, kdyz neni misto pro novy prvek. struct nlist *instal (name,def) /*uloz(name,def)*/ char *name, *def; /*do nashtab*/ { struct nlist *np, *lookup(); char *strsave(), *alloc(); int hashval; if((np = lookup (name)) == NULL) /*nenalezeno*/ { 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 = hashtab [hashval]; hasthab [hashval] = np; } else /*existuje*/ free (np -> def); /*vymazani*/ if ((np -> def = strsave (def)) == NULL ) return (NULL); Š.po 12 return (np); } Strsave kopiruje retezec, ktery je jeho argumentem na bezpe- cne misto. Misto je prideleno funkci alloc. alloc jsme ukazali v kapitole 5. Protoze se volani alloc a free muze objevit v libovolnem poradi a protoze je potreba dodrzovat pravidla zaro- vnani adresy, tak tato jednoducha verze nedostacuje. Viz kapi- tolu 7 a 8. C v i c e n i 6-7 Napiste program, ktery vyjme jmeno a nahra- zujici retezec tabulky, obhospodarovane funkcemi lookup a ins- tall. C v i c e n i 6-8 Implementuje jednoduchou verzi programu, ktery zpracovava prikazy #define v programech v jazyce C. Pou- zijte funkce z teto kapitoly a take funkce getch a ungetch. 6.7 Pole bitu -------------- Jestlize je otazka pameti na prvnim miste, muze byt nezbytne sloucit ruzne objekty do jednoho pocitacoveho slova. Hodne se pouziva souboru priznakovych bitu v aplikacich typu tabulky symbolu prekladace. Predstavte si fragment prekladace, ktery zachazi s tabulkou symbolu. Kazdy identifikator sebou nese jiste informace. Napr. je-li klicovym slovem, zda je externi nebo externi staticky ne- bo interni atd. Nejkompaktnejsim zpusobem zapisu techto infor- maci je jejich zakodovani do promenne typu int nebo char. Obvyklym zpusobem jak to udelat je definice masek, odpovi- dajicich pozici bitu ve slove: #define KEYWORD 01 #define EXTERNAL 02 #define STATIC 04 /Cisla musi byt mocninami dvou/. Pristup k bitum bude provaden posouvanim, maskovanim a doplnkovym operatorem, popsanym v ka- pitole 2. Vyraz flags |= EXTERNAL | STATIC; Nastavuje bity EXTERNAL A STATIC ve flags, zatimco flags &= `(EXTERNAL | STATIC); nuluje tyto bity. Vyraz if ((flags & (EXTERNAL | STATIC)) == 0) Š.po 3 je pravdivy, jestlize je nektery z obou bitu jednotkovy. Jako alternativu nabizi jazyk C moznost definovani a pristup k polim bitu primo. P o l e b i t u je soustava bitu v jedne promenne int. Syntaxe definice pole bitu a pristup k nemu je zalozen na strukture. Napr. tabulka symbolu #define muze byt nahrazena definici tri poli bitu: struct { unsigned is_keyword : 1; unsigned is_extern : 1; unsigned is_static : 1; } flags; Tim je nadefinovana promenna flags, ktera obsahuje 3 pole bitu. Pole bitu jsou definovany jako unsigned, protoze to jsou skutecne veliciny bez znamenka. Jednotliva pole bitu jsou: flags.is_keyword, flags.is_extern atd. stejne jako cleny struktur. Pole bitu se chovaji jako male promenne bez znamenka a mohou vystupovat v aritmetIckych operacich jako jine promenne int. Predchozi priklady mohou byt napsany rovnez takto: flags.is_extern = flags.is_static = 1 nastavuje bity a flags.is_extern = flags.is_static = 0 je nuluje a if (flags.is_extern == 0 && flags.is_static == 0) je testuje. Pole bitu by nemely prekrocit meze promenne int: stane-li se to, tak pole je prirazeno na dalsi adresu. Po- le bitu nemusi mit jmeno. Nepojmenovana pole /dvojtecka s uda- nou delkou/ mohou byt pouzita jako vypln. Pole bitu jsou na nekterych pocitacich prirazovana do pro- menne zleva doprava, na nekterych zprava doleva - zalezi na ty- pu pocitace. Je nutne mit na mysli dalsi omezeni. Pole bitu nemaji zna- menko, mohou byt prirazovany do int nebo unsigned. Nejsou to pole jako takova. Nemaji adresy a tak pro ne nemuze byt pouzi- vano unarni operace &. 6.8 Uniony ----------- Union je promenna, ktera muze obsahovat v ruznych chvilich objekty ruznych typu a velikosti. Uniony umoznuji pracovat s ruznymi typy objektu v jedne oblasti pameti, aniz by vyuzivaly nejake strojove zavisle operace. Pro priklad se vratme opet k tabulce symbolu prekladace. Predpokladejme, ze konstanty mohou byt int, float nebo znakove pointry. Hodnota konstanty musi byt ulozena v promenne odpovi- Š.po 12 dajiciho typu. Konstanty by mely zabirat stejne misto a nemelo by zalezet na typu. Muzeme pouzit union, kde ruzne promenne mohou sdilet stejne misto. Tak jako u pole bitu je syntaxe de- finice zalozena na strukture: union u_tag { inf ival; float fval; char *pval; } uval; Promenna uval bude dostatecne velka, aby mohla obsahovat nejvetsi ze tri typu a nezalezi na hardwaru pocitace. Libovol- ny z techto typu muze byt promenne uval prirazen a potom pou- zit ve vyrazu. Typ musi odpovidat naposled ulozenemu typu. Za- lezi pouze na programatorovi, aby si pamatoval, co do promenne uval ulozit naposledy. Vysledek zalezi na pocitaci pouze tehdy, ulozi-li se do unionu neco jineho, nez co je pozdeji vyuzito. Cleny unionu jsou dosazitelne takto: jmeno unionu.clen nebo pointr_unionu -> clen tak, jako ve strukturach. Jestlize do promenne utype ulozime typ, ktery byl prirazen union uval, pak muzeme psat if (utype == INT) printf ("%d\n", uval.fval); else if (utype == FLOAT) printf ("%f\n", uval.fval); else if (utype == STRING) printf ("%s\b",uval.pval); else printf ("bad type %d in utype\n", utype); Uniony se mohou objevit ve strukturach a polich a naopak. Zapis pro dosazeni clenu unionu ve strukture /a naopak/ je identicky s vnorenymi strukturami. Napr. v poli struktury nadefinovanem takto: struct { char *name; int flags; int utype; union { int ival; float fval; char *pval; } uval; } symtab [NSYM]; Š.po 3 je promenna ival urcena takto symtab[i].uval.ival a prvni znak retezce pval takto *symtab[i]uval.pval Ve skutecnosti union je struktura, ve ktere vsechny cleny maji relativni posun adresy nulovy, struktura je dostatecne velka, aby mohla "pojmout nejsirsi" clen a zarovnanim adresy plati pro vsechny cleny unionu. Jedina povolena operace s uni- ony je dosazeni jejiho clenu a urceni jeji adresy. Uniony nemo- hou byt parametry funkci, nemohou stat na leve strane prirazo- vaciho prikazu a nemohou byt vraceny funkcemi. Pointry na uni- ony mohou byt uzivany stejnym zpusobem jako pointry na struk- tury. V kapitole 8 ukazeme, jak uniony mohou byt pouzivany. 6.9 Prikaz typedef ------------------- C umoznuje definovat nova datova jmena napr. typedef int LENGTH; LENGTH je synonymum pro int. "Typ" LENGTH muze byt pouzit v deklaracich stejnym zpusobem jako int: LENGTH len, maxlen; LENGTH lenghts[]; obdobne deklarace typedef char *STRING; definuje STRING jako synonymum pro char nebo znakovy pointr, ktery potom muze byt pouzit v deklaracich STRING p, lineptr [LINES], alloc(); Uvedomte si, ze typ, ktery je deklarovan v prikazu typedef se objevuje na pozici jmeno promenne a ne primo za slovem type- def. Syntakticky je typedef na stejne urovni jako extern, sta- tic atd. Pouzili jsme rovnez velkych pismen, abychom zduraznili jmeno. Jako slozitejsi priklad uvedeme definici uzlu stromu s pou- zitim typedef: typedef struct tnode /*zakladni uzel*/ { char *word; /*ukazatel na dalsi jmeno*/ int count; /*pocet vyskytu*/ struct tnode *left /*levy poduzel*/ struct tnode *right; /*pravy poduzel*/ } TREENODE, *TREEPTR; Tato definice vytvari dve nova slova: TREENODE /struktura/ a Š.po 12 TREEPTR /pointr na strukturu/. Potom funkce talloc muze byt napsano takto: TREEPTR talloc(); char *alloc(); return((TREEPTR) alloc (sizeof (TREENODE))); Musime zduraznit, ze prikaz typedef n e v y t v a r i nove datove typy. Pridava pouze dalsi jmena existujicim typum. Ne- ni ani pouzito nove semantiky: promenne deklarovane timto zpusobem maji presne stejne vlastnosti, jako kdyby byly defi- novany normalne. Ve skutecnosti je typedef obdobou prikazu #define, ale je interpretovan prekladacem. typedef int (*PFI)(); Vytvari typ PFI pro "pointr na funkci, ktera vraci int", ktere- ho muze byt pouzito v PFI strcmp, numcmp, swap; v programu sort z kapitoly 5. Jsou dva zpusoby pro pouzivani deklarace typedef. Prvni du- vod je, ze umoznuje jednoduse resit problemy presnosti progra- mu. Je-li nektery typ zavisly na pouzitem pocitaci, tak staci zmenit pouze jeden prikaz typedef. Je take mozne pouzivat jmen definovanych v typedef pro ruzne typy int a pak konkretne dosa- dit short, int, long dle potreby pouziteho pocitace. Druhym du- vodem je zajisteni lepsi dokumentace programu: typu nazvanemu TREEPTR je lepe rozumet, nez je-li definovan pouze jako pointr na strukturu. Je take mozne, ze v budoucnu bude prekladac nebo program lint uzivat informace obsazene v typedef pro kontrolu spravnos- ti programu.