Abstraktní datový typ "seznam". abstraktní datový typ data generalities abstrakt

Jazyk C++ umožňuje vytvářet datové typy, které se chovají podobně jako základní typy jazyka C. Tyto typy se obvykle nazývají abstraktní datové typy(ATD).
Struktury se používají k implementaci ADT v jazyce C. Ale využití dat konstrukční typ výrazně omezený oproti použití základní typy data. Strukturální data například nelze použít jako operandy v různých operacích (sčítání, odečítání). Chcete-li manipulovat s takovými daty, musíte napsat sadu funkcí, které provádějí různé akce, a volat tyto funkce místo operací.

Prvky konstrukce navíc nejsou nijak chráněny před náhodnou úpravou. To znamená, že jakákoli funkce (i ne ze sady nástrojů pro manipulaci s daty struktury) může odkazovat na prvek struktury. To je v rozporu s jedním z hlavních principů objektově orientovaného programování - zapouzdřením dat: žádné jiné funkce než speciální funkce manipulace tohoto datového typu by neměly mít přístup k datovým členům.

Zvažte implementaci konceptu data pomocí struktury k definování reprezentace data data a sady funkcí pro práci s proměnnými tohoto typu:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#zahrnout
datum struktury
{
int měsíc; // Měsíc
int den; // den
int rok; // rok
};
void set_date(datum* f, int d, int m, int y)
{
f->den = d;
f->měsíc = m;
f->rok = y;
}
void print_date(date*f)
{
printf("%d.%d.%d" , f->den, f->měsíc, f->rok);
}
int main()
{
datum dnes;
set_date(&dnes, 2., 4., 2014);
print_date(&dnes);
getchar();
návrat 0;
}

V tomto příkladu neexistuje žádný explicitní vztah mezi funkcemi a datovým typem. Chcete-li volat kteroukoli z popsaných funkcí, musíte předat ukazatel na instanci struktury jako argument.

Takový vztah lze vytvořit popisem funkcí jako členů struktury. Tyto funkce mohou působit na data obsažená v samotné struktuře.
Ve výchozím nastavení, když je struktura deklarována, jsou její data a funkce sdíleny, což znamená, že objekty typové struktury nemají ani zapouzdření, ani ochranu dat:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#zahrnout
datum struktury
{
int měsíc; // Měsíc
int den; // den
int rok; // rok
void set_date(int d, int m, int y)
{
den=d; měsíc=m; rok=y;
}
void datum_tisku(void );
};
void date::print_date(void )
{
printf("%d.%d.%d" , den, měsíc, rok);
}
int main()
{
datum dnes;
dnes.set_date(2, 4, 2014);
dnes.print_date();
getchar();
návrat 0;
}

Členové funkce a datové členy

Funkce popsané v těle abstraktní typ data jsou členské funkce nebo metody a lze je volat pouze na speciální proměnné odpovídajícího typu pomocí standardní syntaxe pro přístup k členským datům nebo polím struktury.

Členské funkce lze definovat dvěma způsoby:

• popis funkce přímo v popisu struktury;
• popis funkce mimo strukturu.

Členské funkce, které jsou definovány ve struktuře, jsou implicitně vložené ( ). Obecně platí, že ve struktuře by měly být definovány pouze krátké, často používané členské funkce:

void set(int m, int d, int y) (měsíc = m; den = d; rok = y;);

• typ je návratový typ členské funkce
• ATD— název abstraktního datového typu (název struktury nebo třídy)
• název- název členské funkce

void date::print_date(void )
( printf("%d.%d.%d" ,den, měsíc, rok);)

V členské funkci lze názvy členů použít bez explicitního odkazu na objekt. V tomto případě název odkazuje na člen objektu, na kterém byla funkce volána.

Členské funkce stejné struktury mohou být polymorfní, tedy přetížené.

Přístupová práva

Koncept struktury v C++ (na rozdíl od C) umožňuje členům struktury být veřejné, soukromé nebo chráněné:

• veřejnost - obecná;
• soukromý - soukromý;
• chráněný - chráněný.

Používání klíčové slovo chráněná souvisí s pojmem dědictví.

