Datové struktury a datové typy

Datové struktury a datové typy. Základní datové typy. Odvozené datové typy. Základní datové struktury. Odvozené datové struktury.

Tomáš Bayer | [email protected] ˇ Katedra aplikované geoinformatiky a kartografie, Pˇrírodovedecká fakulta UK.

ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

1 / 53

Obsah pˇrednášky 1

Základní datové typy

2

Datové struktury

3

Základní datové struktury ˇ Promenná Pole Struktura Objekt

4

Odvozené datové struktury Seznam Zásobník Fronta Prioritní fronta Strom


2 / 53


1. Základní datové typy Pˇrehled základních datových typu: ˚ celoˇcíselné, logické, reálné a znakové. Nalezneme prakticky ve všech programovacích jazycích. U každého jednoduchého datového typu definována jeho velikost v bajtech a rozsah. Vyjádˇrení v ruzných ˚ cˇ íselných soustavách: dvojková (binární) soustava: 0011, desítková (decimální) soustava (znaky 0-9): 1987, šestnáctková (hexadecimální) soustava (znaky 0-9, a-f): 16af. ˇ Celocíselné datové typy: Reprezentace diskrétních jevu. ˚ Se znaménky (signed) cˇ i bez znaménka (unsigned). Liší se rozsahem a pˇresností. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

3 / 53


2. Pˇrehled celoˇcíselných datových typu˚ v Javeˇ Rozsah pˇredstavován maximální a minimální hodnotou, které muže ˚ ˇ promenná tohoto datového typu nabývat. Závisí na poˇctu bitu˚ které jsou použity na uložení cˇ íselné hodnoty v ˇ pameti. Unsigned: (0, 2n − 1). Signed (−2n−1 , 2n−1 − 1). ˇ Pokud nevíme, jaký datový typ použít, a nemáme nejaké speciální požadavky, zpravidla používáme typ int. Datový typ

Velikost

Rozsah

byte short int long

8b

-128;127

16b

-32768;32767

32b

-2E09;2E09

64b

-9E18;9E18


4 / 53


3. Znakový typ Datový typ char. Používán pro práci se znaky, ruzná ˚ kódování a sady znaku. ˚ Má vlastnosti celoˇcíselného datového typu bez znaménka, jeho hodnota odpovídá kódu pˇríslušného znaku v ASCII tabulce. Na jednotlivé znaky se lze dívat jako na celá cˇ ísla, lze na neˇ aplikovat stejné aritmetické cˇ i relaˇcní operátory jako na datový typ int. Nabývá hodnot (0, 28 − 1). Zápis znakového typu: znakem uzavˇreným do apostrofu: ˚

char c='A'; prostˇrednictvím escape sekvencí:

char c='\n'; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

5 / 53


4. Kódování ASCII (American Standard Code for Information Interchange): 127 znaku˚ (písmena, cˇ íslice, spec. znaky), 7b + 1b. ˇ celkem 6 speciálních kódování: CP 1250, ISO 8859-2, Problémy s CJ, Latin 2... UNICODE: 16b kódování, 2 nástupce ASCII, 1 114 112 znaku, ˚ napˇr. UTF-8. Ukázka Escape sekvencí: Escape sekvence \n \r \t \\ \' \"

UNICODE \u000A \u000D \u0009 \u005C \u002C \u0022

Význam Nová ˇrádka Návrat na zaˇcátek ˇrádku Tabulátor ˇ Zpetné lomítko Apostrof Uvozovky


6 / 53


5. ASCII tabulka


7 / 53


6. Logický datový typ Datový typ bool, (v Javeˇ boolean). Nabývá dvou hodnot: pravda true, nepravda false. Obeˇ hodnoty lze vyjádˇrit prostˇrednictvím celoˇcíselných hodnot: 1=true 0=false. Pˇríklad:

boolean result=false; boolean result=0; ˇ Uplatnuje se zejména pˇri konstrukci logických podmínek.

if (result==true) if (result) ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

8 / 53


