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ů.

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.

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ů. Často se implementuje jako spojový seznam 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).

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í skrze vnitřní uzly (internal nodes) až k nejnižším prvkům struktury – listům (leaf).

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ů (node, vertex) a hran (edges) a jejich vzájemných incidencí(adjacency). 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í. Jde o metodu,která řádově snižuje asymptotickou složitost vyhledávání až na logaritmickou úroveň. Indexování je hojně používáno například v databázích, kde urychluje vyhledávání.

Odkazy

Použitá literatura

• Dinesh P. Mehta, Sartaj Sahni. Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, 2004.

• Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.

• Kurt Mehlhorn, Peter Sanders. Algorithms and Data Structures. Springer, 2008.

• S.B. Kishor. Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Klíčová slova

algoritmus, data, programy