Datové struktury
4 Datové struktury Zobrazení dat v počítači Každá hodnota v paměti počítače je zakódovaná do posloupnosti bitů. Využívá se přitom dvojková (binární) soustava, která používá dva znaky, „1“ (nebo „I“) a „0“, k vyjádření dvou možných stavů, ve kterých se mohou nacházet příslušné paměťové nebo počítací obvody počítače. Dvojková číslice, jako nejmenší zobrazitelná jednotka informace, jako jedna ze dvou možností, se nazývá bit (binary digit). Bit je technicky vyjádřen dvěma různými úrovněmi napětí (výskyt nebo absence impulsu), či jako různé hodnoty magnetizace na magnetických médiích. Pro kódování základní sady znaků v počítači se bity seskupují do vyšší jednotky, zvané byte. Byte je nejmenší adresovatelná jednotka paměti. Každý byte je označen pořadovým číslem (adresa bytu). 1 byte = 8 bitů = 1 znak Těchto 8 bitů dává 256 možných kombinací nul a jedniček, které se používají ke kódování znaků. Vzniká tak 8bitový znakový kód. Kombinace 8 bitů (v jednom bytu) jsou očíslovány od 0 do 255 (celkem 256 kombinací), seřazeny do tzv. ASCII tabulky (American Standard Code for Information Interchange) a je jim přiřazen význam (znak). Znaky ASCII tabulky: 0 - 31 speciální znaky, neviditelné, např. ovládání periferií (např. znak s kódem 10 je přiřazen příkazu přechodu na novou řádku). 32 - 126
anglická abeceda, číslice
127 - 255 prostor pro tzv. národní abecedy s odlišnými znaky, např. znakové sady LATIN2, ISO 1250, Windows CE pro jazyky střední a východní Evropy. Obdobný znakový kód u sálových počítačů (mainframes) se nazýval EBCDIC (Extended Binary Coded Decimal Interchange Code). Tyto dva znakové kódy byly nekompatibilní, tzn. přenos dat mezi těmito dvěma typy počítačů - PC a sálovými - nebyl možný bez speciálního hardwaru a softwaru. Ani standardní kód ASCII není ustálen v oblasti 127 - 255, kde jsou právě znaky národních abeced.
95
Datové struktury Příklad na odlišnost obou kódů: Písmeno A v ASCII 01000001
v EBCDIC 11000001
V bytech a vyšších jednotkách se měří kapacita vnitřní paměti a paměťových médií. Vyšší jednotky než byte jsou: KB kilobyte
=
210 bytů (1024 bytů)
MB megabyte
=
220 bytů (1048576 bytů)
GB gigabyte
=
230 bytů (1,074 . 109 bytů)
TB terabyte
=
240 bytů (1,010 . 1012 bytů)
Pomocí bytů se dál tvoří různě dlouhá slova, 2, 4, 8 bytů, která se zpracovávají jako celek a mohou obsahovat číslo, text nebo instrukci strojového kódu. Unicode Od roku 1991 prosazuje a vyvíjí Unicode Consorcium šestnáctibitové kódování pro znaky všech hlavních světových jazyků. Prakticky se zde projevuje vliv Internetu a potřeba volné elektronické výměny dokumentů bez závislosti na zdrojovém nebo cílovém prostředí. Unicode je šestnáctibitová kódovací tabulka, konstantní šířky, která vychází z ASCII. Zahrnuje 38885 znaků světových abeced, jako je např. ruština, arabština, anglosaština, řečtina, hebrejština, Thai a Sanskrit. Podmnožina Han představuje národní a průmyslové standardy Číny, Japonska, Korey a Tajwanu. 6400 znaků je vyhrazeno pro potřeby aplikací. Nevýhody kódování v Unicode jsou dvojnásobná délka textu než při osmibitovém kódování, fonty (sady znaků) obsahují 256 krát více znaků než osmibitové sady a problematická bude i kompatibilita s osmibitovým prostředím, některé programové kódy by se musely od základů přepsat. Standard ISO/IEC 10646 Tento znakový kód o šířce 4 byty může kódovat přes 2 miliardy znaků. Představuje snad již konečné schéma pro všechny možné znaky. Skládá se z řady kódovacích schémat. Schémata UCS (Universal Character Set) používají pevný počet bytů pro reprezentaci každého znaku: UCS-2 2-bytové schéma UCS-4 4-bytové schéma
96
Datové struktury Kódování češtiny Kódových tabulek pro češtinu vzniklo hned několik a různě se označují. Existují tabulky prakticky pro každou platformu (operační systém) a navíc se v našem prostředí uchytil kód bratří Kamenických v době, kdy se tyto standardy teprve tvořily. Kódové tabulky: PC LATIN2 (CP 852) tabulka pro MS DOS kód Kamenických alternativa pro MS DOS, (KEYBCS2, CP 895) ISO LATIN2 (ISO 8859-2) norma ISO (podle IBM i CP 912) standard pro UNIX a pro Internet MS Windows (CP 1250) vznikla z ISO záměnou několika znaků Poznámka: CP - code page (kódová stránka).
4.1
Způsoby uložení čísel v počítači Čísla, se kterými probíhají výpočty, nejsou takto dvojkově kódována, používá se jiný způsob uložení, který se ještě liší podle typu číselné hodnoty. S určitým typem hodnot bývají pak spjaty určité typy operací. Je třeba minimálně rozlišovat čísla celá (čísla typu integer) a čísla reálná (čísla typu real), dále ještě čísla s větším počtem platných číslic, pro jejichž uložení se volí tzv. dvojnásobná délka slova (double precision). Celá a reálná čísla jsou zcela odlišně zobrazena a základní operace s nimi jsou prováděny různými algoritmy, přesto, že je vyjadřujeme stejným znakem. Reálná čísla jsou zobrazena zaokrouhleně, přesnost se udává počtem platných cifer. Každé reálné číslo je totiž reprezentantem celého intervalu blízkých reálných čísel, kterých je v každém intervalu nekonečně mnoho. Výpočty s některými z nich (např. s iracionálními čísly) jsou zatíženy chybou v důsledku omezeného počtu platných číslic. Čísla celá se ukládají binárně v tzv. pevné řádové čárce. Detailněji viz dále u jednoduchých typů dat. Čísla desetinná jsou uložena v pohyblivé řádové čárce, (tzv. plovoucí čárka - floating point) ve formě mantisa a exponent. Mantisa je upravena tak, že její první platná číslice je hned za desetinnou (řádovou) čárkou a v souvislosti s posunem řádové čárky dojde k odpovídající změně exponentu, která tento posun vyrovná. Číslo 725 lze tedy vyjádřit jako 0.725 . 103 kde uložené číslice mantisy jsou 725 a exponent je 3. Mantisa je vyjadřována pomocí 24 bitů (3 byty), což zobrazí až 7 platných desítkových cifer (24 bitů = 6 hexadecimálních symbolů). 4.1.1 Šestnáctková soustava Kromě dvojkové číselné soustavy se využívá též soustava šestnáctková (hexadecimální) pro zkrácené vyjádření čtveřic bitů jedním šestnáctkovým symbolem. 97
Datové struktury Znaky šestnáctkové soustavy jsou spolu s desítkovým a binárním ekvivalentem uvedeny v následující tabulce: BIN HEX DEC 0000 0001 0010 0011
0 1 2 3 (třetí symbolu)
BIN HEX DEC
BIN HEX DEC
(0) 0100 4 (4) 1000 8 (8) (1) 0101 5 (5) 1001 9 (9) (2) 0110 6 (6) 1010 A (10) (3) 0111 7 (7) 1011 B (11) sloupec obsahuje desítkový ekvivalent čtveřic bitů, tj.
BIN HEX DEC 1100 C (12) 1101 D (13) 1110 E (14) 1111 F (15) jednoho šestnáctkového
nahrazují dvojciferné číslice 10 -15 neboť kombinací je 24 t.j. celkem 16 (s hodnotou 0 - 15). Základ hexadecimální soustavy je 16. Čím vyšší je základ používané číselné soustavy, tím méně znaků potřebujeme k vyjádření ekvivalentní desítkové hodnoty a naopak (viz dlouhé řetězce nul a jedniček v soustavě dvojkové - např. desítkové číslo 32761 je hexadecimálně vyjádřeno pouze čtyřmi znaky - 7FF9, ale dvojkově pomocí šestnácti znaků 0111111111111001). písmena A - F
4.1.2 Převody mezi číselnými soustavami Číselné soustavy používané pro zobrazování v počítači patří mezi soustavy poziční, tj. desítková hodnota každé číslice (znaku) závisí na její pozici vzhledem k řádové čárce. Váhy v jednotlivých pozicích jsou mocniny základu soustavy. U desítkové soustavy jsou to mocniny 10. Desítkové číslo 725 lze tedy pomocí vah rozložit takto: 7.102+2.101+5.100 Podobně postupujeme u čísel vyjádřených ve dvojkové nebo šestnáctkové soustavě, (nebo kterékoliv jiné soustavě) chceme-li zjistit jejich desítkový ekvivalent. Mocniny základu dvojkové soustavy 21 2
22 4
23 8
24 16
25 32
26 64
27 128
28 256
Příklady: Převod z dvojkové do desítkové soustavy 01010111(2) = 1.26+0.25+1.24+0.23+1.22+1.21+1.20 =87(10) Převod z šestnáctkové do desítkové soustavy B5(16) = 11.161+5.160 = 181(10)
98
29 512
210 1024
atd.
Datové struktury U opačných převodů z desítkové soustavy do jiné musíme zjistit, která nejvyšší mocnina základu té soustavy, do níž převádíme, je v desítkovém čísle obsažena, eventuelně kolikrát, jde-li o soustavy s vyšším základem než 2. Pak je třeba zapsat v příslušné pozici zbytek po odečtení mocniny od převáděného čísla (či po odečtení násobku mocniny)a celý postup opakovat pro výsledek (rozdíl). Obvykle se používá mechanický postup dělení čísla základem soustavy a zaznamenávání zbytků (u hexadecimální soustavy můžeme dostat možné hodnoty u zbytku 1 15, nebo-li 1 - F). Zbytky zapisujeme od konce, tj. od nejnižšího řádu výsledné převedené hodnoty. Dílčí výsledky opět dělíme základem soustavy a výsledek posledního dělení je číslice (příp. znak) nejvyššího řádu. Příklady: Převod z desítkové do dvojkové soustavy 87:2 = 43 zbytek 1 43:2 = 21 1 21:2 = 10 1 10:2 = 5 0 5 :2 = 2 1 2 :2 = 1 0 1
87(10) = 1010111(2)
jednička nejvyššího řádu zbývá nakonec
Převod z desítkové do šestnáctkové soustavy 181:16 = 11 zbytek 5 11
181(10) = B5(16)
Všimněte si, že pro záznam třímístného desítkového čísla 181 stačí dva hexadecimální znaky, z nichž každý se převede na čtveřici bitů. Převody mezi hexadecimální a dvojkovou soustavou Každý hexadecimální znak se vyjádří pomocí čtyř bitů a naopak. B5(16) = 1011 0101(2) (27+25+24+12+20 = 181(10)) 0101
0111(2) = 57(16)
(5.161+7.160 = 87(10))
4.2
Koncepce datových typů Množina dat, s níž pracujeme v programu, reprezentuje určitou realitu, je abstrakcí reality. Volba reprezentace dat je někdy obtížná, není vždy jednoznačně určena vlastnostmi počítače. Je třeba brát v úvahu operace, které se budou nad daty provádět. Vyšší programovací 99
Datové struktury jazyky dodržují většinou princip, že každá konstanta, proměnná, funkce i výraz jsou určitého typu (ale LISP, Smalltalk např. typy nemají). Konstanty, proměnné a funkce jsou tzv. datové objekty. Typ je množina hodnot kam konstanta patří, nebo, v případě proměnné, kterých může proměnná nabýt, kterých může nabýt výraz (složený z konstant, proměnných a operací a po vyhodnocení představující též jednu hodnotu), či které může generovat funkce (podprogram, který po vyvolání dodává do volajícího programu též hodnotu určitého typu). Typ se obvykle explicitně uvádí před použitím příslušného datového objektu v programu, označuje se to jako deklarace typu. Kompilátor pak podle deklarace volí vnitřní reprezentaci datového objektu v paměti, např. uložení v pohyblivé řádové čárce u čísel typu real. S určitými typy dat vždy souvisí určité operace, které se nad nimi provádějí. U datového objektu celé číslo jsou jen určité operace, které s ním lze provádět - sčítání, odčítání, násobení, celočíselné dělení (s potlačením zbytku) a operace pro získání zbytku po celočíselném dělení. Nad hodnotami logického typu jsou definovány operace konjunkce (logický součin), disjunkce (logický součet) a negace. Všechny výrazy relační (kde dochází k porovnávání numerických, ale i textových hodnot) mají výsledek logického typu. Tato deklarace typu dat je jakýsi prostředek pro udržení pořádku v datech. Při překladu programu překladač kontroluje, zda data a operace, které s nimi chceme provádět, patří k sobě. Tato typová kontrola je v různých jazycích různá. Některé datové typy jsou v programovacích jazycích předem definovány, jsou to tzv. standardní datové typy. Překladač je zná a stejně tak operace, které se s nimi mohou provádět. V jiných jazycích si programátor definuje typy podle své potřeby (v objektově orientovaných jazycích). Nový datový typ se definuje pomocí již dříve definovaných tzv. konstitučních typů. Je -li složen z hodnot téhož konstitučního typu, říká se mu bázový typ.
4.3 • • • • •
Standardní jednoduché typy dat integer - celočíselné hodnoty real (též float, double) - reálná čísla boolean (logical) - logické hodnoty, bývají označovány Ano/Ne, nebo True/False char - jednoznakové proměnné (character - znak) string - textové (znakové) řetězce
4.3.1 Vnitřní reprezentace hodnot typu integer Tyto hodnoty zaujímají pevný počet bitů (standardně 16, 32, tj. 2 nebo 4 byty). Zobrazí n se tak přirozená čísla z intervalu 0 - 216-1, tj. M=2 různých hodnot. Při n=16 je M nejvyšší možné celé číslo 65535. Všechna čísla se pak převádějí na přirozená (celá, kladná) čísla z tohoto intervalu transformací.
100
Datové struktury Jsou různé způsoby transformace, např.: kód s posunutou nulou (polovina možného rozsahu hodnot zastupuje nulu) x´ - transformované číslo M= 2n n=16 x - zobrazované číslo přímý kód (první, nejvyšší bit určen pro znaménko, zbývá polovina možných kombinací z 216) x´= x pro x>0 x´= M/2-x pro x<=0 x´= x+M/2
doplňkový kód x´= x x´= x+M
pro x>=0 pro x<0
Následující příklad ukazuje zakódovanou hodnotu +5 a -5 pro uvedené druhy tranformací a rozsahy uvedených kódování pro případ 16 bitového slova (65536 kombinací bitů). Poznámka: v paměti PC s procesorem Intel se na nižší adresu (1. byte) ukládají bity 0 - 7 a na vyšší adresu ( 2. byte) bity 8 - 15. hodnota +5 přímý kód
5
hodnota -5 nelze
0000000000000101
přímý se znam. bitem kód s posunutou nulou doplňkový kód
největší možné kladné číslo +65535
nejmenší možné záporné číslo nelze
1111111111111111
5
32773
+32767
-32767
0000000000000101
1000000000000101
0111111111111111
1111111111111111
32773
32763
+32767
-32768
1000000000000101
0111111111111011
1111111111111111
0000000000000000
5
65531
+32767
-32768
0000000000000101
1111111111111011
0111111111111111
1000000000000000
4.3.2 Vnitřní reprezentace hodnot typu real Číslo typu real obsazuje standardně 4 nebo 8 bytů v paměti. Délka 8 bytů je to v případě, požadujeme-li větší přesnost při výpočtech (více než 7 číslic).
101
Datové struktury 1. byte
2.byte
3. byte
4. byte
+ -
mantisa 6 hexadecimálních znaků = přesnost 7 dekadických míst
exponent v kódu s posunutou nulou
1.bit = znaménko čísla
Obr. 4.1 Zobrazení čísla typu real na slově o standardní délce 4 byty
4.3.3 Typ char S typem char (viz výše) bývají zavedeny následující funkce: 1. transformuje znak na pořadové číslo, které příslušný znak má v množině znaků, která připadá v úvahu, tj. v ASCII tabulce. 2. naopak transformuje číslo na znak s tímtéž pořadovým číslem.
4.3.4 Typ boolean Hodnoty logického typu zaujímají v paměti 1 byte přesto, že by měl stačit 1 bit. Byte je však základní adresovatelná jednotka paměti. Ukládají se hodnoty 1 pro true, 0 pro false.
4.3.5 Definované typy dat Je to např. typ definovaný výčtem - pro nečíselné údaje, které by bylo jinak třeba vyjádřit kódem (podle číselníku). V definici se vyjmenuje množina všech uvažovaných hodnot (maximálně 256 položek, ukládají se do jednoho bytu), např.: typ den=(pondělí, úterý, středa, čtvrtek, pátek, sobota, neděle) „den“ je jméno typu v závorce jsou jména hodnot, která pak mohou být použita jako konstanty v programu S:= středa přiřazovací příkaz proměnná S musí být typu den, příkazem získává hodnotu středa.
102
Datové struktury 4.4
Strukturované typy dat Jsou složené z prvků, s nimž lze manipulovat se všemi najednou. Strukturovaný typ charakterizuje: • typ struktury (rozlišujeme homogenní a heterogenní struktury) • uspořádání prvků (statické, dynamické struktury) • označení prvků (jednotlivé prvky se stejným názvem jsou rozlišeny pomocí indexů – počet indexů = počet rozměrů pole) • typ prvků (jednoduché, strukturované typy) • operace s prvky Homogenní struktura má komponenty téhož typu, na rozdíl od struktury heterogenní. Nemůže-li měnit datová struktura počet svých prvků ani jejich uspořádání během práce s nimi (během výpočtu), je to struktura statická . V opačném případě je dynamická . Zvláštní případy strukturovaných dat jsou objekty.
4.4.1 Typ pole Pole je homogenní, statická (v některých jazycích může být i dynamická ) struktura, se všemi komponenty téhož, kteréhokoliv definovaného typu. Pole může být: • jednorozměrné (vektor) • dvourozměrné (matice) • vícerozměrné (např. kubická matice). Prvky pole jsou označovány: 1. jménem pole 2. pořadovým číslem v poli - indexem A(5) identifikuje pátý prvek vektoru s názvem (identifikátorem) A Př.: B(3,2) druhý prvek ve třetím řádku matice s názvem B Celkový, případně maximální počet prvků pole musí být v případě statického pole předem deklarován. Stejně tak se deklaruje počet prvků dynamického pole vždy před jeho použitím. Musíme mít na paměti to, že např. pravoúhlé uspořádání prvků matice, jak je v našich představách neodpovídá skutečné reprezentaci matice v paměti počítače, protože se skutečné uložení do paměti počítače musí řídit jinými pravidly.
4.4.2 Typ záznam (synonyma record, věta) Záznam je statická struktura, může být heterogenní, t.j. komponenty nemusí být téhož typu. Prvky v jednom záznamu jsou označeny: 1. jménem záznamu 103
Datové struktury 2. identifikátorem položky Např. osoba . jméno označuje hodnotu položky jméno u záznamu osoba Záznam se používá jako konstituční typ (typ tvořící prvky) jiných datových struktur zejména souboru, pole.
4.4.3 Typ množina (set) Množina jako interní datový formát je statická, homogenní struktura. Na rozdíl od pole nedovoluje přístup na položky pomocí indexu, protože ukládá pouze informace o jejich existenci nebo neexistenci v dané množině (bitové pole). Přípustné operace s množinami jsou v různých programovacích jazycích standardně přidání prvku do množiny (kteréhokoliv - ne jako u zásobníku nebo fronty), odebrání prvku z množiny, sjednocení množin, průnik a rozdíl množin.
4.4.4 Typ stream (soubor) Dynamická homogenní struktura. Stream je datový typ nejčastěji přiřazovaný k souborům v diskové paměti. Dynamické struktury vyžadují dynamické přidělování paměti, neboť velikost paměti pro jejich reprezentaci není v době překladu známá a může se v průběhu zpracování programu měnit. Není zde tedy přesně předem definovaná délka (počet prvků) jako tomu bylo u pole. Přístupný je vždy právě jeden prvek určený polohou vhodného ukazatele (přístupové proměnné). Jsou definovány operace: • vkládání (zápis) prvku do souboru • výběr (čtení) prvku ze souboru.
4.5
Abstraktní datové typy Moderní jazyky mohou ze své škály standardních strukturovaných datových typů definovat nový typ, který vyhovuje určité představě při řešení konkretní úlohy. Tento přístup používání abstrakce - pracuje s obecným, zjednodušeným modelem struktury a realizuje ho programově. Abstraktní řídící struktury programu (sekvence, větvení a cyklus) umožnily kdysi v programování odpoutat se od úrovně strojových instrukcí a konkrétní podobu strojového kódu ponechat na starost překladači. Stejně tak i v případě abstraktních datových struktur se abstrahuje od toho, jak jsou data fyzicky uložena. Zejména v počáteční fázi návrhu programu nás nezajímá realizace použité datové struktury v počítači, neboli detaily tzv. implementace. Teprve později, při volbě jazyka, bude důležité jakými strukturami jazyka budeme abstraktní datovou strukturu reprezentovat a jak s ní budeme manipulovat. Nové datové struktury definované pomocí dříve definovaných struktur jazyka umožňují uplatňovat nové efektivnější algoritmy. 104
Datové struktury Implementace pak znamená realizaci datové, ale i řídící struktury (programu) na úrovni jazyka, reálnými prostředky daného počítače. Nejdříve se zvolí struktury pro reprezentaci abstraktní datové stuktury (častým prostředkem pro vytváření takové struktury je např. pole) a pak se navrhují algoritmy pro manipulaci s nimi (procedury).
4.5.1 Lineární abstraktní datové struktury Seznam Seznam je lineární, homogenní, dynamická datová struktura, představovaná posloupností prvků vytvářejících seznam. Uplatňuje se zejména v oblasti nenumerického zpracování. Lineárnost znamená, že ke každému prvku existuje nejvýše jeden bezprostředně následující prvek. Všechny prvky struktury jsou na stejné úrovni, bez vztahu nadřazenosti a podřazenosti. Seznam je buď jednosměrný - prvky v paměti jsou propojeny v jednom směru, nebo obousměrný - prvky jsou propojeny v obou směrech ( mohou se přidat i operace inverzní). Dále může být seznam aktivní - obsahuje jeden prvek, který je aktivní - nebo neaktivní - neobsahuje žádný aktivní prvek. Typické operace se seznamem mohou být: • vytvoření prázdného seznamu • první prvek seznamu nastaven jako aktivní • získání hodnoty aktivního prvku • vložení prvku na začátek seznamu • dotaz, zda seznam obsahuje aktivní prvek atd. Některé vyšší operace nad seznamy: • sloučení dvou nebo více seznamů do jednoho • rozdělení jednoho seznamu na dva nebo více • zjištění počtu prvků seznamu atd.
Obr. 4.2 Jednosměrný seznam
105
Datové struktury
Obr. 4.3 Obousměrný seznam Zásobník Zásobník je lineární, homogenní, dynamický typ. Tato struktura bývá někdy označována LIFO (Last In First Out), neboť manipuluje s prvky na jednom konci lineární struktury. Implementovat se dá i pomocí statického jednorozměrného pole nebo pomocí lineárního seznamu. Charakteristické operace: • vytvoření prázdného zásobníku • vložení nového prvku na vrchol zásobníku • získání hodnoty prvku na vrcholu • zrušení prvku na vrcholu atd.
Obr. 4.4 Princip zásobníku
Fronta (queue) Fronta je též lineární, homogenní, dynamický typ, označovaný jako FIFO (First In First Out). Manipuluje s prvky na obou koncích lineární struktury. Na jednom konci se prvky vkládají, na druhém získávají. Příklady operací: • vytvoření prázdné fronty • vložení nového prvku na konec fronty • získání prvku na začátku fronty • odstranění prvku ze začátku fronty atd.
106
Datové struktury
Obr. 4.5 Princip fronty 4.5.2 Nelineární abstraktní datové struktury Nelineární struktura umožňuje vyjádřit hierarchické vztahy mezi prvky. Tabulka Tabulka je homogenní, dynamická, nelineární struktura, jejíž funkce i operace jsou odvozeny od objektu odpovídajícímu v reálném světě pojmu "kartotéka". Každá položka tabulky (entita v řádku tabulky) je jednoznačně identifikovaná tzv. klíčem, který slouží jako vyhledávací kriterium a s nímž v podstatě pracují všechny operace nad tabulkou. Řádky tabulky tvoří charakteristiky příslušné entity sledované v tabulce. Hodnoty klíče v tabulce jsou navzájem různé, neopakují se. Na práci s tabulkami jsou založeny relační databázové systémy, podrobněji viz příslušná kapitola druhého dílu skript. Graf Graf je obecná nelineární struktura, která pracuje s hranami a uzly. Z jedné části grafu do druhé lze přecházet po specifikované cestě, což je posloupnost uzlů, mezi kterými existují hrany, vztahy (viz cesta tvořená seznamem adresářů a podadresářů). Pokud cesta začíná a končí na stejném uzlu, tvoří cyklus. Graf může být neorientovaný a orientovaný, kdy jeho hrany (spojnice) mají přiřazenou orientaci. Tím se dá vyjádřit hierarchický způsob uspořádání uzlů (dat), nebo postup jejich zpracování. Orientovaný graf může reprezentovat i program, kde jednotlivé příkazy jsou uzly. Zvláštním případem orientovaného grafu je seznam (jednosměrný). Acyklický graf se nazývá strom. Opět je na místě připomenout stromovou strukturu adresářů. Orientovaný strom je kořenový strom. Má tři typy uzlů: kořen (root), nevstupuje do něj žádná hrana, vystupovat může jedna nebo více hran, představuje nejvyšší úroveň struktury (např. hlavní adresář disku) koncové uzly (listy), hrany do nich vstupují, ale žádná nevystupuje, jde o hierarchicky nejnižší úroveň ostatní (běžné) uzly, mají jednu vstupní a jednu nebo více výstupních hran. Jedna vstupní hrana uzlu znamená, že je uzel prvkem vyšší, nadřazené úrovně, výstupní hrany znamenají, že se dále člení. Prvek nadřazené úrovně se také nazývá rodič (předek). Žádný prvek této struktury nemá víc než jednoho rodiče. Uzlů na nižší úrovni, ke kterým má prvek vztah, může být více a nazývají se děti (potomci). 107
Datové struktury Speciální případ orientovaného grafu je binární strom. Počet hran vystupujících z uzlu je omezen na maximálně dvě. Binární strom se využívá v některých algoritmech, např. při vyhledávání hodnoty v řadě hodnot půlením intervalu seřazených hodnot.
Obr. 4.6 Binární strom Literatura: [1] J. Honzík: Programovací techniky, 1986
108
Datové struktury
4
Datové struktury ................................................................................... 95 4.1 Zobrazení dat v počítači ..........................................................................................95 4.1 Způsoby uložení čísel v počítači ............................................................................97 4.1.1 Šestnáctková soustava ................................................................................................... 97 4.1.2 Převody mezi číselnými soustavami ............................................................................. 98 4.2 Koncepce datových typů .........................................................................................99 4.3 Standardní jednoduché typy dat...........................................................................100 4.3.1 Vnitřní reprezentace hodnot typu integer .................................................................... 100 4.3.2 Vnitřní reprezentace hodnot typu real ......................................................................... 101 4.3.3 Typ char ...................................................................................................................... 102 4.3.4 Typ boolean ................................................................................................................ 102 4.3.5 Definované typy dat .................................................................................................... 102 4.4 Strukturované typy dat ..........................................................................................103 4.4.1 Typ pole ...................................................................................................................... 103 4.4.2 Typ záznam (synonyma record, věta) ........................................................................ 103 4.4.3 Typ množina (set) ....................................................................................................... 104 4.4.4 Typ stream (soubor) .................................................................................................... 104 4.5 Abstraktní datové typy ...........................................................................................104 4.5.1 Lineární abstraktní datové struktury ........................................................................... 105 Seznam ................................................................................................................................... 105 Zásobník ................................................................................................................................. 106 Fronta (queue) ........................................................................................................................ 106 4.5.2 Nelineární abstraktní datové struktury ........................................................................ 107 Tabulka ................................................................................................................................... 107 Graf......................................................................................................................................... 107
109
