Upozornění pro čtenáře a uživatele této knihy

Všechna práva vyhrazena. Žádná část této tištěné či elektronické knihy nesmí být reprodukována a šířena v papírové, elektronické či jiné podobě bez předchozího písemného souhlasu nakladatele. Neoprávněné užití této knihy bude trestně stíháno.

Jiří Prokop

Algoritmy v jazyku C a C++

2., rozšířené a aktualizované vydání

TIRÁŽ TIŠTĚNÉ PUBLIKACE

Vydala Grada Publishing, a.s.

U Průhonu 22, Praha 7

jako svou 4705. publikaci

Odpovědný redaktor Pavel Němeček

Sazba Tomáš Brejcha

Počet stran 176

První vydání, Praha 2012

Vytiskly Tiskárny Havlíčkův Brod, a. s.

Husova ulice 1881, Havlíčkův Brod

© Grada Publishing, a.s., 2012

V knize použité názvy programových produktů, firem apod. mohou být ochrannými známkami nebo registrovanými ochrannými známkami příslušných vlastníků.

ISBN 978-80-247-3929-8

ELEKTRONICKÉ PUBLIKACE

ISBN 978-80-247-7715-3 (elektronická verze ve formátu PDF)

ISBN 978-80-247-7716-0 (elektronická verze ve formátu EPUB)

Úvod

V roce 2002, kdy jsem začal na Gymnáziu Christiana Dopplera vést seminář „Programování v jazyku C“, neexistovala na našem knižním trhu učebnice, která by se věnovala algoritmům a používala jazyk C. Algoritmy byly po řadu let prezentovány téměř výlučně v jazyku Pascal, např. [Wir89] a [Top95]. Musel jsem tedy během šesti let algoritmy pro účely výuky naprogramovat, a tak vznikl základ této knihy.

Kniha nechce být učebnicí jazyka C, i když může být k užitku všem, kteří jazyk právě studují. Dobrých učebnic jazyka je dostatek, doporučit lze např. [Her04] nebo [Ka01], pro C++ [Vi02], [Vi97]. Jestliže jsem přesto zařadil do knihy alespoň stručný přehled jazyka C a také úvod do C++, je to proto, aby čtenář měl při studiu knihy vše potřebné pro porozumění zdrojovým textům algoritmů a nemusel hledat informace jinde.

Kdo je s jazykem C seznámen do té míry, že zná nejdůležitější operátory, výrazy a přiřazení, příkazy pro řízení programu, příkazy vstupu a výstupu, funkce a vedle jednoduchých datových typů ještě pole, stačí mu to už ke studiu jednoduchých algoritmů. Takový přehled jazyka obsahuje právě první kapitola, a pak lze studovat druhou, věnovanou rekurzi, a třetí, která se zabývá třídicími algoritmy. Teprve pro studium datových struktur je nutno v kapitole 4 rozšířit zatím popsanou podmnožinu jazyka o struktury a dynamické přidělování paměti. Tyto znalosti jsou pak potřebné i pro pochopení algoritmů na grafech a pro vyhledávání pomocí binárních stromů. Stromy se využívají také k reprezentaci aritmetických výrazů a pro počítačové řešení hlavolamů a her. Popsaná podmnožina jazyka je v těchto kapitolách dále rozšiřována podle potřeby. Algoritmy z kapitol 1 až 8 jsou napsány v jazyku C, teprve kapitola 9 je úvodním popisem C++, a algoritmy v dalších kapitolách jsou v C++.