7. Reálné datové typy Reálná cˇ ísla R které lze vyjádˇrit nekoneˇcneˇ dlouhým desetinným rozvojem, jsou pˇredstavována desetinnými cˇ ísly. Používána pro vyjádˇrení spojitých jevu. ˚ Výpoˇcty v pomalejší než nad celými cˇ ísly. Duležitá ˚ volba správného datového typu. ˇ Zápis reálných císel: 2 formy zápisu. S pevnou rˇádovou cˇ árkou (Fixed-point). ˇ ˇ chybou. Promenná relativní chyba, malá cˇ ísla zatížena vetší

123.456 10.0 V semilogaritmickém tvaru (Floating-point). ”Pˇríliš malá” nebo ”pˇríliš velká” cˇ ísla, stejná relativní chyba. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

9 / 53


8. Reálné datové typy v Javeˇ ˇ Pro vedecké výpoˇcty používáme datový typ double (s dvojnásobnou pˇresností). Pˇri výpoˇctu s datovým typem float dochází k znaˇcným zaokrouhlovacím chybám.

float: 7 platných desetinných míst double: 15 platných desetinných míst

Datový typ float double

Velikost 32b 64b

Rozsah -1.4E45;3.4E48 -4.9E-324,1.7E308;


10 / 53

Datové struktury

9. Datové struktury ˇ uchovávána v datových Data používaná programy v pameti strukturách. Data lze reprezentovat ruznými ˚ datovými typy. Pro efektivní práci s daty nutné zvolit vhodnou datovou strukturu a odpovídající datový typ. ˇ Delení datových struktur: ˇ Datové struktury deleny do dvou kategorií: Základní datové struktury: ˇ r ve všech programovacích jazycích. Vyskytují se témeˇ ˇ ˇ svuj Za behu programu nemení ˚ rozsah. Odvozené datové struktury: Nazývány jako abstraktní datové struktury. ˇ Casto implementovány jako objekty. ˇ ˇ svuj Za behu programu mohou menit ˚ rozsah. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

11 / 53

Datové struktury

ˇ 10. Delení datových struktur ˇ Delení do dvou skupin: Základní datové struktury: ˇ Promenná Pole Struktura Objekt

(Variable). (Array). (Structure). (Object).

Odvozené datové struktury: Seznam Strom Zásobník Fronta Tabulka

(List). (Tree). (Stack). (Query). (Table).


12 / 53

Základní datové struktury

ˇ Promenná

ˇ 11. Promenná ˇ poˇcítaˇce. Pojmenované místo v pameti Je v ní uložena hodnota urˇcitého datového typu. ˇ Deklarace promenné: ˇ Promenné vytváˇreny pomocí deklarace. ˇ V deklaraci uveden datový typ promenné a její identifikátor.

int i; double k; ˇ Typ promenné: ˇ ˇ Specifikace typu promenné ovlivnuje: ˇ A) Urˇcuje množinu hodnot, kterých promenná muže ˚ nabývat. ˇ potˇrebné pro její uložení. B) Množství pameti ˇ ˇ C) Operace, které lze s promennou provádet. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

13 / 53


ˇ Promenná

ˇ 12. Schéma pameti


14 / 53


ˇ Promenná

ˇ 13. Alokace pameti ˇ ˇ ˇ Zpusob, ˚ jakým je promenným pˇridelován pamet’ový prostor v RAM. ˇ 3 metody alokace pameti Statická alokace. Alokace na zásobníku. ˇ Alokace na halde. ˇ Statická alokace pameti: ˇ pˇridelena ˇ ˇ Pamet’ pevneˇ na celou dobu behu programu. ˇ ˇ realizováno již v dobeˇ pˇrekladu. Pˇridelování pameti Rozsah datových struktur musí být znám již v dobeˇ pˇrekladu, což není vždy možné. ˇ Práce s promennými velmi rychlá a efektivní. ˇ Používáno pro promenné deklarované v hlavním programu.

double x; int cislo; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

15 / 53


ˇ Promenná

14. Alokace na zásobníku Zásobník (Stack). ˇ Používána pro lokální promenné, které jsou deklarovány v procedurách cˇ i ˇ funkcích ci pˇri rekurzi. ˇ je alokována pˇri volání procedury/funkce, po jejím ukonˇcení je Pamet’ ˇ uvolnena. ˇ Lokální promenné zanikají, jejich hodnoty jsou nedostupné. ˇ nepotˇrebné promenné ˇ Dochází k úspoˇre pameti, nezabírají místo. ˇ ˇ provádeno ˇ v opaˇcném poˇradí než jejich pˇridelování. ˇ Uvolnování úseku˚ pameti ˇ Nedochází ke fragmentaci pameti. Nejrychlejší... Pˇri pˇrekroˇcení kapacity zásobníku chyba „Stack Overflow“.

