Homepage » C cheatsheet

C – cheatsheet

Úvod: Překlad programu

• Soubor, do kterého ve vimu píšete příkazy, např. ukol.c, je zdrojový kód (zdroják) v jazyce C.
• Ze souboru uděláte program příkazem gcc ukol.c.
• To gcc, kterému jste zdroják předhodili, je překladač jazyka C.
• Z překladače vyleze spustitelný soubor (binárka), např. a.out, který spustíte ./a.out
• Je moudré překladači říct, aby vám co nejvíc pomáhal odhalovat chyby, to se dělá tzv. přepínači, písmenky, které napíšete za gcc na řádek. Doporučuji použít gcc -g -std=c99 -Wall -Wextra, pak překladač upozorňuje na všechny problémy, kterých si umí všimnout. Abyste tuhle nudli nemuseli vždycky znova opisovat, můžete si vytvořit třeba alias gccg, který vám to nahradí, přidáním řádku alias gccg='gcc -g -std=c99 -Wall -Wextra' do souboru ~/.bashrc a restartováním konzole.

Kostra programu

• Nejjednodušší program se skládá z několika málo částí:
  • Vkládání hlavičkových souborů – v té se zařizuje, aby program uměl používat příkazy, které budeme potřebovat, např. #include <stdio.h>
  • Začátek hlavní funkce – příkazy v této funkci se začnou vykonávat, když se program spustí: int main(){
  • Obsah hlavní funkce – sem píšete svoje příkazy, za každým musí být středník
  • Konec hlavní funkce – když program dojde sem, ukončí se: }
• Takže jednoduchý program vypadá třeba takto:

  #include <stdio.h>
  
  int main(){
  	printf("Ahoj svete\n");
  }
  

Procvičovací úkol

Opište výše uvedený program, přeložte ho za použití chytrých přepínačů a pak ho spusťte.

Proměnné

• Proměnná je pojmenovaný kousek paměti.
• Jejímu jménu se říká identifikátor, ten je skoro libovolný – začíná (malým) písmenem, obsahuje písmena anglické abecedy, čísla, podtržítka.
• Každá proměnná je nějakého datového typu, což určuje, jaký typ informace v ní může být obsažen.
• Základní datové typy:
  • int – celé číslo
  • float – desetinné číslo
  • char – znak (ale dá se používat jako číslo s malým rozsahem)
  • bool – pouze hodnoty true a false (tzv. boolean), a je potřeba na začátku zdrojáku includovat soubor stdbool.h
• Deklarace proměnné je vytvoření proměnné, které se musí udělat předtím, než se dá proměnná použít. Napíše se typ a identifikátor, např. int promenna; Pozor, zatím proměnná nemá přiřazenou žádnou hodnotu (neníinicializovaná) a tak by se něměla používat ve výrazech.
• Přiřazení je příkaz, kde je identifikátor, rovnítko a výraz, a mění hodnotu proměnné, např. promenna = 3 * 8; Aritmetika má různé svoje záludnosti, obzvláště pokud se kombinují proměnné typu int a float.
• Textový řetězec (string) je proměnná, která ukazuje na několik znaků uložených za sebou v paměti. Deklaruje se takto: char retezec[16]; Nyní proměnná retezec je string, do kterého se vejde 15tiznakový text, protože za textem ještě musí být znak '\0'. Jiná možnost je deklarovat char retezec[] = "Lokomotiva";, který vytvoří string s 11 znaky (opět je tam potřeba jeden navíc pro ukončovací znak).
• Abyste mohli používat funkce pro práci se stringy, musíte includovat soubor string.h
• Do řetězců se přiřazuje pomocí příkazu strcpy, např. strcpy(retezec, "Kobliha"); nebo strcpy(retezec, jinyretezec); (v druhém případě je však nutné, aby jinyretezec byl správně deklarovaný a inicializovaný řetězec).
• Připojovat řetězce za sebe se dá pomocí strcat, např. strcat(retezec,jinyretezec); připojí za obsah stringu retezec obsah stringu jinyretezec. U obou funkcí pro práci s řetězci si dávejte pozor, aby se vám do nich ten text vešel!
• Zjistit i změnit jeden znak v řetězci můžete pomocí hranatých závorek, ale pozor, počítá se od 0, takže s[1] je druhý znak řetězce.

Procvičovací úkol

Napište program, který nadeklaruje celé číslo s identifikátorem prvocislo s hodnotou 11, reálné číslo s identifikátorem ludolfovo s hodnotou 3.1415926, znak pismenko s hodnotou q, boolean pravda s hodnotou true a textový řetězec pisnicka s hodnotou Jsme silni jak silny je lano co k nebi nas po-ooou-ta. Takový program při spuštění nedává žádný výstup, za úspěch považujte, když se přeloží bez chyb.

Výstup a vstup

• Pro používání funkcí pro výstup a vstup se musí includovat soubor stdio.h
• Pro výpis na obrazovku se používá nejčastěji printf. Ten má jako parametry formátovací řetězec a proměnné či výrazy, které chcete vypsat.
• Ve formátovacím řetězci můžete mít libovolný text, dále nějaké speciální znaky uvozené \, které znamenají výpis něčeho, co se jinak píše blbě (např. \n znamená odřádkování), a jiné speciální znaky uvozené %, které odpovídají proměnným/výrazům v dalších parametrech, ve stejném pořadí.
• Znaky pro výrazy máme tyto:
  • %d – výraz typu int
  • %f – výraz typu float
  • %c – výraz typu char
  • %s – textový řetězec
• Příklad programu (obsahu hlavní funkce):

  int a;
  int b;
  a = 45;
  b = 23;
  char[] s = "Kobliha";
  printf("Ahoj svete,\nmam rad cislo %d, chutna mi %s a nemam rad cislo %d.\n", b, s, a);
  

  Tento program vypíše:

  Ahoj svete,
  mam rad cislo 23, chutna mi Kobliha a nemam rad cislo 45.
  

