- globálne
- to sú všetky premenné definované v hlavnom programe. Sú viditelné zo všetkých častí programu. Vznikajú na začiatku programu a "žijú" si svoj život počas celého behu programu. Túto vlastnosť nazývame statickosť - tieto premenné nevznikajú a nezanikajú v priebehu programu.
- lokálne
- to sú premenné definované v podprogramoch. Sú viditelné, len z v tomto podprograme a v jeho podprogramoch. Vzniknú počas behu programu počas volania podprogramu. Zabezpečí to obslužný podprogram pre volanie podprogramov a užívateľ do toho procesu nemože zasiahnuť.
- dynamické
- to sú premenné, ktoré vytvára a ruší užívateľ. Prístup ku takýmto premenným je pomocou adries - smerníkov. Tieto adresy možu byť globálne alebo lokálne. Pokiaľ je viditelná smerníková premenná je viditelný aj dynamický objekt. Životnosť objektu je plne v réžii užívateľa - programátora. Tieto premenné vznikajú v časti pamäti zvanej halda Každý vytváraný objekt v halde je obmedzený veľkosťou 64kB!.
| Bios-data Dos-data rezidenty | |
| Ide prostredie | |
| Program | Kód programu - preložené príkazy max. 64kB |
| Dáta programu - globálne premenné max. 64kB | |
| Zásobník programu - miesto pre lokálne premenné max. 64kB | |
| Halda - oblasť pamäti môže siahať až po adresu 640kB Jej maximálna veľkosť je určená veľkosťou rezidentov | |
- Získanie väčšieho priestoru pre premenné
- Možnosť vytvoriť objekt - napr. pole väčšie ako 64kB (pole smerníkov na pole)
- Možnosť vytvoriť netypický štruktúrovaný typ - trojuholníková matica
- Lepšia správa pamäti - keď premenné nepotrebujem, môžem ich zrušiť a pamäť uvoľniť pre iné premenné
- Vytváranie dynamických dátových štruktúr
- Syntax:
- <identifikátor premennej>:^<typ>
znak určuje, že bude vytvorená smerníková premenná do ktorej sa už dajú zapisovať adresy. - Postup práce:
- zadeklarovať smerníkovú premennú
- vytvoriť premennú v halde, adresu priradiť do smer. premennej
- pracovať s objektom v halde
- zrušiť objekt v halde
- Operácie so smerníkovými premennými
- Smerníkové premenné môžeme použiť
- v priraďovacom príkaze
- v testovaní na rovnosť, nerovnosť v podmienkach
- ako parametre podprogramov
- Preddefinovaná konštanta
- nil - je špeciálna dodnota adresy, ktorú nemôže žiadny objekt v pamäti nadobudnúť. Používame ju na test, či premenná ukazuje na nejaký objekt v pamäti.
- Používanie smerníkovej premennej
- nech smerníková premenná je zadefinovaná nasledovne:
smer:^integer;
potom v príkazovej časti premenná
smer - predstavuje adresu
smer^ - predstavuje objekt ktorého adresa je v prem. smer zapísaná. Jeho typ je v tomto prípade integer a môžme ho použiť všade tam, kde obyčajnú integer premennú.
- procedure new(<identifikátor smer. premennej>)
- vytvorí v halde objekt podľa typu smerníkovej premennej
- návratová hodnota je smerník na tento objekt
- ak v halde nie je dosť miesta, program končí s chybou - function memavail:longint;
- vráti veľkosť voľnej pamäte v halde. Používame na otestovanie, či sa nový objekt ešte zmestí do haldy, pred volaním funkcie new. - procedure release(<identifikátor smer. premennej>);
- uvoľní z haldy objekt na ktorý ukazuje smer. premenná. Táto premenná je ešte k dispozícii, ale jej pamäť už nie je "chránená" a ďalši nový objekt v halde dostane túto pamäť za svoju. V prípade ak tento objekt nie je v pamäti posledný sú uvoľnené aj objekty, ktoré boli vytvorené až po ňom.
- Príklad
type pole=array[1..100] of real;
var up: ^pole; {vytvorili sme ukazovatel na pole}
i: integer;
Begin
new(up); {v halde sa vytvoril objekt typu pole, jeho adr. je v up}
for i:= 1 to 100 do up^[i] := i*i; {naplnenie pola v halde hodnotami}
{lubovolne pouzitie pola}
release(up); {pamat v halde je uvolnena}
End.- Príklady
- Napíš program na hru "červík - požierač kvetiniek
Ovládanie pomocou šipiek
Po stlačení F10 sa na obrazovke objaví helpové menu
1. Options
2. Save games
3. Load games
4. Return to games - Napíš podprogramy
push pre odloženie stringu do haldy
pop pre zobratie stringu z haldy
isempty pre logickú hodnotu TRUE ak je halda prázdna
pomocou podprogramov načítaj mená ukončené prazdnym reťazcom a vypíš ich v opacnom poradí
Pozn. Nezabudni pamäť uvolniť a vytvárať nový objekt len keď je dosť pam. - Napíš program na tvorbu bitmapy 32x32 bodov, tak aby vždy bolo možné zavolať undo.
Po voľbe 1-3 sa obrazovka prepíše novými textami a po vybavení sa vrátime do menu. Po voľbe 4 pokračujeme v hre.- Napíš program na hru "červík - požierač kvetiniek
- procedure new(<identifikátor smer. premennej>)
- vytvorí v halde objekt podľa typu smerníkovej premennej
- návratová hodnota je smerník na tento objekt
- ak v halde nie je dosť miesta, program končí s chybou - function maxavail:longint;
- vráti veľkosť najväčšej súvislej oblasti v halde. Používame na otestovanie, či sa nový objekt ešte zmestí do haldy, pred volaním funkcie new. - procedure dispose(<identifikátor smer. premennej>);
- uvoľní z haldy objekt na ktorý ukazuje smer. premenná. Táto premenná je ešte k dispozícii, ale jej pamäť už nie je "chránená" a ďalši nový objekt v halde dostane túto pamäť za svoju. V prípade ak tento objekt nie je v pamäti posledný vzniká resp. sa zväčšuje v halde diera.
- Príklad
-
type pole=array[1..100] of real;
var up: array[1..10] of ^pole; {vytvorili sme pole ukazovatelov na pole}
i,j: integer;
Begin
for i:= 1 to 10 do
if maxavail> sizeof(pole) then new(up[i]) else halt 1;
{v halde sme vytvorili 10 objektov typu pole, mozno chapat ako 10 riadkov matice}
for i:= 1 to 10 do
for j:= 1 to 100 do up[i]^[j] := i+j; {naplnenie pola v halde hodnotami}
{lubovolne pouzitie pola}
dispose(up[5]); {pamat 5.teho riadku matice je uvolnena}
for i:= 5 to 9 do up[i] := up[i+1];
up[10] := nil; {matica ma len 9 riadkov}
for i:= 1 to 9 do dispose(up[i]);
End. - Príklady
- Napíš program na evidenciu priateliek:
Chceme evidovať: meno, čís. tel., pozn
Predpokladáme že počet bude <=100- Dátová štruktúra
- - Pole 100 ukazovateľov na záznam o priateľke
- Počet evidovaných priat. v premennej pocet
Výpis - prejde pole ukazovateľov od 1 po pocet a vypíše
Pridaj - vytvorí nový záznam a adresu zapíše do poľa ukazovateľov
Zruš - vypýta meno, nájde, opýta sa, zruší a do poľa zapíše nil
Hladaj - nájde meno
Hladaj dalej- hladá ďalšie meno
Save, load - zapíše a načíta z disku ako txt súbor - Napíš jednoduchý textový editor Parametre: max 2000 riadkov, max. dĺžka riadku 250 znakov
pohyb kurzora šipky, Home, End, PgUp, PgDn
nový riadok Enter, zruš riadok Ctrl Y
vkladanie znakov do riadku
zápis na disk, čítanie z disku- Napíš program na evidenciu priateliek:
- procedure getmem(<Var identifikátor smer. premennej>,<veľkosť v B>);
- vytvorí v halde objekt danej veľkosti a adresu priradí do premennej.
Výhoda je, že veľkosť môže byť menšia ako veľkosť typu prem.
- ak v halde nie je dosť miesta, program končí s chybou - function maxavail:longint;
- vráti veľkosť najväčšej súvislej oblasti v halde. Používame na otestovanie, či sa nový objekt ešte zmestí do haldy, pred volaním funkcie new. - procedure freemem(<identifikátor smer. premennej>, <veľkosť vB>);
- uvoľní z haldy objekt na ktorý ukazuje smer. premenná. Veľkosť musí byť rovnaká ako sme použili u getmem
- Príklady
- Vytvor štruktúru pre odpamätanie matice m x n reálnych čísel, kde m,n<=16 000
Načítaj m,n a vytvor v halde takú štruktúru - Načítaj N prirodzené, vytvor trojuholníkovú maticu, naplň hodnotami a[i,j]=i+j a potom ju vypíš na obrazovku
- Napíš program, ktorý svoj zdroják načíta do haldy.
Pamätáme si len taký počet riadkov koľko ich je v súbore,
V každom riadku si pamätáme len toľko znakov koľko ich je v riadku
- Vytvor štruktúru pre odpamätanie matice m x n reálnych čísel, kde m,n<=16 000
- Vlastnosti:
- Prvky jednej štruktúry sú rovnakého typu - podobne ako u poľa,
prvky vznikajú a zanikajú počas behu programu (podobne ako u súborov) a v čase kompilácie programu sa nedá
určiť koľko ich bude a ani nie je dané ohraničenie pre maximálny počet prvkov štruktúry.
Každý prvok má dve časti - dátovú a adresnú
V adresnej sa nachádza jeden alebo viac alebo viac ukazovateľov na taký istý prvok.
V každej dynamickej štruktúre má jeden prvok významné postavenie - vytvára vstupný bod tejto dynamickej štruktúry - nazývame ho koreň, v jeho adresnej časti sú smerníky na ďalšie vstupné prvky podštruktúr. Prvok, ktorý je posledný v štruktúre má všetky smerníky nil a volá sa list. Ak je celá štruktúra prázdna - ukazovateľ na jej vstupný prvok ukazuje na nil. - Lineárne dynamické štruktúry - lineárne zoznamy
- Je definovaná rekurentne.
Prázna štruktúra je lineárna.
Nech koreň ukazuje na štruktúru, ktorá je lineárna potom celá štruktúra je lineárna.- Schéma
-
Smernik
(koreň)-> 1. prvok
(koreň^)-> 2. prvok ->...-> n. prvok -> nil
- Deklarácia
- Ukážem na príklade.
type uzaz=^zaz; {musí byť prvé} zaz = RECORD meno:string; dlžoba:longint; nasl:uzaz; END; {struktura je vytvorená} Var koren,novy:uzaz; Begin Koren:=nil; End.
Podľa spôsobu práce lineárne zoznamy delíme na- zásobník - LIFO
- front - FIFO
- všeobecný (utriedený) lineárny zoznam
Základné operácie s lineárnymi dynamickými štruktúrami:
Zásobník Front Všeobecný push - vlož na začiatok put - vlož na koniec insert - vlož do utriedeného pop - vyber zo začiatku get - vyber zo začiatku take up - zruš zvolený prvok isempty - log. funkcia
test prázdnostiisempty - log. funkcia
test prázdnostiisempty - log. funkcia
test prázdnostilist - výpis fronty list - výpis lin. zoznamu - Použitie
- Zásobník
- Používa sa na dočasné odloženie stavu premenných ak potrebujeme "vybaviť" niečo dôležité a keď dôležitosť vybavíme načítame si zo zásobníka
stav premenných a môžeme pokračovať v hlavnej práci.
Niektoré typické úlohy
1. Naprogramuj hru life tak aby sme sa mohli medzi obrazovkami-stavmi mohli presúvať dopredu a dozadu.
(zistený stav baktérií v každom čase odložíme do zásobníka) a ak zvolíme "cúvnuť" v čase jednoducho načítame stav z haldy.
2. Naprogramuj výpočet postfixového zápisu matematického zápisu výrazu
(postup výpočtu je nasledovný:
zľava hľadáme operátor +-*/ a aplikujeme na dve čísla pred ním - čísla a operátor nahradíme výsledkom operácie.
Napr. 5 9 8+4 6**7+* = 5*[(9+8)*(4*6)+7] - Fronta
- FIFO - prvý dnu idú aj prvý von. Použitie napr. na simulácie stavu čakárne u lekára
Niektoré typické úlohy
1. Majme "bludisko" zadané tabuľkou. Naprogramuj hľadanie najkratšej cesty z bodu A do bodu B v tabuľke.
Myšlienka - do bodu A sme sa dostali na 0 krokov a označíme si všetky políčka kam sa dá dostať na 1 krok a potom označíme všetky políčka na dva kroky atď. Je výhodné si nájdené políčka zapisovať do frontu.
2. Prezretie stromu po poschodiach (prehľadávanie do šírky) - Všeobecný zoznam
- 1. Pozri úlohu kreslenie grafu jedným ťahom
- Úlohy:
-
Vypracuj program zásobník s nasledovným menu: PUSH, POP, KONIEC
Vypracuj program front s nasledovným menu: PUT, GET, LIST, KONIEC
Vypracuj program LinZoz s nasledovným menu: INSERT, TAKEUP, KONIEC
- Halda
- Halda sa niekedy volá aj prioritná fronta. Vo fronte kto prvý príde je prvý aj zavolaný (prax u doktora býva často iná)
V halde má prvok prioritu podľa ktorej je obslúžený. Halda má tieto vlastnosti:
Na haldu sa môžme pozerať ako na strom, kde pre každý vrchol platí, že je väčší alebo rovný ako jeho deti
(poradie detí je náhodné)
všetky základné operácie (pridaj, zruš robíme s logaritmickou náročnosťou.
oproti stromu nemusíme vyvažovať - je vždy vyvážený
dá sa dobre realizovať v poli prvkov
Haldu možno realizovať v stromovej štruktúre ale často sa používa obyčajné pole.
Stromová štruktúra je vždy vyvážená - len v poslednej úrovni môže na pravej strane chýbať niekoľko "synov".
Nech máme N prvkov v poli A. Každý prvok na adrese i má svoje deti na súradniciach [2i) a [2i+1] alebo naopak každý prvok s adresou [j] má rodiča na súradnici [j div 2].
Stavba haldy:
Nech máme vybudovanú haldu o počte N prvkov a priberieme do haldy prvok N+1. (N+1) postupne delíme 2 (rodič) aby sme napravili vlastnosť, že rodič musí byť väčší ako dieťa. (necháme nový prvok vybublať smerom nahor - táto procedúra sa v objekte HALDA volá Nahor().
Výber najväčšieho prvku z haldy
už vieme, že najväčší prvok "býva" na adrese [0] a jeho výpis je ľahký. Oprava haldy spočíva v krokoch
1. N-tý prvok zoberieme a zapíšeme na adresu [0] a potom aby sme halde vrátili jej základnú vlastnosť necháme ho bublať smerom nadol - na svoje väčšie dieťa. Procedúra Nadol(). - Stromové štruktúry
- Sú definované rekurentne.
- Prázna štruktúra je stromová štruktúra.
- Nech koreň ukazuje na konečný počet štruktúr, ktorá sú disjuktné a sú stromovými štruktúrami, potom celá štruktúra je stromová štruktúra.
Pozn.: Lineárny zoznam je najjednoduchšia stromová štruktúra.- Pojmy:
-
- Koreň - najvyšší vrchol stromu
- Úroveň vrchola - koreň je prvá úroveň, jeho nasledovníci druhá atď.
- Výška stromu - maximálna úroveň stromu
- List - vrchol, ktorý nemá nasledovníkov
- Usporiadaný strom - strom s usporiadanými vetvami
- Stupeň vrchola - počet priamych nasledovníkov vrchola
- Binárne stromy - sú usporiadané a stupeň každého vrchola je 2
(všetky vrcholy lavého podstromu sú <= ako hodnota v koreni,
všetky vrcholy pravého podstromu sú >= ako hodnota v koreni) - Viaccestné stromy - stupeň väčší ako 2
- Vyvážený strom - Výšky podstromov sa líšia najviac o 1
- Úloha:
- Vygeneruj 30 náhodných čísel z <10, 99> a zapíš do binárneho stromu.
Program strom; type uzaz=^zaz; zaz = RECORD cislo: integer; lavy, pravy: uzaz; END; Var koren, novy, pom: uzaz; i:integer; Begin new(koren); {koren naplnim vopred} koren^.cislo:=10+random(89); koren^.lavy:=nil; koren^.pravy:=nil; for i := 1 to 29 do {tu naplnam ostatne vrcholy stromu} Begin new(novy); novy^.cislo:=10+random(89); novy^.lavy:=nil; novy^.pravy:=nil; {novy prvok vytvoreny} {teraz ho treba pripnut do stromu na spravne miesto} pom:=koren; while pom<>novy do {nakoniec sa novy pripne do retaze} if pom^.cislo>novy^.cislo then {ak nove cislo je mensie ako "koren"} begin if pom^.lavy=nil then pom^.lavy:= novy; {ak na mieste kam novy patri je nil daj tam novy} pom:=pom^.lavy {posun na nasledovnika} end else begin if pom^.pravy=nil then pom^.pravy:= novy; pom:=pom^.pravy; end; End; End. - Použitie:
- Binárne stromy sa používajú na rýchle (binárne) vyhľadávanie prvku štruktúry. Štruktúru zapíšeme do binárneho stromu ak počet vyhľadévaní je porovnatelný resp. väčší ako počet pridávaní a vypúšťaní prvkov zo štruktúry. Ku tým istým dátam môžeme vytvoriť viac vyhľadácích kľúčov.
- Typické úlohy:
-
- Hľadaj prvok
- Nakoľko sa nikdy v ceste nebudeme musieť vracať stačí použiť sekvenciu
a nemusíme siahať ku rekurzii.
- zistíme či koreň nie je hľadaný prvok
- podľa veľkosti hľadaného prvku pokračujeme vľavo alebo vpravo
- opakujeme pokiaľ prvok na ktorý ukazujeme nie je hľadaný resp. nil
- Pridaj prvok do stromu
- Postup ako pri hľadaní, opakujeme hľadanie až sa vetva na ktorú máme ísť rovná nil - tam potom nový prvok pripneme.
- Zruš prvok v strome
- treba porozmýšlať ako zrušiť prvok, ktorý nie je listom.
Môžu nastať 3 prípady:- Rušený prvok je listom - tu stačí jeho predkovi povedať, že sa stal nilom a vyhodiť ho z haldy
- Rušený prvok má jedného potomka - adresu u predka prepíšem na adresu potomka a potom prvok možno vyhodiť z haldy
- Rušený prvok má dvoch potomkov - nájdem v ľavom podstrome najväčší prvok (alebo v pravom najmenší) - tento prvok má max. 1 potomka - a okopírujem z neho telo do rušeného prvku. Nájdený max. prvok(alebo min. z pravého) potom ruším podľa predošlých bodov.
- Vypíš strom
- samozrejme, že najľahšie je to rekurzívne. Pri výpise
koreň oproti podstromom býva predsadený o niekoľko medzier.
Používajú sa nasledovné výpisy:- priamy - koren, lavý, pravý
- vnútorný - ľavý, koren, pravý
- spätný - ľavý, pravý, koren
1. vlož koreň do fronty
2. vyber vrchol z frontu vypíš ho
3. vlož do frontu jeho synov ľavého a pravého a pokračuj bodom 2
opakujeme kým nie je fronta prázdna - Vyvažovanie stromu
- nateraz stačí vedieť, že sa to dá. Ak potrebujeme zachovať vyváženosť stromu volíme špeciálne "samovyvažujúce stromy napr. "červeno-čierne stromy", kde vyvažovanie prebieha logaritmicky.
- Intervalové stromy
- Už podľa názvu možno určiť, že sú na rychle spracovávanie intervalov - každý zápis aj čítanie hodnoty vieme robiť v logaritmickom čase. Myšlienku vysvetlím na príklade.
Majme pole A<1, N>, kde N=2^k hodnôt integer. Na vstupe máme intervaly (počet intervalov P), v ktorých máme hodnotu zväčšiť o nejakú rovnakú hodnotu a,b,x.
Nakoniec je na vstupe číslo j a my máme vrátiť hodnotu A[j].
Riešenie
interval 1 až N si zapíšeme do stromu, keďže N je mocnina 2 bude strom dokonale vyvážený. Listy stromu tvoria konkretne hodnoty poľa, prvky vo vyšších riadkoch popisujú intervaly <2^j1+1,2^j2>
Def.
Základný interval - interval tvaru <b,b> alebo <2^j1+1,2^j2>
Veta1
Každý podinterval intervalu 1 až N možno popísať/pokryť O(lnN) disjuktnými základnými intervalmi.
Napr.
interval 3-7 = 3-4 + 5-6 + 7
interval 2-7 = 2 + 3-4 + 5-6 + 7
Teraz keď čítame intervaly na ktorých treba meniť hodnoty nemeníme hodnoty listov ale zapíšeme si zmenu do odpovedajúcich základných intervalov pokryvajúcich náš zadaný interval.
Keď potom hľadáme hodnotu prvku A[j] tak pri hľadaní j-tej položky od koreňa stromu aplikujeme všetky zapísané zmeny v týchto intervaloch
- Všeobecná štruktúra
-
Vytvorme nasledovnú štruktúru:
rodič ^
¦prvok štruktúry -> brat ¦
vpotomok
Každý prvok má teda tri ukazovatele:- Na svojho predka - rodiča
- Na svojho mladšieho súrodenca
- Na svojho najstaršieho potomka
- Úloha
- Naprogramuj simulátor OS DOSGVBN. Program má ovládať nasledovné príkazy:
- privítanie a prompt riadok na vstup príkazov
- ls - výpis aktuálneho adresára, adresáre veľkým súbory malým
- tree - výpis stromu od aktuálneho adresára
- cd podadr - zmena aktuálneho adresára, ak neexistuje zahlási error
- cd .. - zmena akt. adr., ak sme v roote neurobí nič
- cd \ - zmena akt. adr. na root
- md názov - vytvorí podadresár
- rd názov - zruší podadresár
- mf názov - vytvorí prázdny súbor
- rf názov - zruší súbor
- exit - koniec simulátora
Súbory, adresáre nie sú samozrejme vytvárané existujú len v pamäti počítača.