Datová struktura

Základní datové struktury

Pole

Nejjednodušším typem datové struktury je lineární pole. Známá také jako jednorozměrné pole. Pole obsahuje několik hodnot stejného typu (integer, floats, string atd.). Přístup k prvkům v poli je velmi rychlý. Pole má obvykle pevnou velikost. Poté, co je na začátku definována velikost pole, nemusí být možné velikost pole zvětšit, aniž by bylo nutné vytvořit nové větší pole a zkopírovat všechny hodnoty do nového pole. V informatice je datová struktura pole nebo jednoduše pole datová struktura sestávající z kolekce prvků (hodnot nebo proměnných), z nichž každý je identifikován alespoň jedním indexem nebo klíčem pole. Pole je uloženo tak, že pozici každého prvku lze vypočítat z jeho indexového tuplu pomocí matematického vzorce.

Například pole 10 celočíselných proměnných s indexy 0 až 9 může být uloženo jako 10 slov na paměťových adresách 2000, 2004, 2008, 2036, takže prvek s indexem i má adresu 2000 + 4 × i.

Protože matematický pojem matice lze reprezentovat jako dvourozměrnou mřížku, dvourozměrná pole se někdy také nazývají matice. V některých případech se v informatice pro označení matice používá termín "vektor", ačkoli správnějším matematickým ekvivalentem jsou spíše tuply než vektory. Pole se často používají k implementaci tabulek, zejména vyhledávacích tabulek; slovo tabulka se někdy používá jako synonymum pro pole.

Pole patří mezi nejstarší a nejdůležitější datové struktury a používají je téměř všechny programy. Lze je také použít k implementaci mnoha dalších datových struktur, jako jsou seznamy a řetězce. Efektivně využívají adresovací logiku počítačů. Ve většině moderních počítačů a mnoha externích paměťových zařízeních je paměť jednorozměrným polem slov, jejichž indexy jsou jejich adresy. Procesory, zejména vektorové, jsou často optimalizovány pro operace s poli.

Pole jsou užitečná, protože indexy prvků lze vypočítat za běhu. Tato vlastnost mimo jiné umožňuje, aby jediný iterační příkaz zpracoval libovolně mnoho prvků pole. Z tohoto důvodu se vyžaduje, aby prvky datové struktury pole měly stejnou velikost a měly by používat stejnou reprezentaci dat. Množina platných indexových tuplů a adresy prvků (a tedy i vzorec pro adresování prvků) jsou obvykle, ale ne vždy, pevně stanoveny, dokud je pole používáno.

Termín pole se často používá pro označení datového typu pole, což je druh datového typu poskytovaného většinou vysokoúrovňových programovacích jazyků, který se skládá z kolekce hodnot nebo proměnných, které lze vybrat pomocí jednoho nebo více indexů vypočtených za běhu. Typy polí jsou často implementovány pomocí struktur polí; v některých jazycích však mohou být implementovány pomocí hašovacích tabulek, spojovaných seznamů, vyhledávacích stromů nebo jiných datových struktur.

Propojený seznam

Propojená datová struktura je soubor informací/dat propojených odkazy. Data se často nazývají uzly. Reference se často nazývají odkazy nebo ukazatele. Od této chvíle budeme pro tyto pojmy používat slova uzel a ukazatel.

V propojených datových strukturách se ukazatele pouze dereferencují nebo porovnávají na rovnost. Propojené datové struktury se tedy liší od polí, která vyžadují sčítání a odečítání ukazatelů.

Propojené seznamy, vyhledávací stromy a stromy výrazů jsou propojené datové struktury. Jsou také důležité v algoritmech, jako je topologické třídění a hledání sjednocení množin.

Stack

Zásobník je základní datová struktura, kterou lze logicky považovat za lineární strukturu reprezentovanou skutečným fyzickým zásobníkem nebo hromadou, tedy strukturou, kde vkládání a mazání položek probíhá na jednom konci zvaném vrchol zásobníku. Základní koncept lze ilustrovat představou datové množiny jako stohu desek nebo knih, kde lze z hromady odebrat pouze horní položku, aby bylo možné z ní věci odstranit. Tato struktura se používá v celém programování.

Základní implementace zásobníku se také nazývá struktura "Last In First Out", existují však různé varianty implementace zásobníku.

Se zásobníky lze provádět v zásadě tři operace. Jsou to:

• vložení ("posunutí") položky do zásobníku
• odstranění ("vyjmutí") položky ze zásobníku.
• zobrazení obsahu horní položky zásobníku ("peeking").

Fronta

Fronta je abstraktní datový typ nebo lineární datová struktura, do které se první prvek vkládá z jednoho konce ("ocas") a mazání existujícího prvku probíhá z druhého konce ("hlava"). Fronta je struktura "první dovnitř, první ven". "First In First Out" znamená, že prvky vložené do fronty jako první vyjdou první a prvky vložené do fronty jako poslední vyjdou poslední. Příkladem fronty jsou fronty čekajících lidí. První osoba ve frontě jde první a poslední osoba ve frontě jde poslední.

Proces přidání prvku do fronty se nazývá "enqueuing" a proces odebrání prvku z fronty se nazývá "dequeuing".

Graf

Graf je abstraktní datový typ, který má implementovat koncepty grafů a hypergrafů z matematiky.

Datová struktura grafu se skládá z konečné (a případně proměnlivé) množiny uspořádaných dvojic, nazývaných hrany nebo oblouky, určitých entit nazývaných uzly nebo vrcholy. Stejně jako v matematice se říká, že hrana (x,y) směřuje nebo jde z x do y. Uzly mohou být součástí struktury grafu nebo mohou být externími entitami reprezentovanými celočíselnými indexy nebo odkazy. Datová struktura grafu může také každé hraně přiřadit nějakou hodnotu, například symbolickou značku nebo číselný atribut.

Strom

Strom je jednou z nejvýkonnějších pokročilých datových struktur. Často se objevuje v pokročilých oborech, jako je umělá inteligence (AI) a design. Překvapivě je strom důležitý i v mnohem základnější aplikaci - vedení efektivního indexu.

Při použití stromu je vysoká pravděpodobnost, že bude použit index. Nejjednodušším typem indexu je setříděný seznam klíčových polí. Strom má obvykle definovanou strukturu. V případě binárního stromu lze použít binární vyhledávání k nalezení libovolné položky, aniž by bylo nutné prohledávat každou položku.

Datový typ strom je typem grafu, což znamená, že mnoho algoritmů vytvořených k procházení grafu pracuje také se stromem, avšak algoritmy mohou být velmi podobné a musí mít vyhrazený počáteční uzel, tedy uzel, na který nenavazují žádné další uzly.

Problém s jednoduchým uspořádaným seznamem nastává, když začnete přidávat nové položky a musíte seznam udržovat seřazený - lze to provést poměrně efektivně, ale vyžaduje to určité úpravy. Navíc lineární index není snadné sdílet, protože při úpravách jedním uživatelem je třeba "uzamknout" celý index, zatímco jednu "větev" stromu lze uzamknout a ostatní větve ponechat ostatním uživatelům k úpravám (protože je nelze ovlivnit).

Tabulka Hash

Hašovací tabulka je pole, kde každý index ukazuje na spojový seznam založený na hašovací hodnotě. Hodnota hash je hodnota určená hashovací funkcí. Hašovací funkce určuje jedinečnou hodnotu na základě ukládaných dat. To umožňuje přístup k datům v konstantním čase, protože počítač vždy ví, kde má hledat.

Každý uzel ukazuje na jiný uzel.