čo sme sa doteraz naučili

•  štruktúrovaný typ pole je zložený z prvkov rovnakého typu - pristupujeme k nim pomocou indexu

čo sa budeme dnes učiť

• komponent editovací riadok
• nový zložený typ - záznam, ktorý sa môže skladať s prvkov rôznych typov - pristupujeme k nim pomocou mena
• rôzne metódy hľadania informácie v (utriedenej/neutriedenej) tabuľke

Komponent Edit - editovací riadok - (komponent Edit1 zo štandardnej palety komponentov)

• slúži na interaktívne zadávanie znakového reťazca do programu
• počas behu programu môže používateľ do tohto riadka písať, resp. upravovať nejaký text
• program môže zistiť obsah riadka, resp. ho meniť
• pre nás najdôležitejšou stavovou premennou bude Text - v nej sa nachádza momentálny obsah editovacieho riadka
• je typu string
• momentálne nás bude zaujímať len udalosť (Event) onKeyPress - táto udalosť vznikne vždy, keď používateľ, ktorý edituje tento riadok, stlačí nejaký kláves na klávesnici (písmená, číslice, špeciálne znaky ako Enter, Esc a pod.)

• môžeme otestovať pomocou:
• vo formulári bude textové okno (Memo1), tlačidlo (Button1) a editovací riadok (Edit1)

• zatlačenie tlačidla prekopíruje obsah editovacieho riadka do textovej plochy - editovací riadok potom vyčistí

procedure TForm1.Button1Click(Sender: TObject);
begin
  Memo1.Lines.Add(Edit1.Text);
  Edit1.Text:='';
  Edit1.SetFocus;
end;

• bolo by dobre, keby sme po každom zadaní textu nemuseli klikať na tlačidlo, ale fungovalo by aj zatlačenie klávesu Enter
• pridáme spracovanie udalosti onKeyPress pre Edit1
• v Inšpektore objektov sa nastavíme na komponent Edit1, prepneme Udalosti (Events) a dvojklikneme OnKeyPress - vytvorí sa metóda Edit1KeyPress - táto metóda sa zavolá vždy, keď sa bude niečo zapisovať do editovacieho riadka - nás však bude zaujímať len kláves <Enter> s kódom #13

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
begin
  if Key=#13 then Button1.Click;
end;

Typ záznam - record

• pole = n-tica premenných (položiek), ktoré musia byť rovnakého typu
• záznam = n-tica premenných (položiek), nemusia byť rovnakého typu
• premenná typu záznam sa skladá zo svojich súkromných premenných
• prístup pomocou mena položky (selektor)
• s celým záznamom nie je povolený ani vstup ani výstup (len po položkách)
• priradenie je povolené len identického typu (ako pre polia)
• môžu byť použité ako parametre procedúr, resp. výsledok funkcie

type
  zaznam = record
    meno:array[1..10] of char;  // 10 bajtov
    rocnik:1..5;                // 1 bajt
    priemer:real;               // 8 bajtov
  end;

• v pamäti sú položky uložené tesne za sebou:

meno

rocnik

priemer

var
   z:zaznam;
begin
  ...
  z.meno:='Jan Hrasko';
  z.rocnik:=1;
  z.priemer:=1.33;
  ...
end;

• Pomocou záznamu reprezentujeme vektor ako dvojicu čísel (súradníc)

type
  vektor=record x,y:real end;

function StrToVektor(const s:string):vektor;
begin
  Result.x:=StrToFloat(copy(s,1,pos(' ',s)-1));
  Result.y:=StrToFloat(copy(s,pos(' ',s)+1,maxint));
end;

function vektorToStr(v:vektor):string;
begin
  Result:='('+FloatToStr(v.x)+','+FloatToStr(v.y)+')';
end;

function sucet(u,w:vektor):vektor;
begin
  Result.x:=u.x+w.x; Result.y:=u.y+w.y;
end;

function dlzka(v:vektor):real;
begin
  Result:=sqrt(sqr(v.x)+sqr(v.y));
end;

function otoc(v:vektor; uhol:real):vektor;
begin
  uhol:=uhol*pi/180;
  Result.x:=cos(uhol)*v.x+sin(uhol)*v.y;
  Result.y:=cos(uhol)*v.y-sin(uhol)*v.x;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  v1,v2:vektor;
  r:real;
begin
  v1:=StrToVektor(Edit1.Text);
  Memo1.Lines.Add('vektor1='+vektorToStr(v1));
  Memo1.Lines.Add('dlzka='+FloatToStr(dlzka(v1)));

  r:=StrToFloat(Edit2.Text);
  v2:=otoc(v1,r);
  Memo1.Lines.Add('vektor2='+vektorToStr(v2));
  Memo1.Lines.Add('dlzka='+FloatToStr(dlzka(v2)));
  Memo1.Lines.Add('');
