Abstraktní datový typ

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

'''Abstraktní datový typ''' ('''ADT''') je v [[informatika|informatice]] výraz pro typy dat, které jsou nezávislé na vlastní [[implementace|implementaci]]. Hlavním cílem je zjednodušit a zpřehlednit program, který provádí operace s daným datovým typem. ADT umožnuje vytvářet i složitější datové typy, např. operace s ADT typu [[zásobník (informatika)|zásobník]], [[fronta (programování)|fronta]] a [[pole (informatika)|pole]]. Všechny ADT lze realizovat pomocí základních [[Algoritmus|algoritmických]] operací ([[přiřazení]], [[sčítání]], [[násobení]], [[podmíněný skok]],…). == Definice == '''Datový typ''' je rozsah hodnot, které může proměnná tohoto datového typu přijmout, a množina operací (funkce, metody nebo procedury), které jsou pro tento datový typ specifikovány. "+" je například definován pro numerické typy, a v některých programovacích jazycích pro typ string (řetězec). "-" je naproti tomu zpravidla definován jen pro numerické typy dat. Množina operací je uvedena v interface. Abstraktní datový typ může mít odlišnou specifikaci. Ta se skládá z příznaků a sémantiky. Když vyřkneme matematickou definici, jedná se většinou o vztah mezi označením, zdroji a [[axiom]]y. Z toho plyne první způsob specifikace ADT - Matematicko-axiomatický. Další možností specifikace je Matematicko-algebraická, která se odlišuje pouze sémantikou. Po obsahové stránce budou operace popsány matematicky pomocí [[matice|matic]], [[vektor]]ů, [[posloupnost]]í atd. Existují i jiné formy specifikace - přes deklaraci rozhraní v programovacím jazyku. Krátká definice: Abstraktní datový typ je implementačně nezávislá specifikace struktury dat s operacemi povolenými na této struktuře. == Historie == ADT byl představen v roce 1974 [[Barbara Liskov|Barbarou Liskov]] a [[Stephen Zilles|Stephenem Zilles]] a v roce 1977 jej [[John Guttag]] prostřednictvím asociace [[ACM]] srozumitelně vysvětlil široké veřejnosti. == Příklady == Základní ADT jsou například: * [[asociativní pole]] * [[Zásobník (datová struktura)|zásobník]] * [[Lineární seznam|seznam]] * [[Fronta (datová struktura)|fronta]] * [[množina]] * [[zobrazení (matematika)|zobrazení]] * [[textový řetězec]] * [[Strom (datová struktura)|strom]] * [[Halda (datová struktura)|halda]] == Oddělení rozhraní a implementace == Při programování je ADT reprezentováno [[API|rozhraním]], které skrývá vlastní implementaci. Klientského programátora, který ADT používá, zajímá jak objekt používat (jeho rozhraní), ale ne už vlastní implementace. Robustnost ADT spočívá v tom, že implementace je skrytá a programátorovi jsou nabídnuty pouze ovládací prvky. Vlastní implementaci ale lze změnit. Je rozdíl mezi abstraktním datovým typem a datovou strukturou použitou pro jeho implementaci. Například seznam jako ADT může být implementován jako pole, nebo jako spojový seznam. Seznam je ADT s definovanými operacemi (jako vložit_prvek, smazat_prvek atd.), ale spojový seznam je datová struktura, která používá [[Ukazatel (informatika)|ukazatele]] a může být použita k vytvoření seznamu jako ADT. == Zabudované ADT == Protože některé abstraktní datové typy jsou velmi užitečné a běžně používané, některé programovací jazyky používají tyto ADT jako primitivní datové typy, které jsou přidány do jejich [[Knihovna (programování)|knihoven]]. Například v [[Perl]]u je možné pole považovat za implementaci seznamu, standardní knihovny [[C++]] a [[Java (programovací jazyk)|Javy]] zase nabízejí implementaci seznamu, zásobníku, fronty a řetězců. == Abstraktní datová struktura == Abstraktní datová struktura je způsob, jak efektivně uložit data tak, aby práce s nimi byla relativně snadná. Je to abstraktní skladiště pro data definovaná v rámci množiny operací a pro výpočetní složitosti při vykonávání těchto operací, bez ohledu na implementaci v konkrétní datové struktuře. Výběr abstraktní datové struktury je rozhodující pro design účinných algoritmù a pro odhad jejich složitosti, zatímco výběr konkrétních datových struktur je důležitý pro účinnou implementaci těchto algoritmů. Tento pojem je velmi blízký pojmu abstraktní datový typ, který se používá v teorii programovacích jazyků. Názvy mnoha abstraktních datových struktur (a abstraktní datových typů) odpovídají názvům konkrétních datových struktur. == Vlastnosti abstraktního datového typu == Nejdůležitější vlastnosti abstraktního typu dat jsou: * '''Všeobecnost implementace''': jednou navržený ADT může být zabudován a bez problémů používán v jakémkoliv programu. * '''Přesný popis''': propojení mezi implementací a rozhraním musí být jednoznačné a úplné. * '''Jednoduchost''': při používání se uživatel nemusí starat o vnitřní realizaci a správu ADT v paměti. * '''Zapouzdření''': rozhraní by mělo být pojato jako uzavřená část. Uživatel by měl vědět přesně co ADT dělá, ale ne jak to dělá. * '''Integrita''': uživatel nemůže zasahovat do vnitřní struktury dat. Tím se výrazně sníží riziko nechtěného smazání nebo změna již uložených dat. * '''Modularita''': „stavebnicový“ princip programování je přehledný a umožňuje snadnou výměnu části kódu. Při hledání chyb mohou být jednotlivé moduly považovány za kompaktní celky. Při zlepšování ADT není nutné zasahovat do celého programu. Pokud je ADT programován objektově, jsou většinou tyto vlastnosti splněny. == Typy operací == Na abstraktním datovém typu rozlišujeme tři druhy operací: [[konstruktor]], [[selektor]] a [[modifikátor]]. Operace, která ze zadaných parametrů vytváří novou hodnotu abstraktního datového typu, se nazývá konstruktor. Úkolem konstruktoru je sestavení platné vnitřní reprezentace hodnoty na základě dodaných parametrů. Operace označovaná jako selektor slouží k získání hodnot, které tvoří složky nebo vlastnosti konkrétní hodnoty abstraktního datového typu, a konečně operace typu modifikátor provádí změnu hodnoty datového typu. == Související články == * [[Programování]] * [[Datový typ]] {{Článek z Wikipedie}} [[Kategorie:Datové struktury]] [[Kategorie:Datové typy]]

Návrat na stránku „Abstraktní datový typ“.