Použití klíčového slova private omezuje přístup členům, kteří se řídí touto konstrukcí. Soukromé členy může používat pouze několik kategorií funkcí, které mají oprávnění k přístupu k těmto členům. Jsou to v podstatě členské funkce stejné struktury.
Klíčové slovo public tvoří rozhraní k objektu struktury.

Standardně se členská data umísťují do soukromé oblasti ( private ) a části členských funkcí - do veřejné části ( public ) abstraktního datového typu. V tomto případě privátní (soukromá) část definuje datové a obslužné funkce objektu a členské funkce veřejné části implementují metody pro práci s objektem.

Změňme strukturu data, abychom skryli reprezentaci dat (zapouzdření dat):

1
2
3
4
5
6
7
8

datum struktury
{
soukromé:
int měsíc, den, rok;
veřejnost:
void set(int , int , int );
voidprint();
};

Vývoj abstraktních modelů pro data a způsoby zpracování těchto dat je podstatná součást v procesu řešení problémů pomocí počítače. Příklady toho vidíme jak na nízké úrovni v každodenním programování (například při použití polí a propojených seznamů, diskutovaných v), tak na vysoké úrovni při řešení aplikované úkoly(jako při řešení problému s konektivitou pomocí doménové struktury pro vyhledávání spojení v „Úvodu“). Tato přednáška pojednává o abstraktních datových typech ( abstract data type , dále ADT), které umožňují vytvářet programy využívající abstrakcí na vysoké úrovni. Abstraktní datové typy vám umožňují oddělit abstraktní (konceptuální) transformace, které programy provádějí na datech, od jakékoli konkrétní reprezentace datové struktury a jakékoli konkrétní implementace algoritmu.

Všechno výpočetní systémy na základě úrovní abstrakce: určité fyzikální vlastnosti křemíku a dalších materiálů umožňují přijetí abstraktního modelu bitu, který může nabývat binárních hodnot 0-1; pak je abstraktní model stroje postaven na dynamických vlastnostech hodnot určité sady bitů; dále je na základě principu činnosti stroje pod řízením programu ve strojovém jazyce sestaven abstraktní model programovacího jazyka; a nakonec je zkonstruován abstraktní koncept algoritmu, který je implementován jako program v C++. Abstraktní datové typy umožňují pokračovat v tomto procesu dále a rozvíjet abstraktní mechanismy pro určité výpočetní úlohy na vyšší úrovni, než poskytuje systém C++, rozvíjet abstraktní mechanismy zaměřené na konkrétní aplikace a jsou vhodné pro řešení problémů v mnoha oblastech použití, stejně jako pro vytváření abstraktních mechanismů pro více vysoká úroveň které používají tyto základní konstrukce. Abstraktní datové typy nám poskytují nekonečně rozšiřitelný soubor nástrojů pro řešení stále nových a nových problémů.

Na jedné straně použití abstraktních konstrukcí zbavuje člověka starostí s jejich detailní implementací; na druhou stranu, kdy výkon program je důležitý, musíte znát náklady na provádění základních operací. Používáme mnoho základních abstrakcí zabudovaných do Hardware počítač a sloužící jako základ pro strojní instrukce; implementovat další abstrakce v softwaru; a používat další abstrakce poskytované dříve napsaným systémovým softwarem. Abstraktní konstrukce na vysoké úrovni jsou často založeny na jednodušších konstrukcích. Na všech úrovních platí stejný základní princip: v programech je potřeba najít ty nejdůležitější operace a ty nejvíce důležité vlastnosti data a následně přesně definovat obojí na abstraktní úrovni a vyvinout efektivní konkrétní mechanismy pro jejich implementaci. V této přednášce se podíváme na mnoho příkladů aplikace tohoto principu.

Vývoj nové úrovně abstrakce bude vyžadovat (1) definování abstraktních objektů, se kterými se má manipulovat, a operací, které se s nimi mají provádět; (2) reprezentovat data v nějaké datové struktuře a provádět operace; (3) a (co je nejdůležitější) zajistit, aby tyto objekty byly vhodné k použití pro řešení aplikovaných problémů. Tyto body platí i pro jednoduché datové typy, takže základní mechanismy pro podporu datových typů, které byly zahrnuty v "Elementárních datových strukturách" mohou být přizpůsobeny pro naše účely. Jazyk C++ však nabízí důležité rozšíření mechanismu struct nazývaného třída. Třídy jsou mimořádně užitečné při vytváření vrstev abstrakce, a proto jsou ve zbytku knihy považovány za hlavní nástroj používaný pro tento účel.