end;

• v programe predpokladáme, že vo formulári je Edit1, Edit2, Memo1 a Button1. Vektor zadáme do Edit1 a uhol do Edit2, napr.

NDÚ:

• urobte kompletnú vektorovú aritmetiku: posuny, zväčšovanie/zmenšovanie, skalárny súčin, zistenie uhla medzi dvoma vektormi a pod.

Príklad

Postupne - na niekoľko krokov - budeme riešiť takýto príklad: v textovom súbore máme zadané nejaké informácie o mestách na mape. Zatiaľ nás zaujímajú len prvé tri hodnoty z každého riadka a to meno (reťazec ukončený ';') a súradnice x a y na obrazovke (oddelené medzerou).

type
  info = record
    meno:string;
    x,y:integer;
  end;

function CitajRiadok(var t:TextFile):info;
var
  z:char;
begin
  with Result do begin
    meno:=''; read(t,z);     // predpokladáme, že súbor je korektný
    while z<>';' do begin
      meno:=meno+z; read(t,z);
    end;
    readln(t,x,y);
  end;
end;

const
  max=100;

var
  p:array[1..max] of info;
  pocet:integer;              // počet načítaných prvkov v poli p

procedure TForm1.Button1Click(Sender: TObject);
var
  i:integer;
  t:TextFile;
begin
  AssignFile(t,'mesta.txt'); Reset(t); pocet:=0;
  while not SeekEof(t) do begin
    inc(pocet); p[pocet]:=CitajRiadok(t);
  end;
  CloseFile(t);
  for i:=1 to pocet do
    with p[i] do
      Memo1.Lines.Add(IntToStr(i)+'. '+meno+
                      ' ('+IntToStr(x)+','+IntToStr(y)+')');
end;

NDÚ:

• okrem mena a súradníc je v každom riadku súboru aj informácia o počte obyvateľov a číselný kód štátu, do ktorého toto mesto patrí (napr. ČR=1, SR=2, …) – doplňte to do deklarácie typu a aj do programu

• Ďalšia úloha: na obrazovke vytvoríme korytnačky na pozíciách miest, vypíšeme ku nim ich mená a budeme očakávať zadávanie dvojíc miest – ak to budú korektné mená, tak ich spojíme čiarou.
• Nakoľko budeme ďalej hľadať informácie o meste podľa jeho mena, napíšeme si pomocnú funkciu na hľadanie

function hladaj(m:string):integer;
begin
  Result:=pocet;
  while (Result>0) and (p[Result].meno<>m) do dec(Result);
end;

• do formulára umiestnime Image1, Button1, Edit1 a Memo1:

• v programe si všimnite vnorené príkazy with

type
  info = record
    meno:string;
    x,y:integer;
  end;

function CitajRiadok(var t:TextFile):info;
...

const
  max=100;

var
  p:array[1..max] of info;
  pocet:integer;
  k:array[1..max] of TKor;

function hladaj(m:string):integer;
begin
  Result:=pocet;
  while (Result>0) and (p[Result].meno<>m) do dec(Result);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i:integer;
  t:TextFile;
begin
  AssignFile(t,'mesta.txt'); Reset(t); pocet:=0;
  while not SeekEof(t) do begin
    inc(pocet); p[pocet]:=CitajRiadok(t);
  end;
  CloseFile(t);
  for i:=1 to pocet do
    with p[i] do
      Memo1.Lines.Add(IntToStr(i)+'. '+meno+
                      ' ('+IntToStr(x)+','+IntToStr(y)+')');
  for i:=1 to pocet do begin 
    with p[i] do k[i]:=TKor.Create(x,y);
    with k[i] do begin
      HP:=12; FP:=clGreen; Dopredu(0);
      HP:=1; FP:=clBlack;
      Image1.Canvas.Brush.Style:=bsClear;       // text má priesvitné pozadie
      Pis(p[i].meno);
    end;
  end; 
  Button1.Enabled:=false; 
end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
var 
  i,i1,i2:integer; 
  s:string; 
begin 
  if Key<>#13 then exit;
  s:=Edit1.Text; Edit1.Text:=''; 
  i:=pos(';',s); 
  if i>0 then begin 
    i1:=hladaj(copy(s,1,i-1)); 
    i2:=hladaj(copy(s,i+1,maxInt)); 
    if (i1>0) and (i2>0) then 
      with k[i1] do begin 
        with p[i2] do ZmenXY(x,y); 
        with p[i1] do ZmenXY(x,y); 
      end;
  end; 
end;

• Program trochu vylepšíme: nakoľko polia p a k a premenná pocet (počet načítaných prvkov) spolu súvisia, vytvoríme z nich jedinú dátovú štruktúru – tabuľku:

const
  max=100;