double dist(double a, double b) { double d=Math.sqrt(a*a+b*b); return d; } ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

16 / 53


ˇ Promenná

ˇ 15. Dynamická alokace pameti Dynamická alokace na haldeˇ (Heap, realizován binárním stromem): ˇ pˇridelována ˇ Pamet’ na žádost programu operaˇcním systémem, nikoliv kompilátorem. ˇ Na tyto úseky se odkazujeme pomocí speciálních promenných typu ukazatel (pointer). ˇ ˇ ˇ Nepotˇrebná pamet není uvolnována implicitne, musí provést uživatel cˇ i Garbage Collector. ˇ ˇ nemusí být provádeno ˇ Uvolnování úseku˚ pameti v opaˇcném poˇradí než její ˇ ˇ pˇridelování, dochází k fragmentaci pameti. Pˇri pˇrekroˇcení kapacity haldy chyba „Heap Overflow“.

Point p=new Point(100,100); Výhody dynamické alokace: ˇ Promenné existují jen po dobu, kdy jsou potˇreba. ˇ Možnost vytváˇret dynamické datové struktury potˇrebné velikosti za behu programu. Jejich velikost nemusí být známa v dobeˇ pˇrekladu. Nevýhody dynamické alokace: ˇ Dynamicky alokované promenné nemají svuj ˚ jednoznaˇcný identifikátor, pˇrístup prostˇrednictvím ukazatele. Pomalejší pˇrístup k datum ˚ než u statické alokace.


17 / 53


ˇ Promenná

16. Problémy pˇri dynamické alokaci ˇ Dusledky ˚ nevhodné práce s dynamicky alokovanou pametí: ˇ Pˇrístup na nealokované místo v pameti Pˇrepsání vlastních dat cˇ i havárie programu. Zpravidla vede k pádu nebo si pˇrepsání vlastních dat. ˇ pameti ˇ Pˇrístup do uvolnené Zpravidla vede k pádu programu. ˇ pameti ˇ Neuvolnení Pˇri nároˇcných výpoˇcetních procesech muže ˚ nastat nedostatek ˇ pameti vedoucí k pádu aplikace. ˇ Vetšinou se chyba nijak neprojeví. ˇ ˇ uvolní. Operaˇcní systém po skonˇcení behu programu tuto pamet’ ˇ ˇ Opakované uvolnování téže pameti Opakované volání destruktoru. Zpravidla vede k pádu aplikace. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

18 / 53


ˇ Promenná