• Analogická funkce pro načítání vstupu je scanf, také má formátovací řetězec, další parametry jsou však ukazatele na proměnné, to pro vás znamená, že kromě případu řetězců před proměnné musíte napsat &.
• Tato funkce nechá uživatele zadat text a pak se snaží ho pochopit dle formátovacího řetězce. Obyčejný text ve formátovacím řetězci musí odpovídat textu z klávesnice, při načítání čísla si bere ze vstupu číslice, dokud jsou, při načítání řetězce do první mezery (či tabulátoru či odřádkování, prostě bílého znaku).
• Příklad programu (obsahu hlavní funkce):

  int a;
  int b;
  char s[32];
  scanf("%d%d%s", &a, &b, s);
  printf("Ahoj svete,\nmam rad cislo %d, chutna mi %s a nemam rad cislo %d.\n", b, s, a);
  

  Tento program při vstupu (po napsání tohoto na klávesnici)

  45 23 Kobliha
  

  vypíše

  Ahoj svete,
  mam rad cislo 23, chutna mi Kobliha a nemam rad cislo 45.
  

• Ještě přidám dvě užitečné funkce: gets() načte řádek vstupu (do enteru), puts() zase jednoduše vypisuje řetězec. Příklad vše osvětlí:

  char s[32];
  gets(s); // nacte radek, ktery uzivatel zada...
  puts(s); // ...a pak ho vypise.
  

Procvičovací úkoly

Minulý program s deklaracemi proměnných doplňte tak, aby takto vypsal identifikátory a hodnoty proměnných: prvocislo je 11, ludolfovo je 3.14159, pismenko je q a pisnicka je Jsme silni jak silny je lano co k nebi nas po-ooou-ta. Potom program doplňte tak, že hodnoty bude zadávat uživatel z klávesnice a tyto se pak vypíšou. Na boolean se vykašlete, ten se jednoduše vypisovat nedá.

Počítání věku na Biblickou stezku: Zobrazit

Jméno1 Příjmení1 RokNarození1
Jméno2 Příjmení2 RokNarození2
Jméno3 Příjmení3 RokNarození3

Jméno1, Jméno2 a Jméno3 maji dohromady vek SoučetJejichVěků.

Daniel Friedrich 1999
Michaela Mazna 1999
Tadeas Friedrich 1994

Daniel, Michaela a Tadeas maji dohromady vek 44.

Podmínky

• Často se chceme rozhodnout podle hodnot proměnných, co se v programu stane. K tomu slouží mocný příkaz if
• Jeho syntaxe (způsob, jakým se ve zdrojáku C píše) vypadá následovně:

  if (podmínka){
  	příkaz1
  	...
  }else{
  	příkaz2
  	...
  }
  

• Pokud podmínka platí, provede se příkaz1 a všechny další v témže bloku. Pokud neplatí, provede se příkaz2 a ty v jeho bloku. Blok je několik příkazů uzavřených mezi složené závorky.
• Podmínka může vypadat všelijak, nejjednodušší jsou ty, kde se porovnávají čísla. Máme-li číselnou proměnnou a, může být podmínka třeba a < 3, což přirozeně znamená "a je menší, než 3". Jiné porovnávací značky jsou >, <= (menší či rovno), >=, == (rovná se), != (nerovná se).
• Jednoduchý příklad:

  int vek;
  scanf("%d", &vek);
  if (vek > 20){
  	printf("Jsi starej\n");
  }else{
  	printf("Jsi malej\n");
  }
  

• Pokud by v bloku byl jen jeden příkaz, nemusíte blok použít (ale můžete, třeba pro přehlednost)

  if (vek > 20)
  	printf("Jsi starej\n");
  else
  	printf("Jsi malej\n");
  

  funguje naprosto stejně,

  if (vek > 20) printf("Jsi starej\n"); else printf("Jsi malej\n");
  

  taky, jde skutečně jen o vkus a přehlednost.
• Podobně se nemusí použít else a jeho blok, pokud to nepotřebujete.

  if (vek > 20) printf("Jsi starej\n");
  

• Podmínky se dají spojovat pomocí tzv. logických operátorů. Pokud musí platit obě současně, použije se && (logické and), pokud alespoň jedna, použije se || (logické or). Pokud naopak podmínka nesmí platit, použijte před ní ! (logickou negaci). Každá podmínka musí mít vlastní závorku – je to dobré i pro přehlednost.

  int vek;
  int pocetvlasu;
  scanf("%d%d", &vek, &pocetvlasu);
  if ((!(vek <= 20)) && (pocetvlasu == 0)){
  	printf("Jsi starej plesoun\n");
  }else{
  	printf("Starej plesoun zjevne nejsi\n");
  }
  

  Logickými operátory a uzávorkováním můžete združit mnoho podmínek k sobě všelikými způsoby.
• Podmínky se dají i sdružovat k sobě tím, že za else dáte další if:

  int vek;
  int pocetvlasu;
  scanf("%d%d", &vek, &pocetvlasu);
  if ((vek > 20) && (pocetvlasu == 0)){
  	printf("Jsi starej plesoun\n");
  }else if ((vek > 20) || (pocetvlasu == 0)){
  	printf("Jsi bud starej vlasac, nebo malej plesoun\n");
  }else{
  	printf("Jsi mladik s bujnou kstici\n");
  }
  

• Pro podmínky obsahující řetězce se hodí funkce strlen a strcmp. Například podmínka (strlen(s) == 5) zjistí, zda je řetězec s dlouhý přesně 5, (!strcmp(s, "Blaf")) zjistí, zda je v s napsáno "Blaf" (na ! u strcmp nezapomínejte).

Procvičovací úkol

Upravte program pro Biblickou stezku, aby oznámil, zda hlídka smí soupeřit.

Napište program, který zjistí, zda se dá ze tří zadaných čísel sestrojit trojúhelník s těmito délkami stran a pokud ano, tak zda je pravoúhlý.

Intermezzo: přehlednost kódu