type
  info = record
    meno:string;
    x,y:integer;
  end;
  tabulka = record
    pocet:0..max;
    p:array[1..max] of info;
    k:array[1..max] of TKor;
  end;

function CitajRiadok(var t:TextFile):info;
var
  z:char;
begin
  with Result do begin
    meno:=''; read(t,z);
    while z<>';' do begin
      meno:=meno+z; read(t,z);
    end;
    readln(t,x,y);
  end;
end;

procedure zarad(var tab:tabulka; const pp:info);
begin
  with tab do begin
    inc(pocet); p[pocet]:=pp;
  end;
end;

function hladaj(const tab:tabulka; const m:string):integer;
begin
  Result:=tab.pocet;
  while (Result>0) and (tab.p[Result].meno<>m) do dec(Result);
end;

var
  tab:tabulka;

procedure TForm1.Button1Click(Sender: TObject);
var
  i:integer;
  t:TextFile;
begin
  tab.pocet:=0;           // inicializácia tabuľky
  AssignFile(t,'mesta.txt'); Reset(t);
  while not SeekEof(t) do
    zarad(tab,CitajRiadok(t));
  CloseFile(t);
  for i:=1 to tab.pocet do
    with tab,p[i] do begin       // k[i] tu ešte neexistuje
      k[i]:=TKor.Create(x,y);
      with k[i] do begin
        HP:=12; FP:=clGreen; Dopredu(0);
        HP:=1; FP:=clBlack;
        Image1.Canvas.Brush.Style:=bsClear;
        Pis(p[i].meno);
      end;
    end;
  Button1.Enabled:=false;
end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
var
  i,i1,i2:integer;
  s:string;
begin
  if Key<>#13 then exit;
  s:=Edit1.Text;
  i:=pos(';',s);
  if i>0 then begin
    i1:=hladaj(tab,copy(s,1,i-1));
    i2:=hladaj(tab,copy(s,i+1,maxInt));
    if (i1>0) and (i2>0) then
      with tab,k[i1] do begin
        with p[i2] do ZmenXY(x,y);
        with p[i1] do ZmenXY(x,y);
      end;
  end;
  Edit1.SelStart:=0;
  Edit1.SelLength:=Length(s);
end;

• na testovanie programu môžete použiť súbor mesta.txt a ako podklad pre Image1 použite bitmapu mapa.bmp
• je veľmi dôležité správne chápať a aj používať príkaz with - všimnite si riadok with tab,k[i1] do - toto je skrátený tvar konštrukcie: with tab do with k[i1] do - ak by tu nebola čiarka ale bodka with tab.k[i1] do, tak vo vnútri with by sme museli ku p[i1] a p[i2] písať tab. t.j. tab.p[i1] a tab.p[i1]

  with tab,k[i1] do begin
    with p[i2] do ZmenXY(x,y);
    with p[i1] do ZmenXY(x,y);
  end;

  with tab.k[i1] do begin
    with tab.p[i2] do ZmenXY(x,y);
    with tab.p[i1] do ZmenXY(x,y);
  end;

  with tab do begin
    k[i1].ZmenXY(p[i2].x,p[i2].y);
    k[i1].ZmenXY(p[i1].x,p[i1].y);
  end;

  tab.k[i1].ZmenXY(tab.p[i2].x,tab.p[i2].y);
  tab.k[i1].ZmenXY(tab.p[i1].x,tab.p[i1].y);

NDÚ:

• zmeňte definíciu tabuľky (a aj celého programu) tak, aby položka k – pole korytnačiek sa presunula do záznamu info, t.j. v zázname info pribudne položka k:TKor; a tým máme pre každé mesto pripravenú aj korytnačku
• vytvorte veľkú tabuľku (napr. 100000 náhodných čísel) a odmerajte, koľko priemerne trvá nájdenie jedného čísla (odmeriame, koľko trvá 1000 hľadaní a vypísaný výsledok potom vydelíme 1000) – môžete použiť funkciu Now a procedúru DecodeTime, napr.

var
  tab:array[1..100000] of integer;

function hladaj(m:integer):integer;
begin
  Result:=high(tab);
  while (Result>0) and (tab[Result]<>m) do dec(Result);
end;

function CasToStr(cas:TDateTime):string;
var
  hod,min,sek,msek:Word;
begin
  DecodeTime(cas,hod,min,sek,msek);
  Result:=IntToStr(hod)+':'+IntToStr(min)+':'+
          IntToStr(sek)+':'+copy(IntToStr(msek+1000),2,4);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  cas:TDateTime;
  i:integer;
begin
  Screen.Cursor:=crHourGlass;
  cas:=Now;                            // zapamätá si momentálny čas
  for i:=1 to 300 do                   // testovaná časť programu
    hladaj(random(maxint));
  Label1.Caption:=CasToStr(Now-cas);   // vypíše čas trvania testu
  Screen.Cursor:=crDefault;