ˇ 17. Druhy promenných ˇ ˇ ˇ Promenné se liší dle zpusobu ˚ pˇridelování pameti: ˇ Globální promenné: ˇ programu, zanikají po ukonˇcení programu. Vytvoˇreny pˇri spuštení ˇ Existují po celou dobu behu programu. ˇ Nazývány jako statické promenné. ˇ Lokální promenné: Deklarované ve funkcí cˇ i procedurách. Vznikají v okamžiku volání procedury/funkce, zanikají pˇri ukonˇcení procedury/funkce. ˇ Existují pouze po dobu behu procedury/funkce. ˇ Nazývány jako automatické promenné, alokovány v zásobníku. ˇ Dynamické promenné: ˇ ˇ pˇríkazem. Vznikají za behu programu na základeˇ provedené alokace pameti Mohou zanikat automaticky nebo manuálneˇ (pˇríkazem). Nejsou vázány na procedury/funkce. ˇ Tomáš Bayer | [email protected] Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.) 19 / 53 Alokovány na heapu. (Katedra aplikované


ˇ Promenná

18. Pˇriˇrazovací pˇríkaz ˇ Pˇriˇrazuje promenné hodnotu odpovídajícího datového typu. ˇ Dochází k inicializaci hodnoty promenné.

i = 10; k = 13; ˇ Promenné vystupují: v aritmetických operacích (výrazy)

dist = sqrt((xb - xa) * (xb - xa) + (yb - ya) * (yb - ya)); v logických operacích (podmínky)

if (eps > 0) pˇredávány jako parametry funkcí cˇ i procedur

distance (xa, ya, xb, ya); ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

20 / 53


ˇ Promenná

19. Konstanty ˇ ˇ Císelné údaje, jejichž hodnota se nemení. V praxi napˇr. π, e, g, c, i. ˇ Konstanty celoˇcíselné, reálné, znakové a ˇretezcové konstanty. ˇ Celocíselné konstanty: Celoˇcíselné konstanty lze zapisovat v osmiˇckové, desítkové cˇ i šestnáctkové ˇ soustave. Desítková soustava: 9234 Osmiˇcková soustava: 0156 //Zacina nulou Šestnáctková soustava: 0x26AF //Zacina 0x Konstanty jsou standardneˇ datového typu int.

R = 123456; Hodnota typu long, za cˇ íselnou hodnotou symbol L.

A = 12345678910L; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

21 / 53


ˇ Promenná

20. Znakové konstanty Lze je zapsat následujícími zpusoby. ˚ Jedním znakem uzavˇreným do apostrofu: ˚

'A' 'B' 'C' ˇ Císelnou hodnotou v ASCII tabulce (osmiˇcková, šestnáctková soustava):

'\101' '\102' '\103' '\41' '\42' '\43'

//osmickova //sestnactkova

Zápis speciálních znaku˚

'\n' '\r' '\\' '\' Posloupností znaku˚ \’uXXXX’, kde XXXX pˇredstavuje kód znaku v kódování UNICODE:

'\u000A' ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

22 / 53


ˇ Promenná

21. Reálné konstanty Lze je zapsat následujícími zpusoby. ˚ S pevnou ˇrádovou cˇ árkou:

3.14159 9.80665 V semilogaritmickém tvaru

0.314159e-1 0.980665e-1 Reálná konstanta je standardneˇ datového typu double. ˇ znak F. Zápis v datovém typu float, za poslední cˇ íslici umísten

A = 0.1e10F; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

23 / 53


ˇ Promenná

ˇ ezcové ˇ 22. Ret konstanty Zapisuje se jako posloupnost znaku˚ uzavˇrená v uvozovkách. ˇ Pro tvorbu ˇretezcových konstant platí stejné zákonitosti jako pro tvorbu ˇ ezcové ˇ znakových konstant. Ret konstanty mohou být na rozdíl od znakové konstanty tvoˇreny více než jedním znakem. Lze je zapsat následujícími zpusoby ˚ . Jeden cˇ i více znaku˚ do uvozovek (nikoliv do apostrofu). ˚

"Ahoj"; Hodnoty v ASCII/UNICODE tabulce:

"Prvn\u00ED program\n v jazyce Java"; ˇ Sˇcítání ˇretezcových konstant prostˇrednictvím operátoru +.

"prvni slovo"+"druhe slovo"; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

24 / 53


ˇ Promenná

23. Pˇretypování Pˇri pˇriˇrazovacích operacích dochází ke konverzím mezi ruznými ˚ datovými typy ⇒ pˇretypování. ˇ je konvertována na typ Pˇriˇrazovaná hodnota (na pravé strane) ˇ ˇ promenné jíž pˇriˇrazujeme (na levé strane). ˇ ˇ Výsledkem zmena datového typu promenné. Varianty pˇretypování: ˇ Pˇriˇrazení reálné hodnoty celoˇcíselné celoˇcíselné hodnote: Hodnota zaokrouhlena odˇríznutím desetinné cˇ ásti (nedochází k zaokrouhlení podle standardních pravidel!) ˇ Pˇriˇrazení hodnoty s vyšší pˇresností do promenné s nižší pˇresností: Pokud hodnota mimo rozsah výsledného datového typu, muže ˚ vést k nedefinovatelnému výsledku Implicitní vs. explicitní pˇretypování. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

25 / 53


ˇ Promenná

24. Implicitní a explicitní pˇretypování Implicitní pˇretypování ˇ ˇ Pˇretypování promenné s nižším rozsahem na promennou s vyšším rozsahem. Probíhá automaticky, nedochází pˇri ní ke ztráteˇ informací. Poˇradí: byte->short->int->long->float->double.

float a = 50; double b = 30; b = a;//implicitni konverze Explicitní pˇretypování ˇ ˇ Pˇretypování promenné s vyšším rozsahem na promennou s nižším rozsahem. ˇ Neprobehne automaticky,nutno vynutit ji uvedením cílového datového typu. Dochází ke ztráteˇ informací. Poˇradí: double->float->long->int->short->byte.

a = b;//ztrata presnosti, nelze provest a = (float)b;//explicitni konverze ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

26 / 53


ˇ Promenná

25. Smíšené konverze Nastávají, pokud do aritmetických operací vstupují operandy smíšeného typu. Cílem co nejmenší ztráta pˇresnosti pˇri aritmetických operacích. Zákonitosti: A) Pokud je jeden z operandu˚ typu double, bude výsledkem operace datový typ double. B) Pokud je jeden z operandu˚ typu float, bude výsledkem operace datový typ float. C) Pokud je jeden z operandu˚ typu long, bude výsledkem operace datový typ long. Pozor na zlomky:

int a = 5;//int int b = 10;//int int c = a / b;//vysledek=0 ˇ Správne:

int a = 5.0;//double int b = 10;//int


27 / 53


ˇ Promenná

26. Aritmetické operátory Slouží k realizaci základních aritmetických operacích. Vyhodnocování z leva do prava dle priority: ˇ ˇ A) nejprve operace násobení/delení/celoˇ císelné delení, B) poté se vyhodnotí zbývající operace. ˇ Zmena priority vyhodnocování s použitím závorek. ˇ být stejný. Poˇcet pravých a levých závorek by mel

int a = 3 + 3 * 3;//a=12 int a = (3 + 3) * 3;//18

Pˇrehled aritmetických operátoru: ˚ Operátor

Popis

+

Sˇcítání

-

Odeˇcítání

*

Násobení

/

ˇ Delení

%

ˇ Zbytek po celoˇcíselném delení.


28 / 53


ˇ Promenná

27. Operátory pˇriˇrazení ˇ Zkrácený zápis bežných aritmetických operací. ˇ ˇ zápis aritmetických operací. Umožnuje efektivnejší Pˇrehled operátoru˚ pˇriˇrazení.

Operátor a+=5 a-=5 a*=5 a/=5

Úplný zápis a=a+5 a=a-5 a=a*5 a=a/5


29 / 53


ˇ Promenná

28. Operátory inkrementace a dekrementace ˇ Zvyšování cˇ i snižování hodnoty promenné o 1. Pˇredstavují zdvojené operátory ++ resp. −−. Pˇredcházející inkrementace/dekrementace: ˇ pˇred promennou. ˇ Operátory inkrementace/dekrementace umísteny Nejprve se provede inkrementace/dekrementace, poté pˇriˇrazovací pˇríkaz.

int a = 5, b = 5; int c = ++a;//a=6, c=5; int d = --b;//b=4, d=5; Následná inkrementace/dekrementace: ˇ za promennou. ˇ Operátory inkrementace/dekrementace umísteny Nejprve se provede pˇriˇrazovací pˇríkaz, poté inkrementace/dekrementace.

int a = 5, b=5; int c = a++;//a=6, c=6; int d = b--;//b=4, d=4; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

30 / 53


ˇ Promenná

29. Relaˇcní operátory Použití pˇri konstrukci logických podmínek. Binární i unární booleovské operátory. Ruzná ˚ priorita, nejvyšší negace, poté konjunkce, ostatní. ˇ Zmena poˇradí závorkami. Pˇrehled relaˇcních operátoru: ˚ Operátor

Popis

== != && || ! < > <= >=

Rovná se Nerovná se Logický souˇcin Logický souˇcet Negace Menší ˇ Vetší Menší nebo rovno ˇ nebo rovno Vetší


31 / 53


Pole

30. Pole ˇ ˇ chápaných jako jeden Posloupnost promenných stejného typu uložených v pameti celek. ˇ Každé pamet’ové místo reprezentováno prvkem pole. K prvku pole pˇristupujeme prostˇrednictvím indexu, Index pole nesmí být pˇrekroˇcen !