• Při programování je naprosto běžné, že vznikají chyby. Takzvané "pravidlo 90%" říká, že prvních 90% kódu trvá napsat 90% času a zbylých 10% taky trvá 90% času. Tím se myslí, že vychytat chyby v programu trvá přibližně stejně dlouho, jako všechno předchozí psaní.
• Aby bylo psaní programu a vychytávání chyb co nejrychlejší, je nutné udržovat kód přehledný. K tomu slouží několik dobrých návyků. Z těchto návyků se pak stávají konvence a kdo je při psaní nepoužívá je považován za amatéra.
• Komentáře. C vám dovoluje napsat kamkoli do zdrojáku řádek, kterého si nebude překladač všímat, stačí na jeho začátek dát //. Takto si můžete komentovat všechna zajímavá místa v programu. Komentář by měl popisovat, k čemu příkaz/blok je, ne tupě popisovat, co se děje. Například pro

  if (vek > 20){
  

  je komentář

  // je promenna vek vic nez 20?
  

  zbytečný, zato

  // je uzivatel stary?
  

  může pomoci. U složitého příkazu dobrý komentář ušetří mnoho času.
• Členění. Na jeden řádek se píše víc příkazů pouze, pokud spolu úzce souvisí, jako např.

  int a; int b;
  

  ale ne

  int a; printf("%d", b);
  

  Také můžete za skupinu logicky souvisejících příkazů dát jedno- či víceřádkovou mezeru.
• Indentace. Je vhodné každé zanoření bloku dát opticky najevo odsazením, tj. několika mezerami či tabulátorem na začátku řádku.

  int main(){
  	int vek;
  	int pocetvlasu;
  	scanf("%d%d", &vek, &pocetvlasu);
  	if (vek > 20){
  		printf("Jsi starej");
  		if (pocetvlasu == 0){
  			printf(" plesoun\n");
  		}else{
  			printf(" vlasac\n");
  		}
  	}else{
  		printf("Starej zjevne nejsi\n");
  	}
  }
  

  O stylech indentace se více můžete dočíst tady. Můj oblíbený je shodou okolností ten, který se používá v jádře Linuxu. =:)

Náhodná čísla

• Pro různé hry a pokusy se hodí umět si pořídit náhodné číslo. Na to má C taky své funkce, definované v knihovně stdlib, takže bude potřeba includovat soubor stdlib.h.
• Funkce rand() vám potom dá náhodné integerové hodnoty. Problém je, že při každém spuštění programu stejnou posloupnost. Tomu se dá předejít tím, že náhodnému generátoru nastavíme tzv. semínko, tj. nějaké číslo, které určí, jak bude posloupnost vypadat. Jenže kde semínko vzít, když má být při každém spuštění programu jiné? Náhodně vygenerovat ho nemůžeme =:)
• Ale můžeme použít aktuální čas. Funkce time(NULL), definovaná v time.h, vám řekne, kolik sekund uplynulo od 1. ledna 1970.
• Semínko generátoru se nastavuje srand(semínko).
• Program generující pokaždé jiná náhodná čísla vypadá třeba takto:

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  int main(){
  	srand(time(NULL));
  	int a = rand();
  	printf("Nahodne cislo! --> %d\n", a);
  }
  

• Obyčejně chceme číslo v nějakém rozumném rozsahu, třeba od 0 do 99. K tomu si můžeme pomoct tak, že si řekneme o zbytek po dělení 100: int a = rand() % 100;.

Procvičovací úkol

Napište program, který si vymyslí první číslo, operand (+,-,*,/) a druhé číslo a vypíše příklad na obrazovku. Uživatel napíše výsledek. Program mu odpoví spravne nebo spatne a ukončí se. Zkuste pak taky zjistit a vypsat, kolik sekund uživatel příklad počítal. Čísla generujte v rozsahu od 0 do 20. Dejte ale pozor, aby se nedělilo nulou.

Cyklus while

• Někdy chceme, aby se kus programu několikrát zopakoval. K tomu slouží takzvané cykly. Cyklus while má následující syntax:

  while (podmínka){
  	příkaz
  	...
  }
  

• Cyklus funguje tak, že se zkontroluje, zda platí podmínka, a pokud ano, provedou se příkazy uvnitř. Potom se podmínka zase zkontroluje a znovu totéž. Aby se cyklus opustil, musí se uvnitř něj platnost podmínky změnit. Pokud podmínka nepřestane platit, dojde k zacyklení.
• Příklad (výpis čísel od 0 do 99):

  int a = 0;
  while (a < 100){
  	printf("%d\n", a);
  	a++;
  }
  printf("Cyklus skoncil, a uz je %d\n", a);
  

• Můžeme taky chtít, aby se cyklus vždycky provedl alespoň jednou. Potom se hodí mít podmínku na konci, potom cyklus začíná příkazem do:

  do{
  	příkaz
  	...
  } while(podmínka);
  

• Příklad:

  char s[16];
  printf("Budeme si povidat, dokud nenapises prazdny radek.\n");
  do{
  	gets(s);
  	printf("%s, rikas? To je tuze zajimava myslenka.\n", s);
  } while(strlen(s) != 0);
  printf("Tak cau.\n");
  

Procvičovací úkol

Napište program, který si vymyslí číslo mezi 0 a 99 a uživatel hádá. Program mu vždy odpoví vic nebo min nebo, když se uživatel trefí, na kolikátý pokus to uhodl a ukončí se.

Motivační úkoly

Napište program, který vypíše 1000 hvězdiček.

Přepište ho na program, který vypíše čísla od 0 do 999.

Přepište ho na program, který vypíše druhé mocniny čísel od 0 do 999.

Cyklus for

• Výše uvedené programy vypadají asi takto:

  int i=0; // inicializace řídící proměnné
  while (i<1000){ // podmínka na ř. p. k ukončení cyklu
  	... // příkaz(y) v cyklu
  	i++; // změna řídící proměnné
  }
  

• Často chceme mnohokrát zopakovat nějakou akci a víme předem kolikrát, nebo chceme na něco použít čísla třeba od 0 do 999.
• To se dá zvládnout pomocí cyklu while, ale existuje ještě jednodušší prostředek: cyklus for.
• Ten vypadá takto a plní přesně stejnou funkci, jako výše zmíněný while cyklus:

  for (int i=0; i<1000; i++){
  	...
  }
  

• Obecně je tedy syntaxe takováto:

  for (inicializace; podmínka; změna){
  	...
  }
  

• Cyklus for je tzv. syntaktický cukr, tedy konstrukce, bez které byste se obešli, ale může vám usnadnit práci.
• Obvykle se v C indexuje od 0, tedy pro provedení cyklu 10× je běžnější (int i=0; i<10; i++) než (int i=1; i<=10; i++).

Procvičovací úkoly na cykly while a for

Zadá se číslo a program vypíše tolik hvězdiček.

Zadá se číslo a program vypíše prvních jeho 10 násobků.

Zadá se číslo a program vypíše všechny jeho násobky, které jsou menší, než 100.

