SZZ materiály
1
Základní abstraktní kolekce (jejich klasická implementace [seznamy, slovníky], iterátory nad nimi, typické elementární operace a jejich časová složitost) a specializované abstraktní kolekce (fronta, zásobník)
Užitečné odkazy
- https://github.com/pavelberanek91/UJEP/blob/main/APR2/2_sekvencni_struktury.ipynb
- https://ki.ujep.cz/opory/Aplikovana_Informatika/Bc/Algoritmizace_a_programovani_I.html#Seznam
- https://www.geeksforgeeks.org/dsa/abstract-data-types/
- https://medium.com/@tssovi/abstract-data-type-adt-in-python-33e6ce1f961e
- https://bradfieldcs.com/algos/
Abstraktní datový typ
- zkratka ADT (=Abstract Data Type)
- formální specifikace typu definovaná množinou jeho možných hodnot a množinou operací nad těmito hodnotami, včetně jejich sémantiky, bez určení konkrétní implementace
Proč existují kolekce
- uložení více prvků
- přístup k nim
- operace nad nimi
- omezení zdrojů (čas, paměť)
Abstraktní kolekce
- datová struktura definovaná atributy a operacemi, ne konkrétní implementací
- typ ADT
- popisuje:
- jaká data uchovává (např. prvky typu T),
- jaké operace podporuje (vložit, smazat, najít, projít),
- jaké má vlastnosti (uspořádanost, unikátnost klíčů, indexování).
- implementace (pole, spojový seznam, hashovací tabulka…) je oddělená vrstva (určuje složitost operací)
Dělení prvků v kolekci
- homogenní - všechny prvky kolekce mají stejný datový typ
- heterogenní - prvky mohou mít různé datové typy
Základní abstraktní kolekce
- seznam (list)
- množina (set)
- slovník (dictionary)
- zásobník (stack)
- fronta (queue)
Seznam
- kolekce prvků, které mají dané pořadí
- víme, který je první, který druhý, a každý prvek (kromě posledního) má svého následníka
- zachovává pořadí prvků
- umožňuje duplicitní výskyt prvků
- nevynucuje setříděnost
Typické operace
- zjištění počtu prvků
- přístup k prvku na určité pozici
- vložení prvku na určitou pozici
- odstranění prvku z určité pozice
- nahrazení prvku
Typické implementace
- pole (statické/dynamické, jednorozměrné/vícerozměrné)
- spojový seznam (jednosměrný, obousměrný)
Statické pole
- souvislý blok paměti pevné velikosti
- velikost je určena při vytvoření a nelze ji změnit
- prvky jsou uloženy vedle sebe
- podporuje náhodný přístup podle indexu
int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
int length = numbers.Length; // 5
int first = numbers[0]; // 10
| Operace | Best Case | Worst Case | Vysvětlení |
|---|---|---|---|
zjištění délky (Length) |
O(1) | O(1) | Velikost pole je známá od vytvoření |
přístup (numbers[i]) |
O(1) | O(1) | Prvek je uložen na přesně vypočitatelné pozici v souvislé paměti |
změna hodnoty (numbers[i] = x) |
O(1) | O(1) | Mění se jen hodnota na již existující pozici |
| vyhledání hodnoty | O(1) | O(n) | Buď je hledaný prvek hned na začátku, je na konci nebo v poli není |
| vložení/odstranění prvku | O(n) | O(n) | Je nutné vytvořit nové pole a zkopírovat všechny prvky (velikost je pevná) |
Dynamické pole
- interně používá statické pole jako úložiště
- pokud velikost přesáhne kapacitu, dojde k rozšíření a realokaci
- kapacita roste geometricky (např. ×2)
using System.Collections.Generic;
List<int> numbers = new();
numbers.Add(10);
numbers.Add(20);
numbers.Add(30);
int count = numbers.Count; // 3
int first = numbers[0]; // 10
| Operace | Best Case | Worst Case | Vysvětlení |
|---|---|---|---|
zjištění počtu prvků (Count) |
O(1) | O(1) | Počet prvků je uložen jako vlastnost kolekce |
přístup (numbers[i]) |
O(1) | O(1) | Prvek je uložen na přesně vypočitatelné pozici v souvislé paměti |
změna hodnoty (numbers[i] = x) |
O(1) | O(1) | Mění se jen hodnota na existující pozici |
| vyhledání hodnoty | O(1) | O(n) | Buď je prvek hned na začátku, nebo je nutné projít celý seznam |
přidání na konec (Add) |
O(1) | O(n) | Pokud je volná kapacita, jen se zapíše; při zaplnění se vytvoří větší pole a vše se zkopíruje |
| vložení/odstranění uprostřed | O(n) | O(n) | Je nutné posunout prvky za danou pozicí |
Jednosměrný spojový seznam
- sekvenční datová struktura tvořená uzly
- každý uzel obsahuje:
- hodnotu
- referenci na následující uzel
Množina
- kolekce unikátních prvků
- neumožňuje duplicitní výskyt prvků
- nemá definované pořadí
- nemá index
- dvě množiny jsou stejné, pokud obsahují stejné prvky, bez ohledu na pořadí
- musí umět rozhodnout kdy jsou dva prvky stejné (operátor rovnosti)
Typické operace
- vložení prvku
- odstranění prvku
- test existence prvku
- zjištění velikosti
- sjednocení, průnik, rozdíl
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
A ∪ B = {1, 2, 3, 4, 5, 6} // Prvky, které jsou v A nebo v B.
A ∩ B = {3, 4} // Prvky, které jsou zároveň v A i v B
A \ B = {1, 2} // Prvky, které jsou v A, ale nejsou v B.
B \ A = {5, 6} // Prvky, které jsou v B, ale nejsou v A.
Typické implementace
- hashovací množina (HashSet) - interně využívá hashovací tabulku
- stromová množina (TreeSet) - interně využívá vyvážený strom
Hashovací tabulka
- používá hash funkci h(key)
- mapuje klíč na index pole
- řeší kolize (dva různé klíče mohou mít stejný index)
- chaining (uložení více prvků do seznamu na daném indexu)
- hledání další volné pozice (open addressing, např. pomocí druhé hash funkce)
- skládá se z:
- vezme se klíč
- spočítá se jeho hash (nějaké číslo) pomocí hashovací funkce
- pomocí hash % velikost_tabulky se získá index
- na tento index je uložena hodnota
Slovník
- synonyma: mapa, asociativní pole
- ukládá dvojice (klíč -> hodnota)
- klíče jsou unikátní
- hodnoty se mohou opakovat
- rovnost slovníků je dána množinou dvojic
- klíč musí být porovnatelný
- u hash implementace musí být klíč hashovatelný
Typické operace
- získání hodnoty podle klíče
- odstranění dvojice podle klíče
- vložení nebo aktualizace hodnoty podle klíče
- test existence klíče
- počet dvojic
- iterace přes klíče / hodnoty / dvojice
Typické implementace
- hashovací slovník (HashMap) - interně využívá hashovací tabulku
- stromový slovník (TreeMap) - interně využívá vyvážený strom
Fronta
- anglicky: Queue
- abstraktní kolekce typu FIFO (First-In-First-Out)
- prvek, který přijde první, odchází první
Typické implementace
- kruhová fronta
- spojový seznam s ukazatelem na začátek i konec
- obousměrnná fronta
- dynamické pole (méně vhodné, dequeue bývá O(n))
| Implementace | enqueue | dequeue | front | rear | Poznámka |
|---|---|---|---|---|---|
| Kruhové pole | O(1) | O(1) | O(1) | O(1) | Posun indexů pomocí modulo, žádné přesouvání prvků |
| Spojový seznam (head + tail) | O(1) | O(1) | O(1) | O(1) | Vkládání i odebírání jen přepojí ukazatele |
| Dynamické pole (běžný list) | O(1) | O(n) | O(1) | O(1) | dequeue vyžaduje posun všech prvků |
Zásobník
- anglicky: Stack
- abstraktní kolekce typu LIFO (Last-In-First-Out)
Typické implementace
- dynamické pole
- spojový seznam
| Implementace | push | pop | peek | Poznámka |
|---|---|---|---|---|
| Dynamické pole | O(1)* | O(1) | O(1) | *amortizovaně |
| Spojový seznam | O(1) | O(1) | O(1) | Přepojení hlavy |
Iterátor
- objekt, který poskytuje jednotné rozhraní pro průchod kolekcí bez znalosti její vnitřní implementace
- odděluje algoritmus procházení od struktury dat
- Iterator pattern - návrhový vzor
- udržuje si vlastní stav průchodu
- je jednorázový
Typické operace
- získání aktuálního prvku
- posun na další prvek
- zjištění existence dalšího prvku