.pl 60
.po 12
.mt 2
.mb 2
.pn 45

KAPITOLA 3: VETVENI PROGRAMU
----------------------------

   Prikazy pro vetveni programu specifikuji, v jakem poradi
budou instrukce program vykonany. Uz jsme se setkali s nejob-
vyklejsimi prikazy pro vetveni programu v drivejsich prikazech,
zde uvedeme kompletni sestavu techto prikazu a upresime pred-
chozi. 

3.1 Prikazy a bloky
-------------------

   V y r a z jako je x = 0, nebo i++, nebo printf(...) se stava
p r i k a z e m, je-li nasledovan strednikem, jako v

	x = 0;
	i++;
	printf(...);

V jazyku C je strednik spise koncovy znak prikazu nez oddelo-
vac, jako je tomu napr. v jazyku ALGOL.
   Slozene zavorky  { a } se pouzivaji pro zdruzovani deklaraci
a prikazu ve s l o z e n y  p r i k a z  neboli  b l o k, ktery
je syntakticky ekvivalentni jednomu prikazu. Jednim prikladem
jsou slozene zavorky kolem jednoho prikazu. Dalsim prikladem
jsou tyto zavorky kolem nekolika prikazu za prikazem if, else,
while nebo for. /Promenne mohou byt ve skutecnosti definovany
uprostred  l i b o v o l n e h o  bloku; o tom budeme mluvit
v kapitole 4/. Za pravou zavorkou, ktera ukoncuje blok, neni
nikdy strednik.


3.2 If - Else
-------------

   Pro rozhodovani se pouziva kostrukce if - else. 
Formalni syntaxe je asledujici

	if(vyraz)
		p r i k a z - 1
	else
		p r i k a z - 2

kde cast else neni povinna. V y r a z  je vyhodnocen, jestlize
je "pravdivy" /tj. ma nenulovou hodnotu/, p r i k a z - 1 je
vykonan, jestlize je nepravdivy /tj. ma nulovou hodnotu/ a
jestlize je uvedeno else, je vykonan  p r i k a z e m - 2.
   Protoze prikaz if pouze testuje hodnotu vyrazu, je mozne
psat zkracene 

	if(vyraz)
misto
	if(vyraz != 0)

Nekdy je tento zpusob prirozeny a jasny, nekdy je ale tajemny.
Š.po 3
   Protoze cast else prikazu if-else je nepovinna, tak jestlize
else vynechame v sekvenci prikazu if, vznika nejednoznacnost.
else je logicky spojeno s nejblizsim predchozim vyrazem if, 
ktera nema cast else. Napr. v

	if(n > 0)
		if(a > b)
			z = a;
		else
			z = b;

cast else je spojena s vnitrnim prikazem if, jak jsme ukazali
strukturou zapisu. Jestlize teno zpusob neni ten, ktery chcete,
je treba uzit zavorek pro spravne sdruzeni

	if(n > 0)
	{
		if(a > b)
			z = a;
	}
	else
	   z = b;