Zadávají se čísla, dokud se nezadá 0. Pak program vypíše jejich součet.

Zadávají se čísla, dokud se nezadá 0. Pak program vypíše, které bylo největší.

Zadá se textový řetězec, program ho vypíše pozpátku.

Zadá se číslo a program vypíše správně velký trojúhelník z hvězdiček. Příklad:

5
*****
****
***
**
*

Zadá se číslo a program vypíše kruh z písmen (třeba X) o daném poloměru. Příklad:

4
    X    
  XXXXX  
 XXXXXXX 
 XXXXXXX 
XXXXXXXXX
 XXXXXXX 
 XXXXXXX 
  XXXXX  
    X    

Zadá se číslo a program ho vypíše ve dvojkové soustavě. (Pozpátku to je jednodušší.)

Zadá se číslo ve dvojkové soustavě a program ho vypíše v desítkové. (To vstupní si raději načtěte jako string.)

Zadá se číslo a program vypíše všechna prvočísla mezi 0 a tímto číslem.

Pole

• Když si v programu potřebujeme zapamatovat spoustu hodnot stejného typu, potřebujeme nějakou datovou strukturu. Nejjednodušší z nich je pole.
• Pole je skupina několika proměnných stejného typu za sebou. Deklaruje se jako proměnná s velikostí v hranatých závorkách, např. int a[16]; vytvoří pole a 16ti integerů.
• K jednotlivým prvkům pole se přistupuje tak, že se napíše k indentifikátoru pole index v hranatých závorkách, např. p[3]. Indexuje se od 0, to znamená, že prvky pole mají indexy od 0 do velikost-1. V hranaté závorce samozřejmě nemusí být přímo číslo, klidně tam může být zase nějaká integerová proměnná nebo výraz.
• Všimněte si, že textový řetězec je pole znaků takové, že jsou tam za sebou naskládaná písmena řetězce a jako poslední je ukončovací '\0'.

Procvičovací úkoly na pole

Zadá se číslo, program vytvoří tak velké pole, naplní ho náhodnými čísly mezi 0 a 100 a pak hodnoty prvků pole vypíše.

Předchozí program se rozšíří tak, že uživatel zadá další číslo a program mu řekne, zda a na jakém indexu je to číslo v poli.

Zadá se číslo a program vytvoří tak velké pole, naplní ho nějakou rostoucí posloupností čísel (větší indexy mají větší hodnoty) a pak hodnoty prvků pole vypíše.

Předchozí program se zase rozšíří tak, že uživatel zadá další číslo a program mu řekne, zda a na jakém indexu je to číslo v poli, a nějak chytře, aby nezkoumal zbytečně moc prvků.

Vezme se program, co vytváří pole naplněné náhodnými čísly a doplní se tak, že je seřadí podle velikosti. Např.:

6
V poli jsou cisla:
52 12 96 3 12 77
Setridene pole:
3 12 12 52 77 96

Složitost algoritmů (ohleduplný úvod)

Motivace

Měli jsme dva programy na vyhledání prvku v poli. Jeden prostě projde celé pole, druhý funguje jen na rostoucích polích, zato se zdá, že rychleji. Je to skutečně tak?

Povídání o složitosti

• Algoritmus je správný postup na řešení nějakého úkolu. Pro nás pojem algoritmus a program splývá.
• Máme-li na nějaký úkol dva algoritmy, chceme vybrat ten lepší. To většinou znamená vybrat ten rychlejší. Někdy ale máme třeba omezeně paměti a pak chceme ten, který je úspornější na paměť.
• Proto se zavedl pojem složitost algoritmu. Počítá se jednak časová a jednak paměťová (prostorová). Zaměříme se na tu časovou, ta nás zajímá většinou a ony ty základní věci platí u obou stejně.
• První důležitá věc: algoritmus rozhodně netrvá vždycky stejně dlouho, ale zpravidla dost záleží na vstupu. Najít hloupým algoritmem prvek v desetiprvkovém poli bude nejspíš rychlejší, než najít geniálním algoritmem prvek v poli velkém milion prvků. Proto se složitost udává jako nějaká funkce velikosti vstupu.
• Na první pohled bychom od té funkce chtěli dostat, kolik sekund bude program trvat. To však nejde z mnoha důvodů:
  • Nezáleží pouze na velikosti vstupních dat, ale také na tom, jaká jsou. Když bude hledaný prvek pole zrovna první, najde ho program hned, když bude ke konci, bude to trvat dlouho.
  • Záleží, na jak rychlém počítači se algoritmus spustí.
  • Záleží, jak dlouho počítač který příkaz provádí.