Definice 4.1. Abstraktní datový typ (ATD) je datový typ (soubor hodnot a soubor operací s těmito hodnotami), ke kterému se přistupuje pouze prostřednictvím rozhraní. Program, který používá ADT, se bude nazývat klient a program obsahující specifikaci tohoto datového typu se bude nazývat implementace.

Je to slovo, které pouze činí datový typ abstraktním: v případě ADT nemají klientské programy přístup k datovým hodnotám jiným způsobem než operacemi popsanými v rozhraní. Reprezentace těchto dat a funkce, které tyto operace implementují, jsou v implementaci a jsou zcela odděleny rozhraním od klienta. Říkáme, že rozhraní je neprůhledné: klient nevidí implementaci přes rozhraní.

V programech C++ je toto rozlišení obvykle trochu jasnější, protože je nejjednodušší vytvořit rozhraní zahrnutím reprezentace dat, ale s uvedením, že klientské programy nemají povolen přímý přístup k datům. Jinými slovy, vývojáři klientů mohou vědět reprezentace dat, ale nelze jej žádným způsobem použít.

Jako příklad zvažte rozhraní datového typu pro body (Program 3.3) z části 3.1 "Základní datové struktury". Toto rozhraní výslovně deklaruje, že body jsou reprezentovány jako struktury skládající se z dvojice čísel s plovoucí desetinnou čárkou, označených x a y. Toto použití datových typů je běžné ve velkých systémech. software: Vyvíjíme sadu konvencí reprezentace dat (a také definujeme sadu souvisejících operací) a zpřístupňujeme tato pravidla prostřednictvím rozhraní, aby je mohly používat klientské programy, které jsou součástí velkého systému. Datový typ zajišťuje, že všechny části systému jsou konzistentní s reprezentací základních datových struktur celého systému. Jakkoli je tato strategie dobrá, má jednu nevýhodu: je-li nutné ji změnit reprezentace dat, budete muset změnit všechny klientské programy. Program 3.3 nám opět uvádí jednoduchý příklad: jedním z důvodů vývoje tohoto datového typu je pohodlí klientských programů pracujících s body a očekáváme, že klienti budou mít v případě potřeby přístup k jednotlivým souřadnicím bodu. Nemůžeme však přejít na jinou reprezentaci dat (řekněme polární souřadnice nebo 3D souřadnice nebo dokonce jiné datové typy pro jednotlivé souřadnice), aniž bychom změnili všechny klientské programy.

Na rozdíl od toho Program 4.1 obsahuje implementaci abstraktního datového typu, který odpovídá datovému typu v Programu 3.3, ale používá třídu jazyka C++, která definuje jak data, tak související operace najednou. Program 4.2 je klientský program, který pracuje s tímto datovým typem. Tyto dva programy provádějí stejné výpočty jako programy 3.3 a 3.8. Ilustrují řadu hlavních vlastností tříd, které nyní budeme uvažovat.

Když do programu zapíšeme definici jako int i, řekneme systému, aby rezervoval paměťovou oblast pro data typu (vestavěný) int, který lze označit jako i. Jazyk C++ má pro takové entity termín objekt. Když je v programu zapsána definice jako POINT p, říká se, že je vytvořen objekt třídy POINT, na který lze odkazovat jménem p. V našem příkladu každý objekt obsahuje dva datové prvky pojmenované x a y. Stejně jako u struktur mohou být označovány jmény jako p.y.

Datové členy x a y se nazývají datové členy třídy. Třída může také definovat členské funkce, které implementují operace spojené s tímto datovým typem. Například třída definovaná v Programu 4.1 má dvě členské funkce nazvané POINT a distance .

