Datové struktury

Datové struktury

Datové struktury jsou programové konstrukce sloužící k efektivní správě dat v počítačovém softwaru. Data jsou v počítači reprezentována různými datovými typy. Ty lze dále skládat do struktur, které umožňují s daty snadněji a rychleji pracovat.

Datové struktury patří mezi abstraktní datové typy (ADT). Jde o programové abstrakce nezávislé na konkrétním způsobu implementace, programovacím jazyku, nebo typu ukládaných dat. Jednotlivé datové struktury definují jak svou vnitřní strukturu, tak i operace, které je možné nad daty provádět.

V dnešní době známe desítky základních i pokročilých datových struktur. Každá je vhodná k plnění jiných funkcí. Existují obecné datové struktury používané v širokém spektru programů, ale i úzce specializované vhodné k použití ve velmi specifických případech. Pro datovou strukturu a její využití je rozhodující především jejich paměťová náročnost a škála základních operací s jejich asymptotickou složitostí.

Operace

Operace jsou úkony, které lze v rámci dané datové struktury nad daty provádět. Většina operací souvisí s efektivním ukládáním, vyhledáváním, řazením, tříděním nebo mazáním dat ve struktuře. Pro každou operaci lze vypočítat asymptotickou složitost udávající rychlost s kterou se daná operace provede.

Základní datové struktury

Pole (Array)

Pole si můžeme představit jako uspořádanou matici prvků určitého datového typu. Prvky dat jsou v poli ukládány do paměti v navazujících blocích za sebe a jsou identifikovány pomocí indexu. Pozici prvku v paměti počítače pak lze dopočítat pomocí jednoduché rovnice: adresa prvku v paměti = adresa počátku pole + index * velikost prvku

Pole mohou mít libovolný počet rozměrů. Nejjednodušším typem jsou jednorozměrná neboli lineární pole. Dvourozměrná pole někdy nazýváme tabulka. Přístup k prvkům vícerozměrného pole se řeší použitím více indexů podobně jako při práci s maticemi.

• statická pole - jsou pole s pevně daným počtem prvků
• dynamická pole - jsou pole s proměnlivým počtem prvků

Fronta (Queue)

Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu FIFO (First-In-First-Out). Prvek uložený ve frontě jako první, je jako první na řadě pro výběr. Fronta aktivně pracuje pouze s prvním a posledním zařazeným prvkem. K tomuto účelu používá sadu tří základních operací: *Zařazení prvku (Equeue)

• Vyřazení prvku (Dequeue)
• Test prázdnoty (Empty)

Speciálním případem front jsou prioritní fronty. V nich jsou prvky řazeny na základě priority. Zařazený prvek s vyšší prioritou předbíhá méně prioritní prvky. Z prioritní fronty je vybírán vždy prvek s nejvyšší prioritou.

Zásobník (Stack)

Jednoduchá datová struktura s proměnným počtem zařazených prvků fungující na principu LIFO (Last-In-First-Out). Na rozdíl od fronty se ze zásobníku prvky vybírají v opačném pořadí než v jakém byly vloženy. Zásobník tak aktivně pracuje pouze s posledním vloženým prvkem. Díky své rychlosti se zásobníky využívají především pro uchovávání výsledků mezivýpočtů a rekurzivních stavů. Základní sada operací zásobníku obsahuje instrukce:

• Vložit (Push)
• Vybrat (Pop)
• Test prázdnoty (Empty)

Spojový seznam (Linked list)

Je datová struktura určená k ukládání dat předem neznámé délky. Spojové seznamy jsou tvořeny vzájemně propojenými uzly. Každý uzel obsahuje jeden datový prvek a jeden nebo více ukazatelů na další uzly. Na základě použitých ukazatelů rozlišujeme několik druhů spojových seznamů:

Jednosměrně zřetězený spojový seznam

Nejjednodušší varianta spojového seznamu. Jeho prvky obsahují pouze ukazatel na další prvek v seznamu. Jednosměrný spojový seznam lze prohledávat pouze jedním směrem od počátečního prvku struktury dál. Jednosměrné prohledávání je v mnoha případech neefektivní, proto vznikly další varianty spojových seznamů.

Obousměrně zřetězený spojový seznam

Uzly obousměrně zřetězeného seznamu obsahují dva ukazatele na následující a předchozí uzel. Díky zpětnému zřetězení se jde při prohledávání obousměrně zřetězeného seznamu i vracet.

Kruhový spojový seznam

Kruhový seznam je speciálním typem seznamu zřetězeným do kruhu. Poslední uzel seznamu obsahuje místo prázdného odkazu ukazatel na první prvek listu. Kruhový seznam lze vytvořit v obou variantách zřetězení. Obousměrné zřetězení umožňuje tento typ spojového seznamu procházet libovolně v obou směrech od počátku i od konce.

Pokročilé datové struktury

Mezi pokročilé datové struktury řadíme především stromy, hashe a nejrůznější grafové struktury. Konstrukčně složitější datové struktury mají význam především při efektivním třídění a vyhledávání dat.

Stromové struktury (Tree)

Slouží k uchovávání hierarchicky uspořádaných dat jako jsou abecední seznamy, organizační struktury, nebo hierarchie souborů. Ve stromových strukturách jsou data řazeny od tzv. kořene (root) pomocí větvení až k nejnižším prvkům struktury – listům (leaf). Stromy jsou efektivní především při prohledávání setříděných dat s logaritmickou složitostí.

Z hlediska implementace existuje mnoho různých stromových struktur. Mezi nejznámější patří binární stromy, R-stromy, nebo AVL stromy. Vlastnostmi stromů se podrobně zabývá teorie grafů.

Grafy (Graph)

Grafy jsou datové struktury složené z uzlů (nodes) a hran (edges) a jejich vzájemných incidencí. Uzly grafu uchovávají data. Hrany jsou spojnice uzlů označující vazby, nebo vztahy mezi nimi. Z hlediska vnitřní struktury rozlišujeme dva základní typy grafů:

• Neorientovaný graf - hrany nerozlišují směr
• Orientovaný graf - hrany mají určen směr od počátečního do koncového uzlu

Problematikou grafů se v počítačové vědě podrobně zabývá teorie grafů.

Hashe (Hash)

Hash je struktura používaná k sestavování asociativních polí, které za pomoci klíče (key) a správné hashovací funkce (hash function) umožňují indexování. Indexování je hojně používáno například v databázích, kde urychluje vyhledávání.