Data structure

Strukturovaný datový typ sestává z komponent jiného (dříve definovaného) typu, kterému říkáme kompoziční typ. Pokud jsou všechny komponenty strukturovaného typu stejného kompozičního typu, říkáme, že strukturovaný typ je homogenní. Komponentám homogenního typu se někdy říká položky (item), zatím co komponentám heterogenního typu se říká složky (component). Strukturovaný typ má strukturovanou hodnotu. Tato hodnota je definovaná tehdy, když jsou definované hodnoty všech jejích komponent.

Array data structure, String (computer science)

Pole (array) je homogenní ortogonální (pravoúhlý) datový typ. Jednorozměrnému poli říkáme vektor, dvojrozměrnému poli říkáme matice. Lze vytvářet pole s neomezenou vícerozměrnou hierarchickou strukturou. Prvek vektoru je zpřístupňován jedním, prvek matice dvojicí indexů. Indexem může být libovolný ordinální typ. Pro svou homogenitu říkáme prvkům pole také položky. Typ pole je specifikován rozsahem svých dimenzí (rozměrů) a komponentním typem. Pole, jehož jméno a velikost dimenzí je pevně dána deklarací a nemohou se měnit v průběhu programu, se nazývá statické (vs dynamické). Pokus o přístup k prvku pole, jehož index je mimo specifikovaný rozsah, způsobí chybu.

Řetězec (string) je strukturovaný homogenní datový typ. Položkami řetězce je typ znak a řetězec má vlastnosti podobné jednorozměrnému poli znaků.

List (computing), Linked list

Seznam je homogenní, lineární, dynamická struktura.

• Lineárnost znamená, že každý prvek struktury má právě jednoho předchůdce (predecessor) a jednoho následníka (successor). Výjimku tvoří první a poslední prvek.
• Prvkem seznamu může být libovolný jiný datový typ – také strukturovaný. Např. seznam seznamů.
• Seznam může být prázdný.
• Přístup k prvnímu (okrajovému) prvku je přímý, přístup k ostatním prvkům seznamu je sekvenční ve směru průchodu. Seznam, který lze procházet jen jedním směrem se nazývá „jednosměrně vázaný“ zkráceně „jednosměrný“, Seznam u něhož lze procházet oběma směry je „dvousměrně vázaný“ – „dvousměrný“.

Stack (data structure)

Zásobník je homogenní, lineární, dynamická struktura.

Zásobníku se také říká struktura typu LIFO z anglického „Last-In-First-Out“.

Základní operace jsou:

• Push – přidání pvku na vrchol zásobníku
• Pop – vyzvednutí pvku z vrchol zásobníku

Queue (data structure)

Fronta je dynamická, homogenní a lineární struktura.

Někdy se jí říká struktura typu „FIFO“.

Operace:

• Enqueue – zařazení prvku na konec fronty
• Dequeue – vyzvednutí prvku ze začítku fronty

Binary tree

Binární strom je buď prázdný, nebo sestává z jednoho uzlu zvaného kořen a dvou podstromů – levého a pravého. Oba podstromy mají vlastnosti stromu.

Binární strom je váhově vyvážený (weight balanced), když pro všechny jeho uzly platí, že počty uzlů jejich levého podstromu a pravého podstromu se rovnají, nebo se liší právě o 1.

Stromu, počet jehož uzlů je 2ⁿ − 1, pro n > 0 a jehož výška je právě n říkáme absolutně váhově vyvážený strom.

Binární strom je výškově vyvážený (height balanced) , když pro jeho všechny uzly platí, že výška levého podstromu se rovná výšce pravého podstromu, nebo se liší právě o 1.

Tree traversal

Existují 3 způsoby průchodů: Preorder, Inorder a Postorder. Předpony pre, in a post určují kdy přijde na řadu kořenový uzel. Dále vždy projdeme nejdříve levý podstrom a poté pravý. Inverzní varianty průchodů obrací pouze pořadí větví.

Subroutine

int soucet(int x, int y);
 
int soucet(int x, int y) {
    return x + y;
}
 
printf("%d\n", soucet(10, 20)); //30

Funkce umožňují rozložit složitější problémy na jednodušší podproblémy.

Deklarace funkce (někdy také prototyp, v ukázce na začátku) se skládá z návratového typu, názvy funkce a seznamu parametrů. Ve většině případů ji lze vynechat, a použít rovnou definici.

Definice funkce rozšiřuje deklaraci o blok těla funkce.

Tělo funkce by mělo obsahovat příkaz return za kterým by měla následovat vracená hodnota jejíž typ se musí shodovat s návratovým typem funkce. Pokud má funkce návratový typ void, za returnem nic nenásleduje. Příkaz return přeruší další provádění. Někdy se funkce s typem void označuje jako procedura.

Funkce se volá jejím názvem a zadanými prarametry.

Složený příkaz je posloupnost libovolných příkazů (včetně dalších složených). Většinou se syntakticky odlišuje, například {} (C, Java, …) nebo odsazením (Python). Proměnné mají většinou omezenou platnost jen pro blok (a podbloky) ve kterých byly deklarováný.

Výrazem je nejen aritmetický výraz, prostý výskyt konstanty (literálu) či proměnné, ale i funkční volání a přiřazení. Jestliže výraz ukončíme symbolem ; (středník), získáme výrazový příkaz.

Zvláštním případem je prázdný příkaz.

Conditional_(programming), Switch statement

if (/*podmínka*/) {
    /*příkazy*/
}
 
if (/*podmínka*/) {
    /*příkazy*/
} else {
    /*příkazy*/
}
 
switch (/*proměnná*/) {
    case /*stav*/:
        /*příkazy*/
        break;
    case /*stav*/:
        /*příkazy*/
        break;
    /*...*/
    default:
        /*příkazy*/
}

If je nejtypičtější podmíněný příkaz. Podmínka má vždy výsledek true nebo false. Je-li true, provede se příkaz za ifem. Pokračuje-li navíc else, jeho tělo se provede v případě že je výsledek podmínky false.

Složené závorky nejsou nutné, pokud se provede pouze jeden příkaz, společně s odsazením ale zvyšují přehlednost kódu a usnadňují doplnění dalšího kódu.

Switch se používá pokud se rozhodujeme podle různých pevných hodnot jedné proměnně, například barva něčeho.

Podmíněné příkazy je samozřejmě možné do sebe zanořovat.

Slouží k několikanásobnému opakování stejného bloku kódu.

Cykly je možné přerušit dvěma způsoby:

• continue – přestane provádět tělo smyčky a začne další iteraci
• break – úplně přestane smyčku provádět a dál pokračuje v běhu programu

While loop, Do while loop

while (/*podmínka*/) {
    /*příkazy*/
}
 
do {
    /*příkazy*/
} while (/*podmínka*/);

While se používá pokud předem neznáme počet opakování. Pokud je while uveden na začátku, nejdříve se vyhodnotí podmínka a až pak se připadně provede tělo. Je tedy možné, že se tělo neprovede vůbec. Při použití varianty do while se tělo provede nejméně jednou.

For loop

for (/*inicializace*/; /*test podmínky*/; /*inkrementace*/) {
    /*příkazy*/
}

Tělo smyčky se provede tolikrát, dokud platí test podmínky. V těle je možné použít proměnnou inicializovanou v hlavičce smyčky.