Datová struktura - Data structure
V informatice je datová struktura datová organizace, správa a formát úložiště, který umožňuje efektivní přístup a úpravy. Přesněji řečeno, je datová struktura je soubor datových hodnot, vztahy mezi nimi, a funkce nebo operace, které mohou být aplikovány na data, tedy to je algebraická struktura o datech .
Používání
Datové struktury slouží jako základ pro abstraktní datové typy (ADT). ADT definuje logickou formu datového typu. Datová struktura implementuje fyzickou formu datového typu.
Různé typy datových struktur jsou vhodné pro různé druhy aplikací a některé jsou vysoce specializované na konkrétní úkoly. Například relační databáze běžně používají indexy B-stromů pro načítání dat, zatímco implementace kompilátoru obvykle používají hashovací tabulky k vyhledání identifikátorů.
Datové struktury poskytují prostředky pro efektivní správu velkého množství dat pro použití, jako jsou velké databáze a služby indexování internetu. Účinné datové struktury jsou obvykle klíčem k navrhování efektivních algoritmů . Některé formální metody návrhu a programovací jazyky kladou důraz na datové struktury, nikoli na algoritmy, jako na klíčový organizační faktor při návrhu softwaru. Datové struktury lze použít k organizaci ukládání a získávání informací uložených v hlavní i sekundární paměti.
Implementace
Datové struktury jsou obecně založeny na schopnosti počítače načítat a ukládat data na libovolné místo v jeho paměti, určené ukazatelem - bitovým řetězcem, představujícím adresu paměti , který může být sám uložen v paměti a manipulován programem. To znamená, že pole a záznam datové struktury je založena na výpočtu adres datových položek se aritmetické operace , zatímco spojené datové struktury je založena na ukládání adres datové položky v samotné konstrukci.
Implementace datové struktury obvykle vyžaduje napsání sady procedur, které vytvářejí a manipulují instance této struktury. Účinnost datové struktury nelze analyzovat odděleně od těchto operací. Toto pozorování motivuje teoretický koncept abstraktního datového typu , datovou strukturu, která je definována nepřímo operacemi, které na něm mohou být prováděny, a matematické vlastnosti těchto operací (včetně nákladů na jejich prostor a čas).
Příklady
Existuje mnoho typů datových struktur, obvykle postavených na jednodušších primitivních datových typech :
- Pole je počet prvků v určitém pořadí, obvykle všechny stejného typu (v závislosti na jazyku, jednotlivé elementy mohou buď všechny být nucen být stejného typu, nebo může být téměř jakéhokoliv typu). K prvkům se přistupuje pomocí celočíselného indexu k určení, který prvek je vyžadován. Typické implementace přidělují souvislá paměťová slova pro prvky polí (ale to není vždy nutností). Pole mohou mít pevnou délku nebo lze měnit jejich velikost.
- Seznam spojený (také jen tzv seznam ) je lineární soubor datových prvků libovolného typu, nazývaných uzly, kde každý uzel má samo o sobě hodnotu, a poukazuje na další uzel v propojeném seznamu. Hlavní výhodou propojeného seznamu oproti poli je, že hodnoty lze vždy efektivně vkládat a odebírat bez přemístění zbytku seznamu. Některé další operace, například náhodný přístup k určitému prvku, jsou však v seznamech pomalejší než v polích.
- Záznam (nazývaný také n-tice nebo struct ) je Souhrnná data struktury. Záznam je hodnota, která obsahuje další hodnoty, obvykle v pevném počtu a pořadí a obvykle indexované podle jmen. Prvkům záznamů se obvykle říká pole nebo členové .
- Unie je datová struktura, která určuje, který z většího počtu povolených primitivní typy mohou být uloženy ve svých případech, např float nebo dlouhé celé číslo . Kontrast se záznamem , který by mohl být definován tak, aby obsahoval plovák a celé číslo; zatímco v unii existuje vždy jen jedna hodnota. Je přiděleno dost místa, aby obsahovalo nejširší datový typ člena.
- Značený unie (nazývaný také varianta , varianta záznam , diskriminovaná unie , nebo disjunktní unie ) obsahuje další pole indikující jeho aktuální typ, pro zvýšení bezpečnosti typu.
- Objekt je datová struktura, která obsahuje datové pole, jako záznam dělá, stejně jako různé metody , které pracují na obsahu dat. Objekt je instancí třídy v paměti z taxonomie . V kontextu objektově orientovaného programování jsou záznamy známé jako prosté staré datové struktury, které je odlišují od objektů.
Kromě toho jsou grafy a binární stromy dalšími běžně používanými datovými strukturami.
Jazyková podpora
Většina montážních jazyků a některé jazyky na nízké úrovni , jako je BCPL (Basic Combined Programming Language), nemají integrovanou podporu pro datové struktury. Na druhou stranu mnoho programovacích jazyků vyšší úrovně a některé jazyky sestavení vyšší úrovně, jako je MASM , mají speciální syntaxi nebo jinou vestavěnou podporu pro určité datové struktury, jako jsou záznamy a pole. Například jazyky C (přímý potomek BCPL) a Pascal podporují kromě vektorů (jednorozměrná pole ) a vícerozměrných polí také struktury a záznamy .
Většina programovacích jazyků má nějaký knihovní mechanismus, který umožňuje, aby implementace datové struktury byly znovu použity různými programy. Moderní jazyky obvykle přicházejí se standardními knihovnami, které implementují nejběžnější datové struktury. Příklady jsou C ++ Standard Template Library , Java Collections Framework a Microsoft .NET Framework .
Moderní jazyky také obecně podporují modulární programování , oddělení mezi rozhraním modulu knihovny a jeho implementací. Některé poskytují neprůhledné datové typy, které umožňují klientům skrýt podrobnosti implementace. Objektově orientované programovací jazyky , jako C ++ , Java a Smalltalk , obvykle pro tento účel používají třídy .
Mnoho známých datových struktur má souběžné verze, které umožňují více výpočetním vláknům přistupovat k jedné konkrétní instanci datové struktury současně.
Viz také
Reference
Bibliografie
- Peter Brass, Advanced Data Structures , Cambridge University Press , 2008, ISBN 978-0521880374
- Donald Knuth , Umění počítačového programování , sv. 1. Addison-Wesley , 3. vydání, 1997, ISBN 978-0201896831
- Dinesh Mehta a Sartaj Sahni , Handbook of Data Structures and Applications , Chapman and Hall / CRC Press , 2004, ISBN 1584884355
- Niklaus Wirth , Algoritmy a datové struktury , Prentice Hall , 1985, ISBN 978-0130220059
Další čtení
- Alfred Aho , John Hopcroft a Jeffrey Ullman , Datové struktury a algoritmy , Addison-Wesley, 1983, ISBN 0-201-00023-7
- GH Gonnet a R. Baeza-Yates , Handbook of Algorithms and Data Structures-in Pascal a C , druhé vydání, Addison-Wesley, 1991, ISBN 0-201-41607-7
- Ellis Horowitz a Sartaj Sahni, Základy datových struktur v Pascalu , Computer Science Press , 1984, ISBN 0-914894-94-3