ˇ datový typ, identifikátor, poˇcet prvku˚ pole. Deklarace pole: Uváden ˇ Jednorozmerné pole: ˇ ˇ Prvky pole tvoˇrí promenné, nikoliv pole nejakého jiného pole. Pˇredstavuje ho n prvku˚ s indexy 0, ..., n − 1.

double pole[10]; //deklarace pole s deseti prvky pole[0]; //prvni prvek pole pole[9]; //posledni prvek pole


32 / 53


Pole

ˇ 31. Vícerozmerné pole ˇ Pole oznaˇcováno jako N-rozmerné. ˇ ˇ Prvky N-rozmerného pole tvoˇrí prvky (N − 1)-rozmerného pole. ˇ používáno dvojrozmerné ˇ ˇ Nejˇcasteji pole, N = 2. Prvky dvojrozmerného pole ˇ tvoˇrí prvky jednorozmerného pole.


33 / 53


Pole

ˇ 32. Dvojrozmerné pole Tvoˇreno m ˇrádky a n sloupci, pˇredstavuje matici. ˇ Rádkový index: 0, ..., m − 1. Sloupcový index: 0, ..., n − 1. ˇ poslední index, tj index nejvíce vpravo. Nejrychleji se mení ˇ Deklarace dvourozmerného pole:

double pole[6][11]; //deklarace 2D pole 6x10 prvku pole[0][0]; //prvni prvek pole pole[5][10]; //posledni prvek pole ˇ Využití dvojrozmerných polí: reprezentace tabulek, rastru. ˚ Pro práci s poli používány cykly (opakování cˇ inností). ˇ ˇ V nekterých jazycích pole deklarována jako dynamické promenné. ˇ v Operace s 1D neuspoˇrádaným polem (pˇrístup, hledání) jsou provádeny lineárním cˇ ase, s 2D neuspoˇrádaným polem v kvadratickém cˇ ase. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

34 / 53


Pole

33. Pole v Javeˇ S polem v Javeˇ pracujeme prostˇrednictvím odkazu (tj. podobneˇ jako s objekty). 2 kroky: Deklarace odkazu na pole Ve tvaru datovy_typ [] identifikator. Neuvádíme poˇcet prvku. ˚

double [] pole; ˇ ⇒vyvolání výjimky. S polem zatím nelze pracovat, nebyla alokována pamet’ ˇ Alokace pameti ˇ ˇ uvádíme poˇcet prvku. Vytvoˇrení vlastního pole ⇒pˇridelení potˇrebné pameti, ˚ Nastavení odkazu tak, aby ukazoval na vytvoˇrené pole.

pole=new double[10]; Oba kroky lze spojit do jednoho:

double [] pole=new double[10]; Prvky pole celoˇcíselného/ reálného typu automaticky inicializovány na hodotu 0, prvky polí odkazu˚ (tj. referencí) inicializovány na hodnotu null. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

35 / 53


Pole

34. Ilustrace práce s polem v Javeˇ


36 / 53


Pole

35. Další operace s polem v Javeˇ Délka pole: Pˇredstavuje poˇcet prvu, ˚ lze zjistit prostˇrednictvím length.

pole.length; Hodnota length-1 je nastavována jako nejvyšší horní index pole.

pole[pole.length-1]; //Posledni prvek pole pole[pole.length]; //Prekrocen index, prace s nealokovanou Inicializované pole: Pole inicializované pˇredem danými hodnotami, nepoužívá se konstrukce s new (pouze konvence).

double [] pole={2.0, 4.4,17.85}; //1D pole double [][] pole2d={{2.0, 4.4},{17.85, 0.3}, {10.9, 6.4}}; ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

37 / 53


Pole

36. Kopírování polí v Javeˇ Nelze použít pˇriˇrazovací pˇríkaz, provádí kopírování odkazu, ˚ nikoliv kopírování skuteˇcného obsahu polí.

int [] pole1={1,2,3}; int [] pole2=new int [3]; pole2=pole1;//Zkopirovani odkazu, nikoliv obsahu pole! Kopírování obsahu pole po prvku

int [] pole1={1,2,3}; int [] pole2=new int [3]; for (int i=0;i<pole1.length;i++) pole2[i]=pole1[i]; Použití pˇríkazu arraycopy