• První problém se trochu vyřešit dá tím, že se zavede složitost v průměrném případě a složitost v nejhorším případě (nejlepší případ o algoritmu moc nevypovídá). U jednodušších algoritmů průměrný a nejhorší případ je stejný (ač to zní podezřele, za chvíli zjistíme proč), proto často nespecifikujeme, o kterou složitost se jedná.
• Ostatní problémy se obecně vyřešit nedají. Můžu si sice zjistit, jak dlouho který příkaz počítači trvá, ale ani to už není vždy stejně kvůli všelijaké paralelizaci a ukládání mezivýsledků (cacheování). Navíc algoritmus zpravidla nešijete na míru konkrétnímu počítači a museli byste tuto náročnou analýzu dělat vždycky znova.
• Místo toho teoretici zavedli pojem asymptotická složitost. Zní to ošklivě, ale je to vcelku přátelská věc =:)
• Jde o to, že si algoritmus rozpitváme až na tzv. atomické operace, tedy takové, jejichž doba vyhodnocení je omezená nějakou konstantou, tzn. trvá krátce bez ohledu na to, jak dlouhý je vstup. Všechny takové, jako inicializace proměnných (kromě polí), aritmetika integerů a floatů či vyhodnocení podmínek jsou atomické.
• Potom spočítáme, kolikrát se každá ta atomická operace provede, tedy kolikrát se protočí v nějakém cyklu. To už bude nějaká funkce závislá na velikosti vstupu. Potom sečteme tyhle funkce od všech těch atomických operací a vyjde nám jediná funkce velikosti vstupu.
• A k čemu tohle je, když nám to neřekne nijak přesný odhad na čas? Jedna atomická operace přece může trvat mikrosekundu a druhá 10 milisekund. Potom může vyjít větší složitost algoritmu, který je ve skutečnosti rychlejší, než ten, kterému vyšla menší.
• Skutečně se může stát a běžně se u algoritmů stává, že nějaký jakoby hloupější je na malých vstupech rychlejší. Nás ale ani tak nezajímá, jestli algoritmus se vstupem 10 poběží 1ms nebo 10ms, mnohem víc chceme vědět, jestli se vstupem miliarda poběží hodinu nebo týden. Chceme tedy vědět, jak se ta složitost (rozumějte ta funkce) chová pro velké vstupy. K tomu se hodí vědět následující věci z matematiky.
• Když si vezmete dvě nějaké běžné funkce, třeba x³ a 1000x², zjistíte, že i když pro prvních pár hodnot je ta druhá větší, v nějaké chvíli ji ta první přeroste a pak už bude vždycky větší. Ta první je asymptoticky větší. U těchto funkcí typu koef*x^něco je vždycky as. největší ta, která má největší exponent (to něco), bez ohledu na koeficient. A to i tehdy, když je k nim přičtené libovolné množství x^{něco_menšího} .
• Takže když my získáme tu složitost f(n), tak navíc ještě zapomeneme všechny členy, které jsou asymptoticky nedůležité (as. menší než ten největší) a ještě tomu největšímu sebereme koeficient. Např. z f(n)=22n³+123n²+60n+1820 uděláme obyčejné n³.
• Když se kouknete, co nakonec vzniklo, uvidíte, že při tom prvotním počítání můžete všechny atomické operace, které jsou u sebe, brát najednou a navíc stačí brát jen ty, které se pro veliké vstupy provedou nejvíckrát, tj. odpovídají tomu as. největšímu členu.
• Takto už se složitosti algoritmů porovnávají snadno. A když vyjdou asymptoticky stejně? To už je holt potřeba vyzkoušet, který běhá rychleji (a to může záviset na použitém počítači), nebo, pokud jsou ty algoritmy podobné, odhadnout, který je asi rychlejší. Ale to už je nad rámec našeho počítání složitosti.

Úkoly na počítání složitosti

Spočítejte složitost hledání prvku v neuspořádaném poli. (Fáze vytváření pole není součástí algoritmu.)

Spočítejte složitost hledání prvku v uspořádaném poli. (Fáze vytváření pole není součástí algoritmu.)

Spočítejte složitost třídění pole. Najděte rychlejší algoritmus. =:)

Intermezzo: Přesměrování vstupu v shellu

Motivace

Dejme tomu, že dostanete za úkol seřadit 100 jmen, zadávaných z klávesnice, podle abecedy. Při testování takového programu toho napíšete víc při zadávání vstupu, než při psaní kódu.

Shell a standardní vstup/výstup

• Shell je program, jehož součástí je příkazová řádka. Když na ni něco napíšete, shell si to přečte, pokusí se to pochopit a když se mu to podaří, tak i provést.
• Spuštěný program má standardní vstup a standardní výstup, pro nás to zatím vždy byly klávesnice a obrazovka. My ale můžeme shellu velmi snadno říct, že má vstup brát odjinud – ze souboru, a stejně tak že výstup může psát jinam – do souboru.
• Syntax je takto jednoduchá: ./a.out < vstup.txt > vystup.txt
• Pokud soubor vstup.txt je v adresáři, ze kterého program spouštíte a jsou v něm data, kterým rozumí, tak pokud v témže adresáři máte právo vytvořit soubor, bude výstup v souboru vystup.txt. Pokud už výstupní soubor existuje a vy máte právo do něj zapisovat, jeho obsah se přepíše.
• Aby byl život ještě příjemnější, můžete využít >> místo >, v takovém případě se soubor nepřepíše, ale nová data se připojí na konec.
• Vyhněte se tomu, že vstupní a výstupní soubor jsou tentýž, není definováno, co by s tím shell nadělal, ale nejspíš nic pěkného.
• Vstup nemusí být ani klávesnice, ani soubor, může to být výstup jiného programu. Tak můžete zřetězit funkce dvou (či více) programů. To se dělá pomocí pajpy (svislítko, roura, pipe), to je |. Takže pokud program a.out řadí jména podle abecedy a b.out odstraňuje diakritiku, tak příkaz ./b.out < vstup.txt | ./a.out > vystup.txt vezme jména ze vstupního souboru, odstraní z nich diakritiku, seřadí je podle abecedy a nasype do výstupního souboru.
• Když už je to takové nakousané, tak to dojíme, ne: můžete mixovat standardní unixové programy se svými či cizími a z pajp jim udělat hezkou pajplajnu (potrubí, kolona, pipeline). Ta je koneckonců jedním ze základních kamenů shellového skriptování. Např. sort -n -t: -k3 < /etc/passwd | tail -n 10 | cut -d: -f1 vypíše login 10ti uživatelů s nejvyššími User ID.

Procvičovací úkol

V souboru prace.txt plném pracujícího lidu je na každém řádku

Jméno Příjmení Datum ČasPříchodu ČasOdchodu HodinováMzda

Ferdinand Kobliha 29.2. 11:31 23:47 65

Bloky

• O blocích už jste si četli u podmínek, jsou to příkazy spojené dohromady tím, že jsou uzavřeny mezi složené závorky {}.
• Zatím jsme bloky potřebovali jen jako součást nějaké další konstrukce, ale dají se umístit kamkoli. To je ale potřeba jen strašně málo kdy.
• Blok říká obklopující konstrukci, že má obsažené příkazy brát jako jeden. Větev ifu nebo tělo while cyklu tedy jakoby obsahují jen jeden příkaz, ale pomocí bloku jich tam vpravíte libovolně mnoho.
• Ještě má blok jednu důležitou vlastnost: proměnné, které v něm deklarujete, přestanou existovat po jeho opuštění (odeberou se ze zásobníku). Přirozeně však existují uvnitř všech podbloků.

  {
  	int a;
  	{
  		a = 5;
  	}
  	// zde je a == 5
  }
  // zde a nikdo nezna
  a = 3; // zpusobi chybu
  