Dvojznacnost je zvlaste nebezpecna v situacich jako:

	if(n > 0)
		for(i = 0; i < n; i++)
			if(s[i] > 0
			{
				printf("...");
				return(i);
			}
	else		/*chyba*/
		printf("error - n is zero\n");

Logicka struktura zapisu ukazuje presne co chcete, ale pre-
kladac presto spoji else s vnitrnim prikazem if. Tento druh
chyb se velmi tezko odstranuje. 
   Uvedomte si, ze za z = a v

	if(a > b)
		z = a;
	else
		z = b;

je strednik. Je to kvuli gramatickym pravidlum: prikaz nasle-
dujici if je vzdy ukoncen strednikem.


3.3 Else - If
-------------

   Konstrukce

	if(v y r a z)
		p r i k a z
Š.po 12
	else if(v y r a z)
		p r i k a z
	else if(v y r a z)
		p r i k a z
	else
		p r i k a z

se objevuje tak casto, ze stoji zato se podrobneji o nich
zminit. Sekvence prikazu if je nejobecnejsim zpusobem mnoho-
nasobneho rozhodovani. V y r a z y  jsou vyhodnocovany v tom-
to poradi: jestlize je  v y r a z  pravdivy, tak prikaz s nim 
spojeny je vykonan, a tim je cela sekvence ukoncena. 
P r i k a z  znamena bud jeden prikaz nebo skupinu prikazu v
zavorkach.
   Prikaz spojeny s poslednim else je vykonan, jestlize zadna
predchozi podminka nebyla splnena. V nekterych pripadech mu-
ze byt cast

	else
		p r i k a z

vypustena.
   Abychom ilustrovali tricestne rozhodovani, uvedeme binarni
funkci rozhodovani, ktera urcuje, zda se urcita hodnota objevu-
je v roztridenem poli v. Prvky pole musi byt usporadany vzestu-
pne. Funkce vraci pozici /cislo v rozsahu 0 az n-1/ jestlize x 
je obsazeno ve v, a -1 jestlize neni.

	binary(x, v, n)	/*nalezeni x ve v[0]...v[n-1]*/
	int x, v[], n;
	{
		int low, high, mid;
		low = 0;
		high = n - 1;
		while(low <= high)
		{
			mid = (low+high) / 2;
			if(x < v[mid])
				high = mid - 1;
			else if(x > v[mid])
				low = mid + 1;
			else	/*found match*/
				return(mid);
		}
		return(-1)
	}

Zakladnim rozhodnutim je, zda x je mensi, vetsi, nebo rovno 
strednimu prvku v [mid] v kazdem kroku; to je prirozene pro
else-if.

.pa
Š.po 3 
3.4 Prepinac
------------

   Prepinac je specialni, mnohonasobny rozhodovaci prikaz, kte-
ry testuje, zda se vyraz v zavorkach rovna nektere z  k o n-
s t a n t n i c h  hodnot a podle toho pokracuje v cinnosti. V
kapitole 1 jsme zjistovali vyskyt kazde cislice, mezery a 
ostatnich znaku pouzitim sekvence if ...else, if ...else. Zde
uvedeme stejny program s prikazem switch.

	main()	/*pocitani cisel, oddelovacu, ostatnich*/
	{
		int c, i, nwhite, nother, ndigit [10];
		nwhite = nother = 0;
		for(i = 0; i < 10; i++)
			ndigit [i] = 0;
		while((c = getchar ()) != EOF)
			switch(c)
			{
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				ndigit[c-'0']++;
				break;
			case ' ':
			case '\n':
			case '\t':
				nwhite++;
				break;
			default:
				nother++;
				break;
			}
		printf("digits = ");
		for(i = 0; i<10; i++)
			printf(" %d ", ndigit[i]);
		printf("\nwhite space = %d, other = %d\n", 
			nwhite, nother);
	}

   Prikaz switch vyhodnocuje celociselny vyraz v zavorkach /v
nasem prikladu je to znak c/ a porovnava jeho hodnotu se vsemi
case. Kazdy case musi byt oznacen celociselnou nebo znakovou
konstantou, nebo konstantnim vyrazem. Jestlize nektery case 
odpovida hodnote vyrazu, tak zde zacina cinnost programu. Po-
lozka oznacena default je vykonana, jestlize zadny case nebyl
uspokojen. Polozka default nemusi byt uvadena; kdyz neni uvede-
na a zadny case neni uspokojen, tak neni provedena zadna cin-
nost. Polozky case a default se mohou objevit v libovolnem
Š.po 12
poradi. Case musi byt od sebe odlisne.
   Prikaz break zpusobuje okamzite ukonceni prikazu switch. 
Protoze case slouzi pouze jako navesti, tak potom, co jsou vy-
konany prikazy odpovidajici navesti case, tak program dale 
p r o c h a z i  dalsi navesti case, dokud neni nejakym expli-
citnim prikazem ukoncen. Zakladnimi prikazy pro ukonceni prika-
zu switch jsou return a break. Prikaz break muze byt take pou-
zit pro okamzite vystoupeni z cyklu while, for a do, jak bude
ukazano v dalsich kapitolach.
   Postupne prochazeni navesti case je dvojsecne. Na jedne 
strane dovoluje pro jednu cinnost vice navesti case, na druhe 
strane ale musi byt normalne kazda cinnost po navesti case
ukoncena prikazem break pro zamezeni prochazeni dalsich naves-
ti. Prochazeni navesti case neni citelne. S vyjimkou pou-
ziti vice navesti pro jednu cinnost by melo byt postupne pro-
chazeni uzivano ridce.
   Je dobrym zvykem ukoncovat case prikazem break /v nasem
prikladu default/, i kdyz neni z logickeho hlediska potrebny.
Nekdy treba budeme pridavat dalsi navesti case a break se bude
hodit.

C v i c e n i  3-1. Napiste funkci expand (s, t), ktera konver-
tuje znaky jako je znak pro novou radku a tabelator do viditel-
neho tvaru \n a \t pri kopirovani retezce s na t. Pouzijte
switch.


3.5  C y k l y  w h i l e  a  f o r
-----------------------------------

   Jiz jsme se setkali s prikazy cyklu while a for. Ve

	while (v y r a z)
	p r i k a z

je vyraz vyhodnocen. Pokud je nenulovy, tak je  p r i k a z
vykonan a  v y r a z  je znovu vyhodnocen. Cyklus pokracuje do
te doby, nez je vyraz nulovy. Potom program pokracuje za pri-
kazem while.
   Prikaz for

	for(v y r a z 1;  v y r a z 2;  v y r a z 3)
		p r i k a z

je ekvivalentni

	v y r a z 1;
	while( v y r a z 2 )
	{
	p r i k a z
	v y r a z 3	
	}

Z gramatickeho hlediska jsou vsechny tri polozky prikazu for
vyrazy. Obycejne vyraz1 a vyraz3 jsou prirazovaci prikazy
nebo volani funkce a vyraz2 je relacni vyraz. Kterakoliv po-
Š.po 3
lozka muze byt z prikazu for vypustena, ale stredniky musi byt 
uvedeny. Jestlize vypustime vyraz1 a vyraz3, promenna i se 
prestane menit. Jestlize vypustime relacni vyraz2, je tento
vyraz bran jako stale pravdivy:

	for(; ;)
	{
	...
	}

tvori nekonecny cyklus, ktery muze byt ukoncen jinymi zpusoby
/napr. prikazy break nebo return/.
   Zda pouzit prikaz while nebo for je ciste zalezitost vkusu.
Napr. v

	while((c = getchar()) == ' ' || c == '/n' || c == '\t')
		;	/*preskoceni oddelovacu*/

neni zadna inicializace ani reinicializace, takze pouziti pri-
kazu while je prirozene.
   Prikaz for ma jasne prednosti tehdy, je-li v cyklu jednodu-
cha inicializace a reinicializace, protoze soustredi prikazy
cyklu blizko sebe a viditelne na vrcholu cyklu. Je to zcela
zrejme v
	
	for(i = 0; i < N; i++)

coz je v jazyku C prikaz obdobny prikazu cyklu DO v jazyku
FORTRAN nebo PL/1. Analogie to ale neni uplna, protoze limity
cyklu for mohou byt uvnitr meneny a promenne i si uchovavaji
svoji hodnotu, i kdyz je cyklus for z jakychkoliv duvodu ukon-
cen. Protoze slozky cyklu for jsou libovolne vyrazy, tak cyklus
for neni omezen jen na aritmeticke posloupnosti. Nicmene neni 
ale dobrym stylem "vnutit" do prikazu for vyrazy, ktere spolu
nemaji nic spolecneho.
   Jako vetsi priklad uvedeme jinou verzi funkce atoi pro
konvertovani retezce na ciselny ekvivalent. Tato verze je
univerzalnejsi, pocita totiz s uvodnim oddelovacem a znamen-
kem + a - /v kapitole 4 ukazeme funkci atof, ktera provadi
stejnou konverzi pro cisla s pohyblivou radovou carkou/.
   Zakladni struktura programu vypada takto:

	ignoruj oddelovace, jestlize nejake jsou
	----------------------------------------

	vezmi znamenko, jestlize nejake je
	----------------------------------

	vezmi ciselnou cast a konvertuj ji
	----------------------------------

Kazdy krok vykona urcitou cinnost a ponecha veci v jasnem stavu
pro dalsi kroky. Cely proces je ukoncen pri nalezeni prvniho 
znaku, ktery neni soucasti cisla.
.pa
Š.po 12
	atoi(s)		/*konvertovani s na cislo*/
	char s[];
	{
	int i, n; sign;
	for(i=0;s[i] == ' ' || s[i] == '\n'|| s[i] =='\t';i++)
		;	/*preskoceni oddelovacu*/
	sign = 1;
	if(s[i] == '+' || s[i] == '-')		/*znak*/
		sign = (s[i++] == '+') ? 1 : -1;
	for(n=0; s[i] >= '0' && s[i] <= '9'; i++)
		n = 10 * n + s[i] - '0';
	return(sign * n);
	}

   Vyhoda soustredeni cyklu na jedne misto je mnohem jasnejsi,
nez nekolik vnorenych cyklu. Nasledujici funkce je trideni typu
Shell celociselneho pole. Zakladni myslenka tohoto trideni je, 
ze v pocatku jsou spise nez sousedni prvky porovnavany prvky
vzdalene, zrovna tak jako v normalnim trideni. Tim je ale v
prvni fazi vykonano hodne prace, takze dale neni treba uz moc
delat. Interval mezi porovnavanymi prvky je postupne snizovan 
az na jedna, kdy tato metoda efektivne prechazi na normalni
premistovani sousednich prvku.

	shell(v, n,)	/*trideni v [0]...v [n-1] vzestupne*/
	int v[], n;
	{
	int gap, i, j, temp;
		for(gap = n/2; gap > 0; gap /= 2)
			for(i = gap; i < n; i++)
				for(j=i-gap; j>=0 && v[j] >
					 v[j+gap]; j-=gap)
				{
					temp = v[j];
					v[j] = v[j + gap];
					v[j + gap] = temp;
				}
	}

V prehledu jsou tri vnorene cykly. Vnejsi cyklus urcuje vzda-
lenost mezi porovnavanymi prvky a postupne ji zmensuje od n/2
delenim dvema az do nuly. Prostredni cyklus porovnava kazde dva
prvky, jejichz vzdalenost je rovna gap, vnitrni cyklus zamenu-
je ty prvky, ktere jsou nespravne usporadany. Protoze promenna
gap je nakonec zmensena na jedna, tak vsechny prvky jsou sprav-
ne usporadany. Uvedomte si, ze obecnost prikazu for dovoluje 
vnejsimu cyklu mit stejnou formu jako ostatni, i kdyz to neni
aritmeticka rada.
   Jednim z poslednich operatoru jazyka C je carka "," ,
kterou nejcasteji nalezneme v prikazu for. Dvojice vyrazu odde-
lene carkou je vykonavana zleva doprava, a typ i hodnota vys-
ledku je shodna s typem a hodnotou praveho operandu. Proto
je mozne v prikazu for pouzivat na ruznych mistech vicenasobne
vyrazy, napr. menit dva indexy pole soucasne. To je ilustrovano
ve funkce reverse(s), ktera invertuje retezec s.

Š.po 3
	reverse(s)	/*invertovan retezec s*/
	char s[];
	{
		int c, i, j;
		for(i = 0, j = strlen(s) - 1; s < j; i++, j--)
		{
			c = s[i];
			s[i] = s[j];
			s[j] = c;
		}
	}

Carky, ktere oddeluji argumenty funkci, promenne v deklaracich
atd., nejsou operatory a  n e z a r u c u j i  vyhodnocovani
zleva doprava.

C v i c e n i  3-2.  Napiste funkci expand(s1, s2), ktera roze-
pisuje zkratky jako a-z v retezci s1 v kompletni seznam 
abc...xyz v s2. Pripustte velka i mala pismena, cislice a budte
pripraveni zachazet s pripady typu a-b-c a a-z, 0-9 a a-z.
/Uzitecnou konvenci je to, ze znak - je bran doslovne./


3.6  Cyklus do - while
----------------------

   Jak jsme jiz uvedli v kapitole 1, cykly while a for maji
rozhodovaci podminku umistenou na zacatku cyklu. Treti typ 
cyklu v jazyku c, prikazy do - while, maji rozhodovani umis-
teno na konci  p o  vykonani prikazu tela cyklu; telo cyklu
je tady vykonano minimalne jednou. Syntaxe vypada takto

	do
		p r i k a z
	while (v y r a z)

Prikaz je vykonan a potom je vyhodnocen vyraz. Kdyz je pravdi-
vy, prikaz je znovu vykonan atd. Jestlize je vyraz nepravdivy,
cyklus je ukoncen. Jak muzeme ocekavat, do-while se pouziva
mene nez while a for /odhadem je to asi 5% vsech cyklu/ nicme-
ne je cas od casu uzitecny, jako napr. v nasledujici funkci 
itoa, ktera konvertuje cislo na znakovy retezec /inverzni fun-
kce k atoi/. Uloha je ponekud komplikovanejsi, nez by se mohlo
na prvni pohled zdat, protoze jednoducha metoda pro generova-
ni cislic je generuje ve spatnem poradi. Zvolili jsme zpusob
generovani pozpatku a potom invertovani retezce.

	itoa(n, s)	/*konverze n na znaky v s*/
	char s[];
	int n;
	{
		int i, sign;
		if((sign = n) < 0)	/*zjisteni znamenka*/
			n = -n;		/*n bude kladne*/
		i = 0;,
		do	/*generovani cislic v opacnem poradi*/
Š.po 12
		{
			s[i++] = n % 10 + '0';/*dalsi cislice*/
		}
		while((n /= 10) > 0);	/*smazani cislice*/
		if(sign < 0)
			s[i++] = '-';
		s[i] = '\0';
		reverse(s);
	}

Cyklus do-while je zde nezbytny, nebo alespon vyhodny, protoze
pole s musi obsahovat alespon jeden znak nehlede na hodnotu 
cisla n. Uzili jsme rovnez zavorky okolo jednoho prikazu, ktery
tvori telo cyklu do-while, i kdyz jsou zbytecne, takze ukvapeny
ctenar si nesplete cast cyklu do s prikazem cyklu while.

C v i c e n i  3-3. Nase verze programu itoa pri reprezen-
taci cisel ve dvojkovem doplnku neumi zachazet s nejvetsim
zapornym cislem, tj. n = -(2**(delka slova -1)). Vysvetlete
proc. Upravte ji tak, aby tisklo i tuto hodnotu spravne a
nezavisle na typu pocitace.
C v i c e n i  3-4. Napiste obdobnou funkci itob(n, s), ktera
konvertuje cele cislo n bez znamenka na binarni reprezentaci
do retezce s. Napiste take funkce itoh, ktera konvertuje cele
cislo na hexadecimalni reprezentaci.
C v i c e n i  3-5. Napiste verzi funkce itoa, ktera ma tri
argumenty misto dvou. Tretim argumentem bude minimalni delka
pole; konvertovane cislo musi byt doplneno zleva mezerami, aby
bylo dostatecne siroke.


3.7. Break
----------

   Nekdy je vyhodne mit moznost vychazet z cyklu jinde nez na
zacatku nebo na konci. Prikaz break umoznuje predcasny vystup z
cyklu for, while a do a stejne tak z prepinace switch. Prikaz
break pusobi na nejvnitrnejsi vlozeny cyklus /nebo switch/.
   Nasledujici program odstranuje koncove mezery a tabelatory
z kazde radky ze vstupu a pouziva prikazu break k vystupu z
cyklu tehdy, kdyz je nalezen zprava znak, ktery neni tabelator
ani mezera.

	#define	MAXLINE	1000
	main()	/*odstraneni koncovych mezer a tabelatoru*/
	{
		int n;
		char line[MAXLINE];
		while((n = getline(line, MAXLINE)) > 0)
		{
			while(--n >= 0)
				if(line [n] != ' ' && line
					 [n] != '\t')
					break;
			line[n + 1] = '\0';
			printf("%s\n", line);
Š.po 3
		}
	}

Funkce getline vraci delku radky. Vnitrni cyklus while zacina
na poslednim znaku radky /uvedomte si, ze --n zmensuje n pred
pouzitim jeho hodnoty/, prohledava ji odzadu a hleda prvni 
znak, ktery neni mezera, tabelator nebo znak pro novou radku.
Cyklus je prerusen tehdy, je-li takovy znak nalezen nebo kdyz n
se stane zapornym /tzn. cela radka byla prohledana/. Meli byste
si overit, ze program funguje spravne, i kdyz radka obsahuje
jen mezery nebo tabelatory.
   Namisto prikazu break je mozne polozit testovaci relaci na 
zacatek cyklu while:

	while((n = getline(line, MAXLINE)) > 0)
	{
		while(--n > = 0
		&& (line [n] == ' ' || line[n] == '\t' ||
			 line[n] == '\n'))
		;
		...
	}

   Tato varianta neni lepsi nez predchozi, protoze testovaci 
podminka neni jiz tak jasna. Podminkam, ktere obsahuji smes 
&&, ||, ! nebo zavorky je lepsi se vyhnout.


3.8 Continue
------------

   Prikaz continue je obdobou prikazu break, ale mene se ho 
uziva; zpusobuje skok na zacatek  d a l s i   i t e r a c e
nejvnitrnejsiho cyklu /for, while, do/. V cyklech while a do 
je okamzite vyhodnocena podminka, v cyklu for je vykonana
reinicializace. /continue muze byt pouzito pouze v cyklech,
nikolov v prepinacich switch, ktery je uvnitr cyklu, zpusobuje
vykonani dalsi iterace cyklu./
   V nasledujici ukazce jsou vybirana z pole a pouze kladna
cisla, zaporna jsou preskocena.

	for(i = 0; i < N; i++)
	{
		if(a[i] < 0)	/*preskoc zaporne prvky*/
			continue;
		...	/*kladne prvky*/
	}

Prikaz continue je casto pouzivan, kdyz cast cyklu, ktera nas-
leduje, je slozita, takze obracene podminky a vlozeni dalsi by
mohlo byt priliz slozite.

C v i c e n i  3-6. Napiste program, ktery kopiruje vstup na 
vystup s tou vyjimkou, ze kopiruje pouze jednu radku ze skupi-
ny totoznych radek. /Toto je jednoducha verze obsluzneho prog-
ramu uniq v systemu UNIX./
Š.po 12

3.9 Prikaz goto a navesti
-------------------------

   Jazyk C obsahuje take nekonecne zatracovany prikaz goto a
navesti, na ktere smeruje. Obecne vzato, prikaz goto neni nikdy
nepostradatelny a prakticky lze vzdy napsat program bez nej. V
teto knize prikaz goto nepouzivame.
   Nicmene ukazeme nekolik situaci, kde se prikaz goto muze
uplatnit. Obecne pouzitelny je pri vystupu z mnohonasobne vno-
renych struktur, jako napr. vystup ze dvou cyklu najednou. Pri-
kaz break nemuze byt primo pouzit, protoze vystupuje pouze z
vnitrniho cyklu.

	for(...)
		for(...)
		{
		...
		if(katastrofa)
			goto error;
		}
	...
	error:
		chybove hlaseni

Tato organizace je vyhodna, jestlize program neni trivialni a
kdyz se chyba objevuje na ruznych mistech. Navesti ma stejnou
formu jako jmeno promenne a je nasledovano dvojteckou. Muze
byt pripojeno k libovolnemu prikazu ve stejne funkci, jako je
goto.
   Jako jiny prikad uvazujme problem nalezeni prvniho zaporneho
cisla ve dvojdimenzionalnim poli. /Vicedimenzionalni pole jsou
probrany v kap.5./
Jedna moznost je

	for(i = 0; i < N; i++)
		for(j = 0; j < M; j++)
			if(v[i] [j] < 0)
				goto found;
	/*nenalezeno*/
	...
found:
	/*nalezeno na pozici i, j*/
	...

Program, ktery je napsan s prikazem goto muze vzdy byt napsan
bez nej, mozna za cenu opakovanych testu nebo extra promenne.
Nas priklad bez goto bude vypadat takto

	found = 0;,
	for(i = 0; i < N && !found; i++)
		for(j = 0; j < M && !found; j++)
			found = v[i] [j] < 0;
	if(found)
		/*nalezeno na pozici i-1, j-1*/
		...
Š.po 3
	else
		/*nenalezeno*/
		...

Prestoze nejsme dogmatici, vypada to, ze prikaz goto muze byt
uzivan ridce, ne-li vubec.