Z tohoto stručného průvodce obsahem knihy vyplývá samozřejmé doporučení studovat jednotlivé kapitoly postupně, bez přeskakování, protože v každé kapitole se už počítá s tím, co si čtenář osvojil z kapitol předchozích. Výjimkou jsou odstavce přidané ve druhém vydání této knihy, ty je možno při prvním čtení přeskočit. Jedná se o odstavec 1.3 Permutace, odstavec 6.5 AVL stromy, kapitolu 9 Kryptologické algoritmy a odstavec 11.4 Numerické integrování. Dalším doporučením je studium aktivní, usnadňuji ho tím, že všechny algoritmy rozdělené podle kapitol knihy lze najít na webových stránkách www.grada.cz. Zdrojové texty tedy nemusí nikdo pracně vkládat, čtenář může provádět v programech úpravy, mnohde k tomu zdrojový text přímo vybízí tím, že části zdrojového textu jsou „ukryty“ v komentářích. Často lze algoritmus snáze pochopit, zobrazíme-li si některé mezivýsledky. Aktivní způsob studia je kromě toho určitě mnohem zajímavější. Algoritmy jsou ověřeny s použitím kompilátoru Dev C++, některé i kompilátoru Microsoft Visual C++. Čtenář, který by měl ke knize jakékoli připomínky, může je sdělit na emailovou adresu Jiri.Prokop40@seznam.cz. Na závěr přeji svým čtenářům mnoho úspěchů v jejich studiu.

1. Jazyk C

1.1 Stručný přehled jazyka C

Jazyk C rozlišuje velká amalá písmena. „Prog“, „prog“ a„PROG“ jsou tedy tři různé identifikátory. Identifikátory sestávají zpísmen, číslic apodtržítka, číslice nesmí být na prvním místě. Pro oddělování klíčových slov, identifikátorů akonstant slouží oddělovače (tzv. „bílé znaky“). Všude tam, kde mohou být oddělovače, může být komentář.

/*toto je komentar */

Struktura programu: direktivy preprocesoru, deklarace, definice, funkce. Vkaždém programu je právě jedna funkce hlavní (main), která se začne po spuštění programu vykonávat.

1.1.1 Deklarace

Deklarace jsou povinné. Deklaraci jednoduché proměnné tvoří specifikátor typu ajméno (identifikátor proměnné)

int a; /*deklarace celočíselné proměnné a */

int b=1; /*definice proměnné b */

Podle umístění dělíme deklarace na globální (na začátku programu) alokální (vtěle funkce). Lokální proměnné nejsou implicitně inicializovány aobsahují náhodné hodnoty.

Specifikátory typu pro celá čísla: int, char, short int (nebo jen short), long int (nebo jen long).

Každý znich může být signed (se znaménkem) nebo unsigned (bez znaménka), implicitně je signed.

Specifikátory typu pro racionální proměnné: float (32 bytů), double (64), long double (80).

Ukonstant je typ dán způsobem zápisu. Pomocí klíčového slova const můžeme deklarovat konstantní proměnnou, jejíž obsah nelze později měnit:

const float pi=3.14159;

1.1.2 Výrazy apřiřazení

Výrazy jsou vjazyce C tvořeny posloupností operandů aoperátorů. Operátory dělíme podle arity (počet operandů) na unární, binární aternární, podle funkce na aritmetické: +, -, *, /,% pro zbytek po dělení (operátor / má význam reálného nebo celočíselného dělení podle typů operandů), relační: >, <, >=, <=, == (rovnost), != (nerovnost), logické: || (log. součet), && (log. součin), ! (negace). Jazyk C nezná logický typ, nenulová hodnota představuje true, nulová false.

Podmíněný operátor ? (jediný ternární operátor)

x=(a<b) ? a:b;

má stejný význam jako

if (a<b) x=a; else x=b;

Obecně:

v1 ? v2 : v3

v1 je výraz, jehož hodnota je po vyhodnocení považována za logickou. Je-li true, vyhodnotí se výraz v2 avrátí se jeho hodnota, je-li false, pak se vyhodnotí v3 avrátí se jeho hodnota. v2 av3 jsou jednoduché výrazy.

Operátory přiřazení:

a=a+b;

a+=b; /*má význam a=a+b; */

na místě + může být -, *, /,%, & adalší, onichž zatím nebyla řeč.

Operátory inkrementace adekrementace

a++; /*postfixová verze */

--a; /*prefixová verze */

Příklad:

a=10;

x=++a; /*x bude mít hodnotu 11, a taky */

y=a--; /*y=11, a=10 */

Unární operátory: adresní operátor &, operátor dereference *, unární +, unární -, logická negace ! aprefixová inkrementace ++ adekrementace --. Kpostfixovým operátorům patří operátor přístupu kprvkům pole [], operátor volání funkce (), postfixová inkrementace ++ adekrementace -- aoperátory přístupu ke členům struktury, jimž se budu věnovat později.