Klientské programy, jako je program 4.2, mohou volat členské funkce spojené s objektem zadáním jejich názvů stejným způsobem jako názvy dat obsažených v nějaké struktuře struktury. Například výraz p.distance(q) vypočítá vzdálenost mezi body p a q (stejná vzdálenost by měla být vrácena voláním q.distance(p) ). Funkce POINT(), první funkce v Programu 4.1, je speciální členská funkce zvaná konstruktor: má stejný název jako třída a je volána, když je třeba vytvořit objekt této třídy.

Program 4.1. Implementace třídy POINT (bod)

Tato třída definuje datový typ, který se skládá ze sady hodnot, které jsou „páry čísel s plovoucí desetinnou čárkou“ (za předpokladu, že jsou interpretovány jako body v kartézské rovině), a také ze dvou členských funkcí definovaných pro všechny instance BOD. class: function POINT() , což je konstruktor, který inicializuje souřadnice s náhodnými hodnotami od 0 do 1, a funkce distance(POINT), která vypočítá vzdálenost k jinému bodu. Reprezentace dat je soukromý a mohou k němu přistupovat nebo jej upravovat pouze členské funkce. Samotné členské funkce jsou veřejné ( public ) a dostupné každému klientovi. Kód lze uložit např. do souboru s názvem POINT .cxx.

#zahrnout class POINT ( private: float x, y; public: POINT() ( x = 1,0*rand()/RAND_MAX; y = 1,0*rand()/RAND_MAX; ) float distance(POINT a) ( float dx = x-a.x , dy = y-a.y; return sqrt(dx*dx + dy*dy); ));

Program 4.2. Klientský program pro třídu POINT (nalezení nejbližšího bodu)

Tato verze programu 3.8 je klient, který používá POINT ADT definovaný v programu 4.3. Nová operace vytvoří pole objektů POINT (voláním konstruktoru POINT() pro inicializaci každého objektu s náhodnými hodnotami souřadnic). Výraz a[i].distance(a[j]) volá členskou funkci vzdálenost na objektu a[i] s argumentem a[j] .

#zahrnout #zahrnout #include "BOD.cxx" int main(int argc, char *argv) ( float d = atof(argv); int i, cnt = 0, N = atoi(argv); BOD *a = nový BOD[N]; pro (i = 0; i< N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

Definování POINT p v klientském programu má za následek přidělení paměťové oblasti pro nový objekt a poté (pomocí funkce POINT()) přiřazení každému z jeho dvou datových prvků náhodnou hodnotu v rozsahu od 0 do 1.

Tento styl programování, někdy nazývaný objektově orientované programování, je plně podporován konstrukcí třídy C++. Třídu lze chápat jako rozšíření konceptu struktury, kde jsou nejen kombinována data, ale jsou definovány operace s těmito daty. Může existovat mnoho různých objektů patřících do stejné třídy, ale všechny jsou podobné v tom, že jejich datové členy mohou nabývat stejné sady hodnot a s těmito datovými členy lze provádět stejnou sadu operací – obecně jsou instance stejného datového typu. V objektově orientovaném programování jsou objekty navrženy tak, aby zpracovávaly své datové členy (na rozdíl od použití nezávislých funkcí ke zpracování dat uložených v objektech).

Díváme se na výše popsaný příklad malé třídy, abychom se seznámili se základními funkcemi tříd; tak to zdaleka není kompletní. V reálném kódu pro třídu bodů budeme mít mnohem více operací. Například v programu 4.1 nejsou ani operace, které by vám umožnily zjistit hodnoty souřadnic x a y. Jak uvidíme, přidání těchto a dalších operací je poměrně jednoduchý úkol. V části 5 se blíže podíváme na třídy pro body a další geometrické abstrakce, jako jsou čáry a mnohoúhelníky.

V C++ (ale ne v C) mohou mít struktury také spojené funkce. Klíčový rozdíl mezi třídami a strukturami souvisí s přístupem k informacím, který je charakterizován klíčovými slovy.

Hezký den, habravchane!

Následující příspěvek je shrnutím mých myšlenek o povaze tříd a ADT. Tyto úvahy jsou doplněny zajímavými citáty z knih guru vývoje softwaru.

Úvod

Abstrakce je výběr a dávání souboru objektů společných vlastností, které definují jejich pojmové hranice a odlišují je od všech ostatních typů objektů.
Jinými slovy, abstrakce nám umožňuje „posvítit“ na objektová data, která potřebujeme, a zároveň „zakrýt“ data, která pro nás nejsou důležitá.