• Taková trochu divočárna je překrývání proměnných: když znovu nadeklarujete proměnnou, přidá se normálně na zásobník a pod jejím identifikátorem používáte nové místo v paměti. Až její blok skončí, přestane existovat a pod tím identifikátorem najdete svoji starou proměnnou.

  {
  	int a = 3;
  	{
  		// a == 3
  		int a = 5;
  		// a == 5
  	}
  	// a == 3
  }
  // a neexistue
  

Pokračování časem. Určitě by měly přibýt ještě následující kapitoly:

Funkce

Motivace

Jak by vypadal program, který by třídil dvě pole? Pět polí? Dvacet polí?

Opakování kódu

• Základním smyslem funkcí je získat možnost opakovat provádění částí kódu příjemnějším způsobem, než opsat ho několikrát za sebe. To totiž kromě nepřehlednosti způsobuje nutnost při každé úpravě měnit každou kopii, což zdržuje a dává příležitost k chybě.
• Takovému opakovanému kusu se v C říká funkce.
• Podobně jako matematické funkce, i Cčková funkce může mít nějaké parametry a výsledek. Dají se tak matematické funkce psát, ale použití funkcí v C je mnohem širší.
• Funkce má název (identifikátor), parametry, návratový typ a tělo.
  • Názvem je funkce označována a volána v kódu.
  • Parametry jsou nějaké hodnoty proměnných, které jsou funkci předány.
  • Návratový typ je datový typ návratové hodnoty – výsledku funkce.
  • Tělo je samotný kód ve funkci prováděný.
• Příklad programu s funkcí:

  #include <stdio.h>
  
  int mocnina(int zaklad, int exponent){
  	for (int i = 0; i < exponent; i++){
  		vysledek *= zaklad;
  	}
  	return vysledek;
  }
  
  int main(){
  	int a = 3;
  	int b = 4;
  	int c = 5;
  	
  	if (mocnina(a, 2) + mocnina(b, 2) == mocnina(c, 2))
  		printf("Trojuhelnik je pravouhly\n");
  }
  

• Na příkladu je vidět, že už funkci známe, main je funkce se vším všudy.
• Návratový typ je před názvem funkce, po něm následuje v závorce seznam parametrů oddělených čárkou. Pak následuje tělo, blok příkazů.
• Proměnné deklarované v těle funkce neexistují mimo ni, jsou lokální – tak, jak byste od slušného bloku čekali. Z funkce mocnina neuvidíte proměnné mainu a obráceně.
• Funkce se volá prostě tak, že se napíše její název a za ni do závorek parametry.
• Toto pak zároveň můžete používat jako výsledek funkce (pokud nějaký má). Můžete ho přiřazovat do proměnných či používat v matematických a jiných výrazech.
• Při předání parametrů se zkopírují předávané hodnoty do lokálních hodnot ve funkci. Předáváná hodnota se funkcí nezmění.
• Ke vracení výsledku funkce slouží klíčové slovo return, které z funkce zároveň vyskočí. Funkce by vždy měla něco vrátit.
• Pokud nepotřebujete návratovou hodnotu, použijte návratový typ void. Pak naopak nic vracet nesmí. Můžete ji ukončit returnem bez parametrů.
• Když napíšete funkci až za místo, kde je volána (pod main), překladač vás bude přinejmenším varovat, v některých případech překlad selže. gcc totiž při překladu čte kód odshora dolů a nelíbí se mu, když se volá funkce, o které dosud neslyšelo.
• Používání řetězců a polí jako parametrů a návratových typů zmíním u ukazatelů.

Procvičovací úkoly

Napište funkci, která vypíše objem válce, parametry budou poloměr podstavy a výška. Můžou to být i necelá čísla.

Teď ať ta funkce objem vrátí a vypište ho až v pokračování hlavní funkce.

Paměťový zásobník

• V této krátké kapitole se dozvíte podrobnosti o způsobu ukládání proměnných do paměti.
• Mějme nějaký obyčejný program.

  float krat_pi(float b){
  	// 3. zastávka
  	float pi = 3.1; //musi stacit, ne
  	// 4. zastávka
  	b = b * pi;
  	// 5. zastávka
  	return b;
  }
  
  int main(){
  	// 1. zastávka
  	float a = 2;
  	float b;
  	// 2. zastávka
  	b = krat_pi(a); 
  	// 6. zastávka
  }
  

  Podíváme se, jak to vypadá v paměti (na zásobníku) v jednotlivých krocích.
• 1. zastávka:

  
  []
  

  Na počátku byla paměť pustá a prázdná, jen nad zásobníkem se vznášela alokace.
• 2. zastávka:

   a   b
  [2  |?  ]
  

  Pak se alokovaly první proměnné. a byla přiřazena hodnota 2, b má zatím nedefinovanou hodnotu.
• 3. zastávka:

   a   b  |b
  [2  |?  |2  ]
  

  Pak jsme funkci předali hodnotu proměnné a a vznikla nám na zásobníku další proměnná b. Je to úplně jiné b než posledně a k lokálním proměnným mainu se teď nedostaneme.
• 4. zastávka:

   a   b  |b   pi
  [2  |?  |2  |3.1]
  

  Alokace proměnné pi, nic překvapivého.
• 5. zastávka:

   a   b  |b   pi
  [2  |?  |6.2|3.1]
  

  Změna hodnoty proměnné b, taktéž nic překvapivého.
• 6. zastávka:

   a   b
  [2  |6.2]
  

  V okamžiku returnu se vracená hodnota předá zpět volající funkci, v tomto případě do proměnné b a dealokují se lokální proměnné pi a b. Opuštěním mainu pak zanikají i zdejší lokální proměnné a program končí.
• Alokované proměnné vždycky přibývají na konec zásobníku a dealokují se z konce (to ostatně dělá zásobník zásobníkem).
• V dané funkci jsou vidět pouze její lokální proměnné. Proto ničemu nevadí, když se shodují jména proměnných napříč funkcemi.

Ukazatele

• Ukazatel (pointer) je datový typ, který obsahuje adresu do paměti. Většinou odkazuje na nějakou další proměnnou.
• Deklaruje se jako cílový datový typ s hvězdičkou, např. int* a.
• Když už máte nějakou proměnnou a chcete na ni získat ukazatel, použijte &. Říká se tomu referencování proměnné.
• Když naopak chcete hodotu v paměti, kam ukazatel ukazuje, použijte *. Říká se tomu – kupodivu – dereferencování ukazatele.
• Hvězdičky v deklaraci ukazatele a v operaci dereferencování znamenají jiné věci, nenechte se tím zmást. (Navíc násobení je taky hvězdička.)
• Kousek kódu

  int a = 5;
  int* p = &a;
  int b = *p;
  printf("%d", b); // 5
  

  nahraje do ukazatele p adresu proměnné a, pak hodnotu odkazovanou ukazatelem p nahraje do proměnné b a vypíše.
