Úvod

Štruktúry

Používanie jednoduchých neštruktúrovaných premenných je obmedzené na veľmi malý počet premenných. Chceme odpamätávať dĺžku skokov pretekárov a určiť víťaza, pri počte pretekárov 3 je možné použiť napr. premenné d1, d2, d3. Pri väčšom počte je práca s premennými d1,d2,...dn veľmi komplikovaná, navyše pri zmene počtu pretekárov je potrebné radikálne zasahovať do programu. Potrebovali by sme objekt v ktorom by sme mali zapísané viac údajov pod jedným názvom. Takéto premenné voláme štruktúrované (alebo len štruktúry).
Rozdelenie štrutúrovaných premenných:

Homogénne štruktúry - štruktúra, ktorej položky sú rovnakého typu, napr. pole
Nehomogénne štruktúry - štruktúry, ktorých položky môže byť rôznych typov napr. záznam
Konečné štruktúry - počet položiek je obmedzený predpisom napr. pole
Nekonečné štruktúry - počet položiek je obmedzený pamäťou napr. súbor
Statické štruktúry - počet položiek (prvkov) je známy už pri preklade
Dynamické štruktúry - počet položiek sa určí až za behu programu.

Štruktúrovaný typ pole

Štruktúrovaný typu pole je homogénna konečná statická štruktúra

Deklarovanie typu pole - array


type

 <identifikátor_typu> = array[<typ>] of <typ_položky>