Operátor přetypování ukáži na příkladu (i1 ai2 jsou celočíselné proměnné, ale chci reálné dělení):

f=(float) i1/i2;

Operátor sizeof pro zjištění velikosti: argumentem operátoru může být jak název typu, tak identifikátor proměnné.

1.1.3 Priorita aasociativita operátorů

Priorita

Operátory

Vyhodnocuje se

1

()[]->postfix.++--

zleva doprava

2

!-pref.++--+-(typ)*&sizeof

zprava doleva

3

*/%

(multiplikativní oper.)

zleva doprava

4

+-

(aditivní operátory)

zleva doprava

5

<<>>

(operátory posunů)

zleva doprava

6

<<=>>=

(relační operátory)

zleva doprava

7

==!=

(rovnost, nerovnost)

zleva doprava

8

&

(operátor bitového součinu)

zleva doprava

9

^

(exklusivní nebo)

zleva doprava

10

|

(operátor bitového součtu)

zleva doprava

11

&&

(operátor logického součinu)

zleva doprava

12

||

(operátor logického součtu)

zleva doprava

13

?:

(ternární podmínkový operátor)

zprava doleva

14

=+=-=*=/=%=>>=&=|=^=

zprava doleva

15

,

(operátor čárky)

zleva doprava

1.1.4 Příkazy abloky

Napíšeme-li za výraz středník, stává se zněj příkaz, jako je tomu vnásledujících příkladech:

float x,y,z;

x=0;

a++;

x=y=z;

y=z=(f(x)+3); /*k hodnotě vrácené funkcí f je přičtena hodnota 3. */

/*Součet je přiřazen jak proměnné z, tak y. */

Příkazy vjazyce C můžeme sdružovat do tzv. bloků nebo složených příkazů. Blok může obsahovat deklarace proměnných na svém počátku adále pak jednotlivé příkazy. Začátek akonec bloku je vymezen složenými závorkami.

Složené příkazy používáme tam, kde smí být použit pouze jeden příkaz, ale potřebujeme jich více. Za uzavírací složenou závorku se nepíše středník.

Příkaz if

má dvě podoby:

if (výraz) příkaz

nebo

if výraz příkaz1 else příkaz2;

Složitější rozhodovací postup můžeme realizovat konstrukcí if else if.

Každé else se váže vždy knejbližšímu předchozímu if.

Příkaz switch abreak

switch(výraz)

{

case konst_výraz1:

/*příkazy, které se provedou, když výraz=výraz1 */

break;

case konst_výraz2:

/*příkazy, které se provedou, když výraz=výraz2 */

….

break;

default: /*příkazy, které se provedou, není-li výraz roven žádnému z předchozích konstantních výrazů */

}

Příkaz break říká, že tok programu nemá pokračovat následujícím řádkem, nýbrž prvním příkazem za uzavírající složenou závorkou příkazu case.

Vtěle příkazu switch budou provedeny všechny vnořené příkazy počínaje tím, na který bylo předáno řízení, až do konce bloku (pokud některý zpříkazů nezpůsobí něco jiného– např. break). Tím se switch značně liší od pascalského case.

Příkaz while

while (výraz) příkaz;

Výraz za while představuje podmínku pro opakování příkazu. Není-li podmínka splněna už na začátku, nemusí se příkaz provést ani jednou. Je-li splněna, příkaz se provede apo jeho provedení se znovu testuje podmínka pro opakování cyklu.

Příkaz do-while

Zajistí aspoň jedno provedení těla cyklu, protože podmínka opakování se

testuje na konci cyklu.

do příkaz while (výraz);

Příkaz for

Nejčastější podoba příkazu je for (i=0;i<n;i++), kde ije proměnná cyklu, inicializační výraz jí přiřadí počáteční hodnotu 0, opakování cyklu bude probíhat shodnotou proměnné zvýšenou o1 tak dlouho, dokud bude i< n. Obecný tvar příkazu for vypadá následovně:

for(inicializační_výraz;podmíněný výraz;opakovaný výraz) příkaz

je ekvivalentní zápisu:

inicializační výraz;

while (podmíněný výraz)

{

příkaz

opakovaný výraz

}

Inicializační výraz může být vypuštěn, zůstane po něm však středník. Stejně může být vynechán ipodmíněný výraz aopakovaný výraz. Příkaz continue je možno použít ve spolupráci se všemi uvedenými typy cyklů. Ukončí právě prováděný průchod cyklem apokračuje novým průchodem. Podobně ipříkaz break může být použit ve všech typech cyklů kjejich ukončení.

Příkaz goto anávěští

Příkaz goto přenese běh programu na místo označené návěštím (identifikátor ukončený dvojtečkou). Jsou situace, kdy může být výhodný, např. chceme-li vyskočit zvnitřního cyklu zvíce vnořených cyklů.

Prázdný příkaz

;

Použití všude tam, kde je prázdné tělo.

1.1.5 Preprocesor

Preprocesor zpracuje zdrojový text programu před překladačem, vypustí komentáře, provede záměnu textů, např. identifikátorů konstant za odpovídající číselné hodnoty avloží texty ze specifikovaných souborů. Příkazy pro preprocesor začínají znakem # anejsou ukončeny středníkem. Nejdůležitějšími příkazy jsou #define a #include.

#define ID hodnota

Říká, že preprocesor nahradí všude vtextu identifikátor ID specifikovanou hodnotou, např.

#define PI 3.14159

#include <stdio.h>

znamená příkaz vložit do zdrojového textu funkce vstupu avýstupu ze systémového adresáře.

#include "filename"

znamená, že preprocesor vloží text ze specifikovaného souboru vadresáři uživatele.

Některé standardní knihovny:

stdio.h funkce pro vstup avýstup

stdlib.h obecně užitečné funkce

string.h práce sřetězci

math.h matematické funkce vpřesnosti double

time.h práce sdatem ačasem

1.1.6 Funkce

Každá funkce musí mít definici a:

má určeno jméno, pomocí kterého se volá;

může mít parametry, vnichž předáme data, na kterých se budou vykonávat operace;

může mít návratovou hodnotu poskytující výsledek;

má tělo složené zpříkazů, které po svém vyvolání vykoná. Příkazy jsou uzavřeny ve složených závorkách {}.

Příkaz return vyraz; vypočte hodnotu vyraz, přiřadí ji jako návratovou hodnotu funkce afunkci ukončí.

Příklad:

int max(int a, int b) /*hlavička */

{

if (a>b) return a;

return b;

}

Nevrací-li funkce žádnou hodnotu, píšeme vmístě typu návratové hodnoty void. Nepředáváme-li data, uvádíme jen kulaté závorky nebo void. Neznáme-li definici funkce, apřesto ji chceme použít, musíme mít deklaraci funkce (prototyp), která určuje jméno funkce, paměťovou třídu atypy jejích parametrů. Na rozdíl od definice funkce již neobsahuje tělo aje vždy ukončena středníkem.

int max(int a, int b);

nebo jen

int max(int,int);

Pokud neuvedeme paměťovou třídu, je automaticky přiřazena třída extern. Je-li funkce definována vpaměťové třídě extern (explicitně nebo implicitně), můžeme definici funkce umístit do jiného zdrojového souboru. Funkce je společná pro všechny moduly, ze kterých se výsledný program skládá amůže být vlibovolném modulu volána. Je-li deklarována ve třídě static, musí její definice následovat ve stejné překladové jednotce aje dostupná pouze vjednotce, ve které je deklarována adefinována.

Volání funkcí:

výraz(seznam skutečných parametrů);

Nemá-li funkce žádné parametry, musíme napsat (). Parametry se vždy předávají hodnotou, jsou tedy následně překopírovány do formálních parametrů funkce. Rekurzivní funkce jsou vC dovoleny.

1.1.7 Vstup avýstup

Standardní vstup avýstup: stdin, stdout

Standardní vstup avýstup znaků

int getchar(void); /*načte 1 znak */

int putchar(int znak); /*výstup 1 znaku */