arraycopy(Zdroj,pocat_index,Cil,cilovy_index,pocet_prvku); Ukázka kopie dvou polí

int [] pole1={1,2,3}; int [] pole2=new int [3]; System.arraycopy(pole1,0,pole2,0,pole1.length); ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

38 / 53


Pole

37. Ukázka nevhodného kopírování polí


39 / 53


Pole

38. Ukázka správného kopírování polí


40 / 53


Struktura

39. Struktura (Záznam) ˇ Skupina promenných ruzných ˚ typu, ˚ které se dohromady chovají jako celek. Na rozdíl od pole se jedná o strukturu heterogenní. Deklarace struktury: ˇ Jednotlivé položky struktury deklarovány jako samostatné promenné.

struct Point { double x, y; //Bod ma souradnice x,y }; //Ukoncena strednikem Pˇri práci se strukturami je používán princip kvalifikace. ˇ Nejprve vytvoˇrena promenná datového typu struktury. ˇ Pro pˇrístup k jednotlivým složkám struktury používáme promennou datového ˇ ˇ typu struktury doplnenou jménem promenné.

Point p; //Promenna typu point p.x=1024768.57; //nastaveni souradnice x p.y=800000.33; //Nastaveni souradnice y ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

41 / 53


Objekt

40. Objekt V objektoveˇ orientovaném programování objekty pˇredstavují komponenty nehmotného charakteru. ˇ u. Jsou abstrakcí a zjednodušením svých hmotných protejšk ˚ Vykazují urˇcité vlastnosti a chování.

ˇ Rozhraní objektu: umožnuje vzájemnou komunikaci objektu. ˚ ˇ Podrobnosti v kapitole venované OOP. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

42 / 53


Objekt

41. Rozhraní objektu Objekt tvoˇren: Datovou strukturou ˇ Pˇredstavována promennými ruzných ˚ datových typu. ˚ ˇ Ovlivnuje vlastnosti objektu. ˇ Tato cˇ ást objektu bývá oznaˇcována jako soukromá, z vnejšku je pˇred jinými objekty ukryta (princip zapouzdˇrení). Metodami ˇ Definují operace, které je možno s daty provádet. Urˇcují chování objektu. Tato cˇ ást objektu bývá oznaˇcována jako veˇrejná. ˇ Patˇrí mezi dynamické promenné: vytváˇreny a rušeny na pokyn programátora v libovolný okamžik. ˇ S dynamicky vytvoˇrenými objekty pracujeme ve speciální cˇ ásti pameti zvané halda (heap). ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

43 / 53

Odvozené datové struktury

Seznam

42. Seznam Datová struktura, tvoˇrí ji uspoˇrádaná posloupnost položek. ˇ Položky uspoˇrádány podle urˇcité hodnoty, tzv. klíce. ˇ pˇrímo za sebou⇒ každá Jednotlivé položky nemusejí být umísteny položka obsahuje odkaz na následující položku. Patˇrí mezi rekurzivní struktury, každá položka obsahuje odkaz na položku stejného typu. Vlastnost seznamu: Rychlé pˇridávání prvku˚ na poˇcátek/konec seznamu (O(N)). Vhodný pro procházení prvku˚ popoˇradeˇ ⇒ sekvenˇcní uspoˇrádání dat. Nevhodný pro náhodný pˇrístup k prvkum. ˚ Typy seznamu: ˚ ˇ Jednosmerný seznam ˇ Obousmerný seznam Kruhový seznam ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

44 / 53


Seznam

43. Ukázky seznamu. ˚ ˇ Jednosmerný seznam: každý prvek seznamu odkazuje na pˇredchozí resp. následující prvek seznamu. První resp. poslední prvek seznamu neodkazuje nikam (NULL).

seznamu pak obsahuje odkaz na první prvek seznamu, resp. první prvek seznamu obsahuje odkaz na poslední prvek seznamu.

ˇ Obousmerný seznam: každý prvek seznamu obsahuje odkaz na pˇredchozí a následující prvek seznamu. První a poslední prvek seznamu neodkazují nikam (NULL). ˇ Kruhový seznam: jednosmerný i ˇ obousmerný. Poslední prvek ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

45 / 53


Zásobník

44. Zásobník Ze zásobníku odebíráme data v opaˇcném poˇradí, než v jakém jsme je ˇ uložili. do nej Pracovat lze pouze s prvkem, který je na vrcholu zásobníku. Reprezentuje model LIFO (Last In - First Out). ˇ ˇ veci ˇ V bežném životeˇ model zásobníku napˇr. batoh, vyndaváme z nej ˇ ukládáme. v opaˇcném poˇradí, než je do nej Použití pˇri zpracovávání dat v sekvenˇcním poˇradí. Dno zásobníku: ˇ prvek v zásobníku. Nejspodnejší Pˇridán do zásobníku jako první. Vrchol zásobníku: ˇ prvek v zásobníku. Nejvrchnejší Pˇridán do zásobníku jako poslední. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

46 / 53


Zásobník

45. Ukázka zásobníku

Použití: náhrada rekurze, vyhodnocování výrazu... ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

47 / 53


Fronta

46. Fronta Z fronty odebíráme data ve stejném poˇradí, v jakém jsem je do ní uložili. Pracovat lze pouze s prvkem, který je na cˇ ele fronty. Reprezentuje model FIFO (First In-First Out). Využití pˇri sekvenˇcním zpracování dat. Ve fronteˇ nemužeme ˚ pˇredbíhat. Existuje i fronta s pˇredbíháním, tzv. prioritní fronta. Konec fronty: ˇ Prvek na poslední pozici ve fronte. Do fronty pˇridán jako poslední. ˇ Celo fronty: ˇ Prvek na první pozici ve fronte, Do fronty pˇridán jako první. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

48 / 53


Fronta

47. Ukázka fronty a kruhové fronty


49 / 53


Prioritní fronta

48. Prioritní fronta Nazývána fronta s pˇredbíháním. Charakteristika prioritní fronty: Varianta fronty, u které hraje roli ohodnocení prvku. Ohodnocení realizováno ohodnocovací funkcí. ˇ Prvek s vyšší prioritou muže ˚ pˇrebehnout prvek s nižší prioritou. Princip prioritní fronty: 1 2

Prvky pˇridávány do fronty v poˇradí, v jakém jsou na vstupu. Prvky odebírány z fronty na základeˇ ohodnocení (priority prvku). Prvky s nejvyšší prioritou odebrány jako první.

ˇ Casté použití v geoinformatice, souvislost s technikou Sweep Line (zametací pˇrímka). Ohodnocením napˇr. souˇradnice x, y , vzdálenost, váha, atd. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

50 / 53


Strom

49. Strom Takové uspoˇrádání dat, kdy každý prvek má nejvýše jednoho pˇredchudce ˚ a muže ˚ mít více než jednoho následníka. Strom tvoˇren vrcholy (uzly). Typy uzlu: ˚ Listy: Uzly bez následníka. Není k nim pˇripojen žádný podstrom. Koˇren: Uzel bez pˇredchudce=koˇ ˚ ren. Existuje práveˇ 1. Vnitˇrní uzly: Uzly, které nejsou listem ani koˇrenem. Patˇrí mezi rekurzivní datové struktury: každý uzel je souˇcasneˇ ˇ koˇrenem stromu a zárovenˇ listem stromu vyšší úrovne. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Datové struktury geoinformatiky a datové a kartografie, typy. Pˇrírodovedecká fakulta UK.)

51 / 53


Strom

ˇ 50. Delení stromu˚ Podle maximálního poˇctu potomku, ˚ stupenˇ uzlu n. Unární strom: n = 1 (Seznam). Binární strom: n = 2. Ternární strom: n = 3. Stromy vyšších ˇrádu˚ se zpravidla nepoužívají.


52 / 53


Strom

51. Uspoˇrádání dat v binárním stromu Pro každý uzel U platí, že všechny údaje v levém podstromu jsou ˇ než U. menší než U a všechny údaje v pravém podstromu vetší ˇ Tato organizace umožnuje efektivní práci s daty uloženými ve stromu: napˇr. vyhledávání se složitostí O(log(N)). Ukázka binárního stromu.


53 / 53

Datové struktury a datové typy

Recommend Documents