Řekli jsme, že na reprezentaci vlastností části reality byly vytvořeny matematické abstrakce jako čísla, geometrické útvary, funkce atd., které jsou modely zkoumané reality.
Datový typ v programovacích jazycích definuje možné hodnoty dat a operace nad hodnotami datového typu. Navíc mechanizmus třídy nám umožnil vytvářet nové, vlastní datové typy reprezentující matematický model části reprezentované reality potřebné pro řešení zadaného problému. Tak jsme v předcházejících kapitolách vytvořili třídy Auto, Sourozenec, Sourozenci, atd.
Jde tedy o více úrovní datových abstrakcí a jejich implementací. Na nejnižší úrovni jde o abstraktní model bitů v materiálním prostředí uchovávajících zpracovávaná data, využívajíc různých fyzikálních jevů, binárními hodnotami 0 - 1. Následují datové typy, které implementuje programovací jazyk. Dále jsou to uvedené vlastní datové typy, které jsme implementovali pomocí datových typů programovacího jazyka. Tento postup, vytváření datových abstrakcí vyšší úrovně pomocí datových abstrakcí nižší úrovně je možné potenciálně prodloužit tak daleko jak je potřebné pro řešení zadaného problému.
Zdůrazněme, že jde o princip, který je nezávislý na konkrétním jazyce i když jsme ho demonstrovali na jazyce, který používáme. V obecné rovině mluvíme o abstraktních datových typech (ADT).
ADT je matematický model společně s operacemi nad tímto modelem.
Používání ADT nám umožňuje abstrahovat od konkrétní reprezentace dat a implementace operací nad těmito daty. Pro tentýž program MojiSourozenci v článku 2.1jsme použili pro uložení sourozenců jednou pole a podruhé lineární spojový seznam. V závislost na jejich uložení jsme implementovali operace Sourozenci( ), dalsiSourozenec( ) a tiskSourozencu( ) ve třídě Sourozenci. Oddělili jsme tak vrstvu modelu pro reprezentaci sourozenců od vrstvy, která s tímto modelem pracuje. toto oddělení je důležité dodržet také při imlementaci, čím vzniká následující požadavek na ADT.
Oddělení jednotlivých vrstev abstrakce, vyžaduje přistupování k datům ADT jenom přes rozhraní, které tvoří jeho operace.
Program, který používá ADT nazýváme klientem a program, který je realizací ADT nazýváme implementací.
V případě třídy Auto v článku 1.4, která imlementuje datový typ auto jsme demonstrovali jazykové konstrukce umožňující pracovat s členskými proměnnými a možnost definovat operace nad objekty třídy pomocí metod třídy. Na druhé straně, některé operace, například změnu spotřeby, jsme v klientském programu nedělali pomocí metody, ale přímo pomocí přiřazení nové hodnoty členské proměnné. Pokud je takováto operace potřebná pro klientské aplikace, z pohledu ADT nutno definovat metodu
void zmenaSpotreby (float novaSpotreba) {
spotreba = novaSpotreba;
}
Metoda zmenaSpotreby( ) vyhovuje požadavku, aby jsme k datům ADT přstupovali pomocí operací rozhraní. Náš požadavek na ADT je přísnější, když požadujeme, aby data byla přístupná jenom pomocí operací ADT, jinými slovy, aby jinak přístupná pro klienty nebyla. Toto je možné v jazycích, které umožňují kontrolu přístupových práv.
V Javě budeme používat modifikátor přístupu private, o kterém jsme mluvili v článku 1.4.
V definici třídy Auto, potom členskou proměnnou spotreba budeme deklarovat
private float spotreba;
což zabezpečí její nepřístupnost jakémukoli klientskému programu. Členy programu, které mají uveden specifikátor private budeme nazývat privátní a nejsou přístupné vně třídy.
Členy třídy, které nemají uveden specifikátor, nebo mají uveden specifikátor public, budeme v dále textu nazývat veřejné.
Nyní známe všechny prostředky pro realizaci ADT v Javě a můžeme se zabývat vyjádřením rozhraní. Vykonání operace rozhraní implementované metodou, znamená její volání s argumenty správných typů. Na její používání tedy potřebujeme znát typ návratové hodnoty, jméno metody a typy jejích parametrů. Tuto informaci nazýváme signatura metody. V Javě můžeme signaturu metody získat z její deklarace vynecháním jmen formálních parametrů v hlavičce jakož i jejího těla, například
void zmenaSpotreby (float)
Rozhraní potom můžeme vyjádřit signaturami všech veřejných metod. Formálně v deklaraci třídy vynecháme všechny neveřejné členy a z deklarací veřejných metod vytvoříme uvedeným postupem signatury.
Pokud by jsme ve třídách Sourozenci označili členské proměnné specifikátorem private získáme vyjádření signatury její metod ve tvaru
class Sourozenci {
// ADT rozhrani
Sourozenci(Sourozenec)
void dalsiSourozenec(Sourozenec)
void tiskSourozencu()
}
Na vyjádření rozhraní ADT jsme využili formalizmu Javy. Poznamenejme, že Java má vlastní prostředek pro zápis rozhraní a jeho implementaci pomocí třídy, avšak v užším smyslu, protože se v něm nemůže nacházet konstruktor. Vytvoření hodnoty ADT je však jednou ze základních operací ADT.
ADT jako obecný mechanizmus je právě východiskem pro typ class ve zmíněném jazyce SIMULA 67. Připomeňme, že jeho motivace byla dekompozice rozsáhlých problémů. ADT se staly významným nástrojem pro modulární programování, které slouží na organizování velkých moderních softwarových systémů. V procesu jejich návrhu vytvoříme aplikační program na řešení problému, který používá potřebné ADT a specifikujeme jejich rozhraní, například ve tvaru, který jsme si pro Javu uvedli výše. Poznamenejme, že v tomto případě ještě neexistuje implementace ADT. Následně můžeme vytvořit několik implementací ADT a porovnat jejich efektivnost.
Například operace nalezení k-tého sourozence je v případě implementace sourozenců pomocí pole O(1) a při implementaci pomocí spojového seznamu je O(n).
V matematice množina jako souhrn nějakých prvků je po její specifikaci neměnná. Pojmem dynamická množina budeme označovat souhrn prvků, který se může zvětšovat, zmenšovat nebo jinak měnit.
Příkladem dynamické množiny je například množina někoho sourozenců. Na její realizaci v Javě jsme využili pole a lineární spojový seznam. Oba tyto mechanizmy přímočaře vycházejí z organizace fyzické paměti jako posloupnosti bytů, kde k jednotlivým bytům přistupujeme pomocí jejich adresy, kdy první byte má adresu 0, další o 1 větší atd.
K prvkům pole pak přistupujeme pomocí jejich indexů tak, že adresa prvku s indexem i se určí ze vztahu
adresaPrvkuSIndexemI = adresaZačátkuPole + i * velikostPrvku;
Poznamenejme, že adresa prvního prvku tedy prvku s indexem 0, je adresaZačátkuPole. Pro přístup k prvkům pole musíme tedy o každém poli znát adresuZačátkuPole, velikostPrvku a navíc jeho velikost, aby jsme nepřistoupili k datům, které nepatří prvkům pole.
K prvkům lineárního spojového seznamu přistupujeme pomocí adresy následujícího prvku, která je uložena v předcházejícím prvku v seznamu. Pro přístup k seznamu potřebujeme znalost adresy prvního prvku, tj. opět začátku, což nám umožní přístup k druhému prvku, atd., dokud adresa následujícího prvku není hodnota označující, že další prvek není.
Obě tyto struktury můžeme použít na implementaci dynamických množin.
Nad datovým modelem dynamická množina musíme mít ve smyslu její definice dvě základní operace
Jednotlivé prvky jsou identifikovány hodnotou položky klíč, přičemž můžou obsahovat i jiné položky. Klíčem může být například jméno nebo rodné číslo. Z uvedeného vidíme, že více prvků může mít stejnou hodnotu klíče.
Další typickou operací nad dynamickými množinami potom může být operace
Datový model dynamická množina s definovanými operacemi je základem mnoha ADT, které budou předmětem našeho studia. Jednotlivé ADT ve smyslu naší definice jsou užitečné v klientských aplikačních programech pro řešení různých problémů. Budeme se zabývat také různými způsoby jejich implementace.