Pro načtení avýstup celého řádku znaků

char *gets(char *radek);

int puts(const char *radek);

Funkce gets načte znaky ze standardního vstupu, dokud není přechod na nový řádek. Ten už není do pole zapsán. Návratovou hodnotou je ukazatel předaný funkci jako parametr. Když došlo knějaké chybě, má hodnotu NULL. Na řádku nesmíme zadat více znaků než je velikost pole. Funkce puts vypíše 1 řádek textu, za který automaticky přidá přechod na nový řádek. Řetězec samotný nemusí tento znak obsahovat. Vpřípadě, že výstup dopadl dobře, vrátí funkce nezápornou hodnotu, jinak EOF.

Formátovaný vstup avýstup

Funkce printf ascanf snásledujícími deklaracemi:

int printf(const char *format,…);

int scanf(const char *format,…);

Obě funkce mají proměnný počet parametrů, který je určen prvním parametrem– formátovacím

řetězcem. Formátovací řetězec funkce printf může obsahovat dva typy informací. Jednak jde oběžné znaky, které budou vytištěny, dále pak speciální formátovací sekvence znaků začínající% (má-li být% jako obyčejný znak, musím jej zdvojit). Ktisknutelným znakům patří také escape sekvence, např. \n.

scanf se liší tím, že formátovací řetězec smí obsahovat jen formátovací sekvence, atím, že druhým adalším parametrem je vždy ukazatel na proměnnou (adresa proměnné).

Formátovací sekvence (printf)

%[příznak][šířka][přesnost][F][N][h][l][L]typ

typ

d,i znaménkové decimální číslo typu int

o neznam. oktalové číslo typu int

u neznam. decimální číslo typu int

x,X neznam.hexadecimální číslo typu int, pro x tištěno a, b, c, d, e, f,

pro X pak A, B, C…

f znam.racionální číslo formátu [-]dddd.dddd

e,E znam. rac. č. vexp.formátu [-d]d.ddde[+|-]ddd

g,G znam. rac. č. ve formátu bez exponentu nebo sexponentem (vzávislosti na velikosti čísla)

c jednoduchý znak

s ukazatel na pole znaků ukončené nulovým znakem

p tiskne argument jako ukazatel

n ukazatel na číslo typu int, do kterého se uloží počet vytištěných znaků

příznak

- výstup zarovnán zleva adoplněn zprava mezerami

+ učísel vždy znaménko

mezera kladné číslo mezera, záporné minus

# závisí na typu

šířka

n alespoň n znaků se vytiskne doplněno mezerami

0n je vytištěno alespoň n znaků doplněných zleva nulami

* šířka dána následujícím parametrem

přesnost

(nic) je různá podle části typ

.0 stand

.n n des. míst

* přesnost dána následujícím parametrem

h argument funkce chápán jako short int - pouze pro d, i, o, u, x, X

l long int

L long double

Formátovací sekvence (scanf)

%[*][šířka][F|A][h|l|L]typ

typ

d celé číslo

u celé číslo bez znaménka

o oktalové

x hexadecimální

