Programování II.
Mgr. Monika Pinkasová
Zlepšování podmínek pro využívání ICT ve výuce a rozvoj výuky angličtiny na SPŠei Ostrava č. projektu CZ.1.07/1.1.07/03.0089
Ostrava 2011
Obor: Informační technologie Předmět: Programování Ročník: 2. a 3. ročník Autor: Mgr. Monika Pinkasová
Doporučená literatura: Herout, P.: Učebnice jazyka C – 1.díl, Páté vydání, Kopp, 2008, ISBN 978-80-7232-351-7 Herout, P.: Učebnice jazyka C – 2.díl, Druhé přepracované vydání, Kopp, 2004, ISBN 80-7232-221-4 K Kadlec, V.: Učíme se programovat v jazyce C, 2. Vyd., Brno : CP Books, 2005, ISBN 80-7226-715-9 Schildt, H.: Nauč se sám C, překlad Lubomír Kočí, Praha : SoftPress, c2001, ISBN 80-86497-16-X
© Mgr. Monika Pinkasová © Střední průmyslová škola elektrotechniky a informatiky, Ostrava, příspěvková organizace
OBSAH Úvod ............................................................................................................................... 6 1
Funkce, stavba funkce .......................................................................................... 7 1.1
2
Stavba uživatelské funkce .......................................................................................... 8
Deklarace a definice funkce ................................................................................ 11 2.1 2.2
Příkaz return() ...........................................................................................................11 Deklarace a definice funkce.......................................................................................12
3
Volání a provádění funkce .................................................................................. 16
4
Funkce – řešené příklady .................................................................................... 20
5
Funkce – neřešené příklady ................................................................................ 23
6
Strukturované programování.............................................................................. 26
7
Globální a lokální proměnné ............................................................................... 30
8
Rekurzivní funkce ................................................................................................ 34
9
Rekurzivní funkce – shrnutí a procvičování ...................................................... 39
10 10.1 10.2 10.3 10.4 10.5 10.6
11 11.1 11.2
12 12.1 12.2
Způsob zpracování programu ......................................................................... 42 Editor .........................................................................................................................43 Preprocesor ...............................................................................................................43 Compiler ....................................................................................................................44 Linker ........................................................................................................................44 Debugger ..................................................................................................................44 Chyby a chybové hlášení...........................................................................................45
Preprocesor, makra bez parametru ................................................................ 47 Preprocesor ...............................................................................................................47 Makra bez parametru ................................................................................................48
Makra s parametrem ........................................................................................ 51 Makra s parametrem .................................................................................................51 Rozdíl mezi makry a funkcemi ...................................................................................52
13
Makra - procvičování ....................................................................................... 55
14
Podmíněný překlad řízený hodnotou makra .................................................. 58
15
Podmíněný překlad řízený existencí makra ................................................... 61
16
Oddělený překlad a vkládání souborů ........................................................... 64
16.1 16.2
Vkládání souborů.......................................................................................................64 Oddělený překlad ......................................................................................................65
17
Hlavičkové soubory ......................................................................................... 67
18
Projekty ............................................................................................................. 70
19
Projekty – řešené příklady............................................................................... 75
20
Projekty – neřešené příklady .......................................................................... 78
21
Paměťové třídy ................................................................................................. 83
21.1 21.2 21.3 21.4
22 22.1 22.2
Paměťová třída auto ..................................................................................................84 Paměťová třída register .............................................................................................84 Paměťová třída extern ...............................................................................................84 Paměťová třída static.................................................................................................85
Alokace paměti, pointery ................................................................................. 87 Alokace paměti ..........................................................................................................87 Pointery .....................................................................................................................88
23
Pointery - procvičování ................................................................................... 93
24
Pointery a funkce ............................................................................................. 97
25
Pointery a funkce - procvičování .................................................................. 101
26
Jednorozměrné statické pole ........................................................................ 105
27
Práce s jednorozměrným statickým polem ................................................. 108
28
Jednorozměrné dynamické pole................................................................... 111
29
Jednorozměrné pole - procvičování ............................................................. 114
30
Pointerová aritmetika..................................................................................... 119
30.1 30.2
Operace s pointery ..................................................................................................119 Využití pointerové aritmetiky ....................................................................................121
31
Pointerová aritmetika - procvičování ........................................................... 123
32
Pole a funkce .................................................................................................. 126
33
Třídící algoritmy ............................................................................................. 129
34
Bubble sort ..................................................................................................... 133
35
Shrnutí učiva .................................................................................................. 137
Vysvětlivky k používaným symbolům
Obsah hodiny – popisuje náplň hodiny
Cíl hodiny – specifikace dovedností a znalostí, které si studující osvojí během hodiny
Klíčová slova – nové pojmy, specifické termíny či cizí slova, jejichž význam je v textu vysvětlen
Definice – definování a vysvětlení nového pojmu či jevu
Příklad – objasnění nebo konkretizování problematiky na příkladu ze života, z praxe, ze společenské reality apod.
Shrnutí – shrnutí probrané látky, shrnutí kapitoly
Kontrolní otázky a úkoly – prověřují, do jaké míry studující text a problematiku pochopil, zapamatoval si podstatné a důležité informace a zda je dokáže aplikovat při řešení problémů Otázky k zamyšlení - úkoly rozšiřující úroveň základních znalostí
Literatura – literatura a zdroje pro doplnění a rozšíření poznatků kapitoly
6
Úvod Tento výukový modul se zabývá základy programování v jazyce C. Navazuje tak na výukový modul Programování I a znalosti tohoto modulu jsou nezbytně nutné vstupní předpoklady do modulu Programování II. Modul Programování II. je určen pro studenty 2. a 3. ročníku oboru Informační technologie. Cílem modulu Programování II. je rozšířit a zdokonalit stávající znalosti programování v jazyce C. Studenti se seznámí se základními prvky jazyka C - s funkcemi, s tvorbou projektů, se strukturovaným datovým typem pole a jeho využitím. Prostudováním tohoto textu si student osvojí základní znalosti a pojmy, ale jen cvičením a používáním těchto znalostí v praktickém programování se může dostat k aktivnímu použití jazyka.
7
1
Funkce, stavba funkce
Obsah hodiny Seznámíme se s významem funkcí, jejich dělením, důvodem tvorby funkcí a stavbou funkcí.
Cíl hodiny Po této hodině budete schopni: ● ● ●
zdůvodnit vytváření funkcí rozlišit standardní funkce a uživatelské funkce popsat stavbu funkce a specifikovat jednotlivé části hlavičky funkce
Klíčová slova Funkce, funkce main(), standardní funkce, uživatelské funkce, návratová hodnota funkce, název funkce, parametry funkce
Funkce je v jazyce C základním stavebním kamenem programu. Každý program obsahuje vždy alespoň jednu funkci. Zatím jsme vždy programovali vždy s jednou funkcí a tou je funkce main(). Funkce main() je vstupní bod každého programu a po spuštění programu se automaticky začne vykonávat. S koncem funkce main() končí i celý program. Všechny funkce mají stejnou stavbu jako funkce main(). Obecně funkci v programu vytvoříme, pokud se v programu nějaká činnost několikrát opakuje. Nejde však o opakování jako u cyklů, kdy se jedna činnost několikrát opakuje za sebou. Jde o provedení určité stejné činnosti v několika různých částech programu. Pak je výhodné nepsat stejné příkazy pro vykonání stejné činnosti do různých částí programu, ale je vhodné je vyčlenit do funkce a funkci pak volat v místě programu, kde danou činnost potřebujeme. Funkce představují základní jednotku programu, která řeší určitý problém. Funkce umožní složitý problém rozložit do menších částí.
8
Funkce používané v programech rozdělujeme na: Standardní funkce jsou definovány normou jazyka a výrobce překladače je dodává jako součást programového balíku tvořící překladač a jeho podpůrné programy a soubory. Tyto standardní funkce zpravidla dostáváme jako součást standardních knihoven (proto se jim někdy říká knihovní funkce) a jejich deklarace je popsána v hlavičkových souborech. Neznáme jejich zdrojový kód. Například jde o funkce printf() a scanf(), jejichž deklarace je popsána v souboru <stdio.h>. Uživatelské funkce jsou ty funkce, které vytváříme my sami, a proto také máme jejich zdrojové texty. Své funkce vytváříme nejen pro konkrétní program, ale pro jejich možné znovupoužití i v jiných programech. Je pak výhodné své vlastní odladěné funkce ukládat do jednoho nebo více souborů, případně si z nich vytvořit vlastní knihovnu, ale o tom více až v kapitole o projektech. Překladač může obsahovat i mnoho dalších funkcí, které nejsou v normě ANSI C. Jejich použití musíme nastudovat v dokumentaci. Jsou to funkce závislé jak na překladači, tak mnohdy na operačním systému. Proto se jejich použitím značně snižuje přenositelnost kódu.
1.1
Stavba uživatelské funkce
Jak jsme již řekli, každá funkce má stejnou stavbu jako funkce main().
Stavba funkce: návratový_typ název_funkce( seznam_ parametrů ) { deklarace lokálních proměnných příkazy
tělo funkce
} Prvnímu řádku funkce říkáme hlavička funkce.
1.1.1
Návratový typ
Návratový typ určuje datový typ hodnoty, kterou bude funkce vracet. Jestliže datový typ neuvedeme, bude implicitně nastaven datový typ int.
9
Příklad •
pokud funkce bude určovat aritmetický průměr dvou celých čísel, bude návratová hodnota float.
•
pokud bude funkce vracet součet dvou celých čísel, bude návratová hodnota int.
•
pokud bude funkce vykonávat jen určitou činnost ne výpočet (třeba vypisovat naše jméno a adresu), nebude pak vracet nic a návratový typ bude void.
Poznámka: Návratová hodnota funkce main() se vrací operačnímu systému. Zaběhnutá praxe je, že návratová hodnota 0 znamená úspěšné ukončení programu a jakákoliv jiná hodnota určuje číslo chyby.
1.1.2
Název funkce
Název funkce neboli její identifikátor je určující pro identifikaci naší funkce. Musíme si jej promyslet tak, abychom se vyhnuli klíčovým rezervovaným slovům (např. printf, main, for) a vyhovoval stejným pravidlům jako identifikátory proměnných – musí začínat písmenem nebo podtržítkem, rozlišují se velká a malá písmena. Název funkce by měl být volen tak, aby hned z názvu bylo zřejmé, co funkce dělá. Název proměnné a název funkce od sebe my i překladač odlišujeme kulatými závorkami, které u názvu funkce musíme vždy uvést, a to i tehdy kdy funkce nemá žádné parametry a závorka je prázdná.
1.1.3
Parametry funkce
Parametry funkce jsou očekávaná data, která funkce bude zpracovávat. Tyto parametry, které budeme označovat jako formální parametry funkce, jsou lokální proměnné funkce, tzn., že jsou známé jen v rámci této funkce, ne mimo ni. Každý parametr musí mít své jméno a musí být u něj určen datový typ. Pokud funkce nemá žádné parametry, napíšeme do závorky void. Pokud jich máme ve funkci více, oddělujeme je čárkou. Jsou-li parametry stejného datového typu, nemůžeme zkrátit zápis jejich deklarace, jako to jde u proměnných mimo hlavičku funkce, jak ukazuje následující příklad:
10
Příklad int nasobeni (int a,b)
//nelze !!!
int nasobeni (int a, int b)
//správný zápis
Shrnutí kapitoly Funkce je základním stavebním kamenem programů v jazyce C, který řeší určitý dílčí problém v našem programu. Rozlišujeme standardní funkce, kterými jsou příkazy používané v programování v jazyce C, a uživatelské funkce, které vytváří každý programátor sám. Funkce mají jednotně danou stavbu: návratový_typ název_funkce( seznam_ parametrů ) { deklarace lokálních proměnných příkazy }
Kontrolní otázky a úkoly 1) Kdy vytváříme funkce v programu? 2) Co jsou to standardní funkce? 3) Popište jednotlivé části stavby funkce a vysvětlete jejich význam.
11
2
Deklarace a definice funkce
Obsah hodiny Seznámíme se s činností příkazu return. Naučíme se rozlišovat pojmy deklarace a definice funkce a ukážeme si možnosti umístění funkce do kódu našeho programu.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vysvětlit význam příkazu return ve funkcích rozlišit a popsat deklaraci a definici funkce vhodně začlenit deklaraci a definici funkce do kódu programu
Klíčová slova Příkaz return, deklarace funkce, definice funkce
2.1
Příkaz return()
V minulé kapitole jsme si popsali hlavičku funkcí. Za hlavičkou funkce následuje blok příkazů – tzn. příkazy uzavřené do složených závorek. Na začátku každého bloku v programu můžeme nadeklarovat lokální proměnné, které budou viditelné jen v rámci tohoto bloku a po jeho skončení zaniknou. Stejně tak je to u funkcí. Na začátku bloku za složenou závorku si ve funkci nadeklarujeme všechny potřebné proměnné, které ve funkci budeme potřebovat. Za případnou deklaraci proměnných zapisujeme příkazy, které vedou k řešení úlohy zpracovávanou funkcí. Funkci ukončujeme příkazem return výraz; Příkaz return způsobí okamžité ukončení funkce. Příkazy, které jsou zapsány za ním, se neprovedou. Hodnota výraz je návratovou hodnotou funkce a ta bude vrácena na místo, kde byla celá funkce volaná, jako její výsledek.
12
Příklad int secti(int a, int b) { return(a+b); } Tato funkce secti má dva celočíselné vstupní parametry – a, b. Jejím výsledkem (výstupem) je součet těchto parametrů. Proto je také návratový typ funkce secti celočíselný typ int. Příkaz return funkci secti ukončí a vrátí součet a+b do místa volání funkce secti. Příkaz return však nejen ukončuje funkci a vrací výstupní hodnotu funkce, ale provádí také kontrolu a popřípadě konverzi výstupní hodnoty podle návratové hodnoty funkce.
Příklad int pokus( void ) { return(3.54); } V této funkci vracíme reálné číslo 3.54, ale návratová hodnota funkce je int. Příkaz return provede konverzi hodnoty 3.54 na datový typ int, což provede odseknutím reálné části čísla 3.54 a ponechá jen jeho celou část. Funkce pokus tedy bude vracet číslo 3.
2.2
Deklarace a definice funkce
Otázkou vytvoření a využití vlastní funkce v kódu našeho programu zůstává její umístění v rámci stavby programu. Abychom mohli uvést možnosti umístění funkce, musíme si vysvětlit pojmy deklarace a definice funkce. Deklarace funkce je uvedení hlavičky funkce ukončené středníkem. Říkáme tím překladači, že bude někde existovat funkce s daným názvem, návratovým typem a danými parametry. Definice funkce je zápis celé funkce včetně hlavičky i těla funkce. Předtím, než funkci použijeme (zavoláme), měla by být vždy předem definována nebo deklarována. To proto, aby překladač znal všechny formální parametry a mohl vytvořit správný kód.
13
Příklad void vizitka(void) { printf("Ferda Mravenec \n "); printf("práce všeho druhu \n "); } int main() { vizitka();
// volání funkce
getch(); return 0; } Funkce vizitka() nemá žádné parametry, proto je v závorce v hlavičce funkce uvedeno void. Funkce také nemusí nic vracet, protože jen vykonává určitou činnost – vypisuje dva řetězce. Proto ve funkci není uveden příkaz return a návratová hodnota funkce je void. Příklad zapsaný v tomto tvaru bude bez problémů fungovat. Pokud ale celou definici funkce vizitka() přesuneme pod funkci main(), nepůjde program spustit. int main() { vizitka();
// volání funkce
getch(); return 0; } void vizitka(void) { printf("Ferda Mravenec \n "); printf("práce všeho druhu \n "); } Překladač prochází náš kód řádek po řádku, a když narazí na volání funkce vizitka() zastaví se, protože identifikátor vizitka nezná a neví jak s ním naložit.
14 V takovémto případě musíme před funkci main() vložit hlavičku funkce vizitka(). Pak už překladač na řádku volání funkce bude o funkci vizitka() vědět a program přeloží. Funkční program pak bude vypadat takto: void vizitka(void);
// deklarace funkce
int main() { vizitka(); getch(); return 0; } void vizitka(void) // definice funkce { printf("Ferda Mravenec \n "); printf("práce všeho druhu \n "); } Proč si takto zápis funkcí komplikujeme? Představte si, že váš program bude obsahovat dvacet a víc funkcí. Všechny jejich definice umístíte nad funkci main(). Vznikne tak nepřehledný kód, ve kterém třeba po čase budete dlouho hledat hlavní funkci main() a hlavní smysl úlohy, kterou program má řešit. Pokud ale zvolíte druhý postup - před main() zapíšete deklarace všech funkcí a až za main() jejich definice, získáte přehledný kód s úvodním přehledem všech v programu použitých funkcí a po něm kód funkce main(). Proto vám tento druhý přehlednější způsob zápisu funkcí více než doporučuji.
Shrnutí kapitoly Příkaz return ukončí vykonávání funkce, provede případnou konverzi výstupní hodnoty podle návratové hodnoty funkce a tuto hodnotu vrátí do místa volání funkce. Deklarace funkce je uvedení hlavičky funkce ukončené středníkem. Definice funkce je uvedení celé funkce s hlavičkou i s tělem funkce. Deklaraci funkce zapisujeme do kódu programu před funkci main() a definici funkce za funkci main().
15
Kontrolní otázky a úkoly 1) Vysvětlete práci příkazu return. 2) Jaký je rozdíl mezi definici a deklarací funkce? Proč tyto termíny zavádíme? 3) Jaké máme možnosti zápisu funkcí do kódu programu? Vysvětlete, která z těchto možností je vhodnější a proč.
16
3
Volání a provádění funkce
Obsah hodiny Popsat volání a provádění uživatelských funkcí.
Cíl hodiny Po této hodině budete schopni: ● ●
vysvětlit princip provádění funkce navrhnout správné volání funkce
Klíčová slova Volání funkce, skutečné parametry funkce, formální parametry funkce
Definovanou funkci můžeme využít z funkce main() pomocí tzv. volání funkce. Parametry funkce, které uvádíme při volání funkce, nazýváme skutečné parametry. Parametry funkce, které uvádíme v hlavičce funkce, nazýváme formální parametry. Při volání funkce se vyalokují formální parametry jako lokální proměnné funkce a naplní se hodnotami ze skutečných parametrů, které jsou uvedeny při volání funkce. Postup provádění funkce si uvedeme na následujícím příkladu, ve kterém budeme pracovat s funkcí na součet dvou celých čísel. Její deklaraci uvedeme nad main() a definici pod main() z důvodů, které jsme si vysvětlili v předchozí kapitole. Ve funkci main() můžeme funkci soucet využít tzn. zavolat.
17
Příklad // deklarace funkce
int soucet(int a, int b); int main() { int x=5, y=7; printf(“%d“,soucet(x,y));
// volání funkce // x,y jsou skutečné parametry
return; } int soucet(int a, int b)
// definice funkce
{
// a,b jsou formální parametry return(a+b);
} Postup zpracování tohoto programu: Každý program začíná funkci main() a jejím koncem také končí. Proto se nejprve v paměti vyalokují celočíselné proměnné x a y, které se naplní hodnotami 5 a 7.
x
y 5
7
Dalším příkazem printf(“%d“,soucet(x,y)); je volána funkce soucet. Program se posune na definici funkce soucet. Vyalokují se dva celočíselné formální parametry a a b a místo pro návratovou hodnotu funkce, kterou nazveme stejně jako funkci. Formální parametry si převezmou hodnoty ze skutečných parametrů, jak je vyznačeno na obrázku.
x
y 5
a
7 soucet
b 5
7
18 Po tomto vyalokování parametrů, návratové hodnoty a předání hodnot parametrů se provádí tělo funkce. Ve funkci soucet je v těle jediný příkaz return(a+b);, který sečte hodnoty v proměnných a a b, výsledek se uloží do místa pro návratovou hondotu funkce, která se pak vrátí na místo volání funkce- tedy do výpisu.
x
y 5
7
a
b 5
soucet 7
12
Při ukončení funkce soucet končí i platnost formálních parametrů a a b, které se chovají jako lokální proměnné a proto se odalokují. Výstupem uvedeného programu je výpis čísla 12 na obrazovku. Uvědomte si, že skutečné parametry x a y jsou známy jen ve funkci main(), že je nemůžeme použít ve funkci soucet, kde by byly neznámým identifikátorem. Stejně i formální parametry a a b můžeme použít jen ve funkci soucet.
Možnosti volání funkce •
přiřazením
z=soucet(x,y);
- použijeme, pokud hodnotu, kterou funkce soucet vrací, budeme dále potřebovat, a proto si ji uložíme do pomocné proměnné z. •
ve výpisu -
•
použijeme, pokud hodnotu, kterou funkce soucet vrací, nebudeme dále potřebovat, a proto ji jen vypíšeme na obrazovku.
na řádek -
printf(“%d“,soucet(x,y));
soucet(x,y);
použijeme, pokud funkce nevrací žádnou hodnotu (návratový datový typ je void) a provádí jen určitou činnost. Pokud by funkce soucet nějakou hodnotu vracela, byla by tato hodnota při volání na řádek ignorována.
19
Shrnutí kapitoly Pokud chceme funkci využít k nějaké činnosti nebo výpočtu musíme ji zavolat. Parametry z hlavičky funkce se nazývají formální parametry a parametry, které uvádíme při volání funkce, nazýváme skutečné parametry. Při volání funkce se vyalokují formální parametry, které se chovají jako lokální proměnné, a naplní se hodnotami ze skutečných parametrů. Po ukončení funkce se předá návratová hodnota do místa volání funkce a odalokují se všechny formální parametry. Funkci můžeme volat přiřazením do proměnné, ve výpisu a na řádek.
Kontrolní otázky a úkoly 1) Vytvořte svou vlastní funkci, uveďte i její volání ve funkci main() a popište postup zpracování programu. 2) Jaký je rozdíl mezi formálními a skutečnými parametry? 3) Jak můžeme volat funkci a kdy který způsob volání použijeme?
20
4
Funkce – řešené příklady
Obsah hodiny Procvičíme tvorbu funkcí a volání funkcí ve funkci main().
Cíl hodiny Po této hodině budete schopni: vytvořit vlastní uživatelskou funkci a zavolat ji ve funkci main() popsat způsob zpracování funkcí
● ●
Příklad Vytvořte funkci, která převede časový údaj zadaný hodinami, minutami a sekundami na sekundy. Výsledný počet sekund bude funkce vracet.
Řešení int prevod(int hod, int min, int sek);
//deklarace funkce
main() { int hodiny, minuty, sekundy, vysledek; printf(“Zadejte počet hodin, minut a sekund : ”); scanf(“%d %d %d“, &hodiny, &minuty, &sekundy); vysledek=prevod(hodin, minuty, sekundy);
//volání funkce
printf(“\nVýsledný počet sekund : %d”,vysledek); getch(); return 0; } int prevod(int hod, int min, int sek) { return (hodiny*3600+minuty*60+sekundy); }
//definice funkce
21 Funkce prevod bude vracet celé číslo – celkový počet sekund, proto jeho návratová hodnoty je int. Funkce má tři formální parametry. Jde o vstupní hodnoty funkce – počet hodin, minut a sekund. Tyto požadované hodnoty načteme od uživatele ve funkci main() do proměnných hodiny, minuty, sekundy, které pak posíláme do funkce jako skutečné parametry ve volání funkce. Funkci voláme přiřazením do proměnné vysledek, kam se uloží výsledek převodu. Mohli bychom volat funkci prevod i ve výpisu. printf(“\nVýsledný počet sekund : %d”, prevod(hodin, minuty, sekundy));
Příklad Vytvořte funkci, která pro dvě načtená celá čísla d a h vypíše na obrazovku všechna sudá celá čísla v intervalu
.
Řešení Zadaná funkce nebude nic vracet, proto její návratový typ bude void. Bude se tedy volat na řádku. Funkce bude mít dva formální parametry. vodi vypis (int d, int h);
//deklarace funkce
main() { ¨ int dolni, horni; printf(“Zadejte dolní hranici intervalu : ”); scanf(“%d“, &dolni); printf(“Zadejte horní hranici intervalu : ”); scanf(“%d“, &horni); vypis(dolni, horni);
//volání funkce
getch(); return 0; } vodi vypis (int d, int h) { int i; for(i=d; i<=h;i++) if ( i%2==0) printf(“%d“, i); }
//definice funkce
22
Příklad Vytvořte funkci, která vypíše na obrazovku Vaši vizitku.
Řešení Zadaná funkce nebude nic vracet ani do ní nebude nic vstupovat.
void vizitka (void); main() { vizitka( );
//deklarace funkce, // závorku můžeme nechat prázdnou void vizitka ( );
// volání funkce // funkce nic nevrací - volá se na řádku // do funkce nic nevstupuje, proto necháme závorky // prázdné, musíme je však uvést.
getch(); return 0; } void vizitka (void) //definice funkce { printf(“Ferda Mravenec \n Práce všeho druhu \n“); printf(“U mraveniště 6 “); } //příkaz return nemusí být uveden
Shrnutí kapitoly Při vytváření funkce proveďte analýzu a zodpovězte si tyto otázky: • • •
kolik vstupních parametrů budete opravdu potřebovat? má funkce nějakou hodnotu vracet nebo ne? které volání je pro náš program a vytvořenou funkci nejoptimálnější?
Nezapomeňte dodržovat pořadí parametrů včetně jejich datových typů.
23
5
Funkce – neřešené příklady
Obsah hodiny Procvičíme si samostatnou tvorbu funkcí a jejich volání ve funkci main().
Cíl hodiny Po této hodině budete schopni: ● ●
vytvořit vlastní uživatelskou funkci a zavolat ji ve funkci main() popsat způsob zpracování funkcí
Příklad 1. Napište funkci, která vypíše na obrazovku vygenerovaných čísel z intervalu <10;100>.
10
náhodně
2. Napište funkci, která vypíše na obrazovku 10 náhodně vygenerovaných čísel z intervalu <-50;50> a vrátí minimální vygenerovanou hodnotu. 3. Napište funkci, která vypíše na obrazovku zadaný počet náhodně vygenerovaných čísel z intervalu <-30;30>. Počet čísel bude parametrem funkce načtený ve funkci main(). Funkce bude vracet maximální vygenerovanou hodnotu. 4. Napište funkci, která vypíše na obrazovku zadaný počet náhodně vygenerovaných čísel ze zadaného intervalu. Počet čísel a hranice intervalu budou parametry funkce, které načteme ve funkci main(). Funkce bude vracet aritmetický průměr všech takto vygenerovaných čísel.
Příklad Vytvořte v jazyce C následující funkce: 1. int sude(int n); - funkce vrací číslo 1, je-li parametr n sudé číslo, jinak vrací číslo 0.
24 2. int interval(float n, float dolni, float horni); - funkce vrací číslo 1, leží-li parametr n uvnitř intervalu <dolni ; horni> , funkce vrací číslo 0, leží-li parametr n na hranici intervalu <dolni ; horni>, funkce vrací číslo -1, leží-li parametr n mimo interval <dolni ; horni> 3. int abs_hodnota(int x); - funkce vrací absolutní hodnotu daného čísla x 4. long int faktCyklus(int n); - funkce vrací faktoriál čísla n pomoci cyklu 5. char velke_pismeno(char male_pismeno); - funkce vrací pro zadané malé písmeno odpovídající velké písmeno, ostatní znaky vrací nezměněny. 6. int znaky(char znak); - je-li znak malé písmeno anglické abecedy, vrátí funkce číslo 1, je-li znak velké písmeno anglické abecedy, vrátí funkce číslo 2, je-li znak číslicí, vrátí funkce číslo 3, jinak vrátí číslo 0 7. int pismeno(char znak); - je-li „znak“ písmeno a nebo A nebo b nebo B, vrací funkce 1, je-li „znak“ písmeno m nebo M nebo x nebo X, vrací funkce 2, jinak vrací hodnotu 0 (řešte pomocí instrukce switch) 8. int nsd(int a, int b); - funkce vrací největšího společného dělitele dvou celých čísel. 9. long int prevod_tam(int hod, int min, int sec); - čas zadáme v hodinách, minutách a sekundách, funkce vrací čas převedený na sekundy 10. void prevod_zpet(int sec); - funkce převede interval zadaný v sekundách na hodiny, minuty a sekundy a tyto hodnoty vypíšete ve funkci na obrazovku.
Příklad Vytvořte program s nabídkou řešenou pomocí příkazu switch, s volbami 1 až 5 pro jednotlivé úkoly, ve kterých otestujete následující funkce: 1. funkce, která pro tři celá čísla d , h , b a vypočtěte a vrátí součet čísel od d do h bez čísel dělitelných číslem b. Ošetřete případ d
25 2. pro dvě celočíselné proměnné velikost a radek a znak znak vypíše funkce na obrazovku čtverec o zvolené velikosti zvoleného znaku od zvoleného radku PŘ: velikost = 3, znak = *, radek = 4 _ _ _ *** *** *** 3. funkce pro dvě celá čísla a znak, který bude reprezentovat zvolenou operaci (+ součet, - rozdíl, * součin, / podíl vypočte a vrátí výsledek požadované operace. Použijte příkaz switch. 4. funkce, která pro zadané celé číslo (parametr funkce) zjistí a vrátí počet všech přirozených dělitelů zadaného čísla. Pro kontrolu můžete tyto dělitele ve funkci vypsat na obrazovku. 5. Vytvořte program, jehož vstupem je celé číslo a celočíselný exponent. Výstupem programu je mocnina čísla na zadaný exponent.
Shrnutí kapitoly Při vytváření funkce proveďte analýzu a • • •
kolik vstupních parametrů budete opravdu potřebovat zda má funkce nějakou hodnotu vracet nebo ne které volání je pro náš program a vytvořenou funkci nejoptimálnější
Nezapomeňte dodržovat pořadí parametrů včetně jejich datových typů.
26
6
Strukturované programování
Obsah hodiny Objasníme princip a význam strukturovaného programování.
Cíl hodiny Po této hodině budete schopni: ● ●
vysvětlit pojem strukturované programování navrhnout řešení problému pomocí strukturovaného programování - rozdělení řešení na jednotlivé dílčí části
Strukturované programování je metoda návrhu algoritmu založená na principu rozdělení řešení dané úlohy na dílčí části, které řeší samostatně jednotlivý úkol. Následně tyto části propojíme do jednoho celku. Strukturované programování je tedy charakteristické psaním kódu v malých blocích – funkcích, které vzájemným propojením tvoří jeden program řešící zadaný problém. Takto vzniklý algoritmus je jednoduchý a přehledný. Přehlednost a základní principy strukturovaného programování se snadno poruší příkazem skoku, a proto se příkaz skoku ve strukturovaných programech potlačuje.
Příklad Vytvořte program pro výpočet součtu řady, která je dána vztahem:
(n - 1)! /2 + (n - 2)! /3 + (n - 3)! /4 + ... + (n - k)! /(k + 1) Řešení Rozdělíme si řešení této úlohy na jednotlivé menší části. Nejprve vytvoříme funkci na výpočet faktoriálu. Další funkce vypočítá hodnotu jednoho členu řady, což pak použijeme ve funkci, která bude počítat, a vracet součet řady pro zadanou hodnotu n. Po hlubší analýze si uvědomíme, že parametry k a n nemohou být voleny libovolně. Z definice faktoriálu musíme ošetřit, kdy má faktoriál i součet řady smysl.
27 int faktorial(int x); float clen(int n,int k); float rada(int n,int k); float ma_smysl(int n,int k); int main(int argc, char* argv[]) { int n,k; printf("Zadej hodnotu n "); scanf("%d",&n); printf("\nZadej hodnotu k "); scanf("%d",&k); printf("\nVysledek souctu rady je %f", ma_smysl(n,k) ); getch(); return 0; } int faktorial(int x) { int i,vysledek=1; for(i=1;i<=x;i++) vysledek*=i; return vysledek; } float clen(int n,int k) { float vysledek; vysledek=faktorial(n-k)/(float)(k+1); return(vysledek); } float rada(int n,int k) { int i; float vysledek=0; for(i=1;i<=k;i++) vysledek+=clen(n,i); return(vysledek); }
28 float ma_smysl(int n,int k) { while((k==0)||(n
Shrnutí kapitoly Podstatou strukturovaného programování je rozdělení řešení problému na jednotlivé části (např. funkcí), které řeší určité dílčí úkoly. Po spojení a propojení těchto částí získáme program, který řeší celý zadaný problém.
29
Kontrolní otázky a úkoly A) Vytvořte s využitím strukturovaného programování program pro výpočet součtu řady, která je dána vztahem:
(k +1)/1!- (k + 2)/2!+ (k + 3)/3!- (k + 4)/4!+ (k + 5)/5!+ ... + - (k + n)/n! B) Vytvořte program, který pomocí následujících funkcí vypočte životní číslo podle zadaného data narození. 1. Napište funkci cifra, ve které pro zadaný celočíselný parametr vypíšete na obrazovku jeho poslední číslici. 2. Napište funkci cislice, která pro zadaný celočíselný parametr vrátí jeho poslední číslici. 3. Napište funkci pocet, která vrátí počet cifer jejího celočíselného parametru. 4. Napište funkci cifsoucet, která vrátí ciferný součet jejího celočíselného parametru. Využijte přitom funkci cislice. 5. Napište funkci soucet, která pro celočíselný parametr vrátí jednocifernou hodnotu, která vznikne opakovaným ciferným součtem. (př. 358 -> 3+5+8=16 -> 1+6=7) Využijte funkce cifsoucet. 6. Napište funkci zivotni, která pro tři celočíselní parametry představující datum narození: den, mesic, rok vypočte a vrátí životní číslo – jednociferná hodnota = součet ciferného součtu dne, měsíce i roku. Využijte funkci soucet.
30
7
Globální a lokální proměnné
Obsah hodiny Objasníme si pojmy a principy lokálních a globálních proměnných, princip práce s nimi a chování těchto proměnných.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vysvětlit rozdíly lokálních a globálních proměnných aplikovat lokální a globální proměnné do svých programů popsat pojem zastínění proměnných
Klíčová slova Alokace proměnné, lokální proměnné, globální proměnné, zastínění proměnných
Každá proměnná má během existence programu přidělen paměťový prostor odpovídající datovému typu proměnné. Tomuto přidělování paměti říkáme alokace proměnné. Rozdílnost chování proměnných může vzniknout umístěním deklarace proměnné. Globální proměnné se deklarují se mimo všechny funkce i mimo funkci main(). Paměť se alokuje pro tuto proměnnou na začátku programu a uvolňuje se na konci programu. Globální proměnné jsou použitelné v celém souboru, ve kterém je proměnná deklarována, ve všech funkcích, které jsou uloženy v tomto souboru. Globální proměnné se alokují v datové oblasti a automaticky se nulují. Lokální proměnné se deklarují uvnitř funkce nebo bloku ohraničeném závorkami { }. Vznikají na začátku funkce nebo bloku, zanikají na konci této funkce nebo bloku – platí tedy jenom lokálně. Alokují se v zásobníku, nenulují se. Formální parametry funkce jsou také lokální parametry. Rozdílné chování následující příklad.
lokálních
a
globálních
proměnných
vypovídá
31
Příklad int x;
// globální proměnná
void pokus (int c, int d); void main() { int a=3,b=1; printf("Proměnná x před funkcí je %d ", x); pokus(a,b); printf("Výsledek z funkce je %d ", x); getch(); return 0; } void pokus (int c, int d)
// lokální proměnné c, d
{ int pom=4;
// lokální proměnná pom, která se teď alokuje
x=c+d+pom; }
// proměnná pom se na konci funkce odalokuje
Tento příklad je příklad, ze kterého si příklad neberte. Protože je ukázkou toho, jak programátor nepracuje, ale ukazuj nám názorně, jak a kde můžeme použít globální proměnnou x. Globální proměnná x je deklarována mimo všechny funkce a je platná, dostupná a použitelná v obou funkcích – main i pokus. První výpis ve funkci main() vypíše hodnotu nula, protože globální proměnné se automaticky nulují. Po provedení funkce pokus se do proměnné x uloží hodnota, kterou bychom měli raději vrátit pomocí příkazu return. Proto se ve funkci main() vypíše výsledek funkce číslo 8. Tento postup je však nesystémový a „neprogramátorský“. Hodnotu x můžete navíc kdekoliv chtěně i nechtěně přepsat.
32 Jestliže použijete stejný identifikátor pro globální i lokální proměnnou, bude globální proměnná zastíněná. Jak ukazuje následující příklad.
Příklad Text příkladu. // globální proměnné x a y
int x,y=2; int pokus (int c, int d); void main() {
// lokální proměnné a,b, které platí jen ve funkci main()
int a=3,b=1; x=pokus(a,b);
printf("Výsledek z funkce je %d ", x);
// globální proměnná x
getch(); return 0; } void pokus (int c, int d) // lokální proměnné c, d, platné jen ve funkci pokus { int a=4, x; // lokální proměnné a, x platné jen ve funkci pokus // proměnná x zastíní globální proměnnou x x=c+d+a; return x; }
// lokální proměnná x
33
Shrnutí kapitoly Globální proměnné se: • deklarují se mimo všechny funkce i mimo funkci main() • alokují na začátku programu a odalokuje se na konci programu • mohou použít v celém souboru, kde jsou deklarovány, i ve všech funkcích • alokují v datové oblasti • automaticky nulují Lokální proměnné se: • deklarují se na začátku funkce nebo na začátku bloku • alokují na začátku funkce nebo bloku, kde jsou deklarovány. Na jejich konci se odblokují. • mohou použít jen ve funkci nebo v bloku, kde jsou deklarovány • alokují v zásobníku • automaticky nenulují
Kontrolní otázky a úkoly 1) Vyjmenujte rozdíly v chování lokálních a globálních proměnných. 2) Jak se liší práce s lokálními a globálními proměnnými? 3) Co se stane, pokud nazveme stejně lokální i globální proměnnou?
34
8
Rekurzivní funkce
Obsah hodiny Seznámíme se principem rekurze v programování. Popíšeme postup zpracování rekurze.
Cíl hodiny Po této hodině budete schopni: definovat typy rekurze vysvětlit postup zpracování rekurze navrhnout vlastní funkci pracující s rekurzí
● ● ●
Klíčová slova Přímá rekurze, nepřímá rekurze
Z matematiky znáte pojem rekurze jako definování funkce nebo nějakého procesu pomocí sebe sama. V programování lze rekurzi uplatnit, pokud programovací jazyk umožňuje volat program opakovaně v době, kdy jeho předchozí volání ještě nebylo ukončeno. Rekurzivní chování může být různé v závislosti na tom, kolik podprogramů se jí účastní. Rozlišujeme dva základní typy rekurzí: •
Přímá rekurze nastává, pokud funkce volá přímo sama sebe. Pak tuto funkci nazveme rekurzivní funkce.
•
Nepřímá rekurze (vzájemná rekurze) je situace, kdy vzájemné volání podprogramů vytvoří „kruh“. Např. v příkazové části funkce A je volána funkce B, ve funkci B voláme funkci C, která volá funkci A.
Jiné rozlišení rekurze: •
Lineární rekurze - funkce při vykonávání svého úkolu volá sama sebe pouze jednou. Vytváří se takto lineární struktura postupně volaných funkcí.
35
•
Stromová rekurze - funkce se v rámci jednoho vykonání svého úkolu vyvolá vícekrát. Vzniklou strukturu je možné znázornit jako strom.
Obecně se doporučuje rekurzi nepoužívat, protože vždy se dá zapsat algoritmus bez použití rekurze. Řešení ovšem nebývá tak elegantní. A proč se rekurze nedoporučuje? Princip rekurze je, že funkce za svého běhu volá další funkci. Pokud bychom měli toto volání bez nějakého dalšího omezení, dostaneme nekonečný program. První důležitá věc, která musí být při použití rekurze jasně definována, je podmínka pro zastavení. Jde o jakousi zarážku, pro kterou je již přímo definován výsledek. Tím je zajištěno, že se funkce nebude volat donekonečna. Dalším problémem rekurze je tedy spotřeba zdrojů poskytovaných počítačem. Rekurzivní volání vlastně vytváří nové a nové alokace proměnných i návratových datových typů a postupně zaplňuje paměť. Také je potřeba mít zaznamenáno, jak se funkce postupně volaly. To se opět ukládá do paměti, která samozřejmě není neomezená. V případě nevhodného použití lze tuto paměť vyčerpat a výsledný program by havaroval. Proč se tedy rekurzivními funkcemi zabýváme? Existují totiž programovací jazyky, které nepodporují cykly pro opakování určitých činností. Jedná se například o Lisp či Prolog. Pro řešení opakovaných činností používají právě rekurzi a dokazují, že v mnoha případech se jedná o mocnější a univerzálnější programovací techniku.
Příklad Vytvořte funkci pro výpočet n-té mocniny zadaného čísla x.
Řešení bez rekurze Omezíme řešení jen pro n ∈ N . Nejprve vytvoříme funkci jen pomocí cyklu, bez použití rekurze. Využijeme vztahu:
x n = x ⋅ x ⋅ x ⋅ x ⋅ .....x ⋅ x ⋅ n
36
int mocninaC ( int x, int n ) { int i,moc = 1; for( i=0; i< n; i++) moc = moc * x; return moc; } int main(int argc, char* argv[]) { printf("%d",mocninaC(5,3)); getch(); return 0; }
Řešení s rekurzí Rekurzivní řešení využívá vztahu:
x n = x ⋅ x n−1 = x ⋅ x ⋅ x n−2 = ..... = x ⋅ x ⋅ x ⋅ x ⋅ .... ⋅ x ⋅ x 0 n ve kterém se stále opakuje výpočet x , kde mocnina n se
stále zmenšuje, až po nulu, která bude hodnotou pro zastavení rekurze. Pro
x 0 budeme vracet n −1 hodnotu x ⋅ x .
hodnotu 1. Pro ostatní hodnoty bude funkce vracet
int mocninaR ( int x, int n ) { if (n>0) return (x*mocninaR(x,n-1)); else return 1; } int main(int argc, char* argv[]) { printf("%d",mocninaR(5,3)); getch(); return 0; }
37 Grafické znázornění vykonávání rekurzivní funkce mocninaR. Modré šipky znázorňují další a další volání funkce, ještě před tím, než je znám výsledek předchozího volání. Funkce se volá, dokud parametr n=0. Pro toto volání získáme konkrétní výslednou hodnotu - jednička, kterou tzv. zpětným chodem – červenými šipkami vracíme do předchozích volání. Tak získáme výslednou hodnotu pro první volání mocninaR(5,3)=125, což vrátíme do funkce main(). mocninaR(5,3) = 5* mocninaR(5,2) = 5 * 25 = 125
mocninaR(5,2) = 5* mocninaR(5,1) = 5 * 5 = 25
mocninaR(5,1) = 5* mocninaR(5,0) = 5 * 1 = 5
mocninaR(5,0) = 1
Řešení s rekurzí a ternárním operátorem Toto řešení je jen ukázkou efektivního zápisu stejného kódu funkce mocninaR na jednom řádku. int mocninaR ( int x, int n ) { return ( (n>0)? x*mocninaR(x,n-1) : 1); }
Shrnutí kapitoly Rekurzi dělíme na: • přímou – funkce volá sama sebe • nepřímou – funkce volají vzájemně Další dělení rekurze je na lineární a stromovou rekurzi. Při použití rekurze musíme důsledně vytvořit podmínku pro ukončení rekurzivního volání. Jinak vytvoříme nekončící program.
38
Kontrolní otázky a úkoly 1) Vyjmenujte různé typy rekurze. 2) Vysvětlete princip přímé rekurze. 3) Proč se rekurzí zabýváme?
39
9
Rekurzivní funkce – shrnutí a procvičování
Obsah hodiny Shrneme výhody a nevýhody rekurze a procvičíme tvorbu rekurzivních funkcí.
Cíl hodiny Po této hodině budete schopni: vysvětlit výhody a nevýhody rekurze aplikovat rekurzi ve vlastních funkcích sestavit funkci s využitím rekurze
● ● ●
Rekurze je nevýhodná z hlediska efektivity. Každé volání rekurzivní funkce znamená: •
alokování lokálních proměnných, parametrů a návratových hodnot funkcí
•
předávání parametrů a návratových hodnot
•
uvolnění alokované paměti
•
návrat do funkce main()
Velmi nevýhodná je rekurze, pokud počet rekurzivních volání roste rychleji než lineárně. Rekurze je výhodná, pokud: • na efektivitě příliš nezáleží • je zápis rekurzivního algoritmu podstatně jednodušší • nerekurzivní algoritmus neznáme
Příklad Vytvořte funkci, která pomocí rekurze vrátí zadanou hodnotu - faktoriál pro parametr n. Zapište tuto funkci i s využitím ternárního operátoru.
40 Definice faktoriálu: n!=n*(n-1)! =n*(n-1)*(n-2)!= … = n*(n-1)*(n-2)*…*3*2*1
n ⋅ N!(n - 1) pro n > 1 N!(n) = 1 pro n = 1
Příklad Vytvořte funkci, která pomocí rekurze vrátí zadanou hodnotu - ciferný součet pro celočíselný parametr. Příklad výpočtu ciferného součtu pro číslo 523: cifSOU(523)=cifSOU (52)+3 =cifSOU (5)+2+3 =5+2+3=10
x%10 + csoucet(x/ 10) pro x/10 > 0 csoucet(x) = x pro x/10 = 0
Příklad Vytvořte funkci, která pomocí rekurze vrátí zadanou hodnotu - největší společný dělitel dvou celočíselných parametrů x, y pomocí Euklidova algoritmu, který je definovaný takto:
NSD(x - y, y) pro x > y NSD(x, y) = NSD(x, y - x) pro x < y x pro x = y
Příklad Vytvořte funkci, která pomocí rekurze vrátí zadanou hodnotu - n-tého člene Fibonacciho posloupnosti pro celočíselný parametr n.
41 Fibonacciho posloupnost je rekurentně definována:
0 pro n = 0 fibo(n) = 1 pro n = 1 fibo(n - 1) + fibo(n - 2)
Příklad Vytvořte funkci, která pro celočíselný parametr n vypište pomocí rekurze posloupnost n , n-1, n-2, … 3, 2, 1, 1, 2, 3, … n-2, n-1, n Příklad pro n=5 se vypíše: 5, 4, 3, 2, 1, 1, 2, 3, 4, 5
Kontrolní otázky a úkoly 1) Vyjmenujte výhody a nevýhody rekurze. 2) Popište práci na předchozích příkladech. Specifikujte, které části nebo co bylo na jejich vypracování nejsložitější.
42
10 Způsob zpracování programu Obsah hodiny Seznámíme se s průběhem zpracování programu od zapsaného kódu v editoru po spustitelný exe soubor. Jednotlivé části zpracování podrobně popíšeme. Rozdělíme chyby na sémantické a syntaktické.
Cíl hodiny Po této hodině budete schopni: ● ● ●
rozlišit a popsat postup zpracování programu vysvětlit účel jednotlivých části zpracování programu vysvětlit rozdíl mezi syntaktickými a sémantickými chybami
Klíčová slova Preprocesor, compiler, linker, debugger, syntaktická chyba, sémantická chyba
Námi napsaný zdrojový kód v jakémkoliv editoru musí projít několika částmi zpracování tzv. překladem, aby se z něj stal spustitelný exe soubor. Rozeznáváme dva druhy překladačů: 1. Interpret je překladač, který překládá jeden příkaz programu až poté, co byl vykonán předchozí příkaz. Překlad proto probíhá až za běhu programu. Usnadňuje ladění, protože programátor přesně ví, kde se za běhu programu vyskytla chyba. Velikou nevýhodou interpretu je, že překlad příkazů za běhu programu jej velice zpomaluje a proto se interprety dnes téměř nepoužívají. 2. Kompilátor přeloží celý zdrojový kód ještě před spuštěním programu. Tento způsob umožňuje, že program po spuštění probíhá mnohem rychleji než při překladu interpretem. Postup zpracování a jeho jednotlivé části popisuje následující obrázek.
43
EDITOR
*.c
*.h
PREPROCESOR
*.lib
COMPILER
*.lis
*.obj
LINKER
DEBUGGER
*.exe
10.1 Editor Editor slouží pro psaní našeho zdrojového kódu, který vždy uložíme s příponou *.c. Protože jde vždy o text, můžeme pro psaní kódu použít i běžný Poznámkový blok nebo WordPad. Výsledný soubor uložíme s příponou c a přeložíme překladačem do spustitelného souboru. Pokud použijeme pro psaní kódu v jazyce C typické editory např. Dev C++ nebo Turbo C++, soubor se nám s příponou *.c uloží automaticky a kód bude zpracován překladačem integrovaným v tomto vývojovém prostředí.
10.2 Preprocesor Preprocesor je součástí compileru, předzpracovává zdrojový kód před použitím compileru. Nekontroluje syntaktickou správnost. Upravuje jen text našeho zdrojového kódu a proto je jeho výstupem opět textový soubor.
44 Preprocesor vykonává čtyři činnosti: •
Vkládá hlavičkové soubory
•
Rozvíjí makra
•
Provádí podmíněný překlad
•
Odstraňuje komentáře
Podrobněji se preprocesoru budeme věnovat v dalších hodinách.
10.3 Compiler Compiler (překladač) provádí syntaktickou kontrolu zdrojového kódu programu a převádí jej do strojového kódu - kódu instrukcí pro daný procesor. Tento přeložený kód je zapsán do souboru *.obj. Adresy proměnných a funkcí nejsou známy a jsou v souboru *.obj zapsány relativně, proto se takto zapsanému kódu říká relativní kód, který se oficiálně nazývá jazyk relativních adres. Souborům, které vytváří překladač, se říká objektové soubory, jsou ukládány s příponou *.obj nebo *.o. Tento soubor obsahuje program zapsaný binárně, který však ještě není spustitelný. Jestliže je program rozdělen do více částí, vzniká více souborů *.obj, které jsou spojeny linkerem do jednoho *.exe souboru V souboru *.lis je protokol o překladu a o chybách, které nalezl compiler.
10.4 Linker Linker je sestavovací program, který spojí jeden nebo více objektových souborů s knihovnami *.lib do jediného spustitelného *.exe souboru. Linker v kódu nahradí relativní adresy adresami absolutními. Výsledkem práce linkeru je spustitelný *.exe soubor.
10.5 Debugger Debugger je ladící program, který běží zároveň se spuštěným programem a hledá chyby, které nastanou při běhu programu. Debugger je také určený pro krokování programu a hledání chyb. Umožňuje sledovat běh programu řádek po řádku a sledovat při tom hodnoty proměnných, registrů nebo dokonce vybraných míst v paměti.
45
10.6 Chyby a chybové hlášení Při zpracování programu nebo až při spuštění programu může dojít k některým chybám. V následující části si je od sebe rozlišíme. Compiler nebo linker mohou při svém zpracování programu odhalit tzv. syntaktické chyby. Syntaktická chyba je prohřešek proti gramatice programovacího jazyka, je to vše, co způsobí, že kód programu je neplatný, neproveditelný, nepřeložitelný. Počítač vyžaduje naprosto jednoznačný předpis své činnosti. Zdrojový kód nesmí obsahovat žádné syntaktické chyby, aby bylo jednoznačné, co má program vykonávat. Překladač neví, co od programu chcete, co chcete naprogramovat, proto se nemůže snažit o opravu vašich chyb, to musíte udělat sami. Překladač nám jednoznačně lokalizuje chybu v kódu i s případným komentářem. Mezi syntaktické chyby patří zejména překlepy, zapomenutý středník, ale také použití nekompatibilních datových typů nebo třeba chybné použití operátorů. Sémantická chyba je chyba v logice programu. Program může být syntakticky správný, překladač jej přeloží, linker spojí, ale běžící program přesto může fungovat chybně. Za tyto chyby je vždy zodpovědný programátor a je na něm, aby je odhalil, lokalizoval a zbavil se jich. Tyto chyby překladač ani linker neodhalí. Při nalezení chyby v kódu nám překladač nebo linker podá tzv. chybové hlášení. Chybové hlášení je zpráva, kterou vám překladač nebo linker sdělují, proč z našeho kódu nelze vytvořit spustitelný program. Tato zpráva obvykle obsahuje jméno souboru, číslo řádku, kde se chyba nachází a vysvětlení, co je podle překladače špatně. Překladač však může označit chybné místo v kódu na jiném řádku než je skutečná příčina. Pokud chybu na daném řádku nenajdete, zkuste hledat chybu i několik řádků výš či níž. Proto je dobré psát na každý řádek zdrojového kódu maximálně jeden příkaz. Usnadníte si tím nejen lokalizaci chyb, ale i ladění. Kromě chybových hlášení nám může překladač nebo linker podat tzv. varovné hlášení. Varovné hlášení je upozornění, že váš program sice lze přeložit, ale že obsahuje podezřelé konstrukce, které mohou obsahovat závažnější problém. Každý programátor by měl varovným hlášením překladače věnovat náležitou pozornost. Porozumět chybovým hlášením vyžaduje znalost angličtiny a také znalost logiky programovacího jazyka a fungování počítače. Čím více budete programovat, tím to pro vás bude snazší.
46
Shrnutí kapitoly Zdrojový kód programu uložený s příponou *.c zpracovává nejprve Preprocesor, který zdrojový kód jen upraví. Compiler provede syntaktickou kontrolu kódu, převede jej od relativního kódu a uloží do objektového souboru *.obj. Spustitelný soubor *.exe vytvoří sestavovací program – Linker, který přiřadí proměnným a funkcím absolutní adresy. Ladící program Debugger hledá chyby, které nastanou za běhu programu. Syntaktické chyby vznikají při zápisu programu a způsobí neplatnost a nepřeložitelnost zdrojového kódu. Sémantické chyby jsou chyby logické, které způsobí, že spuštěný program nefunguje správně.
Kontrolní otázky a úkoly 1) Popište postup zpracování programu. 2) Co se zdrojovým kódem provádějí jednotlivé části zpracování programu? 3) Jaký je rozdíl mezi syntaktickou a sémantickou chybou?
47
11 Preprocesor, makra bez parametru Obsah hodiny Seznámíme se s prací a příkazy preprocesoru. Použijeme tvorby maker bez parametru.
Cíl hodiny Po této hodině budete schopni: ● ●
rozlišit příkazy preprocesoru od příkazů jazyka C vytvořit a využít makra bez parametru
Klíčová slova Preprocesor, direktivy, makra bez parametru, standardní makra
11.1 Preprocesor Jak již bylo řečeno v minulé kapitole, preprocesor je součástí compileru a předzpracovává kód našeho programu ještě před překladem, tzn. před práci compileru. Nekontroluje syntaktickou správnost kódu, jen upravuje text našeho kódu. Pomocí svých instrukcí (příkazů) provádí preprocesor jednu z následujících činností: vkládá hlavičkové soubory, rozvíjí makra a provádí podmíněný překlad. Dále také odstraňuje všechny komentáře z našeho kódu. Instrukce preprocesoru se nazývají direktivy. Direktivy začínají na řádku znakem # a končí na konci řádku. Pro jejich ukončení tedy nepoužíváme středník. V některých prostředích pro zápis kódu jsou direktivy odlišeny od ostatních příkazů barevně. Instrukce preprocesoru, které budeme na našich cvičeních používat: define, include, if, else, endif, elif, undef, ifdef, ifndef
48
11.2 Makra bez parametru Makra bez parametru nazýváme také symbolické konstanty. Definování makra bez parametru: #define název hodnota Direktivou #define říkáme preprocesoru, že chceme definovat makro. Za tuto direktivu zapisujeme název makra. Název makra se u maker bez parametru píše velkými písmeny. Nejde o chybu, pokud název napíšete malými písmeny. Jedná se o kulturu zápisu kódu jazyka C. Za název makra píšeme hodnotu makra – konstantu, která je po celý program neměnná a kterou můžeme využít pomocí názvu makra. Pro ilustraci si ukážeme příklad definice konstanty Ludolfova čísla. #define PI 3.14 Znamená to, že preprocesor projde celý následující kód a nahradí všechny výskyty názvu konstanty její hodnotou. To znamená, že kdekoliv napíšeme název PI, nahradí jej preprocesor hodnotou 3.14. Říkáme, že preprocesor nahradí řetězec (název) za řetězec (hodnota). Preprocesor však nekontroluje, zda touto záměnou řetězců nevytvořil syntaktickou či sémantickou chybu.
Příklad #define PI 3.14
Kód zpracovaný preprocesorem
int main()
int main()
{ float x;
}
{ float x;
x=PI*2;
x=3.14*2;
printf (“Dve PI je %f”, x);
printf (“Dve PI je %f”, x);
printf (“Polovina PI je %f”, PI/2);
printf (“Polovina PI je %f”, 3.14/2);
return 0;
return 0; }
Všimněte si, že preprocesor nenahradil název PI v řetězci u příkazu printf. Preprocesor nenahrazuje řetězce uvnitř řetězce.
49
Příklad #define MAX 10 #define DVEMAX 2*MAX #define CELE unsigned short int #define JMENO “Jakub” #define ERROR printf(“Chyba”);
Kód zpracovaný preprocesorem
main()
main() { unsigned short int i;
{ CELE i; i= MAX;
i= 10;
if (i> 0 && i< DVEMAX)
if (i>0 && i< 2*10) printf (“Jakub”);
printf (JMENO);
else
else
printf(“Chyba”);
ERROR
return 0; }
return 0; }
Makro také můžeme oddefinovat pomocí direktivy #undef název. Podle normy ANSI C existují standardní makra, která musí každý preprocesor jazyka C znát. Standardní makra preprocesoru začínají a končí dvěma podtržítky.
Makro
Význam
Datový typ
__DATE__
datum spuštění preprocesoru
string
__TIME__
čas spuštění preprocesoru
string
__FILE__
jméno aktuálního vstupního souboru
string
__LINE__
pořadové číslo aktuálního řádku
int
50
Shrnutí kapitoly Preprocesor zpracovává kód programu ještě před překladem. Jeho příkazy se nazývají direktivy. Označují se znakem # a končí na konci řádku. Makra bez parametru jsou symbolické konstanty, jejichž hodnotu můžeme použít v kódu pomocí názvu makra. Preprocesor projde následující část kódu a nahradí název makra jeho hodnotou. Název makra bez parametru píšeme velkými písmeny.
Kontrolní otázky a úkoly 1) Kdy a co provádí preprocesor v průběhu zpracování našeho programu? 2) Jak poznáme příkaz preprocesoru? 3) Jak zpracovává preprocesor makra bez parametru?
Otázky k zamyšlení 1) Kdy by bylo vhodné použít makro bez parametru?
51
12 Makra s parametrem Obsah hodiny Seznámíme se vytvářením a využitím maker s parametrem. Rozlišíme výhody a nevýhody užití funkcí a maker.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vytvořit vhodné makro s parametrem popsat zpracování makra preprocesorem vysvětlit rozdíl ve zpracování funkce a makra s parametrem
Klíčová slova Makra s parametrem
12.1 Makra s parametrem Makra s parametrem použijeme v programu, pokud budeme opakovaně provádět určitou činnost – část kódu, ale pokaždé s jinými hodnotami. Makra s parametrem se tedy podobají funkcím, ale výrazně se liší ve způsobu zpracování. Název makra s parametrem píšeme malými písmeny. Definování makra s parametrem: #define název(argumenty) hodnota Volání makra: název(parametry) Preprocesor projde celý následující kód a nahradí všechny názvy makra (tzn. jeho volání) hodnotou makra a v ní nahradí argumenty za parametry.
52
Příklad
#define na_treti(x) ((x)*(x)*(x)) main() { int a=3;
Kód zpracovaný preprocesorem main() { int a=3; float b=2.1;
float b=2.1;
printf(“%d”, (2)*(2)*(2));
printf(“%d”, na_treti(2));
a= (a)*(a)*(a);
a= na_treti(a);
printf(“%f”,(a+b)*(a+b)*(a+b));
printf(“%f”, na_treti(a+b));
return 0;
return 0; }
}
Všimněte si, že je důležité zapsat argumenty v definici makra do závorek. Kdybychom je nenapsali, poslední volání makra na_treti(a+b) by bylo preprocesorem nahrazeno výrazem: a+b*a+b*a+b, který by byl vyhodnocen jinak než správný očekávaný výraz: (a+b)*(a+b)*(a+b). Závorky u argumentů nejsou nutné, ale vhodné, aby byla dodržena priorita operátorů. Dále si všimněte, že preprocesor neřeší datové typy argumentů. Nepovažuje za chybu, když je v prvních dvou voláních makra argument celé číslo a v posledním číslo reálné. Jeho úkolem je nahradit řetězec za řetězec bez kontroly chyb. Pokud nastane chyba, chybové hlášení compileru bude označovat řádek volání makra, ne v definici makra, protože za jeho práce už v kódu makro zapsáno není. Proto bývá někdy složité nalézt chybu v definici makra. Potřebujeme-li zapsat makro na více řádků, napíšeme na konec řádku znak \. Preprocesor tak bude vědět, že makro nekončí na tomto řádku, ale pokračuje na dalším.
12.2 Rozdíl mezi makry a funkcemi Jak jsme si již řekli, makra s parametrem jsou velmi podobná funkcím. Zásadně se však liší ve způsobu zpracování a díky tomu i při jejich využití. Rozdíly si uvedeme na následujícím příkladu, kde je vytvořeno makro i funkce pro výpočet diskriminantu kvadratické rovnice pro tři celočíselné koeficienty.
53
Příklad #define diskriminant(a,b,c) ((b)*(b)- 4*(a)*(c)) int diskr(int a,int b, int c) { return(b*b- 4*a*c); } main() { int x=3,y=2,z=-5; printf(“%d”, diskriminant(x,y,z)); printf(“%f”, diskriminant(x/2.0, y/2.0, z/2.0)); printf(“%d”, diskr(x,y,z)); }
Ještě před kompilací preprocesor nahradí volání makra diskriminant za jeho hodnotu a nahradí argumenty a, b, c za volané parametry tzn. že první řádky s výpisem budou vypadat takto: printf(“%d”, ((y)*(y)- 4*(x)*(z))); printf(“%f”, ((y/2.0)*( y/2.0)- 4*( x/2.0)*( z/2.0))); Za běhu programu se tedy nebude řešit volání makra či alokace parametrů. Vypočte se a následně se i vypíše hodnota podle patřičného výrazu. Při volání funkce diskr(x,y,z) se musí vyalokovat návratová hodnota funkce a formální parametry funkce – a, b, c. Formální parametry se naplní hodnotami skutečných parametrů. Hodnota diskriminantu se vypočte a pomocí return a návratové hodnoty se vrátí a vypíše na obrazovku. Formální parametry se samozřejmě musí odalokovat. Z výše uvedeného vyplývají následující rozdíly mezi makry s parametrem a funkcemi: •
funkce potřebuje čas a paměť na alokaci parametrů
•
makro zaměňuje řetězec za řetězec ještě před překladem – nepotřebuje alokaci argumentů
•
makra neumožňují typovou kontrolu ani použití rekurze
54
Shrnutí kapitoly Makro s parametrem použijeme podobně jako funkce při opakování činnosti s jinými parametry. Makro je však zpracováno preprocesorem, proto nedochází k alokaci parametrů a není náročné na paměť. Makra neumožňují kontrolu datových typů parametrů a neumožňují rekurzi.
Kontrolní otázky a úkoly 1) Popište zpracování maker s parametrem preprocesorem. Uveďte na příkladu. 2) Jak a proč se liší makra s parametrem od funkcí?
55
13 Makra - procvičování Obsah hodiny Procvičíme tvorbu maker bez parametru i s maker s parametrem.
Cíl hodiny Po této hodině budete schopni: vytvořit makro s parametrem i bez parametru posoudit vhodnost použití maker resp. funkcí
● ●
Příklad Napište makro, které vypočte objem válce (V=πr2v) pro zadané parametry – výška a poloměr. Pro výpočet si definujte makro PI jako 3.1415926535 nebo 22/7.
Řešení #define PI 3.1415926535 #define objem(vyska, polomer) PI*polomer*polomer*vyska main() { floatt v,p,o; printf(“Zadej výšku”); scanf(“%f”,&v); printf(“Zadej poloměr”); scanf(“%f”,&p); o=objem(v,p); printf(“Objem je %f”,o); printf(“Menší válec má objem %f”, objem(v/2,p/2)); return 0; }
56 Buďte opatrní při psaní středníku na konec maker, protože preprocesor nahradí hodnotu makra i se středníkem a může tak dojít k chybě v místě, kde tento středník nemá být.
Příklad Napište makro matice(r,s,z), které vypíše na obrazovku matici o r řádcích a s sloupcích znaku z. Napište funkci Matice(r,s,z), které vypíše na obrazovku matici o r řádcích a s sloupcích znaku z.
Řešení #define matice(r,s,z) { int i,j; \ for (i=0; i
57
Shrnutí kapitoly Vždy si dobře rozmyslete, zda je vhodné použít funkci nebo makro s parametrem. Buďte obezřetní v zápisu makra, protože případná chyba při překladu je označena v místě volání makra.
Kontrolní otázky a úkoly 1) Napište makro, které pro tři parametry vypočte jejich aritmetický průměr. Napište funkci, která pro tři celočíselné parametry vrátí jejich aritmetický průměr. 2) Napište makro, které vypíše na obrazovku zadaný počet (parametr) náhodných celých čísel z intervalu <50; 100> 3) Napište makro, které pro tři parametry d, h, b vypíše na obrazovku součet čísel od d do h bez čísel dělitelných číslem b. Předpokládáme pravdivost výroku d
58
14 Podmíněný překlad řízený hodnotou makra Obsah hodiny Seznámíme se s podmíněným překladem jako nástrojem programátora při ladění programu.
Cíl hodiny Po této hodině budete schopni: ● ●
vysvětlit použití a zpracování podmíněného překladu aplikovat podmíněný překlad řízený hodnotou makra
Klíčová slova Podmíněný překlad, podmíněný překlad řízený hodnotou makra
Podmíněný překlad znamená, že při splnění patřičných podmínek budou nebo nebudou některé části programu přeloženy. Jinými slovy jde tedy o překlad za určité podmínky. Testovaný kód uzavřeme mezi direktivy preprocesoru. Podmíněný překlad využíváme, pokud potřebujeme mít v jednom zdrojovém programu více variant chování, pokud program ladíme nebo testujeme. Jde tedy o nástroj programátora, který uživatel nemůže ovlivnit. Při použití podmíněného překladu využíváme několika direktiv preprocesoru a rozlišujeme jej podle podmínky, kterou je podmíněný překlad řízen. Podmíněný překlad řízený hodnotou konstantního výrazu určuje, která část kódu bude nebo nebude přeložena podle hodnoty makra nebo výrazu. Zapisuje se pomocí direktiv #if, #else, #elif, #endif.
59 Obecně: #if konstantní výraz část_1 #else část_2 #endif Je-li hodnota konstantního výrazu rovna 0, přeloží se jen část_2. Je-li hodnota konstantního výrazu různá od 0, přeloží se část_1. Každá část mezi direktivami může obsahovat libovolný počet řádků. Každý podmíněný překlad musí být ukončen direktivou #endif. V konstantním výrazu nemůžeme použít proměnné, protože v době práce preprocesoru ještě nejsou ani alokovány.
Příklad #define MAKRO 0 int main()
Protože je hodnota makra MAKRO nula, je podmínka podmíněného překladu vyhodnocena jako false a kód zpracovaný preprocesorem vypadá takto:
{ #if MAKRO printf(“Nevypisu se!”);
int main()
#endif
{ return 0;
return 0; }
}
Příklad #define MAKRO 0 int main() { #if MAKRO==2 printf(“Makro je dve!”);
Protože je hodnota makra MAKRO nula, je podmínka podmíněného překladu vyhodnocena jako false a kód zpracovaný preprocesorem vypadá takto:
#else printf(“Makro neni dve!”);
int main()
#endif
{ printf(“Makro neni dve!”);
return 0; }
return 0; }
60 Pokud potřebujeme větvit podmíněný překlad vícenásobně, můžeme využít direktivy #elif, která je spojením #else a #if.
Příklad #define MAKRO 0 int main() {
Kód zpracovaný preprocesorem vypadá takto:
int main() #if MAKRO==0
{
printf(“Nula”);
printf(“Nula”);
#elif MAKRO==1 printf(“Jedna”);
return 0; }
#elif MAKRO==2 printf(“Dva”); #endif return 0;
Pokud potřebujeme testovat jiné části kódu, změníme hodnotu makra a přeloží se a provede jiný výpis.
}
Shrnutí kapitoly Podmíněný překlad používáme k testování programu, kdy můžeme překládat jen části programu, které budou zpracovány na základě splnění podmínky. Při podmíněném překladu řízeném hodnotou konstantního výrazu je podmínka nejčastěji určována hodnotou makra.
Kontrolní otázky a úkoly 1) Co určuje podmíněný překlad a k čemu jej používáme? 2) Jde o nástroj uživatele nebo programátora? 3) Které direktivy preprocesoru používáme k podmíněnému překladu řízenému hodnotou konstantního výrazu? 4) Na příkladech popište užití podmíněného překlad řízeného hodnotou konstantního výrazu.
61
15 Podmíněný překlad řízený existencí makra Obsah hodiny Seznámíme se s řízením podmíněného překladu pomocí existence či neexistence makra.
Cíl hodiny Po této hodině budete schopni: ● ●
popsat zápis a zpracování podmíněného překladu řízeného existencí makra aplikovat podmíněný překlad řízený existencí makra
Klíčová slova Podmíněný překlad řízený existencí makra
Podmíněný překlad může být také závislý na tom, zda je makro definováno nebo ne. Nezáleží přitom na jeho hodnotě. Podmíněný překlad řízený existencí makra určuje, která část kódu bude nebo nebude přeložena podle toho, zda je makro nadefinováno nebo ne. Zapisuje se pomocí direktiv #ifdef, #ifndef, #else, #endif. Obecně: #ifdef název_makra část_1 #else část_2 #endif Je-li makro definováno před podmíněným překladem, přeloží se jen část_1, jinak se přeloží část_2. I u tohoto podmíněného překladu může každá část mezi direktivami obsahovat libovolný počet řádků a vždy musí být podmíněný překlad ukončen direktivou #endif.
62 Namísto #ifdef lze také použít negaci #ifndef, která vyhodnotí podmínku jako true, pokud makro není nadefinováno před tímto podmíněným překladem. Pokud chceme makro oddefinovat, použijeme direktivu #undef, jako v následujícím příkladu.
Příklad #define MAKRO int main() { #ifdef MAKRO printf(" Makro je definovane "); #else printf(" Makro neni definovane ");
Kód zpracovaný preprocesorem
#endif #undef MAKRO #ifndef MAKRO printf(" Makro je ");
int main() { printf(" Makro je definovane ");
#else
printf(" Makro neni ");
printf(" Makro neni "); #endif return 0; }
return 0; }
63
Příklad Do podmíněného překladu můžeme dát i celé funkce main. #define POKUS #ifdef POKUS int main() { printf(" Vypocet faktorialu "); return 0; } #else int main() { printf(" Vypocet mocniny "); return 0; }
Shrnutí kapitoly U podmíněného překladu řízeného existencí makra se vyhodnocuje podmínka podle toho, zda je makro před podmíněným překladem definováno nebo ne.
Kontrolní otázky a úkoly 1) Jak je zpracováván podmíněný překlad řízený existencí makra? 2) Které direktivy preprocesoru používáme k podmíněnému překladu řízenému existencí makra? 3) Na příkladech popište užití podmíněného překlad řízeného existencí makra.
64
16 Oddělený překlad a vkládání souborů Obsah hodiny Seznámíme se s principem spojování více souboru do jednoho celku pomocí vkládání souborů i pomocí odděleného překladu.
Cíl hodiny Po této hodině budete schopni: ● ●
popsat princip vkládání souborů popsat princip odděleného překladu
Klíčová slova Vkládání souborů, oddělený překlad
16.1 Vkládání souborů Pomocí vkládání souborů můžeme do našeho zdrojového kódu vložit kód z jiného souboru nebo vložit hlavičkový soubor. Vkládání souborů provádíme pomocí direktivy preprocesoru #include, která vloží obsah zadaného souboru na místo, kde je zapsána. Používáme tyto dva zápisy: #include -
soubor se vyhledává v systémovém adresáři (nejčastěji se jmenuje include) Není-li soubor nalezen, je hlášena chyba. Tímto zápisem nečastěji vkládáme standardní hlavičkové soubory.
#include "název_souboru" -
soubor se vyhledává v pracovním adresáři. Není-li tam soubor nalezen, pak pokračuje jako u výše zmíněného zápisu do systémové složky. Tímto zápisem vkládáme do našeho kódu uživatelské hlavičkové soubory.
65 Do zdrojového kódu nemusíme vkládat jen hlavičkové soubory, ale také další zdrojové soubory. Postup zpracování je zakreslen na následujícím obrázku.
Preprocesor vloží obsah souborů soubor1.c, soubor2.c a soubor3.c do souboru soubor.c, který je dále zkompilován compilerem do jednoho souboru soubor.obj. Ten dále postupuje do linkeru atd. Nevýhodou tohoto způsobu spojování více souborů do jednoho je, že při změně jednoho z vkládaných souborů se musí zkompilovat znovu všechny.
16.2 Oddělený překlad Na rozdíl od vkládání souborů při odděleném překladu je každý vkládaný soubor zkompilován samostatně a až linker spojuje tyto přeložené soubory do jednoho celku a vytváří z něj spustitelný soubor. Výhodou je, že při změně jakéhokoliv souboru compiler přeloží jen upravený soubor. Oddělený překlad umožňuje rozdělit si větší program do více souborů (modulů), vytvářet vlastní knihovny a pracovat na programu v týmu programátorů. Většina kompilátorů podporuje oddělený překlad pomocí tzv. projektů, se kterými se seznámíme v jedné z dalších hodin.
66 Postup zpracování odděleného překladu je popsán na následujícím obrázku.
Shrnutí kapitoly Vkládání souborů provádíme pomocí direktivy #include. Preprocesor vloží obsah požadovaného souboru na místo této direktivy. Nevýhodou vkládání souboru je, že při změně jednoho vkládaného souboru, musí být zkompilovány všechny vložené soubory. Oddělený překlad je vhodný pro práci v týmu, pro rozdělení programu na menší moduly. Tyto moduly se kompilují samostatně a jsou spojovány až linkerem do jednoho spustitelného souboru. Při změně vkládaného souboru se kompiluje jen změněný soubor.
Kontrolní otázky a úkoly 1) Popište postup zpracování programu s využitím vkládání souborů a s využitím odděleného překladu. 2) Jaké jsou výhody a nevýhody těchto dvou postupů? 3) Jaké dva postupy vkládání souborů znáš?
67
17 Hlavičkové soubory Obsah hodiny Seznámíme se se stavbou a obsahem standardních i uživatelských hlavičkových souborů.
Cíl hodiny Po této hodině budete schopni: ● ●
popsat stavbu hlavičkových souborů vytvořit vlastní uživatelský hlavičkový soubor
Klíčová slova Hlavičkový soubor, standardní hlavičkový soubor, uživatelský hlavičkový soubor
S hlavičkovými soubory se setkáváme již od první hodiny programování v jazyce C. Vkládáme je do našeho kódu pomocí direktivy preprocesoru #include. V předchozí kapitole jsme si řekli, že můžeme do našeho zdrojového souboru vkládat hlavičkové soubory ze standardního adresáře nebo uživatelské hlavičkové soubory. Doposud jsme vkládali do našeho zdrojového kódu standardní hlavičkové soubory. Díky standardním hlavičkovým souborům můžeme používat předdefinované funkce a příkazy. Např. po vložení hlavičkového souboru stdio.h můžeme mj. využít příkazu printf a scanf. Standardní hlavičkové soubory najdeme v místě instalace našeho překladače nebo celého vývojového prostředí ve složce include. Úkol Najděte na Vašem počítači složku include a prohlédněte si, kolik hlavičkových souborů můžete využít. Najděte ve složce include soubor stdio.h a otevřete jej. Jde o textový soubor, proto by s jeho zobrazením neměl být problém. Nic však v tomto souboru neměňte a nepřepisujte! Mohli byste vytvořit chyby, které se velice těžko dohledávají.
68 Prohlédněte si jeho obsah. Všimněte si, že jsou zde deklarovány makra, funkce, datové typy a globální proměnné. Na začátku každého hlavičkového souboru je použit podmíněný překlad, který zabraňuje několikanásobnému vložení hlavičkového souboru do projektu.
Jestliže rozdělujeme vlastní program na několik částí - modulů, měl by ke každému souboru *.c, který obsahuje funkce, makra či globální proměnné, odpovídat jeden hlavičkový soubor. Vytvoříme tak uživatelský hlavičkový soubor, který se nazývá stejně jako zdrojový a liší se jen příponou *.h. V tomto hlavičkovém souboru jsou hlavičky (deklarace) všech funkcí, které chceme použít v dalších zdrojových souborech *.c, dále extern deklarace globálních proměnných (extern je paměťová třída, se kterou se seznámíme v dalších kapitolách) a makra preprocesoru, která nějak souvisí s obsahem příslušného *.c souboru. Hlavičkový soubor obsahuje i definice uživatelských typů, ale to bude také obsahem až dalších kapitol. V hlavičkovém souboru by se nikdy neměl vyskytovat kód, ani definice proměnných, či konstantních proměnných. Každá konstrukce v hlavičkovém souboru by měla být dobře okomentována. Tento soubor se pak pomocí příkazu #include "název_souboru" vkládá na začátek všech *.c nebo i jiných *.h souborů, které jej potřebují a chtějí využít vše, co je v nich nadeklarováno. Samozřejmě by náš hlavičkový soubor měl obsahovat podmíněný překlad. Příklad stavby hlavičkového souboru:
#ifndef _MAKRO_H #define _MAKRO _H #define MAX 10 int soucet(int a,int b); #endif Pokud tento hlavičkový soubor bude pomocí #include vložen do více zdrojových souborů v projektu, preprocesor vloží jeho obsah do zdrojového souboru jen jednou.
69 Pomocí podmíněného překladu, tedy direktivy #ifndef se ptáme, zda je nadefinováno makro _MAKRO_H. Protože není nadefinováno, nadefinujeme jej v dalším řádku pomocí #define _MAKRO _H. Dále hlavičkový soubor obsahuje vše, co bychom chtěli využít v dalších zdrojových souborech – v tomto případě je to makro MAX a funkce soucet. Posledním řádkem je ukončení podmíněného překladu #endif. Při druhém vložení hlavičkového souboru už úvodní podmínka #ifndef _MAKRO_H není splněna, protože makro _MAKRO_H bylo již nadefinováno při prvním vložení hlavičkového souboru. Proto se další řádky neprovedou a ukončí se podmíněný překlad. Díky podmíněnému překladu se vloží hlavičkový soubor do projektu jen jednou.
Shrnutí kapitoly Hlavičkové soubory mají příponu *.h, obsahují hlavičky funkcí, definice maker, deklarace globálních proměnných, definice uživatelských datových typů a podmíněný překlad, který zabrání několikanásobnému vložení hlavičkových souborů do projektu. Vložení standardního hlavičkového souboru nám umožní použít funkce (příkazy), makra a datové typy, které jsou v hlavičkovém souboru zapsány. Uživatelské hlavičkové soubory tvoříme pro každý zdrojový soubor *.c, jehož funkce chceme využít v jiných zdrojových souborech.
Kontrolní otázky a úkoly 1) Kde najdeme standardní hlavičkové soubory? 2) Jak vkládáme hlavičkové soubory do našeho zdrojového kódu? 3) Co zapisujeme do hlavičkových souborů? Popište stavbu hlavičkových souborů. 4) Proč používáme podmíněný překlad v hlavičkových souborech?
70
18 Projekty Obsah hodiny Seznámíme se s rozdělováním programů do více modulů a s tvorbou projektů.
Cíl hodiny Po této hodině budete schopni: ● ●
rozčlenit program do více modulů vytvořit projekt se všemi jeho potřebnými částmi
Klíčová slova Projekt, modul, hlavičkový soubor
Doposud jsme zapisovali program do jednoho souboru. Tento postup je však nevhodný, pokud budeme například vytvářet program dlouhý třicet tisíc řádků a třeba i víc. Orientace v takovémto kódu je velice nesnadná a je pravděpodobné, že tak dlouhý program nebude vytvářet jen jeden programátor. V jazyce C si můžeme rozčlenit program do několika modulů i pro tým lidí a pracovat takzvaným modulárním způsobem. Spojovat soubory můžeme vkládáním souborů nebo odděleným překladem tzv. projekty. S nevýhodami vkládání souborů jsme se seznámili v předchozích hodinách, proto se teď budeme soustředit na oddělený překlad, tedy vytváření projektů. Zdrojový kód rozdělíme do několika logických částí tzv. modulů. Moduly umožňují organizovat datové struktury a podprogramy do relativně samostatných a nezávislých celků, čímž zvyšují přehlednost rozsáhlejších programů a umožňují dělit programování v týmu lidí. Do modulu zapisujeme funkce a datové struktury, které spolu souvisí. Navíc lze určit, co bude viditelné pro uživatele modulu a co zůstane mimo modul skryto. Dobře navržené moduly můžeme opakovaně použít i v jiných projektech. Moduly lze samostatně ladit. Modul je tvořen alespoň dvěma soubory – hlavičkovým a zdrojovým. Hlavičkový soubor slouží jako rozhraní modulu a musí být přístupný
71 každému uživateli tohoto modulu (tedy programátorovi). Toto rozhraní slouží překladači k provedení typové kontroly při používání funkcí. Proto je dobré vše v hlavičkovém souboru řádně okomentovat. Druhým souborem je zdrojový soubor s příponou *.c. Tento soubor obsahuje deklarace všech skrytých datových typů a konstant, definice a inicializace veřejných globálních proměnných a implementace všech, skrytých i veřejných funkcí modulu. Výhodou je, že v projektech můžeme použít zkompilovaný zdrojový soubor s příponou *.o, který je binární. Hlavičkový soubor pak slouží pro informace o názvech proměnných a funkcí a počtech parametrů funkcí.
Příklad Pro názornost si uvedeme jednoduchý příklad. Kód programu si rozdělíme do jednotlivých částí, jak je vyznačeno. #include <stdio.h> #include #define MAX 123.45 #define PONDELI printf("Dnes je pondeli"); int soucin(int a, int b); float plusMAX(int a); int main() {
int x=5,y=2; PONDELI printf("Soucin %d * %d je %d \n", x,y,soucin(x,y)); printf("%d plus %.3f je %.3f \n", x,MAX,plusMAX(x)); return 0;
}
int soucin(int a, int b) { PONDELI return(a*b); } float plusMAX(int a) { PONDELI return(a+MAX); }
72 Jednotlivé vyznačené části zdrojového kódu si uložíme do souborů podle následujícího schéma. main.c #include <stdio.h> #include int main() {
int x=5,y=2; PONDELI printf("Soucin %d * %d je %d \n", x,y,soucin(x,y)); printf("%d plus %.3f je %.3f \n", x,MAX,plusMAX(x)); return 0;
}
funkce.c
funkce.h
int soucin(int a, int b)
int soucin(int a, int b);
{ PONDELI
float plusMAX(int a);
return(a*b); } float plusMAX(int a) { PONDELI return(a+MAX); }
makra.h #define MAX 123.45 #define PONDELI printf("Dnes je pondeli");
Abychom mohli makra a funkce ve zdrojových souborech použít, musíme do nich vložit hlavičkové soubory pomocí direktivy #include. main.c #include <stdio.h> #include #include “makra.h” #include “funkce.h” int main() {
……..atd.
73
funkce.c #include “makra.h” int soucin(int a, int b) { PONDELI return(a*b); } float plusMAX(int a) { PONDELI return(a+MAX); }
A poslední úpravou bude vložení podmíněného překlad do hlavičkových souborů. funkce.h #ifndef _FUNKCE_H #define _FUNKCE_H int soucin(int a, int b); float plusMAX(int a); #endif
makra.h #ifndef _MAKRA_H #define _ MAKRA _H #define MAX 123.45 #define PONDELI printf("Dnes je pondeli"); #endif
Vytváření projektů podporuje většina kompilátorů. Do projektu vkládáme jen zdrojové soubory *.c, protože hlavičkové soubory vkládá preprocesor pomocí #include. Projekt umožňuje nezávislý překlad jednotlivých částí, které pak linker spojí do jednoho *.exe souboru.
74 Pro usnadnění správy projektů se používá program make. Program je řízen textovým souborem definujícím vzájemné závislosti souborů projektu, konfiguraci překladače, informace o adresářích. Make čte řídící informace a podle stavu, v němž se právě nachází, vyvolává pro vykonání potřebných akcí odpovídající programy. Informace jim předává jako argumenty. Výhodou je značná pružnost a rovněž jistá nezávislost na použitém překladači. Teoreticky i na operačním systému.
Shrnutí kapitoly Projekty umožňují rozčlenění programu do více modulů i pro tým lidí a umožňují vytvoření a použití vlastních znovupoužitelných knihoven funkcí. Obsahují jen zdrojové soubory *.c, protože hlavičkové soubory vkládá preprocesor. Zdrojový kód členíme na několik modulů, do kterých zapisujeme datové struktury a podprogramy, které k sobě logicky patří. Modul se skládá ze zdrojového souboru (*.c nebo *.o) a k němu příslušného hlavičkového souboru.
Kontrolní otázky a úkoly 1) Proč tvoříme projekty? 2) Jak členíme rozsáhlý zdrojový kód? 3) Co rozumíme pojmem modul?
Otázky k zamyšlení 1) Navrhněte příklad programu, který byste dokázali rozčlenit do jednotlivých modulů. Jak by tyto moduly vypadaly a co by bylo jejich obsahem?
75
19 Projekty – řešené příklady Obsah hodiny Procvičíme rozdělení programu na jednotlivé moduly a procvičíme tvorbu projektu.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vhodně navrhnout rozdělení programu na moduly správně zapsat jednotlivé moduly vytvořit projekt
Klíčová slova Projekt, modul, hlavičkový soubor
Příklad Vytvořte projekt, který bude obsahovat modul s funkcemi na základní matematické operace (+,-,*,/) a modul main.c. Projekt doplňte o správně zapsané hlavičkové soubory.
Řešení Modul funkce.c int soucet(int x, int y) { return(x+y); } int rozdil(int x, int y) { return(x-y); } int soucin(int x, int y) { return(x*y); }
76
int podil(int x, int y) { return(x/y); }
Soubor hlavicky.h #ifndef _Hlavicky #define _Hlavicky int soucet(int x, int y); int rozdil(int x, int y); int soucin(int x, int y); int podil(int x, int y); #endif
Modul main.c #include <stdio.h> #include #include "hlavicky.h" int main() { int a=5,b=2; printf("%d + %d = %d \n",a,b,soucet(a,b)); printf("%d - %d = %d \n",a,b,rozdil(a,b)); printf("%d * %d = %d \n",a,b,soucin(a,b)); printf("%d / %d = %d \n",a,b,podil(a,b)); getch(); return 0; }
Nesmíme zapomenout vložit do modulu main.c hlavičkový soubor #include "hlavicky.h".
77
Kontrolní otázky a úkoly Vytvořte projekt, který bude obsahovat modul s funkcemi: •
funkce, která pro tři celočíselné parametry vrátí jejich aritmetický průměr.
•
funkce Matice(r,s,z), které vypíše na obrazovku matici o r řádcích a s sloupcích znaku z.
•
funkce, která pro tři celočíselné parametry d, h, b vrátí součet čísel od d do h bez čísel dělitelných číslem b. Předpokládáme pravdivost výroku d
soubor s makry: •
makro, které pro tři parametry vypočte jejich aritmetický průměr.
•
makro matice(r,s,z), které vypíše na obrazovku matici o r řádcích a s sloupcích znaku z.
•
makro, které pro tři parametry d, h, b vypíše na obrazovku součet čísel od d do h bez čísel dělitelných číslem b. Předpokládáme pravdivost výroku d
Otázky k zamyšlení 1) Zamyslete se nad vlastním programem, který byste chtěli rozdělit na několik modulů a realizovat tak vlastní projekt.
78
20 Projekty – neřešené příklady Obsah hodiny Procvičíme rozdělení programu na jednotlivé moduly a procvičíme tvorbu projektu.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vhodně navrhnout rozdělení programu na moduly správně zapsat jednotlivé moduly vytvořit projekt
Klíčová slova Projekt, modul, hlavičkový soubor
Příklad Sestavte projekt, který bude obsahovat modul s funkcí main() a modul s funkcemi (viz. níže). Projekt doplňte o správně zapsaný hlavičkový soubor. Ve funkci main() načtete dva vektory v rovině jejich celočíselnými souřadnicemi od uživatele. Pro tyto vektory vypište s pomocí níže popsaných popsaných funkcí velikost obou vektorů, zda jsou rovnoběžné, kolmé nebo ani rovnoběžné ani kolmé, zda jsou si rovny, jejich součet, rozdíl, skalární součin a vektorový součin. Všechny parametry budete načítat ve funkci main() a do funkcí je budete posílat. Pokud má funkce hodnotu vracet, budete ji vypisovat ve funkci main(). Funkce pro práci s vektory: • funkce, která bude vracet velikost jednoho vektoru • funkce, která bude vypisovat výsledek jejich rozdílu
79 • funkce, která bude vypisovat výsledek jejich součtu • funkce, která bude vracet číslo 2, jsou- li vektory rovnoběžné, číslo 1, jsou – vektory kolmé a číslo 0, nejsou-li ani kolmé ani rovnoběžné. • funkce, která bude vracet číslo 1, jsou- li si vektory rovny, jinak vrátí číslo 0 • funkce, která bude vypisovat výsledný vektor vektorového součinu • funkce, která bude vracet hodnotu skalárního součtu vektorů
Příklad Vytvořte nebo simulujte tým dvou programátorů. Každý sestavte projekt DVA ZLOMKY podle následujících instrukcí: Programátor A Sestavte projekt, který bude obsahovat modul s funkcí main(), přeložený modul (*.obj) od Vašeho spolužáka ze skupiny a modul s Vašimi funkcemi (viz. níže). Doplňte projekt o hlavičkové soubory ke každému modulu s funkcemi. Ve funkci main() načtěte celočíselné hodnoty pro dva zlomky – dva čitatele a dva jmenovatele. Pro tyto dva zlomky vypište s využitím Vašich i spolužákových funkcí jejich součet, rozdíl, součin, podíl, součin prvního zlomku se zadaným celým číslem a vypište výsledek vzájemného porovnání zlomků. Všechny parametry budete načítat ve funkci main() a do funkcí je budete posílat. Pokud má funkce hodnotu vracet, budete ji vypisovat ve funkci main(). Vaše funkce pro práci se zlomky: • funkce, která bude vypisovat s využitím spolužákovy funkce tisk výsledek součtu zlomků. • funkce, která bude vypisovat s využitím spolužákovy funkce tisk výsledek součinu zlomků. • funkce, která bude vracet výsledek porovnání zlomků – bude vracet číslo1, pokud první zlomek bude větší než druhý, číslo 0 pokud si budou rovny a číslo -1 pokud první zlomek bude menší než druhý. Přeložený soubor (*.obj) s Vašimi funkcemi i správně zapsaný hlavičkový soubor (s podmíněným překladem a komentářem Vašich funkcí) pošlete svému spolužákovi ve skupině, aby mohl vytvořit vlastní projekt.
80 Programátor B Sestavte projekt, který bude obsahovat modul s funkcí main(), přeložený modul (*.obj) od Vašeho spolužáka ze skupiny a modul s Vašimi funkcemi (viz. níže). Doplňte projekt o hlavičkové soubory ke každému modulu s funkcemi. Ve funkci main() načtěte celočíselné hodnoty pro dva zlomky – dva čitatele a dva jmenovatele. Pro tyto dva zlomky vypište s využitím Vašich i spolužákových funkcí jejich součet, rozdíl, součin, podíl, součin prvního zlomku se zadaným celým číslem a vypište výsledek vzájemného porovnání zlomků. Všechny parametry budete načítat ve funkci main() a do funkcí je budete posílat. Pokud má funkce hodnotu vracet, budete ji vypisovat ve funkci main(). Vaše funkce pro práci se zlomky: • funkce tisk bude vypisovat zlomek ve tvaru čitatel/jmenovatel • funkce, která bude vypisovat s využitím funkce tisk výsledek rozdíl zlomků. • funkce, která bude vypisovat s využitím funkce tisk výsledek podíl zlomků. • funkce, která bude vypisovat s využitím funkce tisk výsledek součin zlomku a zadaného celého čísla, které bude parametrem funkce Přeložený soubor (*.obj) s Vašimi funkcemi i správně zapsaný hlavičkový soubor (s podmíněným překladem a komentářem Vašich funkcí) pošlete svému spolužákovi ve skupině, aby mohl vytvořit vlastní projekt.
Příklad Vytvořte a simulujte tým dvou programátorů. Každý sestavte projekt VEKTORY podle následujících instrukcí: Programátor A Sestavte projekt, který bude obsahovat modul s funkcí main(), přeložený modul (*.obj) od Vašeho spolužáka ze skupiny a modul s Vašimi funkcemi (viz. níže). Doplňte projekt o hlavičkové soubory ke každému modulu s funkcemi. Ve funkci main() načtete dva vektory v rovině jejich celočíselnými souřadnicemi od uživatele. Pro tyto vektory vypište s využitím Vašich i spolužákových funkcí velikost obou vektorů, zda jsou rovnoběžné,
81 kolmé nebo ani rovnoběžné ani kolmé, zda jsou si rovny, jejich součet, rozdíl, skalární součin a vektorový součin a obecnou rovnici přímky, která je zadaná prvním vektorem a zadaným bodem. Všechny parametry budete načítat ve funkci main() a do funkcí je budete posílat. Pokud má funkce hodnotu vracet, budete ji vypisovat ve funkci main(). Vaše funkce pro práci s vektory: • funkce, která bude vracet velikost jednoho vektoru • funkce, která bude vracet číslo 2, jsou- li vektory rovnoběžné, číslo 1, jsou – vektory kolmé a číslo 0, nejsou-li ani kolmé ani rovnoběžné. • funkce, která bude vypisovat výsledek jejich součtu • funkce, která bude vypisovat výsledný vektor vektorového součinu Přeložený soubor (*.obj) s Vašimi funkcemi i správně zapsaný hlavičkový soubor (s podmíněným překladem a komentářem Vašich funkcí) pošlete svému spolužákovi ve skupině, aby mohl vytvořit vlastní projekt. Programátor B Sestavte projekt, který bude obsahovat modul s funkcí main(), přeložený modul (*.obj) od Vašeho spolužáka ze skupiny a modul s Vašimi funkcemi (viz. níže). Doplňte projekt o hlavičkové soubory ke každému modulu s funkcemi. Ve funkci main() načtete dva vektory v rovině jejich celočíselnými souřadnicemi od uživatele. Pro tyto vektory vypište s využitím Vašich i spolužákových funkcí velikost obou vektorů, zda jsou rovnoběžné, kolmé nebo ani rovnoběžné ani kolmé, zda jsou si rovny, jejich součet, rozdíl, skalární součin a vektorový součin a obecnou rovnici přímky, která je zadaná prvním vektorem a zadaným bodem. Všechny parametry budete načítat ve funkci main() a do funkcí je budete posílat. Pokud má funkce hodnotu vracet, budete ji vypisovat ve funkci main(). Vaše funkce pro práci s vektory: • funkce, která bude vracet číslo 1, jsou- li si vektory rovny, jinak vrátí číslo 0 • funkce, která bude vypisovat výsledek jejich rozdílu
82 • funkce, která bude vracet hodnotu skalárního součtu vektorů • funkce, která bude vypisovat obecnou rovnici přímky, která je zadaná vektorem (dva parametry funkce) a bodem (další dva parametry funkce). Souřadnice bodu načtete ve funkci main(). Přeložený soubor (*.obj) s Vašimi funkcemi i správně zapsaný hlavičkový soubor (s podmíněným překladem a komentářem Vašich funkcí) pošlete svému spolužákovi ve skupině, aby mohl vytvořit vlastní projekt.
Kontrolní otázky a úkoly 4) Musíme do projektů vkládat jen soubory s příponou *.c? Můžeme použít i soubory s příponou *.obj? Jestliže ano, v čem je výhoda? 5) Popište práci na předchozích příkladech, které jste vypracovávali ve dvojicích. Specifikujte, které části či co bylo na týmové práci nejsložitější.
83
21 Paměťové třídy Obsah hodiny Seznámíme se se všemi typy paměťových tříd a s jejich využitím ve vlastních programech.
Cíl hodiny Po této hodině budete schopni: ● ● ●
popsat jednotlivé části operační paměti charakterizovat jednotlivé paměťové třídy využít paměťové třídy ve vlastních programech
Klíčová slova Datová oblast, zásobník, halda, paměťová třída auto, register, extern a static
Operační paměť použitelnou pro náš program dělíme podle následujícího obrázku.
84 Jak a kde jsou proměnné deklarovány, určuje jejich chování a místo v paměti, kde budou alokovány. Obojí lze změnit pro jednotlivé proměnné pomocí paměťových tříd. Paměťové třídy určují, ve které části paměti bude proměnná alokována, kdy a kde bude použitelná. Zapisujeme je k deklaraci proměnných ve formátu: třída typ proměnná;
21.1 Paměťová třída auto Paměťová třída auto je pozůstatkem ze starších verzí jazyka C. Je implicitně používána pro všechny lokální proměnné, které se alokují v zásobníku. Nepoužívá se.
21.2 Paměťová třída register Proměnná je alokována v registru procesoru, ne v paměti. Je k ní proto rychlejší přístup, nemá však adresu a nemůžeme tak použít &.Proměnná se alokuje v registru pokud je volný, jinak se alokuje v zásobníku. Používá se jen pro lokální proměnné, nejčastěji pro řídící proměnné v cyklech, ke kterým přistupujeme často a proto je rychlejší přístup výhodou.
21.3 Paměťová třída extern Používá se pro globální proměnné, které se ukládají do datové oblasti a které potřebujeme v projektech sdílet ve více modulech. Paměťová třída extern se používá také v deklaraci uvnitř hlavičkového souboru, pokud používáme sdílenou globální proměnnou.
Příklad
85
21.4 Paměťová třída static Používá se pro globální i lokální proměnné, ukládají se do datové oblasti a chovají se jako globální proměnné. Paměťovou třídu static použijeme pro globální proměnnou, pokud potřebujeme, aby proměnná byla dostupná jen v modulu, ve kterém je definovaná.
Příklad
Paměťovou třídu static můžeme použít pro lokální proměnnou. Proměnná je pak dostupná jen ve funkci, kde je definovaná, ale existuje od prvního volání funkce až do konce programu. Ponechává si svou hodnotu mezi jednotlivými voláními.
Příklad void fce(); int main() { int i; for(i=1;i<=10;i++) fce(); return 0; } void fce() { static int x=0; x++; printf(“x je %d”,x); }
86 Proměnná x se inicializuje na 0 jen při prvním volání funkce fce(), pak už si jeho hodnotu pamatuje. Tzn. x bude měnit svou hodnotu při každém volání funkce a na obrazovku se vypíšou čísla 1 až 10.
Shrnutí kapitoly Paměťové třídy používáme pro změnu chování proměnné a pro změnu jejích umístění v paměti. Paměťové třídy jsou auto, register, extern a static.
Kontrolní otázky a úkoly 1) Vyjmenujte paměťové třídy a určete, zda se používají pro lokální nebo globální proměnné. 2) U každé paměťové třídy popište, jak ovlivňuje chování proměnné.
87
22 Alokace paměti, pointery Obsah hodiny Seznámíme se s novým typem proměnné - s pointery, se statickou a dynamickou alokací paměti.
Cíl hodiny Po této hodině budete schopni: ● ● ●
deklarovat pointer na daný datový typ využít pointer jako ukazatel na statickou proměnnou dynamicky alokovat, využít a odalokovat paměť v haldě
Klíčová slova Alokace paměti, statická data, dynamická data, pointer, dynamická alokace, funkce malloc, zásobník, halda
22.1 Alokace paměti Alokace paměti je vymezení místa v paměti pro proměnnou. Každé proměnné musí být během své existence přidělen paměťový prostor, který je dán datovým typem. Adresu proměnné v paměti získáme pomocí &. Jméno proměnné je symbolická adresa tohoto prostoru. Proměnné můžeme rozdělit do dvou základních skupin: 1. statická data •
v době překladu je znám jejich identifikátor a jejich velikost
•
jde o globální a lokální proměnné, které se alokují automaticky, vždy mají své jméno – identifikátor a velikost určenou datovým typem proměnné
2. dynamická data •
nemají předem stanovenou velikost, může ji dokonce určit uživatel až za běhu programu
88
•
jejich alokaci provádíme speciálním příkazem za běhu programu a musíme se také postarat o její odalokování
•
nemají svůj identifikátor
•
přistupujeme k nim pomocí pointerů
Každá statická proměnná má svůj identifikátor, velikost v paměti a adresu místa alokace v paměti, jak popisuje následující obrázek.
int a=10;
22.2 Pointery Pointer je proměnná, jejíž hodnota je paměťová adresa jiné statické nebo dynamické proměnné. Pointer nazýváme také ukazatel. Protože pointer obsahuje adresu jiného paměťového bloku, říkáme, že na tuto adresu pointer ukazuje. V obrázcích tento vztah značíme šipkou. Práce s pointery má několik částí, které si nyní vysvětlíme.
22.2.1 Deklarace pointeru Abychom mohli proměnnou pointer použít, musíme ji, jako každou jinou proměnnou, nejprve nadeklarovat. Vždy deklarujeme pointer podle toho, na který datový typ (resp. na jakou proměnnou) bude pointer ukazovat. U deklarace pointeru přidáváme k identifikátoru znak *. Obecně: datový_typ *identifikátor;
89
int *p, *p_a, a; Touto deklarací jsme nadeklarovali dva pointery s identifikátorem p a p_a. Dále také celočíselnou porměnnou a. Pokud jsme tuto deklaraci napsali do funkce main(), vytvořili jsme tři lokální proměnné, které se vyalokovaly v části paměti nazvané zásobník, jak zobrazuje následující obrázek. Uvědomte si, že oba pointery jsou statické proměnné – mají svůj identifikátor a je přesně dána jejich velikost už před překladem.
22.2.2 Uložení hodnoty do pointeru Aby pointer mohl někam ukazovat, musím do něj uložit adresu jiné proměnné nebo paměťového prostoru. Pokud chceme, aby pointer ukazoval na jinou statickou proměnnou, použijeme znak & pro získání adresy statické proměnné. Tuto adresu uložíme do pointeru.
p_a = &a;
V obrázku jsme si pro názornost určili, že adresa proměnné a je 8AB. Adresa se zobrazuje jako hexadecimální číslo, které je delší. Pro názornost jsem adresu zkrátila. Tato adresa se uložila do pointeru p_a a my tento zápis čteme: pointer p_a ukazuje na adresu 8AB (resp. na proměnnou a). Tento vztah značíme šipkou.
90 Ne vždy však potřebujeme pointer, který bude ukazovat na jinou statickou proměnnou. Pomocí pointeru můžeme využít část paměti nazvané halda, která je určena pro dynamické proměnné. Pokud chceme vyalokovat paměť v haldě, musíme použít funkci pro alokaci malloc(). Pro bezchybné použití funkce malloc() potřebujeme vložit do programu hlavičkový soubor .
p= (int*) malloc( sizeof (int)); Takto použitý příkaz malloc() vytvoří paměťový prostor v haldě o velikosti celočíselné proměnné, jejíž adresu uloží do pointeru p. Pointer p pak obsahuje adresu dynamické proměnné alokované v haldě. Všimněte si, že vytvořená dynamická proměnná nemá svůj identifikátor. Jediný přístup k ní je pomocí pointeru p. Její velikost jsme určili my v jediném parametru funkce malloc(). Popišme si tedy podrobně příkaz pro alokaci dynamické proměnné: p= (int*) malloc( sizeof (int)); Jak jsme již napsali, funkce malloc() využíváme pro alokaci dynamických proměnných v haldě. Její jediný parametr je počet bytů, které chceme alokovat. Můžeme napsat konkrétní číslo, ale vhodnější je použití operátoru sizeof(), který vrací velikost datového typu nebo proměnné. Funkce malloc() vrací adresu na datový typ void (tzv. generický pointer), proto jej musíme přetypovat, protože na levé straně příkazu máme pointer na datový typ int. Před malloc() napíšeme (int*), čímž přetypujeme pointer na void na pointer na int. Adresu, na které byla dynamická proměnná alokována, uložíme do pointeru p. Jestliže v haldě není dostatek místa, vrací malloc() hodnotu NULL. Můžeme při každé alokaci kontrolovat, zda se dynamickou proměnnou podařilo alokovat. if ((p=(int*)malloc(sizeof (int)))==NULL) printf(“Málo místa”);
91
22.2.3
Uložení hodnoty na místo, kam pointer ukazuje
Chceme-li uložit hodnotu na místo, kam pointer ukazuje, použijeme opět znak *.
*p_a=10; Příkaz můžeme číst: „tam kam ukazuje pointer p_a, ulož číslo 10“. Znamená to, že se do proměnné a uloží číslo 10. Ekvivalentní příkaz je tedy a=10;
*p=15; Číslo 15 se uloží do dynamické proměnné (na místo kam ukazuje pointer p).
Upřesníme si jednotlivá označení, která využíváváme u pointeru pomocí referenčního operátoru & a derefenčního operátoru *. &p – adresa uložení pointeru p p – adresa, kterou p obsahuje („kam ukazuje p“) *p – hodnota, na kterou p ukazuje
Adresy proměnných i jejich hodnoty můžeme vypsat na obrazovku: printf(“ %p %p %d “, &p, p,*p ); Pokud přistoupíme na označení hodnot z obrázku, vypíše se na obrazovku: 4C3 2F6 15
92
22.2.4
Uvolnění paměti a zakotvení pointeru
Po využití dynamické proměnné, musíme tuto proměnnou odalokovat. K odalokování používáme funkci free(). Ke každému maloc() přísluší jedno free(). Funkce free() uvolní paměť v haldě, která je poskytnuta k dalšímu využití, ale v pointeru p, zůstává stále adresa, jak je patrné z následujícího příkladu a obrázku. free(p); Abychom zrušili i spojení mezi pointerem a paměťovým prostorem, kam pointer ukazuje, musíme pointer tzv. zakotvit. Uložíme do něj hodnotu NULL. NULL je symbolická konstanta definovaná v stdio.h a znamená nulovou adresu. p=NULL; Po tomto příkazu zmizí z obrázku i červená šipka u pointeru p. Nesnažte se odalokovat statickou proměnnou!!! Jak jsme již uvedli, statická proměnná se alokuje i odalokovat automaticky. Funkci free() použijte jen pro proměnné, které jste alokovali příkazem malloc().
Shrnutí kapitoly Alokace paměti je vymezení místa v paměti pro proměnnou. Data dělíme na statická a dynamická. Pointer je proměnná, jejíž hodnota je paměťová adresa jiné statické nebo dynamické proměnné. Pro alokaci dynamické proměnné používáme funkci malloc() a pro odalokaci funkci free().
Kontrolní otázky a úkoly 1) 2) 3) 4)
Co je to alokace proměnné? Jak se liší statická a dynamická data? Co je to pointer? Popište práci s pointery. Uveďte příklady a popište situaci obrázkem.
93
23 Pointery - procvičování Obsah hodiny Procvičíme použití pointerů a dynamickou alokaci proměnných.
Cíl hodiny Po této hodině budete schopni: ● ●
vhodně použít pointery vytvořit dynamickou proměnnou, zapsat do ní hodnotu a proměnnou odalokovat
Klíčová slova Dynamická alokace, pointer, malloc()
Příklad Napište v jazyce C příkazy z komentářů tak, aby vznikl spustitelný program. /* 1. nadeklarujte reálnou proměnnou x a pointer u, který bude ukazovat na reálné číslo */ /* 2. naplňte pointer u adresou proměnné x */ /* 3. pomocí pointeru u, uložte do proměnné x číslo 12,3 */ /* 4. vypište tři hodnoty: hodnotu uloženou na místě, kam u ukazuje adresu, na které je pointer u uložen obsah pointeru u */ /* 5. vytvořte dynamickou reálnou proměnnou, na kterou bude ukazovat pointer u */ /* 6. načtěte od uživatele reálné číslo do dynamické proměnné, na kterou ukazuje pointer u */
94 /* 7. vypíšete hodnotu dynamické proměnné, na kterou u ukazuje */ /* 8. pomocí ternárního operátoru zjistěte a vypište, zda je načtené číslo v intervalu <-10;10> */ /* 9. uvolněte paměť, kterou zabral pointer u a pointer u zakotvěte */
Řešení #include <stdio.h> #include int main() { /* 1. */
float x,*u;
/* 2. */
u=&x;
/* 3. */
*u=12.3;
/* 4. */
printf(“hodnota %f adresa u %p, obsah u %p“, *u, &u, u);
/* 5. */
u=(float*) malloc( sizeof (float));
/* 6. */
scanf(“%f“,u);
/* 7. */
printf(“hodnota dynamicke promenne %f “, *u );
/* 8. */
((*u>=-10)&& (*u<=10)) ? printf(“Je”) : printf(“Neni”);
/* 9. */
free(u); u=NULL; return 0; }
Příklad Načtěte koeficienty a, b, c kvadratické rovnice do lokálních proměnných. Vypočtěte diskriminant. Jestliže D<0 vypište, že rovnice nemá v R řešení, jestliže D=0 alokujte dynamickou proměnnou, do které uložíte kořen rovnice a jestliže D>0 alokujte dvě proměnné, do nichž uložte kořeny rovnice. Vypište kořeny.
95
Řešení int main() { int a,b,c,D; scanf(“%d %d %d“,&a, &b,&c); D=b*b-4*a*c; if(D<0) printf(“Rovnice nemá řešení v R.“); if(D==0) { float *x; x=(float*)malloc(sizeof(float)); *x=(-b) / (2.0 *a); printf(“Jediný kořen rovnice je %.2f.“,*x); free(x); x=NULL; } if(D>0) { float *x1,*x2; x1=(float*)malloc(sizeof(float)); x2=(float*)malloc(sizeof(float)); *x1= (-b+ sqrt(D)) / (2*a); *x2= (-b- sqrt(D)) / (2*a); printf(“Jeden kořen rovnice je %.2f.“,*x1); printf(“Druhý kořen rovnice je %.2f.“,*x2); free(x1); free(x2); x1=NULL; x2=NULL; } return 0; }
96
Kontrolní otázky a úkoly 1) Načtěte hodnoty do dvou celočíselných dynamických proměnných a určete jejich největšího společného dělitele a jejich aritmetický průměr. 2) Načtěte dvě znakové dynamické proměnné. Je-li načteno malé písmeno, změňte jej ternárním operátorem na velké písmeno. Obsah obou proměnných vypište. 3) V cyklu načítejte do znakové dynamické proměnné znak. Pro každý znak vypište jeho předchůdce a následovníka v ASCII tabulce a jeho ordinální hodnotu. Načítání ukončete znakem ´.´ . 4) Načtěte hodnoty do celočíselné a reálné dynamické proměnné. Vypočtěte součet číselné řady 1/(x+1) + 2/(x+2) + 3/(x+3) + ... + n/(x+n) , kde celočíselná hodnota je označena písmenem n a reálná písmenem x.
97
24 Pointery a funkce Obsah hodiny Seznámíme se s použitím pointerů ve funkcích a práci s funkcemi s parametry volanými odkazem.
Cíl hodiny Po této hodině budete schopni: ● ●
aplikovat pointery jako parametry funkcí vysvětlit a popsat rozdíl mezi parametry volanými hodnotou a odkazem
Klíčová slova Skutečný parametr, formální parametr, parametr volaný odkazem, parametr volaný hodnotou
Pointery využíváme ve funkcích, pokud chceme, aby funkce vracela více než jednu hodnotu. Návrat dvou či více hodnot nemůžeme realizovat přes return(). Příkaz return() může vracet jen jednu hodnotu a proto pro další hodnotu, kterou z funkce chceme získat, použijeme pointer jako formální parametr funkce. Při volání funkce použijeme adresu lokální proměnné jako skutečný parametr. Tuto situaci si popíšeme na příkladu.
Příklad Vytvoříme funkci, která bude vracet součet i rozdíl dvou celých čísel.
int pocty(int a, int b, int *c); int main() { int x=5,y=3,s,r; s=pocty(x, y, &r ); printf(“Součet je %d“,s);
98
printf(“Rozdíl je %d“,r); return 0; } int pocty(int a, int b, int *c); { *c =a-b; return (a+b); }
Popišme si, jak bude provádění programu vypadat v paměti. •
Při deklaraci int x=5,y=3,s,r; se v paměti pro lokální proměnné vyblokuje místo pro proměnné x, y, s, r a proměnné x a y se naplní zadanými hodnotami.
•
Při volání funkce s=pocty(x, y, &r); se vyalokují formální parametry a, b, c, jak jsou uvedeny v hlavičce funkce int pocty(int a, int b, int *c); To znamená, že do proměnných a a b můžeme uložit celé číslo a do proměnné c můžeme uložit jen adresu, protože jde o pointer. Což se také stane. Do formálních parametrů a a b se uloží hodnoty ze skutečných parametrů x a y. Proto formální parametry a a b nazýváme parametry volané hodnotou. Do formálního parametru c se uloží adresa proměnné r a říkáme, že ukazatel c ukazuje na proměnnou r. Proto formální parametr c nazýváme parametr volaný odkazem.
99
•
Pokud pak ve funkci chceme uložit výsledek rozdílu, ukládáme jej tam, kam ukazuje pointer c – tedy do proměnné r. Příkaz *c =a-b; uloží hodnotu 2 do proměnné r. Příkaz return (a+b); ukončí funkci pocty a uloží hodnotu 8 do návratové hodnoty funkce a ta bude následně vrácena do funkce main() a uložena do proměnné s.
•
Po ukončení funkce jsou odalokovány formální parametry a požadované výsledky můžeme získat z proměnných x a y.
Formální parametry (z hlavičky funkce) jsou •
volány hodnotou – převezmou ze skutečného parametru hodnotu, ale skutečný parametr nemohou ovlivnit
•
volané odkazem – do formálního parametru (pointeru) se uloží adresa skutečného parametru, proto lze skutečný parametr změnit
Shrnutí kapitoly Parametry funkcí dělíme na parametry skutečné – parametry ve volání funkce, a formální parametry – parametry v hlavičce funkce. Formální parametry dále dělíme na parametry volané hodnotou, do kterých se uloží hodnoty ze skutečných parametrů, ale nemohou skutečné parametry ovlivnit, a parametry volané odkazem, které realizujme pomocí pointerů, do kterých uložíme adresu skutečného parametru a tak můžeme ovlivnit jeho hodnotu.
100
Kontrolní otázky a úkoly 1) Kdy a proč používáme pointery ve funkcích? 2) Vysvětlete rozdíl mezi parametry volanými hodnotou a parametry volanými odkazem.
Otázky k zamyšlení 1) Uveďte příklady funkcí, ve kterých byste museli použít parametr volaný odkazem.
101
25 Pointery a funkce - procvičování Obsah hodiny Procvičíme použití pointerů ve funkcích, které vrací více než jednu hodnotu.
Cíl hodiny Po této hodině budete schopni: ● ●
aplikovat pointery jako parametry volané odkazem vytvořit funkce, které budou vracet vice než jednu hodnotu
Klíčová slova Parametr volaný odkazem, parametr volaný hodnotou
Příklad Vytvořte funkci s hlavičkou void cifry(int x, int *soucet, int *pocet), která pro načtené číslo x vrací jeho ciferný součet a počet cifer.
Řešení void cifry(int x, int *soucet, int *pocet); int main() {
int cislo, s,p; scanf(“%d“,&cislo); cifry(cislo,&s,&p); printf(“Ciferný součet čísla %d je %d“,cislo,s); printf(“Počet cifer čísla %d je %d“,cislo,p); return 0;
} void cifry(int x, int *soucet, int *pocet);
102
{ soucet=0; pocet=0; while(x!=0) { (*soucet)+=x%10; (*pocet)++; x/=10; } } Jen díky pointerů, které použijeme jako parametry volané odkazem, můžeme z funkce získat dvě hodnoty. Ve funkci pak musím pracovat s pointery, proto musíme použít operátor *. V příkazu (*pocet)++; musíme uzávorkovat pointer, protože příkaz je vykonáván zprava do leva. Bez závorky by se nejprve vyhodnotil příkaz pocet++, který by zvýšil adresu (viz. kapitola o pointerové aritmetice) a na této změněné adrese by se hledala hodnota. V příkazu (*pocet)++; se nejprve zjistí hodnota na adrese, na kterou ukazuje pointer pocet, a pak se tato hodnota zvýši o jedna.
Příklad Vytvořte funkci, která pro tři celočíselné parametry d, h, b vrátí součet a aritmetický průměr celých čísel od d do h bez čísel dělitelných číslem b. Jestliže d>h zaměňte je pomocí funkce prohod, která zamění hodnoty dvou celočíselných proměnných.
Řešení void interval(int dolni, int horni,int bez, int *soucet, float *prumer); void prohod(int *a, int *b); int main() {
int d,h,b,s; float p; scanf(“%d“,&d); scanf(“%d“,&h);
103
scanf(“%d“,&b); interval(d,h,b,&s,&p); printf(“Součet čísel v intervalu je %d “,s); printf(“Aritmetický průměr je %f “, p); return 0; } void interval(int dolni, int horni,int bez, int *soucet, float *prumer) { int i,pocet=0; *soucet=0; for(i=dolni;i<=horni;i++) if ( i%bez==0) { (*soucet)+=i; pocet++; } *prumer= (*soucet) / (float) pocet; }
104
Kontrolní otázky a úkoly A)
Vytvořte funkci void obezita(float vyska, float vaha, float *bmi, int *obez), která podle hodnot vaha a vyska vypočte BMI (váha v kg dělená výškou v metrech na druhou) a do proměnné obez uloží hodnotu podle následujícího: 0 … BMI< 20 Podváha 1… BMI je mezi 20 – 25 Ideál 2… BMI je mezi 25 – 30 Mírná nadváha 3… BMI je mezi 30 – 40 Obezita 4… BMI >40 Těžká obezita Funkci otestujte v main a vypište, jak je na tom uživatel s hodnotou BMI a obezitou.
B)
Vytvořte funkce pro práci s komplexními čísly.
1. Vytvořte funkci, která načte a vrátí reálnou a imaginární složku (celá čísla) komplexního čísla. 2. Vytvořte funkci, která pro dva celočíselné zadané parametry (reálnou a imaginární složku komplexního čísla) vypíše číslo v jeho algebraickém tvaru: re + im i 3. Vytvořte funkci, která vypočte a vrátí součet dvou komplexních čísel. Vstupní parametry budou reálné a imaginární složky obou komplexních čísel a výstupní parametry bude reálná a imaginární složka výsledného komplexního čísla. 4. Vytvořte funkci, která vypočte a vrátí součin dvou komplexních čísel. Vstupní parametry budou reálné a imaginární složky obou komplexních čísel a výstupní parametry bude reálná a imaginární složka výsledného komplexního čísla. 5. Vytvořte funkci, která vypočte a vrátí absolutní hodnotu komplexního čísla. Vstupní parametry budou reálná a imaginární složka komplexního čísla. Ve funkci main načtěte pomocí funkce dvě komplexní čísla. Pomocí další funkce je vypište v algebraickém tvaru. Pro obě čísla vypočtěte a v main vypište jejich absolutní hodnotu. Vypočtěte součet a podíl těchto dvou komplexních čísel a vypište výsledky opět pomocí funkce v algebraickém tvaru.
105
26 Jednorozměrné statické pole Obsah hodiny Seznámíme se s novým strukturovaným homogenním datovým typem – s polem.
Cíl hodiny Po této hodině budete schopni: ● ●
charakterizovat datový typ pole deklarovat jednorozměrné statické pole
Klíčová slova Homogenní strukturovaný datový typ, heterogenní strukturovaný datový typ, pole, index
Pro uchování více hodnot stejného nebo různého datového typu bychom bez znalosti strukturovaných datových typů museli deklarovat mnoho proměnných s mnoha identifikátory. Například, kdybychom chtěli uchovat průměrnou teplotu pro každý den v roce a tyto hodnoty dále statisticky zpracovávat, potřebovali bychom 365 či 366 proměnných. Sami jistě tušíte, že zpracování takto uložených dat by bylo nepřehledné a zdlouhavé. Pro práci s větším množstvím hodnot využíváme strukturované datové typy. Pokud jsou všechny hodnoty stejného datového typu, říkáme, že je to homogenní datový typ. Jsou-li hodnoty různých datových typů, nazýváme tento typ heterogenní datový typ. Jako první ze strukturovaných datových typů prostudujeme pole. Pole je uspořádaná množina hodnot stejného datového typu. Jde tedy o homogenní strukturovaný datový typ. Statické pole musí mít známý počet prvků již při překladu. Deklarace statického pole: datový_typ název[počet_prvků];
106
Příklad int p[5]; Vytvoří se pětiprvkové pole pro celá čísla a pointer p, který ukazuje na toto pole - obsahuje adresu prvního prvku pole.
Pointer p je statický a po celý běh programu neměnný! K jednotlivým prvkům pole přistupujeme pomocí indexů. Jazyk C vždy indexuje pole od nuly a nekontroluje meze pole. Jednotlivé prvky pole budeme označovat a přistupovat k nim takto:
Index posledního prvku je tedy vždy o 1 menší než počet prvků pole. Výše jsme uvedli, že statické pole musí mít známý počet prvků již při překladu. Pro deklaraci pole můžeme tedy využít konstanty i makra bez parametru.
Příklady deklarace statického pole 1) int p[5]; Vytvoří se statické pole pro pět celých čísel 2) #define MAX 10 char x[MAX], y[MAX*2]; Preprocesor ještě před překladem zpracuje makro MAX tak, že nahradí všechny řetězce “MAX“ v kódu za hodnotu 10. Proto v době překladu vypadá deklarace polí x a y takto: char x[10], y[10*2];
107 Vytvoří se desetiprvkové pole x po 10 znaků a dvacetiprvkové pole y pro 20 znaků. 3) int a; float pole[pocet]; NELZE použít!!! V době překladu neznáme hodnotu proměnné pocet a nevíme kolik prvků je potřeba alokovat 4) Statické pole můžeme již při deklaraci inicializovat. int pole[4]={8,2,4,3}; Vytvoří se pole pro 4 celá čísla a prvky pole se naplní hodnotami uvedanými v závorce. 5) int pole[ ]={10,20,30}; Překladač zjistí počet prvků pole podle počtu hodnot ve složených závorkách.
Shrnutí kapitoly Datový typ pole použijeme, pokud potřebujeme zpracovat více hodnot stejného datového typu. Statické jednorozměrné pole musí mít známý počet prvků již při překladu. Obecně deklaraci pole zapisujeme: datový_typ název[počet_prvků]; V paměti se vytvoří zadaný počet prvků daného datového typu a pointer, který obsahuje adresu prvního prvku pole. K prvkům pole a k jejich hodnotám přistupujeme pomocí indexů, které začínají číslem 0. Index posledního prvku je tedy vždy o 1 menší než počet prvků pole.
Kontrolní otázky a úkoly 1) Jaký je rozdíl mez homogenním a heterogenním datovým typem? 2) Uveďte příklady deklarací statických jednorozměrných polí. Zakreslete tyto pole tak, jak se alokují v paměti.
Otázky k zamyšlení 1) Promyslete příklady programů, kdy by bylo vhodné použít jednorozměrné statické pole.
108
27 Práce s jednorozměrným statickým polem Obsah hodiny Seznámíme se s principy práce s jednorozměrným statickým polem.
Cíl hodiny Po této hodině budete schopni: ● ●
vhodně použít datový typ pole pracovat s jednotlivými prvky pole i s polem jako celkem
Zápis i přístup k hodnotám prvků pole provádíme přes indexy v hranatých závorkách.
Příklady zápisů hodnot prvků pole int p[3]; p[0]= 10; //do prvního prvku pole se uloží číslo 10 scanf(“%d”,&p[1]); // do druhého prvku pole se uloží číslo načtené od uživatele srand((long)time(NULL)); p[2]= rand() % 100; // do třetího prvku pole se uloží náhodně vygenerované číslo p[3]= 8; // do nevyalokované části paměti se zapíše číslo 8. Jazyk C nekontroluje meze polí, proto nebude hlášena chyba. Ale zápis mimo vyalokovanou paměť je velice nebezpečná činnost.
109 S poli většinou pracujeme jako s celkem - načítáme, vypisujeme nebo procházíme všechny prvky pole. Při práci s poli používáme nejčastěji cyklus for, protože víme, kolik má pole prvků a kolikrát se tedy daná činnost bude opakovat.
Příklad práce s polem #define MAX 5 float a[MAX];
//deklarace pole pěti prvků
for (i=0;i<MAX;i++)
//pro indexy 0 až 4
scanf(“%f“,&a[i]);
//načítáme hodnoty prvků v pole od uživatele
for (i=0;i<MAX;i++) printf(“%f “,a[i]);
//vypisujeme hodnoty prvků pole
Všimněte si, výhodného použítí konstanty MAX. Pokud změníte hodnotu této konstanty, bude tento program schopen pracovat bezchybně i s jiným počtem prvků.
Příklad kopírování pole char a[ ]={‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘y’}, b[6]; V paměti se vytvoří tato pole.
Chceme-li nakopírovat prvky z pole a do pole b, nemůžeme použít příkaz b=a; Identifikátory a a b jsou pointery – ukazatele na první prvky polí. Příkazem b=a; bychom se snažili přepsat adresu v pointeru b. Ale pointery a a b jsou statické, neměnné, proto tento příkaz nebude přeložen. Kopírování prvků provádíme prvek po prvku v cyklu for. for (i=0;i<6;i++) b[i]=a[i];
110
Shrnutí kapitoly K prvkům pole a k jejich hodnotám přistupujeme pomocí indexů, které začínají číslem 0. Musíme kontrolovat meze pole, abychom nezapisovali do nevyalokované paměti. Pro práci s polem nejčastěji používáme cyklus for. Kopírování prvků pole musíme provádět prvek po prvku. Práci s identifikátory polí – pointery provádíme s vědomím, že jde o pointery.
Kontrolní otázky a úkoly 1) Do pole char pole[8] zapište do jeho prvního prvku písmeno M a do posledního prvku pole znak *. 2) Vytvořte program, který do desetiprvkového znakového pole náhodně vygeneruje znaky z malé anglické abecedy (hodnoty v ASCII tabulce od 97 až 122). Pole vypište.
111
28 Jednorozměrné dynamické pole Obsah hodiny Seznámíme se jednorozměrným polem, které vytvoříme dynamicky.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vyalokovat dynamické jednorozměrné pole popsat rozdíly mezi statickým a dynamickým jednorozměrným polem pracovat s prvky jednorozměrného dynamického pole
Klíčová slova Dynamické jednorozměrné pole, alokace pole
Dynamické jednorozměrné pole úzce souvisí s dynamickými proměnnými, které jsme tvořili v kapitolách o pointerech. Připomeňme si, že dynamická data nemají předem stanovenou velikost, může ji dokonce určit uživatel až za běhu programu. Jejich alokaci provádíme speciálním příkazem za běhu programu a musíme se také postarat o její odalokování. Dynamické proměnné nemají svůj identifikátor a přistupujeme k nim pomocí pointerů. Při deklaraci dynamického pole nemusíme znát počet prvků pole. Postačí znát jen datový typ prvků pole. Tyto prvky pak musíme sami vyalokovat a odalokovat.
Příklad vytvoření dynamického pole int *p, pocet=5; // Touto deklarací se vytvoří pointer na celé číslo. Je jen na nás jestli bude ukazovat na jedno celé číslo číslo nebo na celé pole.
112
p = (int*)malloc(sizeof(int)*pocet); // Vyalokuje se v haldě zadaný počet prvků pole. Adresa prvního prvku tohoto dynamického pole se uloží do pointeru p. // V příkazu pro alokaci můžeme místo proměnné pocet uvést konstantu nebo výraz, který nemusí být vyhodnocen při překladu, ale třeba až za běhu programu. Proto můžeme počet požadovaných prvků pole načíst i od uživatele a podle jeho požadavků vyalokovat zadaný počet prvků. // V paměti bude vypadat naše pole takto:
free(p); p=NULL; // Nesmíme zapomenout vyalokované pole odalokovat a pointer p zakotvit. Práce se statickým a dynamickým polem je shodná. K jednotlivým prvkům dynamického pole přistupujeme pomocí indexů, které začínají číslem 0. Rozdíl je v alokaci a odalokaci pole a v umístění jeho prvků v paměti.
Příklad int a[5],*p; // Prvky statického pole se vytvoří automaticky. p = (int*)malloc(sizeof(int)*5); // Prvky dynamického pole musí vytvořit programátor. a[0]=15; p[0]=15; scanf(“%d”,&a[1]); scanf(“%d”,&p[1]);
113 // Přístup k jednotlivým prvkům je shodný. free(p); p=NULL; // Prvky dynamického pole musíme odalokovat. V paměti budou pole umístěna takto:
Všimněte si, že jediným rozdílem mezi statickým pole a dynamickým polem je v umístění prvků pole.
Shrnutí kapitoly Při deklaraci dynamického pole musíme znát jen datový typ prvků pole, nemusíme znát jejich počet. Prvky pole musíme sami vyalokovat a odalokovat. Rozdíl mezi statickým a dynamickým polem je v umístění prvků pole v paměti. Práce s prvky statického a s prvky dynamického pole je totožná.
Kontrolní otázky a úkoly 1) Vysvětlete, proč je práce s prvky dynamických i statických polí shodná a v čem se tyto pole liší. 2) Vytvořte program, který načte od uživatele požadovaný počet prvků pole. Vyalokujte požadované pole reálných čísel a naplňte jej hodnotami zadanými uživatelem. Pole vypište.
114
29 Jednorozměrné pole - procvičování Obsah hodiny Procvičíme práci se statickým i dynamickým polem.
Cíl hodiny Po této hodině budete schopni: ● ● ●
vytvořit statické i dynamické jednorozměrné pole využít pole pro zpracování dat stejného datového typu zpracovat jednotlivé prvky pole k získání potřebných údajů
Klíčová slova Statické jednorozměrné pole, dynamické jednorozměrné pole, alokace pole, index.
Příklad Vytvořte pole pro deset celých čísel. Načtěte od uživatele celé číslo a do pole vložte deset násobku (od 1 do 10) tohoto zadaného čísla. • Zaměňte v poli první prvek za poslední a druhý za předposlední. Pole vytiskněte. • Vytiskněte prvky pole do jednoho řádku oddělené mezerou a na novém řádku v opačném pořadí.
Řešení #include <stdio.h> int main() { int pole[10],cislo,i,pom;
115
printf("Zadej cele cislo: "); scanf("%d",&cislo);
// Načteme požadované číslo
for(i=0;i<10;i++) pole[i]=cislo*(i+1); // Zápis násobků zadaného čísla do pole. V závorce je uvedeno i+1, aby násobky začínaly od čísla 1 ne od 0, jako cyklus a indexace prvků pole.
printf("\n\nPrvky pole: "); for(i=0;i<10;i++)
// Výpis prvků pole
printf("%d ",pole[i]); // Pomocí pomocné proměnné pom provedeme záměnu hodnoty prvního prvku pole za hodnotu posledního prvku pole. pom=pole[0]; pole[0]=pole[9]; pole[9]=pom;
// Obdobně zaměníme hodnotu druhého prvku za hodnotu předposledního (devátého) prvku pole. pom=pole[1]; pole[1]=pole[8]; pole[8]=pom;
printf("\n\nPrvky pole po zamene: "); for(i=0;i<10;i++)
// Výpis prvků pole
printf("%d ",pole[i]);
printf("\n\nPrvky pole v opacnem poradi: "); for(i=9;i>=0;i--) printf("%d ",pole[i]);
// Výpis prvků pole od indexu 9 až po index 0
116
getch(); return 0;} Výstup programu bude vypadat takto:
Příklad Pole p naplňte 10 náhodnými čísly z intervalu <1;10> a pole p vypište. •
Určete kolik je v poli p čísel sudých.
•
Určete minimální hodnotu v poli p.
•
Vytvořte dynamické pole suda, pro všechny sudá čísla z pole p. Nakopírujte všechny sudá čísla z pole p do pole suda.
Řešení #include <stdio.h> int main() { int pole[10],i,j=0,sud=0,min,*suda; srand((long)time(NULL));
// inicializace generátoru náhodných čísel
for(i=0;i<10;i++) pole[i]=rand() % 10 + 1; printf("Prvky pole p: ");
// zápis generovaných čísel do pole // výpis prvků pole
for(i=0;i<10;i++) printf("%d ",pole[i]); min=pole[0];
//do minima uložíme hodnotu prvního prvku
117
for(i=0;i<10;i++) { if(pole[i]%2==0) sud++;
//zjišťujeme počet sudých čísel
if(min>pole[i]) min=pole[i]; }
//zjišťujeme, zda jsme našli nové min
// po ukončení cyklu vypíšeme počet sudých čísel a hodnotu minima printf("\n\nPocet sudych cisel je: %d ",sud); printf("\n\nMinimum pole je: %d ",min); suda=(int*)malloc(sizeof(int)*sud); // vytvoříme dynamické pole suda, které bude mít počet prvků podle počtu sudých čísel v poli p for(i=0;i<10;i++) if(pole[i]%2==0)
// jestliže je prvek pole p sudé číslo
{ suda[j]=pole[i];
//uložíme jej do pole sudá
j++;
//zvýšíme index j pro zapisování do pole suda
} // výpis prvků pole suda; jejich počet je uložen v proměnné j printf("\n\nPrvky pole suda: "); for(i=0;i<j;i++) printf("%d ",suda[i]); getch(); return 0; } Výstup programu bude vypadat například takto:
.
118
Shrnutí kapitoly Pro práci s polem využívejte cyklus for. Bedlivě sledujte indexy v poli, ať nepracujete mimo meze pole v nevyalokované části paměti.
Kontrolní otázky a úkoly 1) Pole naplňte 10 náhodnými čísly z intervalu <1;10>. •
Určete, kolikrát se v poli vyskytuje číslo 5 a vypište všechny pozice všech jeho výskytů v poli.
•
Určete jaký je součet všech lichých čísel v poli.
•
Určete průměrnou hodnotu čísel v poli.
•
Určete maximální hodnotu v poli.
•
Určete dvě čísla v poli, která dávají nejmenší součet a tento součet vypíše (tzn. dvě nejmenší čísla)
•
Určete počet čísel dělitelných číslem 3.
2) Načtěte do pole větu ukončenou tečkou (maximálně však 60 znaků). •
Všechna malá písmena v poli přepište velkými písmeny. Ostatní znaky ponechte.
•
Odstraňte z pole stejné hodnoty.
3) Vytvořte program, který simuluje hru Šťastných 10. Pole 20 tažených čísel naplňte náhodně generovanými čísly z intervalu <1; 80>. Pole 10 tipovaných čísel načtěte od uživatele. Vypište uhodnutá čísla, jejich počet a výši výhry.
119
30 Pointerová aritmetika Obsah hodiny Seznámíme se s operacemi, které můžeme provádět s pointery.
Cíl hodiny Po této hodině budete schopni: ● ●
popsat přípustné operace s pointery použít pointerovou aritmetiku v práci s jednorozměrným polem
Klíčová slova Pointerová aritmetika, operátory
30.1 Operace s pointery Pro pointery můžeme mimo operátory * a & použít také operátory,++,-,+,-, <, == a další. Tyto operace mají význam, pokud pointery ukazují na stejný blok paměti – na pole a pokud jsou stejného datového typu. Veškeré operace se pak musí provádět s ohledem na tento datový typ.
30.1.1 Součet pointeru a celého čísla Pokud sečteme pointer s celým číslem ukazatel + n výsledkem bude adresa n-tého prvku za prvkem, na který ukazuje pointer ukazatel. Posun v paměti je součin čísla n a velikosti bázového datového typu pointeru ukazatel.
Příklad
120
30.1.2 Rozdíl pointeru a celého čísla Analogicky při rozdílu pointeru a celého čísla ukazatel - n bude výsledkem adresa ukazuje pointer ukazatel.
n-tého
prvku
před
prvkem,
na
který
Příklad
30.1.3 Odečítání pointerů Rozdíl dvou pointerů ukazatel1 – ukazatel2 má smysl pouze tehdy, pokud oba pointery ukazují na stejný celek paměti, tedy na pole. Tento rozdíl vrací počet položek, které se nacházejí mezi těmito pointery.
Příklad
30.1.4 Porovnání pointerů Pro dva pointery můžeme použít relační operátory <, <=, >, >=, ==, !=, což má opět smysl jen pokud oba pointery ukazují na stejný celek paměti a jsou stejného datového typu.
121
Příklad
30.2 Využití pointerové aritmetiky Pointerovou aritmetiku používáme k přístupu jednotlivým prvkům pole.
Příklad
Hodnoty prvků polí můžeme zapsat pomocí indexace. Například hodnotu třetího prvku pole p můžeme vypsat pomocí p[2], nebo můžeme využít pointerové aritmetiky a posunu pointeru p o zadaný počet prvků v poli. Hodnotu třetího prvku můžeme vypsat jako hodnotu na adrese p+2, tedy *(p+2).
122
Shrnutí kapitoly Pro práci s pointery používáme některé operátory. ukazatel + n – posune adresu o n prvků za pointer ukazatel ukazatel – n – posune adresu o n prvků před pointer ukazatel ukazatel1 – ukazatel2 – vrátí počet prvků mezi adresami porovnávání pointeru, porovnává adresy v paměti. Pointerovou aritmetiku používáme k přístupu jednotlivým prvkům pole.
Kontrolní otázky a úkoly 1) Popište jednotlivé operace s pointery a určete, co bude výsledkem či výstupem dané operace. 2) Vytvořte si pole znaky deseti znaků a pointer uk, který bude ukazovat za pátý prvek v poli znaky. a. Vypište pomocí pointeru uk všemi způsoby adresu a hodnotu druhého a devátého prvku pole znaky. b. O jak velkou paměť se uk posune, když přiřadíme uk=uk+3;
123
31 Pointerová aritmetika - procvičování Obsah hodiny Procvičíme pointerovou aritmetiku v jednorozměrném poli.
Cíl hodiny Po této hodině budete schopni: ●
použít pointerovou aritmetiku v přístupu k jednotlivým prvkům jednorozměrného statického pole
Klíčová slova Pointerová aritmetika
Příklad Mějme nadeklarovány tyto proměnné a jim přiřazené hodnoty.
int p[6], *a,*b; a=p+5; b=a-3;
Pomocí všech tří pointerů vypište adresu i hodnotu čtvrtého prvku pole p pointerovou aritmetikou.
Řešení Situaci máme znázorněnu na následujícím obrázku.
124
Pokud se ke čtvrtému prvku budeme chtít dostat přes pointer p, budeme se muset posunout o tři prvky pole. Proto adresu získáme nejen jako &p[3], ale i pomocí p+3. Hodnotu získáme jako p[3] a také pomocí *(p+3). Čtvrtý prvek je dostupný přes pointer b po posunu o jeden prvek pole. Adresa čtvrtého prvku je b+1, hodnota pak *(b+1). Analogicky pomocí pointeru a. Adresa čtvrtého prvku je a-2, hodnota *(a-2). V programu má řešení tento zápis: printf(“hodnota: %d %d %d ”,*(p+3), *(b+1), *(a-2) ); printf(“adresa: %p %p %p ”, p+3, b+1, a-2 );
Shrnutí kapitoly Operace se pointery mají smysl, jen pokud pointery ukazují na stejný blok paměti, tedy na pole. K prvkům pole se dostaneme přes různě umístěné pointery v poli pomocí pointerové aritmetiky.
125
Kontrolní otázky a úkoly
1) Nadeklarujte tři celočíselné pointery a, b, c. 2) Pro pointer a vytvořte dynamické pole šesti celých čísel, které načtěte náhodné čísly z intervalu <-9;9>. Pole vypište. 3) Do pointeru b uložte adresu třetího prvku dynamického pole. 4) Do pointeru c uložte adresu pátého prvku dynamického pole. viz. obrázek
5) Vypište obsahy (adresy) pointerů a, b, c. 6) Pomocí všech tří pointerů a, b, c vypište všemi možnostmi adresu čtvrtého prvku v poli. 7) Pomocí všech tří pointerů a, b, c vypište všemi možnostmi hodnotu druhého prvku v poli. 8) Určete rozdíl pointerů a, b ; a, c; c, b. 9) Porovnejte pointery b, c; c, a. 10) Odalokujte vymezenou paměť a zakotvěte pointery a, b, c.
126
32 Pole a funkce Obsah hodiny Seznámíme se s využitím polí ve funkcích.
Cíl hodiny Po této hodině budete schopni: ● ●
vysvětlit využití polí jako parametrů funkcí s jejich správným zápisem navrhnout funkci s vhodnými parametry pro zpracování polí
Klíčová slova Parametr volaný odkazem.
Vytváříme-li funkci pro zpracování pole (např. pro zjištění maximální hodnoty nebo pro uspořádání pole), posíláme do funkce toto pole jako její parametr. Je-li pole parametrem funkce, předává se do funkce jen adresa pole – adresa prvního prvku pole, ne celé pole. Jde tedy o parametr volaný odkazem. To znamená, že jakákoliv změna způsobena v poli ve funkci, v poli zůstane i po skončení této funkce.
Příklad Vytvořte funkci pro výpočet aritmetického průměru hodnot v poli.
Řešení Rozeberme si nyní, jak by mohla vypadat deklarace zadané funkce. 1) float prumer( int pole[10 ] ); - překladač však informaci o velikosti pole ignoruje, protože předáváme jen adresu 2) float prumer( int pole[ ] ); nebo float prumer( int *pole ); - v obou případech je p pointer, do kterého je při volání funkce načtena adresa prvního prvku pole. Problémem však zůstává, že
127 neznáme velikost pole ve funkci. Našim úkolem by mělo být vytvořit funkci pro univerzální použití, tedy pro pole s různým počtem prvků. Proto se jako nevhodnější jeví poslední deklarace s dvěma parametry – adresou prvků pole a počtem prvků. •
float prumer( int pole[ ], int pocet ); - parametr počet udržuje informaci o počtu prvků pole a zajistí tak kontrolu mezí pole a díky němu můžeme do funkce poslat pěti-prvkové i sto-prvkové pole
Celý kód programu může vypadat takto: float prumer( int pole[ ], int pocet ); int main() { int p1[ ]={5,7,3,9,1};
//inicializujeme si dvě pole
int p2[ ]={4,2,8}; printf(“Prumer p1 je %f”, prumer ( p1,5)); printf(“Prumer p2 je %f”, prumer ( p2,3)); //posíláme do funkce adresu prvního prvku pole a počet return 0; } float prumer ( int pole[ ], int pocet ) { int i, soucet=0; for (i=0; i<pocet ;i++) soucet+=pole[i];
//sčítáme všechny prvky pole
return ( (float)soucet / pocet ); } //vrací aritmetický průměr = součet/počet Ve chvíli, kdy je volána funkce prumer pro pole p1 je v paměti vyalokován pointer pole a parametr pocet. Do pointeru pole se uloží adresa prvního prvku pole p1 a do proměnné pocet se uloží číslo 5. V paměti se prvky pole nealokují znovu. Ve funkci main i ve funkci prumer pracujeme se stejným paměťovým prostorem. Ve funkci main na něj ukazuje pointer p1 a ve funkci prumer na něj ukazuje pointer pole. Proto jakékoliv změny v poli provedené ve funkci prumer by v poli zůstaly i po ukončení funkce. Situace je zobrazena na následujícím obrázku.
128
Shrnutí kapitoly Do funkce zpracovávající jednorozměrné pole posíláme vždy jen adresu prvního prvku pole a počet prvků pole.
Kontrolní otázky a úkoly 1) Načtěte do pole větu ukončenou tečkou (maximálně 60 znaků). Vytvořte funkce, které: a) vrátí počet znaků ve větě b) vypíše větu pozpátku c) vrátí počet slov v zadané větě podle počtu mezer a čárek. d) vrátí počet malých písmenek a počet velkých písmenek v zadané větě. e) vrátí počet výskytů zadaného znaku ve větě. f) změní všechna první písmena ve slovech na velké písmeno, pole v main() vypište 2) Načtěte od uživatele počet prvků a vytvořte celočíselné dynamické pole zadaného počtu prvků. Naplňte toto pole náhodně vygenerovanými čísly z intervalu <10;20> a) vytvořte funkci pro výpis pole. b) vytvořte funkci, která vypočte a vrátí průměrnou hodnotu čísel v poli. c) vytvořte funkci, která najde a vrátí maximální hodnotu v poli a jeho pozici. d) vytvořte funkci, která vrátí ukazatel na minimální hodnotu v poli. e) vytvořte nové dynamické pole, do kterého zapíšete všechna sudá čísla z prvního pole. f) načtěte od uživatele, o kolik prvků chce toto nové pole zvětšit. Pole zvětšete a doplňte uživatelem zadanými hodnotami.
129
33 Třídící algoritmy Obsah hodiny Seznámíme se třídícími algoritmy, s požadavky na třídící algoritmy a s typy řazení.
Cíl hodiny Po této hodině budete schopni: ● ● ● ● ●
vysvětlit důvody třídění dat charakterizovat skupiny třídících algoritmů popsat požadavky na třídící algoritmy vyjmenovat jednotlivé metody řazení vyjmenovat neznámější třídící algoritmy
Klíčová slova Třídění, vnitřní třídění, vnější třídění, požadavky na třídící algoritmy, principy řazení
Tříděním (resp. řazením) rozumíme uspořádání množiny dat podle zvolené klíčové položky - vzestupně nebo sestupně. Se setříděnými daty se lépe pracuje, například je snadnější vyhledávání. Podle různých kritérií se algoritmy řazení dají dělit do různých skupin. Dvě základní skupiny algoritmů jsou tzv. vnitřní a vnější třídění. Vnitřní třídění •
použijeme tehdy, pokud lze množinu tříděných dat umístit do vnitřní paměti počítače
•
data jsou uložena v poli a algoritmy využívají možnosti přímého přístupu k jednotlivým prvkům (třídění polí)
Vnější třídění •
použijeme tehdy, kdy se tříděná data nevejdou do vnitřní paměti
•
data jsou umístěna v souborech na vnějším paměťovém médiu
•
třídění je založeno na opakovaném čtení a vytváření souborů
130 Řazení je velmi častá úloha, která je také částí mnoha dalších algoritmů; vývoji co možná nejefektivnějších algoritmů řazení se proto věnuje velké úsilí. Pro řazení existuje spousta hotových algoritmů, které se liší v mnoha aspektech, jako je složitost, stabilita, nebo metoda pro řazení. Od těchto vlastností se odvíjí také požadavky, které jsou na algoritmy kladeny: 1) Paměťová náročnost, která by měla být minimální. Tento faktor je velmi důležitý, hlavně při řazení velkého počtu záznamů. 2) Rychlost algoritmu, neboli její časová složitost, je ovlivňována počtem operací, které je nutno se vstupním souborem provést a je ovlivněna i počtem prvků, které jsou ve vstupním souboru dat. Většinou je tato složitost kvadratická, logaritmická nebo lineární, dle výběru algoritmu. 3) Délka kódu není až tak důležitý faktor, ale v praxi většinou platí, že čím kratší kód, tím efektivnější zpracování vstupu. Ovšem není to podmínkou. 4) Stabilita určuje, zda budou seřazené prvky souhlasit s jejich klíči. Většinou jsou při řazení využívány klíče a hodnoty, které se řadí závisle nebo nezávisle na sobě. 5) Přirozenost je vlastnost, kdy algoritmus je přirozený v případě, že čas řazení již z části seřazené vstupní posloupnosti je menší než čas pro řazení neseřazené posloupnosti. Existuje několik základních druhů algoritmů univerzální vnitřního řazení, přičemž některé pokročilejší algoritmy kombinují více postupů. Řazení výběrem V souboru se vždy najde nejmenší ze zbývajících položek a uloží na konec postupně budovaného seřazeného souboru. Řazení vkládáním Ze souboru neseřazených dat se postupně bere položka po položce a vkládá se na správné místo v seřazeném souboru (zpočátku prázdném). Řazení záměnou V souboru se vždy nalezne (nějakou metodou závislou na konkrétním algoritmu) nějaká dvojice prvků, která je ve špatném pořadí, a tyto prvky se navzájem zamění.
131 Řazení slučováním Vstupní soubor se rozdělí na části, které se (nejčastěji rekurzivně) seřadí. Výsledné seřazené části se poté sloučí takovým způsobem, aby i výsledek byl seřazený. Neexistuje žádný „dokonalý“ řadicí algoritmus, který by byl ideální pro všechna použití. Různé algoritmy mají různé vlastnosti, co se týká jejich očekávané časové a paměťové složitosti, náročnosti implementace a dalších vlastností. Pro konkrétní podmínky se tak často navrhují specifické varianty.
Shrnutí kapitoly Tříděním je uspořádání množiny dat podle zvolených parametrů vzestupně nebo sestupně. Podle různých kritérií se algoritmy řazení lze dělit na algoritmy s vnitřním nebo vnějším tříděním. Na třídící algoritmy máme určité požadavky – paměťová náročnost, rychlost, délka kódu, stabilita, přirozenost. Základní postupy třídění jsou – řazení výběrem, vkládáním, záměnou a slučováním.
132
Kontrolní otázky a úkoly 1) 2) 3) 4) 5)
Vysvětlete důvody třídění dat. Co znamená vnitřní a vnější třídění? Vyjmenujte a popište požadavky na třídící algoritmy. Vyjmenujte jednotlivé metody řazení. Vyjmenujte neznámější třídící algoritmy.
133
34 Bubble sort Obsah hodiny Seznámíme se třídícím algoritmem Bubble Sort.
Cíl hodiny Po této hodině budete schopni: ● ●
charakterizovat třídící algoritmus Bubble sort vysvětlit způsob a postup třídění pomocí algoritmu Bubble sort
Klíčová slova Bubble sort
Třídící algoritmus Bubble Sort třídí data metodou záměny. Jde o nejjednodušší algoritmus, ale také o nejpomalejší třídící algoritmus. Bubble sort nepotřebuje žádnou pomocnou paměť, je stabilní a patří mezi přirozené algoritmy. Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený. Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely či v nenáročných aplikacích pro třídění malých polí nebo polí, která jsou už částečně setřízená. Bubble sort obsahuje dva vnořené cykly for, kterými procházíme pole, které máme setřídit. Pro napsání zdrojového kódu Bubble sortu si nejprve definujeme makro bez parametrů MAX, kterým pak můžeme měnit velikost pole. Tělo třídícího algoritmu Bubble sort, který setřídí prvky v poli s MAX prvky, vypadá takto:
134
#define MAX 5 int i,j,a,pole[MAX]; for (j=0; j<MAX-1; j++) for (i=0; i<MAX-1; i++) if (pole[i]>pole[i+1]) { a=pole[i]; pole[i]=pole[i+1]; pole[i+1]=a; } Algoritmus Bubble sort:
Zdroj: Www.manualy.net. Www.manualy.net [online]. 19.2. 2007 [cit. 2012-02-01]. Dostupné z: http://www.manualy.net/article.php?articleID=19
135 Pojďme si jednotlivé části Bubble Sortu projít podrobně s cvičným polem pole, které bude obsahovat prvky: 5,4,6,2,3.
5
4
6
2
3
Začneme tou nejvnitřnější částí. if (pole[i]>pole[i+1]) { a=pole[i]; pole[i]=pole[i+1]; pole[i+1]=a; } V této části porovnáváme dva sousedící prvky v poli pole[i] a pole[i+1]. Jestliže je prvek pole[i] větší než prvek pole[i+1], prvky mezi sebou prohodím pomocí pomocné proměnné a. Vnitřní cyklus for (i=0; i<MAX-1; i++) zajistí, že se takto projdou všechny prvky v poli a vzájemně se porovnají. Výsledek porovnávání a záměny prvků v našem poli pole vidíme na obrázku.
4
5
2
3
6
Všimněte si, že provedením vnitřního cyklu Bubblesortu se dostalo největší číslo v poli na konec pole. Říká se, že tzv. „probublalo“. Další věcí, kterou si musíme uvědomit, je počet opakování vnitřního cyklu. Cyklus se musí pro naše pětiprvkové pole provést čtyřikrát, to znamená pro i=0 až po i=4, tedy dokud i<MAX-1.Kdybychom prováděli cyklus až do i<MAX budeme v posledním běhu cyklu porovnávat prvky pole[4] a pole[5]. Což je velice nebezpečné! Prvek pole[5] není prvkem vyblokované paměti pro pole pole a procujeme tedy mimo vyalokovanou paměť. Do pole se nám může dostat číslo, které tam nepatří. Aby se setřídilo celé pole a všechny prvky se dostaly na své místo, musíme použít vnější cyklus for (j=0; j<MAX-1; j++), který zopakuje vnitřní cyklus tolikrát, aby pole bylo setřízeno.
136
2
3
4
5
6
Počet opakování vnějšího cyklu je také dán podmínkou dokud i<MAX-1, protože na setřízení pětiprvkového pole nám postačí čtyři průchody pole. Popáté bychom procházeli již setřízené pole.
Shrnutí kapitoly Bubble Sort je třídící algoritmus, který: • třídí data metodou záměny • je nejjednodušší a nejpomalejší třídící algoritmus • používá vnitřní třídění - nepotřebuje žádnou „pomocnou paměť“ • je stabilní - prvkům se stejným klíčem nemění vzájemnou polohu • je přirozený - částečně seřazený seznam zpracuje rychleji než neseřazený Vnitřním cyklem Bubble Sortu získáme při vzestupném třídění největší prvek na konec pole – tzv. „probublá“. Vnější cyklus zajistí, aby „porbublaly“ i ostatní prvky pole a setřídily se vzestupně.
Kontrolní otázky a úkoly 1) Charakterizujte Bubble sort podle jeho vlastností. 2) Vysvětlete postup třídění algoritmu Bubble sort. 3) Proč ve vnitřním cyklu Bubble sort je podmínka dokud i<MAX-1? Proč je tato podmínka také u vnějšího cyklu?
137
35 Shrnutí učiva Obsah hodiny Pomocí testu si ověříte znalosti, které jste získali v tomto výukovém modulu.
Cíl hodiny Po této hodině budete schopni: ● ●
analyzovat, kterou část učiva jste zvládli a kterou část učiva musíte ještě prostudovat posoudit vlastní úspěšnost v kurzu
Test Odpovězte na následující otázky. V každé otázce je jedna nebo více správných odpovědí. 1. Debugger a) je sestavovací program b) vytvoří exe soubor c) umožňuje krokování programu d) vkládá hlavičková soubory 2. Mezi příkazy preprocesoru nepatří a) elif b) typedef c) ifndef d) define 3. V jazyce C makro na rozdíl od funkcí a) je pomalejší b) nepotřebuje alokaci paměti c) je náročnější na paměť d) je rychlejší
138
4. Podmíněný překlad a) může být řízen hodnotou makra b) může využít uživatel k provedení určité části programu c) určuje, která část kódu bude přeložena d) rozvíjí makra 5. Do hlavičkových souborů nezapisujeme a) definice funkcí b) definice vlastních datových typů c) makra s parametrem d) podmíněný překlad 6. Lokální proměnné se ukládají do a) haldy b) zásobníku c) datové oblasti d) kódové oblasti 7. Formální parametry nazýváme parametry a) ve volání funkce b) v definici funkce c) v cyklu for d) v cyklu while 8. Paměťová třída extern je určena a) jen pro lokální proměnné b) lokální i globální proměnné c) jen pro globální proměnné d) jen pro dynamické proměnné
139 9. Paměťová třída static je určena: a) jen pro lokální proměnné b) lokální i globální proměnné c) jen pro globální proměnné d) jen pro dynamické proměnné 10. Globální proměnné se ukládají do a) zásobníku b) haldy c) kódové oblasti d) datové oblasti 11. Linker a) překládá program do relativního kódu b) vkládá hlavičková soubory c) přiřadí relativním adresám adresy absolutní d) vytvoří obj soubor 12. Funkce na rozdíl od makra v jazyce C a) je náročnější na paměť b) je rychlejší c) je pomalejší d) neumožňuje rekurzi 13. Funkci pro výpočet rozdílu dvou celých čísel s hlavičkou: void Rozdil(int a, int b, int *roz) zavoláme pro proměnné int x,y,r; a) Rozdil (x, y, &r); b) Rozdil (x, y, r); c) r= Rozdil (x, y, &r); d) Rozdil (x, y, *r);
140 14. Pro pointer platí a) jeho hodnotou je jen adresa v paměti b) je vždy alokován v haldě c) nemůže ukazovat na statickou proměnnou d) využíváme jej při volání parametrů odkazem 15. Příkaz malloc a) alokuje statickou proměnnou v zásobníku b) alokuje dynamickou proměnnou v zásobníku c) alokuje statickou proměnnou v haldě d) alokuje dynamickou proměnnou v haldě 16. Mezi nejznámější třídící algoritmy nepatří: a) Soft sort b) Quick sort c) Insert sort d) Input sort 17. Pro pointer int *p vypíšeme adresu, kterou obsahuje a) printf(“%p“,*p); b) printf(“%p“,p); c) printf(“%p“,&p); d) printf(“%p“,&(*p));
18. Skutečné parametry nazýváme parametry a) v definici funkce b) v cyklu while c) ve volání funkce d) v cyklu for
141
Řešení 1.
c)
2.
b)
3.
b) d)
4.
a) c)
5.
a) c)
6.
b)
7.
b)
8.
c)
9.
b)
10.
d)
11.
c)
12.
a) c)
13.
a) c)
14.
a) d)
15.
d)
16.
a) d)
17.
b)
18.
c)