Co se tedy stane, pokud spojíme pojmy „datový typ“ a „abstrakce“ dohromady? Získáme datový typ, který nám poskytuje množinu operací zajišťujících chování objektů tohoto datového typu a tento datový typ skryje i data, se kterými je toto chování implementováno. Odtud se dostáváme ke konceptu ATD:

ADT je ​​datový typ, který před klienty skrývá svou interní implementaci.
Úžasné je, že použitím abstrakce nám ADT umožňuje nemyslet na detaily implementace na nízké úrovni, ale pracovat s entitou na vysoké úrovni reálného světa (Steve McConnell).

Věřím, že při navrhování ADT musíte nejprve definovat rozhraní, protože rozhraní by nemělo záviset na interní reprezentaci dat v ADT. Po definování operací, které tvoří rozhraní, se musíte zaměřit na data, která budou implementovat zadané chování ADT. Díky tomu získáme určitou datovou strukturu – mechanismus, který umožňuje ukládat a zpracovávat data. Krása ADT je ​​zároveň v tom, že pokud chceme změnit vnitřní reprezentaci dat, pak nemusíme bloudit celým programem a měnit každý řádek kódu, který závisí na datech, která chceme změnit. ADT tato data zapouzdří, což vám umožní změnit chování objektů tohoto typu, spíše než celý program.

Výhody ATD

Používání ADT má mnoho výhod (všechny popsané výhody lze nalézt v Code Perfect od Steva McConnella):

• Zapouzdření detailů implementace.
  To znamená, že jakmile zapouzdříme implementační podrobnosti o tom, jak ADT funguje, poskytneme klientovi rozhraní, jehož prostřednictvím může komunikovat s ADT. Změnou detailů implementace se nezmění pohled klienta na provoz ADT.

• Snížená složitost.
  Abstrahováním od detailů implementace se soustředíme na rozhraní, tedy na to, co ADT umí, spíše než na to, jak se to dělá. ADT nám navíc umožňuje pracovat s podstatou skutečného světa.

• Omezení rozsahu použití dat.
  Pomocí ADT si můžeme být jisti, že data představující vnitřní strukturu ADT nebudou záviset na jiných částech kódu. V tomto případě je realizována „nezávislost“ ADT.

• Vysoký informační obsah rozhraní.
  ADT vám umožňuje reprezentovat celé rozhraní z hlediska entit předmětné oblasti, což, jak vidíte, zvyšuje čitelnost a informativnost rozhraní.

Steve McConnell doporučuje reprezentovat datové typy nízké úrovně, jako je zásobník nebo seznam, jako ADT. Zeptejte se sami sebe, jaký je tento seznam. Pokud představuje seznam zaměstnanců banky, zacházejte s ADT jako se seznamem zaměstnanců banky.

Takže jsme přišli na to, co je ATD, a nazvali jsme výhody jeho použití. Nyní stojí za zmínku, že při vývoji tříd v OOP byste měli myslet především na ADT. Jak již bylo řečeno, jak řekl Steve McConnell, neprogramujete v jazyce, ale v jazyce. To znamená, že budete programovat mimo jazyk, neomezující se na myšlenky ve smyslu polí nebo jednoduchých datových typů. Místo toho budete uvažovat z hlediska vysoké úrovně abstrakce (např. z hlediska tabulek nebo seznamů zaměstnanců). Třída není nic jiného než doplněk a způsob, jak implementovat koncept ADT. Můžeme dokonce reprezentovat třídu jako vzorec:
Třída = ATD + Dědičnost + Polymorfismus.
Proč byste tedy měli myslet na ADT při navrhování tříd. Protože nejprve se musíme rozhodnout, které operace budou tvořit rozhraní budoucí třídy, která data skryjeme a ke kterým poskytneme veřejný přístup. Musíme myslet na to, aby bylo rozhraní vysoce informativní, aby bylo možné kód snadno optimalizovat a testovat a jak můžeme poskytnout správnou abstrakci, abychom mohli přemýšlet o entitách reálného světa spíše než o podrobnostech implementace na nízké úrovni. Domnívám se, že až po definici ADT bychom měli přemýšlet o otázkách dědičnosti a polymorfismu.

