Datová struktura

Schéma hašovací tabulky

V matematické informatice a programování představuje datová struktura konkrétní způsob organizace dat v paměti počítače, který zajišťuje, aby mohla data být používána efektivně.^[1][2] Datová struktura umožňuje uchovávat a zpracovávat množinu dat stejného typu nebo různorodých, ale logicky souvisejících dat.

Termín „datová struktura“ může mít několik příbuzných významů:

• abstraktní datový typ,
• implementace abstraktního datového typu,
• instance datového typu, například konkrétní seznam.

Datové struktury mohou implementovat jeden nebo více abstraktních datových typů (ADT). Abstraktní datový typ je abstrakce datové struktury; je určen operacemi, které nad ním mohou být prováděny (kontraktem), a matematickými vlastnostmi těchto operací (včetně jejich paměťové a časové složitosti).

Datová struktura pak je konkrétní implementací kontraktu. Datová struktura poskytuje sadu operací pro vkládání, vyhledávání, aktualizování a mazání dat. Tento soubor operací tvoří rozhraní datové struktury. Efektivitu datové struktury nelze posuzovat odděleně od těchto operací. Ukládání a vyhledávání může být prováděno nad daty uloženými v hlavní paměti nebo v sekundární paměti; podle typu paměti volíme vhodné datové struktury a algoritmy.

Při vývoji softwaru závisí složitost implementace a rychlost práce výsledného programu na správném výběru datových struktur. Pro různé druhy aplikací se hodí různé typy datových struktur. Některé datové struktury jsou úzce specializovány pro určité úkoly. Například databázové systémy obvykle spoléhají na indexy ukládané pomocí B-stromů. Pokročilé datové struktury poskytují prostředky pro efektivní správu velkého množství dat. Efektivní datové struktury jsou klíčem k návrhu efektivních algoritmů. Některé formální konstrukční metody a programovací jazyky zdůrazňují datové struktury (spíše než algoritmy) jako klíčový organizační faktor při návrhu softwaru.

Datové struktury jsou obvykle založeny na schopnosti počítače načítat a ukládat data na jakékoliv místo v paměti, určené ukazatelem, což je bitový řetězec, představující adresu v paměti. Tento ukazatel může být sám uložen v paměti a manipulován programem. Například datové struktury pole a záznam jsou založeny na výpočtu adresy datových položek pomocí aritmetických operací, zatímco spojové seznamy jsou založeny na ukládání adres datových položek v rámci struktury samotné. Mnoho datových struktur používá oba principy, někdy kombinované netriviálním způsobem.

Mnohé klasické datové struktury jsou obsaženy buď ve standardních knihovnách programovacích jazyků nebo vestavěny přímo v programovacích jazycích. Například datová struktura hašovací tabulka je vestavěna do většiny skriptovacích jazyků.

Kritéria pro návrh datových struktur:

• rychlost čtení (včetně nalezení dat),
• rychlost zápisu (operace vložení, mazání, aktualizace),
• paměťová náročnost,
• náročnost implementace (čím komplikovanější algoritmus, tím větší pravděpodobnost chyby).

Příklad

Abstraktní datové typy zásobník a fronta můžeme implementovat spojovým seznamem. Je sice možné spojový seznam (záznamů spojujících klíč a hodnotu) použít i pro abstraktní datový typ asociativní pole, ale výsledek bude pro větší počet prvků málo efektivní. Pro realizaci asociativního pole si tedy spíše vybereme hašovací tabulku nebo některý typ binárního stromu. Pokud si můžeme dovolit předem omezit množinu klíčů, nebo pokud realizujeme asociativní pole, ve kterém se často hledá a méně často se do něj zapisuje, můžeme využít dokonalé hašování.

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Data structure na anglické Wikipedii a Структура данных na ruské Wikipedii.

Literatura

• Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft: Data Structures and Algorithms. Addison-Wesley, 1983, ISBN 978-0201000238.
• Niklaus Wirth: Algorithms + Data Structures = Programs, Prentice-Hall, New Jersey, 1975, ISBN 0-13-022418-9.

Externí odkazy

• Obrázky, zvuky či videa k tématu datová struktura na Wikimedia Commons