end;

• použili sme tu komponent Label, ktorý slúži len na výpis jednoduchého textu do formulára
• tiež si môžete všimnúť, že funkciu hladaj sme volali ako keby to bola procedúra - v tomto prípade sa vyvolá funkcia a potom sa "zahodí" jej vypočítaný výsledok
• existuje aj štandardná funkcia podobná našej CasToStr a to TimeToStr - poexperimentujte s ňou
• pomocou Screen.Cursor môžeme počas dlhšie trvajúcich výpočtov zapnúť kurzor myši na tvar "presýpacích hodín"

Hľadanie informácií v tabuľke

• Algoritmus hľadania môžeme vylepšiť, ak budeme predpokladať, že tabuľka je vzostupne utriedená (abecedne - lexikograficky):

function hladaj(const tab:tabulka; const m:string):integer;
begin
  Result:=1;
  while (Result<=tab.pocet) and (tab.p[Result].meno<m) do
    inc(Result);
  if (Result>tab.pocet) or (tab.p[Result].meno<>m) then Result:=0;
end;

• zistite, čo bude funkcia hladaj vyhľadávať, ak z nej vyhodíme podčiarknutú časť
• utriedenú tabuľku môžeme prehľadávať aj od konca:

function hladaj(const tab:tabulka; const m:string):integer; 
begin 
  Result:=tab.pocet; 
  while (Result>0) and (tab.p[Result].meno>m) do 
    dec(Result); 
  if (Result<>0) and (tab.p[Result].meno<>m) then Result:=0; 
end;

• Predpokladali sme, že tabuľka je utriedená – môžeme opraviť procedúru zarad napr. takto:

procedure zarad(var tab:tabulka; const pp:info); 
var
  i:integer;
begin
  with tab do begin
    i:=pocet;
    while (i>0) and (p[i].meno>pp.meno) do begin
      p[i+1]:=p[i]; dec(i)
    end;
    p[i+1]:=pp;
    inc(pocet);
  end;
end;

• vnútorný while-cyklus posunie prvky tabuľky tak, aby sa nová položka mohla zasunúť na správne miesto
• zrejme predpokladáme, že zaraďovaný prvok sa ešte v tabuľke nenachádza

Binárne vyhľadávanie

• Naučíme sa nový typ algoritmu - binárne vyhľadávanie - podobný, ako keď hľadáme v telefónnom zozname:
• otvoríme v strede zoznamu: ak je hľadané slovo v abecede skôr ako slovo v strede, tak budeme pokračovať v prednej polovici zoznamu, inak v druhej polovici
• opäť vo vybranej polovici zoznamu sa pozrieme do jeho stredu a porovnáme s hľadaným slovom
• takto budeme postupne hľadať v menšom a menšom úseku zoznamu, až kým nenarazíme na hľadané slovo
• treba si zapamätať, že to funguje, len ak je pole / tabuľka utriedená:

function hladaj(const tab:tabulka; const m:string):integer;
var
  z,k,s:integer;
begin
  z:=1; k:=tab.pocet; s:=1;    // začiatok a koniec intervalu
  while z<=k do begin
    s:=(z+k) div 2;            // stred intervalu
    if tab.p[s].meno<m then z:=s+1
    else if tab.p[s].meno>m then k:=s-1
    else z:=k+1;
  end;
  if tab.p[s].meno=m then Result:=s
  else Result:=0;
end;

function hladaj(const tab:tabulka; const m:string):integer;
var
  z,k,s:integer;
begin
  z:=1; k:=tab.pocet;
  while z<k do begin
    s:=(z+k) div 2;
    if tab.p[s].meno<m then z:=s+1
    else if tab.p[s].meno>m then k:=s-1
    else begin z:=s; k:=s end
  end;
  if (z=k) and (tab.p[z].meno=m) then Result:=z
  else Result:=0;
end;

• snažte sa pochopiť rozdiely medzi oboma riešeniami

NDÚ:

• podobne ako predtým, otestujte priemerný čas nájdenia prvku
• pokúste sa matematicky vypočítať maximálny čas na nájdenie, resp. na zistenie, že sa tam prvok nenachádza
• v predchádzajúcom príklade s mestami vytvorte procedúru vyhod, ktorá vyhodí z tabuľky dané mesto (zachová sa vzostupné usporiadanie tabuľky)
• ďalej vytvorte vyhod1, ktorá vyhodí z tabuľky všetky mestá medzi m1 a m2 (v lexikografickom usporiadaní)
• preprogramujte zarad tak, aby správnu pozíciu nového mesta našiel pomocou binárneho vyhľadávania (t.j. na menej porovnaní) a až potom tabuľku posunul a teda vytvoril voľné miesto pre nové mesto