Stojí za zmínku, že koncept ADT našel v OOP široké uplatnění, protože právě tento koncept doplňuje OOP a umožňuje snížit složitost programů v rychle se měnícím světě softwarových požadavků.

Tento článek jsem napsal proto, abych upozornil vývojáře na ATD za účelem zlepšení kvality práce a vývoje softwaru.

Použité zdroje:

Steve McConnell - "Perfektní kód";
Robert Sedgwick - Algoritmy v Javě.

1.2. Abstraktní datové typy

Většina pojmů představených v předchozí části se obvykle vyučuje v úvodním kurzu programování a měli byste je znát. Nové mohou být pouze abstraktní datové typy, proto nejprve proberme jejich roli v procesu vývoje softwaru. Nejprve porovnejme abstraktní datový typ se známým konceptem procedury.

Procedura, základní programovací nástroj, může být chápána jako zobecněný koncept operátora. Na rozdíl od vestavěných operátorů programovacího jazyka, které jsou omezeny ve svých možnostech (sčítání, násobení atd.), může programátor pomocí procedur vytvářet vlastní operátory a aplikovat je na operandy různých typů, nejen na základní. Příkladem takového operátora procedury je standardní podprogram násobení matic.

Další výhodou procedur (kromě možnosti vytvářet nové výpisy) je, že se na ně dá zvyknout zapouzdřeníčásti algoritmu umístěním všech operátorů odpovědných za určitý aspekt fungování programu do samostatné části programu. Příklad zapouzdření: Použití jediné procedury ke čtení vstupu libovolného typu a jeho ověření. Výhodou zapouzdření je, že víme, které zapouzdřené příkazy je potřeba změnit v případě problémů s chodem programu. Pokud je například nutné zorganizovat kontrolu vstupních dat na kladné hodnoty, potřebujeme změnit pouze několik řádků kódu a víme přesně, kde se tyto řádky nacházejí.

Definování abstraktního datového typu

Definujeme abstraktní datový typ(ATD) jako matematický model se sadou operátorů definovaných v tomto modelu. Jednoduchým příkladem ADT by byly množiny celých čísel s operátory sjednocení, průniku a rozdílu množin. V modelu ADT mohou mít operandy jako operandy nejen data definovaná ADT, ale také data jiných typů: standardní typy programovacího jazyka nebo ty definované v jiných ADT. Výsledek akce operátora může být i jiného typu, než jsou definovány v daném modelu ADT. Předpokládáme však, že alespoň jeden operand nebo výsledek jakéhokoli operátoru má datový typ definovaný v příslušném modelu ADT.

Dva hlavní rysy procedur, zobecnění a zapouzdření, diskutované výše, jsou vynikajícím popisem abstraktních datových typů. ADT si lze představit jako zobecnění jednoduchých datových typů (celá čísla, reálná čísla atd.), stejně jako procedura je zobecněním jednoduchých operátorů (+, - atd.). ADT zapouzdřuje datové typy v tom smyslu, že definice typu a všechny operátory, které lze na datech tohoto typu provést, jsou umístěny v jedné části programu. Pokud je nutné změnit implementaci ADT, víme, kde najít a co změnit v jedné malé části programu a můžeme si být jisti, že to nepovede k chybám nikde v programu při práci s těmito daty typ. Kromě toho, mimo část o definování operátorů ADT, můžeme typy ADT považovat za primární typy, protože deklarace typů formálně nesouvisí s jejich implementací. V tomto případě však mohou nastat komplikace, protože některé příkazy mohou být iniciovány pro více než jeden ADT a odkazy na tyto příkazy musí být v sekcích několika ADT.

Pro ilustraci základních myšlenek, které vedou k vytvoření ADT, zvažte postup zištný z předchozí části (výpis 1.3), který používá jednoduché operátory na datech abstraktního datového typu LIST (seznam celých čísel). Tyto operátory musí provést následující akce s proměnnou newclr typu LIST.

1. Vyprázdněte seznam.

2. Vyberte první prvek seznamu a pokud je seznam prázdný, vraťte hodnotu nula.