identifikátor_typu: je identifikátor pomocou ktorého budeme deklarovať premenné takéhoto typu. Na názov typu sú kladené také isté podmienky ako na ľubovoľný iný identifikátor.
typ: môže byť ľubovoľný ordinálny typ ale musí byť splnená podmienka aby celková veľkosť premennej nami vytvoreného typu zaberala v pamäti maximálne 65 536 bajtov (platí pre DOS - Borland Pascal, ak vytvárame program pre konzolovú aplikáciu v Delphi/Lazaruse alebo robíme program pod Free Pascal nie sme touto hranicou obmedzený. Tento typ určuje akého typu budú poradové čísla - indexy objektov tvoriacich pole. Teda typ uvedený v hranatých zátvorkách určuje aký počet položiek bude pole mať. Pri zadeklarovaní premennej takéhoto typu budú v pamäti vytvorené objekty od poradového čísla minimálnej hodnoty typu po maximálnu hodnotu typu.

príklad typ=1..10 tento typ obsahuje 10 objektov číslovaných od 1 po 10
príklad typ=byte tento typ obsahuje 256 objektov číslovaných od 0 po 255
typ_položky=ľub. typ, môže byť aj štruktúrovaný (napr. pole polí)

Pozn.
vytvorením identifikátora nami vytvoreného typu sa samozrejme v pamäti nič nezmení, žiadna premenná ešte nie je vytvorená, len sme si pomenovali tento typ aby sme ho mohli používať.

Deklarovanie typu pole - array


Var 

<identifikátor_premennej>: <identifikátor_typu_pole> ;

identifikátor_premennej: názov objektu, ktorý vytvárame v pamäti. Počet a typ položiek tohto objektu je popísaný v popise nami (pred týmto príkazom) vytvoreného typu identifikátor_typu_pole.
identifikátor_typu_pole: typ popísaný v časti type.

Príklad

type pole=array[byte] of integer; {vytvorili sme novy typ}
var p,pom:pole; {vytvorili sme v pamäti objekty p a pom}

Každé vytvorené pole má svoj názov ale rovnaký počet položiek 256, rovnaký typ položiek typ integer, rovnaký typ indexov - poradových čísel typ byte, rovnaký rozsah indexov - od 0 po 255

Práca s celým polom

Celé pole môžeme okopírovať do premennej rovnakého typu pomocou priraďovacieho príkazu.

Príklad:

pom := p;
Celé pole môže byť parametrom procedúry resp. fumkcie

Príklad:


Procedure napln(Var p:pole,n:word);

var i:word;

Begin

for i:= 1 to n do p[i] := random(100); 

End;


Procedure spocitaj(Var p:pole; p,pom:pole; n:word);

var i:word;

Begin

for i:= 1 to n do p[i] := p[i]+pom[i]; 

End;

Pozn. Všimnite si kľúčového slova var v deklarácii štruktúrovaného parametra, bez neho by všetky zmeny položiek prebiehali len v duplikáte poľa a po skončení procedúry by boli zabudnuté.

Práca s položkami poľa

Ku položkám poľa pristupujeme pomocou indexu umiestneného v hranatých zátvorkách hneď za identifikátorom poľa.
Syntax:
identifikátor[<výraz>]
výraz musí byť kompatibilného typu s typom indexu priradeného poľu
Použitie:
Položky poľa môžeme použiť všade tam kde môžme použiť premennú rovnakého typu ako je položka poľa - okrem premennej cyklu.
Ku položkám poľa často pristupujeme pomocou cyklu:
for i:=0 to 255 do p[i]:=1; {naplni vsetky polozky poľa hodnotou 1}
for i:=0 to 255 do write(p[i]:4); {vypíše vsetky polozky pola}

Základné dovednosti pri práci s poľom:

1. Výpis poľa na obrazovku

Vypis možno robiť po n-čísel na riadok, po výpise k-riadkov výpis prerušiť (odstránkovať)
For i:=1 to 255 do
Begin
write(p[i]:4)
if i mod n = 0 then writeln;
if i mod n*k = 0 then readln;
End;

2. Zmena hodnôt poľa

Meniť možno všetky prvky rovnako (zväčšiť o d, vynásobiť číslom k), alebo meniť len niektoré (napr. párne vydel 2, nepárne zvačsi o 1)

3. Naplnenie celého poľa resp. jeho časti postupnosťou dát

postupnosti:
1,2,3,...
N,N-1,N-2,...
1,3,5,7,...
0,1,0,1,0,1,...
Napĺňať položky poľa možno zadaním vzorca p[i]:=f(i);
Napr.
for i:=1 to 255 do p[i]:=2*i-1; {naplní pole hodnotami 1,3,5,...}
Iný spôsob je určiť hodnotu pomocou jedného aleho viacerých susedov p[i]:=f(p[i-1)
Napr.
p[1]:=1;for i:=2 to 255 do p[i]:=p[i-1]+2; {naplní pole hodnotami 1,3,5,...}

Ďalší spôsob ako určiť hodnotu položky poľa je pomocou pomocných premenných: p[i]:=f(a,b,...)
Napr.
a:=1;for i:=1 to 255 do Begin p[i]:=a; a:=a+2; End; {naplní pole hodnotami 1,3,5,...}

4. Vsúvanie jednej položky na určené miesto v postupnosti

Celá akcia sa dá rozdeliť na kroky

nájdi miesto kde vkladáme nový prvok
odsuň prvky z toho miesta až do konca o jedno miesto doprava
vlož na uvoľnené miesto nový prvok
oprav počet prvkov poľa

5. Vsúvanie jednej položky na určené miesto v utriedenej postupnosti

Celá akcia sa dá rozdeliť na kroky

nájdi miesto kde vkladáme nový prvok
odsuň prvky z toho miesta až do konca o jedno miesto doprava
vlož na uvoľnené miesto nový prvok
oprav počet prvkov poľa

6. Odstránenie jednej položky z postupnosti

Celá akcia sa dá rozdeliť na kroky

nájdi prvok ktorý rušíme
odsuň prvky od nasledujúceho miesta až do konca o jedno miesto doľava
oprav počet prvkov poľa

7. Hľadanie hodnoty v neutriedenom poli

Pri hľadaní musíme prejsť celé pole
dokážeme zistiť:
- či sa hľadaný prvok vyskytuje v poli
- koľko krát sa vyskytuje

8. Hľadanie hodnoty M v utriedenom poli

Pri hľadaní nemusíme prejsť celé pole
dokážeme zistiť:
- či sa hľadaný prvok vyskytuje v poli
Postup
Hľadanú hodnotu M porovnávame s prostredným prvkom skúmanej oblasti pola
ak je rovná -> našli sme hodnotu v poli
ak stredný prvok je menší tak budeme hľadať v hornej polovici
ak stredný prvok je väčšší tak budeme hľadať v dolnej polovici

9. Hľadanie maximálnej hodnoty

11. Zápis poľa na disk

ak vieme pracovať s textovými alebo typovými súbormi možno pole zapísať do súboru.

12. Čítanie poľa z disku

ak vieme pracovať s textovými alebo typovými súbormi možno pole načítať zo súboru.

13. Otočenie poľa

otočenie poľa spočíva co výmene prvého prvku s posledným, druhého s predposledným atď. Je zrejmé, že algoritmus je korektný pre počet prvkov párny i nepárny.

14. Utriedenie poľa

15. Výpočet súčtu hodnôt poľa, priemernej hodnoty

16. Výpočet absolútnej hodnoty vektora uloženého v poli

17. Výpočet skalárneho súčinu dvoch vektorov

18. Zistenie, či je pole symetrické

19. Hľadanie maximálnej súvislej a rastúcej oblasti

20. Hladanie znaku najviac sa vyskytujúceho sa v zadanom texte.

Na vstupe máme text tvorený ľubovoľnými znakmi ukončený Enterom.
Všetky znaky možno pokryť intervalom #0..#255, pre každý znak z tohoto intervalu vytvorím položku.
Vytvoríme si pole POCET[#0..#255], kde hodnota prvku bude početnosť daného znaku.

Var POCET[#0..#255] of integer;
	     c,mc:char;
	
		 Begin
		    repeat 
			  read(c);
			  POCET[c]:=POCET[c]+1;
			until c=#13;
			{ Teraz este najdem max v poli POCET}
			for c:=#1 to #255 do if POCET[c]>POCET[mc] then mc:=c;
			Writeln('Pismeno:',mc,'   Pocet:',POCET[mc]);
			readln;readln;
		End;

Vcelku milý príklad na pole, ktoré nemá indexy číselné :-)
Skús naprogramovať trochu zmenenú úlohu:
Naplň pole A[1..100] náhodnými číslami 1-5 a zisti ktoré číslo sa v poli A vyskytuje najčastejšie.

Úlohy na naplnenie položiek poľa

1. Naplň pole p postupnosťou 0,1,2,3,...,255
2. Naplň pole p postupnosťou 1,2,1,2,1,2...
3. Naplň pole p postupnosťou 255,254,253,...,1,0
4. Naplň pole p náhodnými číslami z intervalu 10-99
5. Naplň pole A1 ...A100 reálnych čísel s postupnosťou danou rekurentne
A1=10.0, A2=100.0, AN=(AN-2+AN-1)/2 ...pre N>2

Úlohy:

Rozdeľ obrazovku na 4 časti.

V 1. časti bude menu, v 2. bude pomocný jednoriadkový výpis, v 3. časti bude výpis poľa p a v 4. časti bude výpis poľa pom. Menu bude obsahovať tieto voľby
1. naplnenie prvých 10 položiek poľa p náhodnými číslami, výpis do okna
2. naplnenie prvých 10 položiek poľa pom náhodnými číslami, výpis do okna
3. odloženie poľa p do poľa pom, výpis poľa pom
4. odloženie poľa pom do poľa p, výpis poľa p
5. zapísanie poľa p na disk
6. načítanie poľa p z disku
7. hľadanie zvolenej hodnoty v poli p výpis v pomocnom výpise
8. hľadanie maximálnej hodnoty v poli p, výpis v pomocnom výpise
9. výpočet absolútnej hodnoty poľa p, výpis v pomocnom výpise
10. Otočenie poľa p, výpis
11. Výpočet skalárneho súčinu poľa p
12. Vkladanie čísla do poľa p za prvú menšiu hodnotu, výpis
13. Odstránenie čísla na zvolenom por. čísle poľa p, výpis
14. Utriedenie poľa p, výpis

Napíš program na spracovanie súťaže v skoku do diaľky. Program má umožňovať:
1. Zápis mena do databázy- pridelenie štartovacieho čísla
2. Vstup dĺžky dvoch skokov
3. V hociktorom okamžiku vypísať predbežné poradie
4. Možnosť po skončení súťaže diskvalifikovať súťažiaceho

Pole ako parameter podprogramu

Pole možno preniesť do podprogramu tak, že ho uvedieme ako parameter. Máme viac možností

uvedieme identifikátor typu poľa (napr procedure vypis(a: pole))
týmto podprogram vie akého typu sú položky poľa, akého typu sú indexy poľa a tiež rozsah indexov.
uvediem konštrukciu array of typ (napr. procedure vypis(a: array of char))
Tu sme podprogramu oznámili, že položky poľa budú char, ale o indexoch poľa sme nepovedali nič.
Index takéhoto poľa bude vždy číselný od 0 po (n-1), kde n je podľa toho s akým poľom to zavoláme. Rozsah povolených indexov možno určiť pomocou štandartných funkcií
Low(pole) .. vráti najmenší povolený index (v tomto prípade vždy 0)
High(pole) .. vráti (n-1), kde n je počet prvkov poľa
Poznámka:
Konštrukcia array aj s uvedením rozsahu indexov (array [1..10] of char) je pri deklarovaní parametra zakázaná.

Podobne ako jednoduché premenné možno prenášať do podprogramu hodnotou alebo menom. Pri prenose hodnotou sa v zásobníku vytvorí kópia volaného poľa a zmeny tohoto poľa nemajú vplyv na volané pole. Pri volaní menom (pomocou Var) sa prenesie adresa poľa (volané pole a pole v podprograme budú totožné a teda každá zmena pola-parametra zmení aj volané pole.
Pozn1.
Ak nechceme dovoliť meniť volané pole prenášané menom, tak namiesto Var použijeme Const. Polia budú totožné, ale kompilátor nám nedovolí v podprograme meniť položky tohoto poľa.
Pozn2.
Je "dobrým" zvykom pole preniesť menom, čo šetrí pamäť zásobníka a urýchli to volanie podprogramu (odpadne kopírovanie poľa).

Algoritmitcké úlohy