SecuroVerse

Abstraktní datové typy

4 min read

Co to jsou abstraktní datové typy?

Abstraktní datové typy (ADT) popisují způsob organizace a manipulace s daty, aniž by specifikovaly konkrétní implementaci. Jinými slovy, ADT říká, co daný typ dat dělá, ale ne jak to dělá.

Klíčové vlastnosti ADT:

  1. Skrytá implementace: Programátor pracuje s datovým typem pomocí definovaných operací, aniž by věděl, jak je uvnitř implementován.
  2. Definované operace: Každý ADT má přesně dané operace, které s ním lze provádět (například vložení, odebrání, hledání).
  3. Modularita a znovu použitelnost: Díky skrytí detailů implementace, je možné ADT snadno měnit nebo nahradit jinou implementací bez dopadu na zbytek programu.

Základní abstraktní datové typy

Mezi základní abstraktní datové typy se řadí:

Ukázky práce s některými z výše zmíněných datových typů lze nalézt v Kolekce.

Fronta (Queue)

  • Datový typ, který se řídí principem FIFO (First in First out), tedy kdo dříve přijde, ten dříve odejde.
  • Lze ji využít například pro uložení přicházejících požadavků na server před jejich zpracováním

Základní operace

  • enqueue – vložení prvku na konec fronty
  • dequeue – odebrání prvku ze začátku fronty
  • peek – nahlédnutí na prvek na začátku fronty

Ukázka rozhraní

public interface IQueue<T>
{
    void Enqueue(T item);
    T Dequeue();
    T Peek();
    bool IsEmpty { get; }
    int Count { get; }
}

Ilustrace

Zásobník (Stack)

  • Datový typ, který se řídí principem LIFO (Last in First out), tedy kdo přijde poslední, odejde jako první.
  • Lze jej využít například pro uložení operací, nad kterými je potřeba podporovat možnost vrátit zpět (undo – CTRL + Z).

Základní operace

  • push – vložení prvku na vrcholu zásobníku
  • pop – odebrání prvku z vrcholu zásobníku
  • peek – nahlédnutí na prvek na vrcholu zásobníku

Ukázka rozhraní

public interface IStack<T>
{
    void Push(T item);
    T Pop();
    T Peek();
    bool IsEmpty { get; }
    int Count { get; }
}

Ilustrace

Slovník (Dictionary)

  • Datový typ pro ukládání dvojic prvků, které jsou ve vztahu klíč a hodnota
  • Pro získání hodnoty je nutné vědět klíč, pod kterým je uložena
  • Pro slovníky je typické, že dokáží vrátit hodnotu v konstantním čase

Operace

  • insert – vloží dvojici klíč-hodnota do slovníku
  • delete – odstraní dvojici na základě předaného klíče
  • get – vyhledá hodnotu na základě klíče

Ukázka rozhraní

public interface IDictionary<K, V>
{
    void Add(K key, V value);
    bool Remove(K key);
    bool TryGetValue(K key, out V value);
    bool ContainsKey(K key);
    ICollection<K> Keys { get; }
    ICollection<V> Values { get; }
    int Count { get; }
}

Ilustrace

Seznam (List)

  • Datový typ pro ukládání více hodnot stejného datového typu

Seznam může být implementován různými způsoby

Základní operace

  • insert – vložení prvku na konec seznamu
  • remove – odebrání prvku ze seznamu
  • find – nalezení prvku v seznamu

Ukázka rozhraní

public interface IList<T>
{
    void Add(T item);
    bool Remove(T item);
    bool Contains(T item);
    int Count { get; }
}

Spojový seznam

  • Spojový seznam se skládá z dvojic (hodnota;odkaz)
    • Hodnota je obsah prvku
    • Odkaz je reference na další prvek
  • Výhodou spojových seznamů je to, že nevyžadují souvislou paměť, ale že každý prvek může být v paměti uložen někde jinde.
  • Pod pojmem spojový seznam se typicky myslí lineární jednosměrný spojový seznam. Vysvětlení:
    • Lineární – Prvky následují jeden po druhém, a pokud se při procházení dojde na konec, tak se nelze vrátit zpět na začátek
    • Jednosměrný – prvky lze procházet pouze ve směru od začátku do konce bez možnosti se vrátit zpět na předchozí prvek
  • Existují i další varianty
    • Lineární obousměrný spojový seznam
    • Cyklický jednosměrný spojový seznam
    • Cyklický obousměrný spojový seznam
Ilustrace

Dynamické pole

  • Pole s flexibilní velikostí, které se dokáže “nafukovat” tak, aby obsáhlo požadovaný počet prvků.
  • Prvky jsou v paměti vždy v jedné souvislé paměťové oblasti
  • Umožňuje přístup pomocí indexů
  • Pokud je potřebné alokovat paměť nad velikost pole, provádí se vytvoření nové paměťové oblasti (typicky o dvojnásobné velikosti) a následně se provede překopírování hodnot z původní paměti do nové paměti. Následně se původní paměť může uvolnit.
Ilustrace

Množina (Set)

  • Slouží pro uložení hodnot stejného datového typu tak, že v rámci množiny jsou uloženy pouze unikátní hodnoty (stejně jako v matematice).

Operace

  • insert – vloží prvek do množiny
  • remove – odebrání prvku z množiny
  • contains – zjištění, jestli prvek je přítomný v množině

Ukázka rozhraní

public interface ISet<T>
{
    void Insert(T item);
    void Remove(T item);
    bool Contains(T item);
    int Count { get; }
}

Ilustrace

Graf

  • Umožňuje modelovat vztahy mezi prvky
  • Například: uložení organizační struktury, kde každý zaměstnanec má právě jednoho nadřízeného

Více o grafech lze nalézt v přehledu grafů.

Operace

  • addNode – vložení nového vrcholu do grafu
  • addEdge – vložení nové hrany

Ukázka rozhraní

public interface IGraph<T>
{
    void AddVertex(T vertex);
    void AddEdge(T from, T to);
    bool ContainsVertex(T vertex);
    IEnumerable<T> GetNeighbors(T vertex);
}

Ilustrace

Graph View

Backlinks