i celé číslo (spředponou o- oktalové, 0x hexadecimální

a počet přečtených znaků do aktuální chvíle

e, f, g racionální čísla typu float, lze modifikovat pomocí l, L

s řetězec znaků na vstupu oddělený mezerou od ostatních znaků

c jeden znak

* přeskočení dané položky vstupu

šířka max. počet znaků vstupu pro danou proměnnou

sprintf asscanf realizují formátovaný vstup avýstup zpaměti. Potřebují textový řetězec, který se bude chovat jako standardní vstup / výstup

int sprintf(char *buffer,const char *format,…);

int sscanf(char *buffer,const char *format,…);

1.1.8 Ukazatele

Ukazatel je proměnná, jejíž hodnota je adresa jiné proměnné nebo funkce. Deklarace ukazatele se skládá zuvedení typu, na který ukazujeme, ajména ukazatele, doplněného zleva hvězdičkou.

int *pCeleCis; /*může ukazovat na libovolné místo, kde je uložena proměnná typu int */

float *pReal1, *pReal2; /*ukazatelé na libovolné proměnné typu float */

Ukazatel po svém založení neukazuje na žádnou platnou proměnnou aoznačujeme jej neinicializovaný ukazatel. Shodnotou neinicializovaného ukazatele nesmíme nikdy pracovat. Inicializaci ukazatele můžeme provést např. pomocí operátoru &, který slouží kzískání adresy objektu.

int Cislo=7;

int *pCislo;

pCislo=&Cislo;

Jakmile ukazatel odkazuje na smysluplné místo vpaměti, můžeme sním pracovat. Ktomu potřebujeme ještě operátor *, kterému říkáme operátor dereference.

int x, y=8;

int *pInt;

pInt=&y;

x=*pInt; /*v x je 8 */

y=*pInt+20; /*do y se uloží součet obsahu proměnné, na kterou ukazuje pInt, a konstanty 20 */

1.1.9 Adresní aritmetika

Význam aritmetických operací sukazateli spočívá ve zvýšení přehlednosti azrychlení chodu programu. Aritmetika ukazatelů je omezena na operace sčítání, odčítání, porovnání aunární operace inkrementace adekrementace. Jestliže p je ukazatel, p++ inkrementuje p tak, že zvýší jeho hodnotu nikoli ojedničku, nýbrž opočet bytů představující velikost typu, na který ukazatel p ukazuje.

y=*(pInt+50); /*tady zvětšuji hodnotu ukazatele o 50*sizeof(int) */

1.1.10 Ukazatele afunkce

Má-li funkce vrátit více než jednu hodnotu, použijeme ukazatele:

void vymen(int *px, int *py)

{

int pom; pom=*px; *px=*py; *py=pom;

}

int a=7,b=4;

vymen(&a, &b); /*tím vlastně dosáhnu předání odkazem */

Ukazatel na funkci afunkce jako parametry funkcí

Definice double (*pf)(); definuje pf jako ukazatel na funkci vracející hodnotu typu double. Dvojice prázdných závorek je nezbytná, jinak by pf byl ukazatel na double. Závorky kolem jména proměnné jsou také nutné, protože double *pf() znamená deklaraci funkce pf, která vrací ukazatel na double. Přiřadíme-li ukazateli pf jméno funkce, můžeme tuto funkci vyvolat příkazem pf(); i (*pf)();. Jméno funkce je tedy adresou funkce podobně jako jméno pole je adresou pole. Ukazatel, jemuž jsme přiřadili jméno funkce, může být také předán jako parametr jiné funkci. Příklad užitečného využití této možnosti uvidíme vodstavci 3.9.

1.1.11 Pole

Pole je datová struktura složená zprvků stejného datového typu. Deklarace pole vypadá obecně takto:

typ id_pole [pocet];

Vhranatých závorkách musí být konstantní výraz, který udává počet prvků pole. Pole vjazyku C začíná vždy prvkem sindexem nula anejvyšší hodnota indexu je počet-1. Jazyk C zásadně nekontroluje meze polí! Kprvkům pole přistupujeme pomocí indexu, např. id_pole[0] pro první prvek pole. Indexem může být výraz. Pole můžeme při jeho deklaraci inicializovat konstantami, uvedenými mezi složenými závorkami aoddělovanými čárkou:

int pole[5]={6,7,8,9,10}

Počet inicializátorů by měl být menší nebo roven počtu prvků pole. Má-li pole být parametrem funkce, bude formální parametr tvořen typem aidentifikátorem pole následovaným prázdnými hranatými závorkami, např. double pole[]. Jako skutečný parametr stačí jméno pole, tedy adresa začátku pole. Pole se tedy předává na rozdíl od jednoduchých proměnných odkazem. Pole nemůže být typem návratové hodnoty funkce (ikdyž struktura obsahující pole jím být může). Spolem jako celkem není možné provádět žádné operace svýjimkou určení velikosti pole operátorem sizeof aurčení adresy pole operátorem &.

1.1.12 Ukazatele apole

int *pData;

zapíšeme explicitně všechny jednoprvkové cykly;

vkaždém cyklu bude na prvním místě nejmenší prvek;

cykly seřadíme vklesajícím pořadí jejich prvních prvků.