• Jednou z nejčastějších chyb s ukazateli je, když zapomenete (de)referencovat. Zkuste si třeba vypsat ukazatel místo čísla. Překladač vás nejspíš upozorní, ale nezvykněte si na to spoléhat.
• U funkcí jste se dozvěděli, že předávaná hodnota se nedá změnit. To je pravda. Ale pomocí ukazatelů můžeme přecejen docílit toho, aby se naše proměnná ve volané funkci změnila:

  #include <stdio.h>
  
  void plusJedna(int* p_a){
  	int a = *p_a;
  	a++;
  	*p_a = a;
  }
  
  int main(){
  	int a = 3;
  	plusJedna(&a);
  	printf("%d", a);
  }
  

  Proměnnou nepředáme funkci přímo, ale referencujeme ji a předáme ukazatel. Ten ve funkci dereferencujeme a děláme si s proměnnou, co chceme. Nakonec výslednou hodnotu uložíme na místo v paměti odkazované ukazatelem.
• V těle funkce by mohlo být taky jenom *p_a = *p_a + 1;.
• Teď už rozumíte, proč jsou printf vypisované proměnné předávány normálně, zatímco scanf, který hodnoty mění, dostává ukazatele na proměnné.
• O těchto způsobech zadávání parametrů funkce se mluví jako o předávání hodnotou a předávání odkazem.
• Řetězce jsou sami o sobě určeny ukazatelem, proto jsou vlastně vždy předávány odkazem. Řetězec se funkci předává vždy jako char *.

  #include <stdio.h>
  #include <string.h>
  
  void pridejKoblihu(char* s){
  	strcat(s, " a kobliha");
  }
  
  int main(){
  	char s[20];
  	strcpy(s, "Mrkev");
  	pridejKoblihu(s);
  	printf("%s", s); // Mrkev a kobliha
  }
  

• Pole mají jak známo s řetězci mnoho společného, takže ano, předávají se podobně, např. int * a taky se dají uvnitř funkce bez problému modifikovat.

  #include <stdio.h>
  
  void vynulujPosledni(int* pole, int velikost){
  	pole[velikost-1] = 0;
  }
  
  int main(){
  	int a[3];
  	a[0] = 5;
  	a[1] = 7;
  	a[2] = 9;
  	vynulujPosledni(a, 3);
  	printf("%d %d %d", a[0], a[1], a[2]); // 5 7 0
  }
  

• Kdybyste museli předávat funkci celý obsah řetězce nebo pole, kopírovaly by se v paměti třeba desítky megabajtů. Předání ukazatele je obyčejně otázka čtyř nebo osmi bajtů (záleží, jestli máte 32bitový nebo 64bitový systém). A to je jedna z největších výhod pointerů.
• Vracet pole nebo řetězec jako výsledek funkce zatím nedoporučuju. Potýká se to s problémy alokace paměti. Proměnné deklarované uvnitř funkce zanikají po jejím opuštění, proto kdybyste v ní vytvořili pole a vrátili ukazatel, tak až ho pak použijete, způsobíte si neoprávněný přístup do paměti. V takovém případě se musí používat jiný způsob alokace paměti a o tom třeba jindy.

Procvičovací úkol

Napište funkci, která dostane dvě čísla a prohodí jejich hodnoty.

Napište funkci, která dostane pole a jeho velikost a setřídí ho.

Rekurze

• Může funkce zavolat sama sebe? Jo, může. A to je rekurze.
• Příklad:

  #include <stdio.h>
  
  int faktorial(int f){
  	if (f <= 0)
  		return 1;
  	else
  		return f * faktorial(f - 1);
  }
  
  int main(){
  	printf("%d", faktorial(5)); // 120
  }
  

• Nejdůležitější je uvědomit si, že v tom není žádný háček. Každý vstup do funkce znamená vytvoření nové sady lokálních proměnných (v tomto případě pouze f) a je úplně jedno, že funkce se jmenuje stejně.
• V okamžiku největšího zanoření – když je f rovno 0 – vypadá zásobník takto:

   f  |f  |f  |f  |f  |f  
  [5  |4  |3  |2  |1  |0  ]
  

  Pak se z rekurze zase vynořuje, předává se součin výsledků a nakonec vypadne 120.
• Běžná chyba při používání rekurze je, že se nepodchytí ta koncová podmínka (if (f <= 0)) a rekurze se zacyklí. Rozdíl oproti nezvládnutému while cyklu je v tom, že tady vám roste zásobník a po čase dojde paměť.

• Význam rekurze je v určité změně pohledu na problém. Funkce faktoriál je napsaná tímto způsobem:
  „Kolik je faktoriál 5 nevím, ale když mi řeknete, kolik je faktoriál 4, tak už to vědět budu.”

  V dalším kroku:
  „Kolik je faktoriál 4 nevím, ale když mi řeknete, kolik je faktoriál 3, tak už to vědět budu.”

  A tak dál, až na konec:
  „Kolik je faktoriál 0? No jedna, samozřejmě.”

  Pak zase zpátky:
  „Faktoriál 0 je 1? Potom faktoriál 1 je 1*1, takže 1.”

  A stejně tak:
  „Faktoriál 1 je 1? Potom faktoriál 2 je 2*1, takže 2.”

  A nakonec:
  „Faktoriál 4 je 24? Potom faktoriál 5 je 5*24, takže 120.”

• Takže pomocí rekurze jsme schopni řešit problémy, které je jednoduché převést na jeden či více podobných podproblémů.

Procvičovací úkol

Spočítejte složitost výpočtu faktoriálu rekurzí a porovnejte to se složitostí výpočtu faktoriálu cyklem for.

Napište za použití rekurze funkci, která počítá Fibonacciho posloupnost. Ta je definována takto:
fi₁ = 1; fi₂ = 1; pro n > 2 fi_n = fi_n-1 + fi_n-2
Pak tutéž funkci napište bez rekurze.
Pak porovnejte složitosti těchto funkcí. Zjistíte, že zatímco u faktoriálu to vyjde nastejno, v tomto případě rekurze zoufale zaostává, že je v podstatě nepoužitelná. Jak si s tím poradit, o tom zas jindy.