3. Vyberte další prvek seznamu a vraťte hodnotu nula, pokud neexistuje žádný další prvek.

4. Vložte do seznamu celé číslo.

Je možné použít různé datové struktury, se kterými lze efektivně provádět popsané akce. (Datové struktury podrobně probereme v tématu 2.) Pokud ve Výpisu 1.3 nahradíme odpovídající operátory výrazy

MAKENULL(newcJr);

w:= FIRST(newcJr);

w:= NEXT(newcfr);

INSERT(v, newclr);

pak bude jasný jeden z hlavních aspektů (a výhod) abstraktních datových typů. Datový typ můžete implementovat jakýmkoli způsobem a programy, které používají objekty tohoto typu, nejsou závislé na tom, jak je typ implementován - za to jsou zodpovědné procedury, které implementují operátory pro tento datový typ.

Vraťme se k abstraktnímu datovému typu GRAPH (Graph). Objekty tohoto typu vyžadují operátory, kteří provádějí následující akce.

1. Vyberte první nenabarvený vrchol.

2. Zkontrolujte, zda je mezi dvěma vrcholy hrana.

3. Vršek označte barvou.

4. Vyberte další nevyplněný vrchol.

Je zřejmé, že ostatní operátory, jako je vkládání vrcholů a hran do grafu nebo označení všech vrcholů grafu jako nevyplněných, zůstávají mimo rozsah zištné procedury. Různé datové struktury, které podporují tento datový typ, budou popsány v tématech 6 a 7.

Je třeba zdůraznit, že počet operátorů aplikovaných na objekty tohoto matematického modelu není omezen. Každá sada příkazů definuje samostatný ADT. Zde jsou příklady operátorů, které lze definovat pro abstraktní datový typ SET (Set).

1. MAKENULL(A), Tento postup udělá ze sady A prázdnou sadu.

2. UNION (A, B, C). Tento postup vezme dva "vstupní" argumenty, množiny A a B, a přiřadí sjednocení těchto množin svému "výstupnímu" argumentu, množině C.

3. VELIKOST (A). Tato funkce má argument množiny A a vrací objekt typu celé číslo rovnající se počtu prvků množiny A. Termín implementace ADT implikuje následující: překlad příkazů deklarací, které definují proměnné tohoto abstraktního datového typu, do programovacího jazyka, plus procedury pro každý příkaz provedený na objektech ADT. Implementace závisí na datové struktury, zastupující ATD. Každá datová struktura je postavena na základě základních datových typů použitého programovacího jazyka pomocí nástrojů pro strukturování dat dostupných v tomto jazyce. Struktury polí a záznamů jsou dva důležité prostředky pro strukturování dat možné v Pascalu. Například jednou z možných implementací proměnné S typu SET může být pole obsahující prvky množiny S.

Jedním z hlavních důvodů pro definování dvou různých ADT v rámci stejného modelu je, že na objektech těchto ADT musí být prováděny různé akce, tzn. definovat operátory různých typů. Tato synopse pokrývá pouze několik základních matematických modelů, jako je teorie množin a teorie grafů, ale různé implementace vytvoří různé sady operátorů založené na těchto modelech určitých ADT.

V ideálním případě je žádoucí psát programy v jazyce, jehož základní datové typy a operátory postačují k implementaci ADT. Z tohoto pohledu není jazyk Pascal příliš vhodným jazykem pro implementaci různých ADT, ale na druhou stranu je obtížné najít jiný programovací jazyk, ve kterém by bylo možné ADT takto přímo deklarovat. . Další informace o těchto programovacích jazycích naleznete v bibliografických poznámkách na konci tématu.

Abstraktní datový typ

Abstraktní datový typ (ATD) je datový typ, který poskytuje určitou sadu funkcí pro práci s prvky tohoto typu a také možnost vytvářet prvky tohoto typu pomocí speciálních funkcí. Celá vnitřní struktura tohoto typu je skryta vývojáři softwaru – to je podstata abstrakce. Abstraktní datový typ definuje sadu funkcí, které jsou nezávislé na konkrétní implementaci typu pro práci s jeho hodnotami. Konkrétní implementace ADT se nazývají datové struktury.

