Datové struktury

Úvod

Datový typ je název pro množinu hodnot a množinu operací, které lze nad danými hodnotami provádět. Datový typ určuje, jak se data ukládají do paměti a jak s nimi pracovat.

Základní kategorie datových typů

Abstraktní datový typ (ADT)

Abstraktní datový typ je určen pouze svojí definicí – říká co dělá, ne jak to dělá. Odděluje rozhraní od implementace. ADT se označují jako kontejnery a měly by definovat minimálně tyto operace:

• Vytvoření prázdného kontejneru
• Zjištění počtu prvků
• Přístup k prvkům
• Vložení prvku
• Odstranění prvku
• Vymazání všech prvků

Jednoduché struktury

Pole

Pole (anglicky Array) je strukturovaný datový typ, který seskupuje pevný počet položek stejného typu. Prvky jsou rozlišovány pomocí indexů – jeden index odkazuje právě na jednu položku.

Textový řetězec

Textový řetězec je strukturovaný datový typ, který bývá chápán jako pole znaků. Většina moderních jazyků ho však implementuje jako samostatný, neměnný (immutable) typ s bohatou sadou operací: spojování, hledání podřetězců, dělení, nahrazování, změna velikosti písmen atd.

Ukazatel

Ukazatel (anglicky Pointer) je abstraktní datový typ, který uchovává adresu v operační paměti. Ukazatel má svůj typ, který odpovídá typu dat uložených na odkazované adrese – int* ukazuje na data typu int.

Výčet

Výčet (anglicky Enum) je ordinální datový typ, který definuje pevnou množinu pojmenovaných konstant. Slouží k omezení hodnot, kterých může proměnná nabývat – např. dny v týdnu, stavy automatu, typy logovacích úrovní.

enum Den {
    PONDELI,
    UTERY,
    STREDA,
    CTVRTEK,
    PATEK,
    SOBOTA,
    NEDELE
};

V Javě jsou výčty plnohodnotné třídy – mohou mít atributy, metody a konstruktor:

enum Den {
    PONDELI("Pondělí"),
    UTERY("Úterý"),
    STREDA("Středa");

    private final String nazev;
    Den(String nazev) { this.nazev = nazev; }
    public String getNazev() { return nazev; }
}

Lineární struktury

Lineární datové struktury organizují prvky v jedné linii – každý prvek má (až na krajní) právě jednoho předchůdce a jednoho následníka. Liší se tím, odkud lze přidávat a odebírat.

Seznam

Seznam (anglicky List) je homogenní, lineární a dynamický ADT, který je zobecněním zásobníku a fronty – narozdíl od nich dovoluje přidávat a odebírat prvky na libovolné pozici.

graph LR
    A[Začátek] --> C[1] --> E[2] --> F[...] --> B[Konec]
    B --> A

LIFO – Zásobník (Stack)

Zásobník (anglicky Stack) je homogenní, lineární a dynamický ADT fungující na principu LIFO – Last In, First Out (poslední vložený, první odebraný). Data se ukládají v pořadí vložení, ale čtení probíhá od nejnovějšího po nejstaršímu.

Zásobník lze implementovat pomocí pole (s proměnnou top ukazující na vrchol) nebo spojového seznamu. Při implementaci polem o pevné délce je nutné hlídat přetečení (overflow).

FIFO – Fronta (Queue)

Fronta (anglicky Queue) je homogenní, lineární a dynamický ADT fungující na principu FIFO – First In, First Out (první vložený, první odebraný). Data se ukládají v pořadí vložení a čtení probíhá ve stejném pořadí.

Frontu lze implementovat pomocí pole či spojového seznamu. Při implementaci polem je vhodné použít kruhový buffer, aby se zabránilo posouvání prvků.

Kruhový Buffer

Kruhový buffer (anglicky Circular Buffer) je speciální případ fronty implementované pomocí pole, používaný jako vyrovnávací paměť mezi producentem a konzumentem. Díky své implementaci nabízí operace v \(O(1)\) bez nutnosti realokace.

Nelineární struktury

Strom

Strom je abstraktní datová struktura, která reprezentuje souvislý, neorientovaný, acyklický graf. Každý vrchol má \(n\) potomků a každý potomek má právě \(1\) rodiče (kromě kořene, který rodiče nemá).

Procházení stromu

Stromy lze procházet dvěma základními způsoby:

• Do šířky (BFS): po patrech – od kořene přes všechny jeho potomky, pak jejich potomky…
• Do hloubky (DFS): po větvích – tři varianty podle pořadí návštěvy kořene:
  • Pre-order: Kořen → levý podstrom → pravý podstrom.
  • In-order: Levý podstrom → kořen → pravý podstrom (v BST dává seřazené pořadí).
  • Post-order: Levý podstrom → pravý podstrom → kořen.

Binární strom

Binární strom je strom, jehož každý vrchol má maximálně 2 potomky (levý a pravý). Je základem pro binární vyhledávací stromy, haldy a další struktury.

Halda

Halda (anglicky Heap) je případ binárního stromu, který navíc splňuje jednu z podmínek haldy:

• Max-heap: Hodnota potomka je vždy menší než hodnota jeho rodiče. Kořen obsahuje maximum.
• Min-heap: Hodnota potomka je vždy větší než hodnota jeho rodiče. Kořen obsahuje minimum.

Halda se chová jako prioritní fronta – umožňuje rychle získat a odebrat prvek s nejvyšší prioritou.

Množina

Množina (anglicky Set) je ADT, který negarantuje pořadí prvků, ale garantuje jejich jedinečnost – každý prvek se v množině vyskytuje nejvýše jednou.

Tabulka

Tabulka (anglicky Map, Dictionary, Associative Array) je ADT, který ukládá dvojice klíč–hodnota. Každý klíč je unikátní a mapuje se právě na jednu hodnotu. Na rozdíl od pole, kde jsou indexy celá čísla, v tabulce může být klíčem libovolný typ (řetězec, objekt…).