.pl 60 .po 12 .mt 2 .mb 2 .pn 79 KAPITOLA 5: POINTERY A POLE --------------------------- Pointr (ukazatel) je promenna, ktera obsahuje adresu jine promenne. V jazyku C se pointru hojne pouziva. Castecne proto, ze je to casto jedina moznost pro vykonani vypoctu a castecne proto, ze vedou ke kompaktnejsimu kodu. Pointry jsou hazeny do jednoho pytle spolu s prikazy goto jako prikazy, ktere dokazou nadhernym zpusobem vytvaret progra- my, kterym neni vubec rozumet. To je castecne pravda tehdy, nejsou-li vyuzivany rozumne a opatrne. Je totiz velice snadne vytvorit pointer, ktery ukazuje nekam, kam to neocekavame. Naopak jsou-li pointry vyuzivany disciplinovane, muzeme napsat programy jasne a jednoduse. Tuto vlastnost pointru se budeme snazit popsat. 5.1. Pointry a adresy --------------------- Protoze pointry obsahuji adresy objektu, je mozne dosahnout objektu "neprimo" - prave pomoci pointru. Predpokladejme, ze x je promenna typu int a px je pointr, vytvoreny zatim nespeci- fikovanym zpusobem. Unarni operator & udava adresu objektu, a tak prikaz px = &x; prirazuje adresu promenne x do promenne px; rikame, ze px "uka- zuje" na x. Operator & muze byt aplikovan pouze na promenne a prvky pole; vyraz ve tvaru &(x + 1) nebo &3 je nedovoleny. Neni rovnez mozne ziskat adresu promenne typu registr. Unarni operator * naklada se svym operandem jako s adresou a z dane adresy vybira obsah. Proto je-li y promenna int, tak y = *px; prirazuje promenne y to, na co ukazuje pointr px. Sekvence px = &x; y = *px; je ekvivalentni s prikazem y = x; Rovnez je nutne deklarovat vsechny promenne takto: int x, y; int *px; S deklaraci promennych x a y jsme se jiz setkali drive. Dekla- race pointru je ale novinkou. int *px; Š.po 3 je mnemonikem: rika, ze kombinace *px je typu int, coz znamena, ze objevi-li se px v kontextu *px, je ekvivalentni promenne typu int. Ve skutecnosti syntaxe deklarace tohoto typu promenne simuluje syntaxi vyrazu, ve kterem se dana promenna vyskytuje. To je uzitecne ve vsech komplikovanych deklaracich. Napr. deklarace double atof(), *dp; urcuje, ze ve vyrazu maji funkce atof() a *dp hodnotu typu double. Meli byste si uvedomit, ze v deklaraci je pointr svazan s urcitym objektem, na ktery ukazuje. Pointry se mohou objevit ve vyrazech. Napr. ukazuje-li px na celociselnou promennou x, potom se *px muze objevit vsude tam, kde x. y = *px + 1; prirazuje promenne y hodnotu o jednu vetsi nez x. printf("%d\n", *px); tiskne obsah promenne x. d = sqrt((double) *px); prirazuje promenne d odmocninu promenne x, ktera je predtim prevedena na typ double /viz kap. 2/. Ve vyrazech typu y = *px + 1; maji unarni operatory * a & vetsi prioritu nez operatory arit- meticke. Brzy se vratime k tomu, co znamena y = *(px + 1); Odkaz na pointr se muze rovnez objevit na leve strane prira- zovaciho prikazu. Ukazuje-li px na promennou x, potom *px = 0; nuluje promennou x, a *px += 1; ji zvetsuje o jednotku zrovna tak jako (*px)++; V tomto prikazu jsou zavorky nezbytne. Bez nich by byla jednic- ka prictena k px a ne k tomu, na co px ukazuje, protoze unarni operatory jako * a ++ jsou provadeny zprava doleva. Protoze pointry jsou promenne, muze byt s nimi nakladano jako s normalnimi promennymi. Jestlize py je pointr na promen- nou int, potom Š.po 12 py = px; zkopiruje obsah promenne px do py. Potom py ukazuje na stejne misto jako px. FF 5.2 Pointry a argumenty funkci ------------------------------- Protoze promenne jsou predavany funkcim "hodnotou", tak funkce nemuze primo zmenit hodnoty techto promennych ve volaji- ci funkci. Co musite udelat, chcete-li opravdu zmenit obycejny argument? Napr. podprogram pro trideni muze vymenit dva prvky pomoci funkce swap. Nestaci ale napsat pouze swap(a, b); je-li funkce swap nadefinovana takto swap(x, y) /*chybne!*/ int x, y; { int temp; temp = x; x = y; y = temp; } Funkce swap nemuze ovlivnit argumenty ve volajici jednotce, protoze jsou predavany hodnotou. Nastesti existuje zpusob, jak muze dosahnout zadaneho efek- tu. Volajici program bude predavat p o i n t r y promennych: swap(&a, &b); Protoze operator & udava adresu promenne, tak &a je pointr na a. Ve funkci swap musi byt argumenty deklarovany jako pointry a skutecne parametry jsou jejich prostrednictvim ovlivnovany. swap(px, py) /*vymena *px a *py*/ int *px, *py; { int temp; temp = *px; *px = *py; *py = temp; } Pointru jako argumentu funkci se pouziva hojne tehdy, vyzadujeme-li, aby funkce vracela vice nez jednu hodnotu /mu- zeme rici, ze funkce swap vraci dve hodnoty - nove hodnoty svych argumentu/. Jako priklad uvazujme funkci getint, ktera zajistuje cteni cisel ve volnem formatu rozdelenim vstupni sekvence na celociselne hodnoty; pri jednom vyvolani jedno cis- lo. getint vraci hodnotu, ktera byla nactena, nebo EOF, kdyz Š.po 3 narazila na konec vstupu. Tyto hodnoty musi byt vraceny v ruz- nych promennych, protoze at uz pro EOF zvolime jakoukoli hodno- tu, mohlo by dojit ke kolizi. Jedno z reseni je zalozeno na funkci scanf, ktera bude po- psana v kapitole 7. Tato funkce vyuziva toho, ze getint vraci jako hodnotu EOF, kdyz je nalezen konec souboru. Kazda jina hodnota znamena, ze bylo nacteno cislo. Numericka hodnota na- cteneho cisla je predavana argumentem, ktery musi byt pointr. Tento zpusob oddeluje urcovani konce souboru od predani cisel- nych hodnot. Nasledujici cyklus vyplnuje pole celymi cisly, nactene funkci getint: int n, v, array[SIZE]; for(n = 0; n < SIZE && getint(&v) != EOF; n++) array[n] = v; Pri kazdem volani je promenne v prirazeno nactene cislo. Uve- domte si, ze je nezbytne uvest &v jako argument funkce getint. Pouzijeme-li jako argument jenom v, bude ohlasena adresova chy- ba, protoze getint pocita s tim, ze argument je pointr. Funkce getint je modifikaci funkce atoi, kterou jsme jiz drive tvorili: getint(pn); /*nacti cislo ze vstupu*/ int *pn; { intc, sign; while((c = getch()) == ' ' || c == '\n' || c =='\t') ; /*ignoruj oddelovace*/ sign = 1; if(c == '+' || c == '-') { /*znamenko*/ sign = (c == '+') ? 1 : -1; c = getch(); } for(*pn = 0; c >= '0' && c <= '9'; c = getch()) *pn = 10 * *pn + c - '0'; *pn *= sign; if(c != EOF) ungetch(c); return(c); } Uvnitr funkce getint je *pn pouzita jako normalni promenna typu int. Rovnez jsme pouzili funkci getch a ungetch /popsane v ka- pitole 4./, takze znak, ktery byl nacten navic, muze byt vracen zpatky na vstup. C v i c e n i 5-1. Napiste funkci getfloat, ktera nacita cislo float, analogickou funkci getint. Jaky typ bude funkce getfloat vracet jako hodnotu? .pa Š.po 12 5.3 Pointry a pole ------------------ V jazyce C je uzky vztah mezi pointry a poli. Dokonce tak uzky, ze s poitry a poli muze byt nakladano stejne. Kazda ope- race s prvkem pole muze byt provedena s pointry. Obecne je ver- ze s pointry rychlejsi, ale nekdy je tezsi k pochopeni. Deklarace int a[10] definuje pole o delce 10 jako blok deseti po sobe nasledujicich prvku a[0], a[1], ... , a[9]. Notace a[i] znamena, ze tento prvek je vzdalen i pozic od pocatku. Jestlize je pa pointr na promennou typu integer definovany takto int *pa; potom prirazeni pa = &a[0]; nastavuje pa na nulny prvek pole a. pa obsahuje adresu prvku a[0]. Nyni prikaz x = *pa; zkopiruje obsah a[0] do x. Jestlize pa ukazuje na urcity prvek pole a, potom pa + 1 ukazuje na dalsi prvek. Obecne pa - i ukazuje na i-ty prvek vlevo a pa + i na i-ty prvek vpravo. Proto kdyz pa ukazuje na a[0], tak *(pa + 1); ukazuje na prvek a[1] pa + i je adresa a[i] a *(pa + i) je obsah prvku a[i]. Tyto poznatky plati nehlede na to, jakeho typu jsou promen- ne pole a. Definice "pricti 1 k pointru" a obecne cela aritme- tika pointru je zalozena na tom, ze prirustek je vynasoben velikosti objektu, na ktery pointer ukazuje. Proto v pa + i je i vynasobeno rozmerem objektu, na ktery ukazuje pointr pa. Souhlas mezi indexovanim a aritmetikou pointru je zrejmy. Ve skutecnosti je odkaz na pole prekladacem preveden na pointr na zacatek pole. Z toho plyne, ze nazev pole j e vlastne pointr. To je velice uzitecny zaver. Protoze jmeno pole je synonymem pro umisteni nulteho prvku, pak prirazeni pa = &a[0]; muze byt zrovna tak napsano pa = a; Jeste vice prekvapive, alespon na prvni pohled, je fakt, ze Š.po 3 odkaz na a[i] muze byt napsano jako *(a + i). Prekladac jazyka C totiz vyraz a[i] prevadi vzdy na *(a + i). Tyto formy jsou naprosto ekvivalentni. Aplikujeme-li operator & na obe casti teto ekvivalence dostaneme, ze &a[i] a a + i jsou rovnez iden- ticke: a + i je adresa i-teho prvku pole a. Druhou stranou teto mince je to, ze je-li pa pointr, tak muze byt pouzivan s indexem: pa[i] je totozne s *(pa + i). Kratce receno indexovy vyraz z libovolneho pole muze byt napsan jako pointr a offset a naopak; dokonce ve stejnem prikazu. Je jenom jeden rozdil mezi jmenem pole a pointrem, ktery si musime uvedomit. Pointr je promenna a proto pa = a a pa++ jsou dovolene operace. Nazev pole je naproti tomu k o n- s t a n t a a ne promenna. Proto jsou vyrazy typu a = pa nebo a++ nebo p = &a neplatne. Kdyz je funkci predavano jmeno pole, tak je predana adresa pocatku pole. Uvnitr volane funkce je argument jiz ale normal- ni promennou a tak jmeno pole je opravdu pointr, tj. promenna obsahujici adresu. Tento fakt muzeme pouzit k napsani nove verze funkce strlen, ktera pocita delku retezce strlen(s) /*zjisteni delky retezce*/ char *s; { int n; for(n = 0; *s != n '\0'; s++) n++; return(n); } Zvetsovani promenne s je dovolene, protoze to je pointr. s++ nijak neovlivnuje retezec ve funkci, ktera strlen vola, ale jenon zvetsuje privatni kopii adresy tohoto pole. Formalni parametr ve funkci muze byt definovan bud takto char s[]; nebo takto char *s; Obe definice jsou totozne. Ktera z nich ma byt pouzita zalezi vyhradne na tom, v jakem tvaru budou psany vyrazy teto funkce. Jestlize je funkci predano pole, funkce predpoklada, ze ji bylo predano pole nebo pointr a podle toho s nim take naklada. Fun- kci je take mozno predat pouze cast pole predanim pointru zacatku tohoto podretezce. Napr. je-li a pole, potom f(&a[2]) a f(a+2) oboji predava adresu prvku a[2], protoze &a[2] a a+2 jsou vyra- zy, ktere ukazuji na treti prvek pole a. Ve funkci f muze byt provedena deklarace takto .pa Š.po 12 f(arr) int arr[]; { ... } nebo takto f(arr) int *arr; { ... } Co se tyce funkce f same, tak vubec nezalezi na tom, ze argument ukazuje pouze na cast nejakeho vetsiho pole. 5.4 Adresova aritmetika ------------------------ Jestlize je p pointr, potom operace p++ zvetsuje p a p po- tom ukazuje na dalsi prvek a p++ = i zvetsuje p a i tak, ze ukazuje o i prvku dal. Tyto a jim podobne operace jsou nej- jednodussi a nejvice pouzivanou formou adresove aritmetiky. C je konzistentni a regularni v pristupu k adresove aritme- tice. System pointru poli a adresove aritmetiky je hlavni silou jazyka. Ilustrujme nektere vlastnosti tim, ze napiseme jednodu- chy program pro alokaci pameti. Budou to dva podprogramy: alloc(n) vraci pointr p na n po sobe jdoucich znakovych pozic, ktere mohou byt pouzity pro ulozeni znaku. Funkce free(p) uvol- nuje alokovanou pamet. Funkce jsou opravdu "zakladni", protoze funkce free musi byt vyvolana, je-li vyvolana funkce alloc. To znamena, ze pamet obhospodarovana temito funkcemi je zasobnik neboli LIFO /last in first out/. Ve standartni knihovne jsou obdobne funkce, ktere nemaji dana omezeni a v kap.8 ukazeme zdokonalenou verzi. Zatim ale potrebujeme pouze trivialni fun- kci alloc, abychom mohli alokovat pamet nezname velikosti v ruznych chvilich. Funkce alloc bude "podavat kousky pole", nazvaneho allocbuf. Toto pole bude soukrome pro funkce free a alloc. Protoze tyto funkce pracuji s pointry a nikoliv s idexy, jine funkce nemusi o tom poli nic vedet. Toto pole muze byt tedy deklarovano jako extern static, coz znamena, ze je mistni ve zdrojovem souboru obsahujici funkce alloc a free a mimo ne je "nevi- ditelne". Toto pole nemusi mit ani jmeno. Muze byt ziskano tak, ze pozadame operacni system o nejaky nepojmenovany blok pame- ti. Dalsi informace, kterou potrebujeme znat je to, jak casto je allocbuf vyuzivano. Budeme pouzivat pointr nazvany allocp na dalsi volny prvek. Jestlize pozadame funkci alloc o ,n znaku, tak alloc zjisti, jestli je jeste misto v poli allocbuf. Jestlize je, tak alloc vrati stavajici hodnotu pointru allocp /tzn. zacatek volneho bloku/ a zvysi hodnotu allocp o n. free(p) nastavi allocp na p, kdyz p je uvnitr allocbuf. Š.po 3 #define NULL 0 /*pointr pro chybove hlaseni*/ #define ALLOCSIZE 1000 /*maximalni dosazitelna pamet*/ static char allocbuf[ALLOCSIZE]; /*pamet pro alloc*/ static char *allocp = allocbuf; /*dalsi volna pozice*/ char *alloc(n) /*vrat ukazatel na n znaku*/ int n; { if(allocp + n <= allocbuf + ALLOCSIZE) { /*sedi to*/ allocp += n; return(allocp - n); /*stare p*\ } else /*malo mista*/ return(NULL); } free(p) /*volna pamet*/ char *p; { if(p >= allocbuf && p < allocbuf + ALLOCSIZE) allocp = p; } Obecne muze byt pointr inicializovan zrovna tak jako kazda jina promenna, prestoze normalne ma jedine vyznam NULL, nebo vyraz zahrnujici adresy drive definovanych dat shodneho typu. Deklarace static char *allocp = allocbuf; definuje allocp jako znakovy pointr a inicializuje jej tak,ze ukazuje na allocbuf, coz je vlastne prvni volne misto v pameti, kdyz program zacina cinnost. To by ale take stejne dobre mohlo byt napsano ve tvaru static char *allocp = &allocbuf[0]; protoze jmeno pole j e adresa jeho nulteho prvku. Podminka if(allocp + n <= allocbuf + ALLOCSIZE) testuje, zda je jeste dostatek pameti pro n znaku. Jestlize je, tak allocp bude maximalne o jednu za koncem pole allocbuf. Jestlize pozadavek muze byt splnen, tak alloc vraci normalni pointr /vsimnete si vlastni definice funkce/. Jestlize nemuze byt pozadavek splnen, tak alloc musi nejak tuto skutecnost signalizovat. V jazyku C je zaruceno, ze zadny pointr nebude obsahovat nulu jako hodnotu, a proto nule muze byt pouzita pro tuto signalizaci. Piseme radeji NULL nez nula, protoze to je jasnejsi. Pointrum obecne vzato nemohou byt prirazena cis- la integer. Nula je ale specialni pripad. Podminky jako if(allocp + n < = allocbuf + ALLOCSIZE) a Š.po 12 if(p > = allocbuf && p < allocbuf + ALLOCSIZE) ukazuji dalsi uzitecne vlastnosti aritmetiky pointru. Pointry mohou byt za urcitych okolnosti porovnavany. Jestlize p a q ukazuji na prvky tehoz pole, tak relace <, >= atd. maji vyznam p < q muze byt pravda, napr. jestlize p ukazuje na drivejsi clen pole nez q. Relace == a != je rovnez mozno pouzit. Libovolny pointr muze byt porovnan s NULL. Ale vsechny vyhody jsou pryc, poro- vnavate-li pointry, ktere ukazuji kazdy na neco jineho. Jestli- ze mate stesti, tak program nebude pracovat na zadnem pocitaci. Jestlize ale stesti nemate, tak program bude na jednom pocitaci radne pracovat a na druhem zkolabuje. Dale jsme si mohli vsimnout, ze pointr a cislo integer mohou byt secteny nebo odecteny. Konstrukce p + n znamena n-ty prvek za mistem, kam ukazuje pointr p. Pocitac vy- nasobi n odpovidajicim rozmerem objektu, na ktery pointr ukazu- je. Napr. na pocitaci PDP-11 je pro char nasobny faktor 1, pro int a short 2, pro long a float 4 a pro double 8. Odecitani pointru ma take vyznam; jestlize p a q ukazuji do stejneho pole, pak p-q je pocet prvku mezi p a q. Tohoto faktu muze byt pouzito pro novou variantu funkce strlen strlen(s) /*vypocet delky retezce s*/ char *s; { char *p = s; while(*p != '\0') p++; return(p-s); } V deklaraci je p inicializovano na s, to znamena, ze ukazuje na jeho prvni znak. V cyklu while jsou znaky testovany na \0. Protoze \0 je nula a protoze while testuje, zda je vyraz nulo- vy, muzeme vynechat explicitni text a cyklus muzeme psat while(*p) p++; Protoze p ukazuje na znak, p++ posouva p na dalsi znak a p-s udava pocet znaku, o ktery je p posunuto - tj. delka retezce. Aritmetika pointru je konzistentni. Jestlize pracujeme s float, p++ se posune na dalsi float. Tak muzeme napsat dalsi funkci alloc, ktera bude pracovat s float misto s char. Toho docilime tim, ze vsude ve funkcich alloc a free nahradime deklaraci char deklaraci float. Operace s pointry budou provadeny opet sprav- ne. Jine operace s pointry, nez o kterych jsme se zde zminili, jsou nedovolene. Nemuzeme scitat dva pointry, nasobit je, nebo k nim pricitat cisla float a double. Š.po 3 5.5 Znakove pointry a funkce ---------------------------- Z n a k o v a k o n s t a n t a, psana jako "I am a string" je znakovym polem. Ve vnitrni interpretaci prekladac toto pole zakoncuje znakem \0, takze program snadno nalezne konec. Poza- davek na pamet je tady o jednotku vyssi nez skutecna delka retezce. Pravdepodobne se retezce nejcasteji vyskytuji jako para- metry funkci printf("hello, world\n"); Jestlize se takovyto retezec znaku objevi v programu, tak pri- stup k nemu je zprostredkovan pointry. Funkce printf ve skutec- nosti obdrzi pointr na tento retezec znaku. Znakova pole nemusi ale byt pouze argumenty funkci. Jestlize message je deklarovano takto char *message; potom prikaz message = "now is the time"; priradi message pointr na skutecny retezec. Neni to k o p i e retezce. C neumoznuje praci s retezci jako s jednotkami. Dalsi vlastnosti pointru a poli budeme ilustrovat dvema uzi- tecnymi funkcemi ze standardni knihovny vstupu a vystupu, ktere budou probrany v kapitole 7. Prvni funkci je strcpy(s,t), ktera kopiruje retezec t do retezce s. Argumenty jsou v tomto poradi podle analogie a pri- razovacim prikazem s = t; Prvni verze s pouzitim poli strcpy(s, t) /*kopiruj t do s*/ char s[], t[]; { int i; i = 0; while((s[i] = t[i]) != '\0') i+++; } Pro srovnani nyni strcpy s pointry strcpy(s, t) /*kopiruj t do s; verze s pointry*/ char *s, *t; { while((*s = *t) != '\0') Š.po 12 { s++; t++; } } Protoze argumenty jsou predavany hodnotou strcpy muze pouzit s a t jak chce. Prakticky strcpy nebude napsana tak, jak jsme uvedli. Dalsi moznost je: strcpy(s, t) /*kopiruj t do s; 2. verze s pointry*/ char *s, *t; { while((*s++ = *t++) != '\0') ; } Tato verze zvetsuje s i t v testovaci casti. Hodnota *t++ ma hodnotu znaku, na ktery t ukazuje jeste pred zvetsenim. Postfix ++ nemeni t dokud nebyl vybran prvek. Podobnym zpusobem je znak ulozen na starou hodnotu s. Tento znak je take porov- nan s \0. Vysledkem je, ze jsou kopirovany znaky retezce az po znak \0 vcetne. Znovu si uvedomime, ze porovnavani s \0 je zbytecne a napiseme konecnou verzi strcpy(s, t) /*kopiruj t do s; 3. verze s pointry*/ char *s; *t; { while(*s++ = *t++) ; } Prestoze se to na prvni pohled muze zdat nesrozumitelne, vy- hoda je zrejma a tento tvar se nam musi vzit uz jen proto, ze se casto v C programech uziva. Druhou funkci je funkce strcmp(s,t), ktera porovnava znakove retezce s a t a vraci bud zapornou hodnotu, nulu nebo kladnou hodnotu podle toho, je-li retezec s lexikalne mensi, roven nebo vetsi nez t. Vracena hodnota je rozdilem prvnich dvou znaku, ve kterych se retezec s a t lisi. strcpm(s,t) /*vrat<0 kdyz s0 kdyz s>t*/ char s[], t[]; { int i; i = 0; while(s[i] == t[i]) if(s[i++ == '\0') return(0); return(s[i] - t[i]); } Verze s pouzitim pointru: Š.po 3 strcmp(s, t) /*dtto*/ char *s, *t; { for(; *s == *t; s++, t++) if(*s == '\0') return(0); return(*s -*t); } Protoze ++ a -- mohou byt bud pred nebo za promennou, mohou se objevit i jine kombinace ++ a --. Napr. *++p zvetsuje p p r e d vybiranim znaku, na ktery ukazuje. C v i c e n i 5-2. Napiste pointrovou verzi funkce strcat, kterou jsme uvedli v kapitole 2. strcat(s, t) kopiruje retzec t na konec retezce s. C v i c e n i 5-3. Napiste makro pro strcpy. C v i c e n i 5-4. Prepiste programy z drivejsich kapitol s pouzitim pointru. 5.6 Pointry nejsou cela cisla ----------------------------- V minulych programech v jazyce C jste si mohli vsimnout kavalirskeho pristupu k pointrum. Obecne plati, ze na mnoha po- citacich je pointrem prirazeno cele cislo a naopak. To ale ved- lo k prilisne svobode. V podprogramech, ktere vraci pointry ktere jsou predavany dale, jsou vynechany deklarace pointru. Uvazujme napr. funkci strsave(s), ktera uklada retezec s na bezpecne misto, ktere ziska pomoci funkce alloc. Spravne ma byt napsano takto: char *strsave(s) /*uloz nekam retezec/* char *s; { char *p, *alloc(); if((p = alloc(strlen(s)+1)) != NULL) strcpy(p, s); return(p); } Prakticky se ale vynechava deklarace strsave(s) /*uloz nekam retezec*/ { char *p; if((p = alloc(strlen(s)+1)) != NULL) strcpy(p, s); return(p); } Š.po 12 Tato verze bude fungovat na mnoha typech pocitacu, protoze implicitni hodnota pro funkce a argumenty je int a pointr a int je mozno casto zamenit navzajem. Nicmene je tento zpusob zapisu riskantni, protoze priliz zavisi na pouzitem pocitaci. Moudrej- si je psat radne vsechny deklarace. /Program lint nas bude pri takovych konstrukcich varovat/. 5.7 Vicerozmerna pole ---------------------- C umoznuje pouzivani vicerozmernych poli, prestoze jsou v praxi mnohem mene pouzivany nez pole nebo pointry. V tomto odstavci si ukazeme nektere jejich vlastnosti. Uvazujme o problemu konverze data ze dne a mesice na den v roce a naopak. Napr. 1. brezen je 60. den neprestupneho roku a 61. den roku prestupneho. Budeme definovat dve funkce: day_of_year bude konvertovat mesic a den na den v roce a month_day bude konvertovat den v roce na mesic a den. Protoze tato funkce vraci dve hodnoty, tak month a day budou pointry month_day(1977, 60, &m, &d) nastavi m na 3 a d na 1 /1.brezen/. Obe funkce potrebuji shodne informace: tabulku poctu dni kazdeho mesice. Protoze se pocet dni lisi podle toho, je-li rok prestupny nebo ne, je jednodussi pouzit dvourozmerneho po- le. Funkce bude vypadat takto: static int day_tab[2] [13] = { (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31), (0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31), } ; day_of_year(year, month, day) int year, mont, day; { int i, leap; leap = year % 4 == 0 && year % 100 != 0 || year % 400 ==0; for(i = 1; i < month; i++) day += day_tab[leap] [i]; return(day); } month_day(year, yearday, pmonh, pday) int year, yearday, *pmonth, pday; { int i, leap; leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0; for(i = 1; yeardy > day_tab[leap] [i]; i++) yearday -=day_tab[leap] [i]; *pmonth = i; Š.po 3 *pday = yearday; } Pole day_tab je externi obema funkcim a je prvnim vicerozmernym polem, se kterym jsme se setkali. V jazyku C je dvojrozmerne - pole, jehoz prvky jsou zase jednorozmerna pole. Proto je psano day_tab[i][j] spise nez day_tab[i, j] jako je tomu v jinych jazycich. Jinak se s dvojrozmernymi poli naklada uplne stejne. Prvky jsou skladany po sloupcich, coz znamena, ze pravy index se meni nejrychleji. Pole je inicializovano seznamem hodnot v zavorkach. Kazda radka dvojrozmerneho pole je inicializovana odpovidajicim podsezna- mem. Prvni prvek pole day_tab jsme inicializovali na nulu, takze muzeme pracovat s celymi cisly 1 - 12 namisto 0 - 11. Jeden prvek navic zde neni rozhodujici a tak se vyhneme ze- sloziteni indexu pole. Jestlize je funkci predavano dvojrozmerne pole, tak v dekla- raci argumentu m u s i byt uveden pocet sloupcu pole. Dekla- race poctu radek neni rozhodujici, protoze je predavan pointr. V tomto pripade je to pointr na objekty, ktere jsou 13-ti di- menzionalnimi poli. Je-li tedy predavano pole day_tab funkci, tak deklarace ve funkci f musi vypadat takto f(day_tab) int day_tab[2] [13]; { ... } Deklarace argumentu muze stejne dobre vypadat takto int day_tab[] [13]; protoze pocet radek neni dulezity, nebo takto int *day_tab[13]; V teto deklaraci je uvedeno, ze argument je pointer na pole 13 celych cisel. Kulate zavorky jsou nezbytne, protoze hranate zavorky maji vyssi prioritu nez *. Bez zavorek bude int(*day_tab)[13]; deklarovano pole 13 pointru. To uvidime v dalsim odstavci. .pa Š.po 12 5.8 Pole pointru. Pointry na pointry ------------------------------------- Protoze pointry jsou promenne, tak muzeme predpokladat, ze muzeme vyuzit pole pointru. Ilustrujeme to na programu, ktery bude tridit soubor radek podle abecedy. /Bude to zjednodusena forma utility sort systemu UNIX./ V kapitole 3 jsme uvedli funkci Shell sort, ktera tridi pole celych cisel. Pouzijeme stejny algoritmus s tim, ze nyni musi- me nakladat s retezci cisel nezname delky, ktere nemohou byt porovnavany nebo premisteny jednou operaci. Potrebujeme vhodnou a dostatecne efektivni datovou reprezentaci radek promenne del- ky. Nyni vstoupi na scenu pole pointru. Jestlize jsou radky, ktere maji byt trideny, ulozeny v jednom poli bez mezer mezi sebou, tak kazda radka muze byt reprezentovana pointrem na jeji prvni znak. Pointry mohou byt ulozeny do pole. Dve radky mohou byt potom porovnavany funkci strcmp. Jestlize chceme prohodit dve radky, potom staci prohodit pouze pointry na ne. To znacne zjednodusuje celou operaci. Tridici postup sestava ze tri casti: nacteni vsech radek ze vstupu trideni vytisteni serazenych radek Jako obvykle rozdelime program na funkce, ktere budou vykona- vat jednotlive kroky a hlavni program, ktery vse bude ridit. Odlozme na chvili krok trideni a venujme se datovym struk- turam vstupu a vystupu. Vstupni funkce musi cist a uchovavat znaky kazde radky a sestavit pole pointru na tyto radky. Protoze vstupni funkce muze nakladat pouze s konecnym poctem radek, mohla by vratit nesmyslnou hodnotu, pokud by radek bylo priliz mnoho. Vystupni funkce pouze radky tiskne podle poradi pole pointru. #define NULL 0 #define LINES 100 /*maximalni pocet radek*/ main() /*trideni vstupnich radek*/ { char *lineptr[LINES]; /*pointry na radky*/ int nlines: /*pocet nactenych radek*/ if((nlines = readlines(lineptr, LINES)) >= 0) { sort(lineptr, nlines); writelines(lineptr, nlines); } else printf("input too big to sort\n"); } #define MAXLEN 1000 readlines(lineptr, maxlines) /*cti vsupni radky*/ char *lineptr[]; Š.po 3 int maxlines; { int len, nlines; char *p, *alloc(), line[MAXLEN]; nlines = 0; while((len = getline(line,MAXLEN)) > 0) if(nlines >= maxlines) return(-1); else if((p = alloc(len)) == NULL) return(-1); else { line[len-1]='\0';/*novy radek*/ strcpy(p, line); lineptr[nlines++] = p; } return(nlines); } Znak pro novou radku je z konce radek vymazan, aby neovlivnil poradi pro trideni. writelines(lineptr, nlines) /*vypis radky*/ char *lineptr[]; int nlines; { int i; for(i = 0; i= 0) printf("%s\n", *lineptr++); } lineptr na zacatku ukazuje na prvni radku. Kazdy inkrement jej posouva na dalsi radku a pritom se promenna nlines zmensuje. Kdyz jsme se postarali o vstup a vystup, muzeme prejit ke trideni. Program Shell sort z kapitoly 3 potrebuje ale jiste Š.po 12 zmeny: musi byt modifikovany deklarace a srovnani musi byt pre- vedeno do specialni funkce. Zaklad algoritmu se nezmenil, coz nam dokazuje, ze je stale dobry. sort(v, n) /*roztrid retezec v[0]...v[n-1]*/ char *v[]; /*vzestupne*/ int n; { int gap, i, j; char *temp; for(gap = n\2; gap>0; gap /= 2) for(i = gap; i= 0; j -= gap) { if(strcmp(v[j], v[j+gap]) <=0) break; temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } } Protoze libovolny prvek v /neboli lineptr/ je znakovy pointr, tak temp take musi byt znakovy pointr. Napsali jsme tento program tak, aby pracoval co nejrychleji. Mohl by byt ovsem rychlejsi. Mohl by totiz kopirovat radky ze vstupu primo do pole array a ne do pole line a potom dale. Je ale lepsi udelat prvni verzi jasne a o "ucinnost" se starat pozdeji. Tato uprava by ale program nijak podstatne nezrychli- la. Rozdil by ale byl, poud bychom pouzili nejaky lepsi tridi- ci algoritmus / napr. QUICKSORT/. V kap. 1 jsme si ukazali, ze prikazy while a for provadeji testovani p r e d prvnim vykonanim tela cyklu. To nam zarucu- je, ze program bude fungovt spravne, i kdyz na vstupu nejsou zadne radky. Je dobre si program pro trideni projit a zjisto- vat, co se stane, nebyl-li nacten zadny vstup. C v i c e n i 5-5. Prepiste readlines tak, aby radky ukladal v jednotce main a ne ve funkci alloc. O kolik bude program rychlejsi? 5.9 Inicializace pole pointru ----------------------------- Napisme funkci month_name(n), ktera vraci pointer na rete- zec, obsahujici jmeno n-teho mesice. To je idealni aplikace in- terniho statickeho pole. Funkce month_day obsahuje svoje vnitr- ni pole retezce znaku a je-li vyvolana, vraci spravny pointr na patricne misto. V teto casti se budeme zabyvat problemem inicializace pole jmen. Syntaxe je obdobna jako drive: .pa Š.po 3 char *month_name(n) /*vrat jmeno n-teho mesice*/ int n; { static char *name[] = { "illegal month", "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December", } ; return((n < 1 || n > 12) ? name[0] : name[n]); } Deklarace promenne name, ktera je polem znakovych pointru, je obdobna deklarci lineptr v tridicim programu. Iniciali- zace se provadi jednoduse seznamem znakovych retezcu. Kazdy retezec ma v poli odpovidajici misto. Presneji receno znaky i-teho retezce jsou nekdy ulozeny a pointr na ne je ulozen v name[i]. Protoze neni specifikovana delka pole name, prekla- dac ji sam zjisti z poctu inicializaci. 5.10 Pointry a vicedimenzionalni pole -------------------------------------- Zacatecnici jsou obcas zmateni rozdilem mezi dvojdimenzi- oalnim polem a polem pointru, jako je napr. pole jmen mesicu v predchozim priklade. Mame-li dany deklarace int a[10][10]; int *b[10]; tak pouziti a a b je obdobne v tom, ze a[5] [5] a b[5] [5] jsou dovolene reference na jeden prvek int. a je opravdove po- le. Bylo pro nej alokovano 100 prvku a pouzivano normalniho postupu pri vypoctu indexu. V pripade pole b je ale alokova- no pouze 10 pointru. Kazdy musi byt nastaven tak, aby ukazoval na pole typu int. Kdyz predpokladame, ze kazdy pointr ukazuje na pole int o rozmeru 10, tak bude alokovano celkem 100 bunek plus 10 bunek pro pointry. Pole pointru potrebuje tedy vice pa- meti a muze tak pozadovat explicitni inicializaci. Ma ale take dve vyhody: adresovani prvku je provadeno neprimo pointrem a ne nasobenim a scitanim jako u pole normalniho a navic radky mohou mit promennou delku. To znamena, ze ne kazdy prvek b musi uka- zovat na pole o rozmeru 10. Nektery muze ukazovat na 2 pole, druhy na 20 a dalsi na zadny. Š.po 12 Prestoze jsme se zde omezili na prvky typu int, tak nejvet- si pouziti pro pole pointru je takove, jako v pripade pole month_name: tj. ukladani znakovych retezcu ruzne delky. C v i c e n i 5-6. Prepiste funkce day_of_year a month_day s pouzitim pointru. 5.11 Argumenty ve tvaru prikazove radky ---------------------------------------- Existuje zpusob, jak predavat argumenty nebo parametry pro- gramu, ktery zacina svou cinnost. Kdyz je spousten program main, tak ma dva argumenty. Prvni z nich /obycejne nazyvany (argc) udava pocet argumentu prikazove radky, kterou byl pro- gram vyvolan. Druhy parametr (argv) je pointr na pole znakovych retezcu, ktere obsahuji argumenty - vzdy jeden na retezec. Nejjednodussi ilustrace pouziti nezbytnych deklaraci je program echo, ktery proste tiskne argumenty. Potom prikaz echo hello, world bude mit vystup hello, world argv[0] je jmeno programu, ktery byl vyvolan a tak argc je prinejmensim 1. V predchozim priklade je argc 3 a argv[0] je "echo", argv[1] je "hello," a argv[2] je "world". Prvnim skutecnym argumentem je argv[1] a poslednim argv[argc-1]. Je-li argc = 1, potom nebyly zadany parametry. Zde je prog- ram echo: main(argc, argv) /*opakuj argumenty, 1.verze*/ int argc; char *argv[]; { int i; for(i = 1; i < argc; i++) printf("%s%c", argv[i], (i < argc-1) ? ' ' : '\n'); } Protoze argv je pointr na pole pointru, tak tento program mu- zeme napsat mnoha zpusoby. Ukazeme 2 varianty. main(argc, argv) /*opakuj argumenty, 2. verze*/ int argc; char *argv[]; { while(--argc > 0) printf("%s%c, *++argv,(argc > 1) ? '': '\n'); } Protoze argv je pointrem na zacatek pole retezcu argumentu, Š.po 3 tak zvetsenim o 1(++argv) bude ukazovat na argv[1] a ne na argv[0]. Kazde zvetseni ho posouva na dalsi argument. Ve stej- nem case je argc zmensovano. Kdyz je nulove, tak jiz nejsou zadne dalsi agrumenty. main(argc, argv) /*opakuj argumenty 3. verze*/ int argc; char *argv[]; { while(--argc > 0) printf((argc > 1) ? "%s" : "%s\n", *++argv); } V teto verzi je ukazano, ze argumenty funkce printf mohou byt vyrazy. Neni to priliz caste, ale stoji za zapamatovani. Ve druhem priklade provedeme vylepseni programu pro vyhle- davani retezcu z kap. 4. Tam jsme retezec, ktery ma byt vyhle- dan zaclenili do programu. Nyni tento program zmenime tak, ze retezec bude zadavan jako argument /obdoba systemove funkce grep v UNIX/. #define MAXLINE 1000 main(argc, argv) /*nalezni prvni vyskyt retezce s*/ int argc; char *argv[]; { char line[MAXLINE] if(argc != 2) printf("Usage: find pattern\n"); else while(getline(line, MAXLINE) > 0) if(index(line, argv[1] >= 0) printf("%s, line); } Na tomto zakladnim modelu budeme ilustrovat dalsi konstrukce s pointry. Predpokladejme, ze chceme pouzivat dva argumenty. Je- den rika: "vytiskni vsechny radky m i m o tu, ve ktere je da- ny retezec" a druhy "vytiskni kazdou radku s cislem radky". Zacina-li v C nejaky argument znakem minus, tak je to para- metr. Vybereme si tuto konvenci: -x(except) pro inverzi a -n(numer) pro cislovani. Potom find -x -n the se vstupem ve tvaru now is the time for all good men to come to the eid of their party vytiskne 2: for all good men Š.po 12 Parametry se mohou vyskytovat v libovolnem poradi a program by nemel byt citlivy na to, kolik argumentu bylo zadno. Kon- kretne, volani programu index by nemelo referovat na argv[2], kdyz tam byl zadan parametr a na argv[1], kdyz tam parametr za- dan nebyl. Navic je pro uzivatele vyhodne, mohou-li byt para- metry slucovany. Tj. find -nx the Zde je program: #define MAXLINE 1000 main(argv, argc) /*nalezni retezec*/ int argc; char *argv[]; { char line[MAXLINE], *s; long lineno = 0; int except = 0, number = 0; while(--argc > 0 && (*++argv)[0] == '-') for(s = argv[0]+1; *s != '0'; s++) switch(*s) { case 'x': except = 1; break; case 'n': numer = 1; break; default: printf("find: illeagal option%c\n",*s); argc = 0; break; } if(argc != 1) printf("Usage: find -x -n pattern\n"); else while(getline(line, MAXLINE) > 0) { lineno++; if(index(line, *argv) >= 0) != except) { if(number) printf("%1d: ", lineno); printf("%s", line); } } } argv je zvetseno pred kazdym parametrem a argc je zmenseno. Jestlize nenastaly chyby, tak na konci musi byt argc=1 a argv ukazovat na retezec, ktery ma byt vyhledan. Uvedomte si, ze Š.po 3 *++argv je pointr na retezec argumentu; (*++argv)[0] je jeho prvni znak. Zavorky jsou zde nezbytne, protoze jinak by byl tento vyraz chapan takto: *++(argv[0]), coz je nespravne. Dalsi vhodnou formou zapisu je **++argv. C v i c e n i 5-7. Napiste program add, ktery vycisluje v obracene polske notaci vyraz, zadany jako argument. Napr. add 2 3 4 + * vypocte 2 * (3+4). C v i c e n i 5-8. Modifikujte program entab a detab /z kap.1/ aby tabelatory byly zadavany jako argumenty. Pouzijte normalni tabelator, nebyl-li zadan zadny argument. C v i c e n i 5-9. Rozsirte entab a detab tak, aby umoznoval zadai ve tvaru entab m + n coz jest: tabelator stavi kazdy n-ty sloupec, pocinaje na sloupci m. C v i c e n i 5-10. Napiste program tail, ktery tiskne poslednich n radek ze vstupu. Implicitne bude n=10, ale muze byt zmeneno argumentem tail -n Program by se mel chovat normalne bez ohledu nato, jak nesmy- slna hodnota n je. Napiste program tak, aby co nejlepe vyuzival pamet. Radky by mely byt ukladany stejnym zpusobem jako ve funkci sort a ne jako v dvoudimenzionalnim poli konstantni delky. 5.12 Pointry funkci -------------------- Funkce v C neni promenna, ale je mozno defiovat p o i n t r f u n k c e, se kterym muze byt manipulovano /muze byt preda- van jako argument funkcim, ukladan do pole atd./. Budeme to ilustrovat tim, ze zmodifikujeme tridici program tak, ze bude- li uveden parmetr -n, tak rady budou setrideny ciselne a ne podle abecedy. Trideni obvykle sestava ze tri casti: P o r o v n a v a n i, ktere urcuje poradi porovnavaneho paru, v y m e n y, ktera meni poradi paru a t r i d i c i h o a l g o r i t m u, ktery pro- vadi porovnani a vymenu tak dlouho, dokud neni vse utrideno. Tridici algoritmus je nezavisly na porovnavacich operacich a operacich vymeny, takze predanim ruznych porovnavacich funkci a funkci vymeny muzeme provadet trideni podle libovolnych krite- rii. Teto postup bude pouzit v novem tridicim programu. Porovnani podle abecedy provadi funkce strcmp, vymenu fun- kce swap. Dale budeme potrebovat funkci numcmp, ktera radky porovnava na zaklade ciselne hodnoty a vraci stejnou indikaci jako funkce strcmp. Tyto tri funkce jsou deklarovany v jed- notce main a jejich pointry jsou predavany funkci sort. Funkce sort vola funkce pomoci pointru. #define LINES 100 /*maximalni pocet radek*/ main(argc, argv) /*setrideni vstupnich radek*/ int argc; char *argv[]; Š.po 12 { char *lineptr[LINES];/*pointry na text. radky*/ int nlines; /*pocet nacteych radek*/ int strcmp(),numcmp(); /*porovnavaci funkce*/ int swap(); /*funkce vymeny*/ int numeric = 0; /*1 pro numerickou vymenu*/ if(argc > 1 && argv[1][0] == '-' && argv[1][1] == 'n') numeric = 1; if((nlines = readlines(lineptr, LINES)) >= 0) { if(numeric) sort(lineptr,nlines,numcmp,swap); else sort(lineptr,nlines,strcmp,swap); writelines(lineptr,nlines); } else printf("input too big to sort\n"); } strcmp, numcmp a swap jsou adresy funkci. Protoze vime, ze jde o funkce, tak operator & neni nezbytny. Proto ho ta- ke neni treba uvadet pred nazvem pole. Prekladac sam pripra- vi adresy funkci nebo poli. Funkce sort vypada takto: sort(v, n, comp, exch) /*setrideni v[0]...v[n-1]*/ char *v[]; int n; int(*comp)(),(*exch)(); { int gap, i, j; for(gap = n/2; gap > 0; gap /= 2) for(i = gap; i= 0;j -= gap) { if((*comp)(v[j],v[j+gap]) <= 0) break; (*exch)(&v[j],&v[j+gap]); } } Musime dat pozor na deklarace. Deklarace int(*comp)() rika, ze comp je pointr funkce, ktera vraci int. Prvni par za- vorek je nezbytny, protoze bez nich int*comp() znamena, ze comp je funkce, ktera vraci pointr, coz jak vidime je neco zcela odlisneho. Š.po 3 Pouziti funkce comp v radce if((*comp) (v[j], v[j+gap]) <= 0) je v souhlase s deklaraci: comp je pointr na funkci, *comp je funkce a (*comp)(v[j], v[j+gap]) je volani funkce. Zavorky jsou nezbytne. Jeste uvedeme funkci numcmp: numcmp(s1, s2) /*porovnavani s1 a s2 ciselne*/ char *s1, *s2; { double atof(), v1, v2; v1 = atof(s1); v2 = atof(s2); if(v1 < v2) return(-1); else if(v1 > v2) return(1); else return(0); } Nakonec uvedeme funkci swap, ktera meni dva pointry: swap(px, py) /*vymena *px a *py*/ char *px[], *py[]; { char *temp; temp = *px; *px = *py; *py = temp; } C v i c e n i 5-11. Upravte sort tak, aby bylo mozno zadat parametr -r, ktery pozaduje trideni sestupne. -r musi rovnez pracovat s -n. C v i c e n i 5-12. Pridejte parametr -f, ktery dava naroven mala a velka pimena. C v i c e n i 5-13. Pridejte parametr -d /"slovnikove srovna- vani"/. Potom budou porovnavany pouze pismena, cisla mezery. Zkontrolujte, zda bude pracovat spolu s -f.