Globální proměnné

• Když potřebujete ve více funkcích pracovat s nějakou proměnnou, musíte si ji předávat parametrem. Kde ji chcete měnit, tam dokonce pomocí ukazatele.
• Existují ale také globální proměnné, které jsou vidět všude. Ty se deklarují mimo jakoukoli funkci.
• Zase v tom není moc žádný háček. Proměnné se alokují na začátku zásobníku a zůstanou tam až do konce programu.

  #include <stdio.h>
  
  int c = 1;
  
  void prase(int b){
  	c = b;
  }
  
  int main(){
  	int a = 5;
  	prase(3);
  	a = c;
  }
  

  Takový program má při vstupu do funkce prase na zásobníku:

   c  |a  |b
  [1  |5  |3  ]
  

  S tím, že proměnná c je vidět odkudkoli.
• I globální proměnná se dá zakrýt lokální proměnnou stejného jména. V jejím bloku se pak ke globální proměnné nedostanete.

Struktury

Zatímco rekurze z hlediska jazyka nebyla nic objevného, zato měla nedozírné důsledky z hlediska uvažování o problémech, se strukturami je to přesně naopak. Problém vám nevyřeší, obejdete se bez nich, ale je to tuze praktická věc.

• Struktury umožňují seskupovat více proměnných. Třeba chcete popisovat v programu zvířata, která mají rychlost, barvu a počet nohou, nebo kola, která mají velikost rámu, typ řidítek a počet koleček na přehazovačce, nebo třeba lidi, kteří mají jméno, věk, výšku a možná pleš.

  #include <stdbool.h>
  #include <string.h>
  #include <stdio.h>
  
  struct clovek{
  	char jmeno[16];
  	int vek;
  	int vyska;
  	bool ples;
  };
  
  int vypis(struct clovek nekdo){
  	printf("Ahoj, jmenuju se %s, je mi %d let, jsem vysokej %d cm a ",
  		nekdo.jmeno, nekdo.vek, nekdo.vyska);
  	if (nekdo.ples) printf("ne");
  	printf("mam vlasy\n");
  }
  
  int main(){
  	struct clovek blaf;
  	strcpy(blaf.jmeno, "Blaf");
  	blaf.vek = 24;
  	blaf.vyska = 186;
  	blaf.ples = false;
  
  	vypis(blaf);
  
  	struct clovek blafovo_plesate_dvojce;
  	blafovo_plesate_dvojce = blaf;
  	strcpy(blafovo_plesate_dvojce.jmeno, "Blof");
  	blafovo_plesate_dvojce.ples = true;
  
  	vypis(blafovo_plesate_dvojce);
  }
  

• Nejprve se musí struktura definovat. Napíšete někam nad všechny funkce struct typ_struktury a za to do složených závorek výčet takzvaných členských proměnných, jako byste je deklarovali, vždycky typ a název. V tuto chvíli se ještě žádná paměť nealokuje, jen dáváte popis struktury.
• Pak můžete deklarovat proměnnou tohoto typu tak, že napíšete struct typ_struktury promenna. V tuto chvíli se na zásobníku naalokuje přesně tolik místa, kolik struktura zabere.
• Ke členským proměnným deklarované struktury se přistupuje přes tečku – promenna.clenska_promenna a pracuje se s nimi úplně stejně jako s jinými proměnnými.
• I s celými strukturami se dá pracovat stejně jako s jinými proměnnými, včetně přiřazování či předávání funkcím.
• Zde opět přichází ke slovu ukazatele. Při předání struktury funkci se zkopíruje obsah předávané struktury do lokální proměnné funkce. To může být pěkných pár bajtů a proto, pokud tomu nic nebrání, je lepší větší struktury předávat odkazem.
• Chcete-li naopak docílit předání pole hodnotou, můžete ho uzavřít do struktury.

Dynamické programování

Pokud jste ještě nečetli kapitolu o rekurzi a nepokusili jste se splnit úkoly k ní, nemá moc smysl se pouštět do této.

• Dynamické programování je způsob získání optimálního řešení problému pomocí jeho rozložení na podproblémy, jejichž řešení jsme získali podobně, nebo jsou tak elementární, že jsou zřejmé.
• Při implementaci často přijde ke slovu rekurze. Myšlenku dynamického programování si ukážeme na počítání Fibbonaciho posloupnosti.

  int fib(int n){
  	if ((n == 1) || (n == 2))
  		return 1;
  	else
  		return fib(n - 1) + fib(n - 2);
  }
  

• Tento kód sice funguje, ale je zoufale pomalý (má exponenciální složitost). Proč? Protože funkce se spustí jednou pro n, dvakrát pro n - 1, pro n - 5 už osmkrát. A vždycky se to všechno počítá znova.
• Ale my už přece výsledek máme. Proto si ho uložíme, a až se bude hodit, vytáhneme ho.

  int fi[100];
  
  int fib(int n){
  	if (!fi[n]) fi[n] = fib(n - 1) + fib(n - 2);
  	return fi[n];
  }
  
  int main{
  	fi[1] = 1;
  	fi[2] = 1;
  	for (int i=3; i<100; i++) fi[i] = 0;
  	fib(99);
  }
  

• Myšlenka kódu je: známe-li hodnotu, vrátíme ji, neznáme-li, rekurzivně ji vypočítáme. Tedy stejně jako u faktoriálu, ale tam nebylo nutné si cokoli pamatovat bokem.

Procvičovací úkol

Jaká je složitost zrychleného algoritmu na počítání Fibbonaciho posloupnosti?

Máte n záhonků vedle sebe. Na každém můžete zasadit mrkev nebo petržel, nesmí však být dva záhonky petržele hned vedle sebe. Kolika způsoby lze osadit vašich n záhonků?

Časem by měly přibýt ještě tyto kapitoly:

A u těchto to konečně začne být opravdu zábava:

Hlavní programová smyčka

Grafika

Síťování

Tato témata jsou pokročilejší:

Preprocesor

Kód ve více souborech

Automatizovaný překlad

Dynamická alokace paměti

Dynamické datové struktury