V programování jsou abstraktní datové typy obvykle reprezentovány jako rozhraní, která skrývají odpovídající implementace typu. Programátoři pracují s abstraktními datovými typy výhradně prostřednictvím svých rozhraní, protože implementace se může v budoucnu změnit. Tento přístup je v souladu s principem zapouzdření v objektově orientovaném programování. Silnou stránkou této techniky je právě skrytí provedení. Vzhledem k tomu, že venku je publikováno pouze rozhraní, pak dokud datová struktura toto rozhraní podporuje, budou nadále fungovat všechny programy, které pracují s danou strukturou s abstraktním datovým typem. Vývojáři datových struktur se snaží, aniž by měnili vnější rozhraní a sémantiku funkcí, postupně zdokonalovat implementace, zlepšovat algoritmy z hlediska rychlosti, spolehlivosti a použité paměti.

Rozdíl mezi abstraktními datovými typy a datovými strukturami, které implementují abstraktní typy, lze ilustrovat na následujícím příkladu. Abstraktní datový typ seznamu lze implementovat pomocí pole nebo lineárního seznamu pomocí různých metod dynamické alokace paměti. Každá implementace však definuje stejnou sadu funkcí, které by měly fungovat stejně (ve výsledku, nikoli v rychlosti) pro všechny implementace.

Abstraktní datové typy umožňují dosáhnout modularity softwarových produktů a mít několik alternativních zaměnitelných implementací jednoho modulu.

Příklady ADT

viz také

Odkazy

• Lapshin V. A. Abstraktní datové typy v programování

Nadace Wikimedia. 2010 .

Podívejte se, co je "Abstraktní datový typ" v jiných slovnících:

abstraktní datový typ- Datový typ (abstraktní třída) definovaný výčtem jeho metod a vlastností bez vytvoření jejich konkrétní implementace. Témata informační technologie obecně EN Abstrakt Data TypeADT ... Technická příručka překladatele

V teorii programování jakýkoli typ, jehož hodnoty jsou hodnoty nějakého jiného typu zabalené do algebraických typových konstruktorů. Jinými slovy, algebraický datový typ má sadu typových konstruktorů, z nichž každý ... ... Wikipedia

Integer, celočíselný datový typ (anglicky Integer), v informatice jeden z nejjednodušších a nejběžnějších datových typů v programovacích jazycích. Používá se k reprezentaci celých čísel. Množina čísel tohoto typu je ... ... Wikipedie

Tento termín má jiné významy, viz Set (významy). Množina je typ a datová struktura v informatice, je implementací množiny matematických objektů. Nastavit datový typ umožňuje uložit omezený počet hodnot... ... Wikipedie

Některé programovací jazyky poskytují speciální datový typ pro komplexní čísla. Přítomnost vestavěného typu zjednodušuje ukládání složitých hodnot a výpočtů na nich. Obsah 1 Aritmetika přes komplexní 2 Podpora v jazycích… Wikipedie

Tento termín má jiné významy, viz Rejstřík. Pointer diagram Pointer (ukazatel, anglicky pointer) je proměnná, jejíž rozsah hodnot se skládá z adres paměťových buněk a speciální hodnoty nulové adresy. ... ... Wikipedia

Jeden z typů algebraických datových typů, který se vyznačuje tím, že jeho konstruktory mohou vracet hodnoty, které nejsou jejich vlastního typu. Tento koncept je implementován v několika programovacích jazycích, zejména v ML a Haskell a ve ... ... Wikipedii

Vlastnost je abstraktní typ, v informatice, používaný jako „jednoduchý koncepční model pro strukturování objektově orientovaných programů“. Vlastnosti jsou jako mixiny, ale mohou zahrnovat definice metod tříd... ... Wikipedie

Binární strom je jednoduchým příkladem větvené propojené datové struktury. Datová struktura (anglicky data structure) softwarová jednotka, která umožňuje ukládání ... Wikipedie

- (vrcholový typ) v teorii typů, často označovaný jednoduše jako vrchol nebo „pevný“ symbol (⊤), univerzální typ, to znamená typ, který obsahuje všechny možné objekty v požadovaném typovém systému. Nejvyšší typ je někdy označován jako ... ... Wikipedie