9prva_druha

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

napr.

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

napr. vektor ako dvojicu čísel (súradníc):

Type 
    vektor=record x,y:real end;

Pomocou záznamu vektor vyjadríme operácie s vektormi

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;

Dátová štruktúra Tabuľka

štruktúra tabuľka:

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

Typy tabuliek

sekvenčné

usporiadané

s priamym prístupom

hašované

Ukladanie údajov do tabuliek závisí od ich typu

sekvenčné - uloženie informácie na koniec tabuľky

usporiadané - na miesto kam patrí, aby bolo zachované usporiadanie

s priamym prístupom - priamo na miesto, kam patrí

hašované - miesto uloženia je vypočítané pomocou hašovacej funkcie

Vyhľadávanie v tabuľkách závisí od ich typu

sekvenčné - hľadáme systematicky od začiatku do konca

usporiadané - binárne vyhľadávanie

s priamym prístupom - informácia je hneď dostupná

hašované - pomocou hašovacej funkcie, ktorá bola použitá pri ich vytvorení

Sekvenčné tabuľky

štruktúra tabuľka:

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

procedure zarad(var tab:tabulka; pp:info);

begin

with tab do

begin inc(pocet); p[pocet]:=pp; end;

end;

function hladaj(tab:tabulka;m:string):integer;

begin

Result:=tab.pocet;

while(Result>0)and(tab.p[Result].meno<>m) do

dec(Result);

end;

Usporiadané tabuľky

zaraďovanie do usporiadanej tabuľky:

const
  max=100;

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

  tabulka = record
    pocet:0..max;
    p:array[1..max] of info;
  end;

procedure zarad(var tab:tabulka;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;

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á:

algoritmus binárneho vyhľadávania:

function hladaj(tab:tabulka; 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 Hladaj:=s
  else Hladaj:=0;
end;

Úloha:

V štáte do značnej miery využívajú cestnú dopravu. Štát sa rozhodol, že niektoré cesty zruší a ostatné opraví, ale opraví len minimálny počet kilometrov ciest taký, aby sa dalo dostať z každého mesta do každého. Aj pred opravou sa dá dostať z každého mesta do každého.

{Urcenie minimalnej kostry ciest suvisleho prepojenia miest}

program MinimalnaKostraCiest;

const MaxMiest = 100;    {maximalny pocet miest}
      MaxHran = 1000;   {maximalny pocet ciest medzi mestami}

type Jedna_cesta = record
                V1, V2: integer; {spojene mesta}
                Dlzka: integer   {ohodnotenie cesty}
             end;

var Cesty: array[1..MaxHran] of Jedna_cesta;        {ulozenie systemu}
    Komponent: array[1..MaxMiest] of integer;    {komponenty }
    N: 1..MaxMiest;      {skutocny pocet miest}
    PomJedna_cesta: Jedna_cesta;
    K1,K2: integer;
    S,I,J,K: integer;

begin

{Nacitanie vstupnych dat:}
write('Pocet vrcholov Cestyu: ');
readln(N);
writeln('Cesty:  ODKIAL  KAM  DLZKA');
S:=0;
while not eof do
  begin
  S:=S+1;          {pocet vsetkych ciest}
  with Cesty[S] do read(V1, V2, Dlzka)
  end;
  

{Utriedenie ciest podla velkosti od najkratsej k najdlhsej
 - pre jednoduchost pouzijeme jednoduchy triediaci
   algoritmus triedenia priamym vyberom:}

for I:=1 to S-1 do
  begin
  K:=I;
  for J:=I+1 to S do
    if Cesty[J].Dlzka<Cesty[K].Dlzka then K:=J;
  if K<>I then
    begin
    PomJedna_cesta:=Cesty[K];
    Cesty[K]:=Cesty[I];
    Cesty[I]:=PomJedna_cesta
    end
  end;

{Vlastne urcenie minimalnej kostry ciest


najdena kostra sa neuklada, priamo sa vypisuje:}

writeln;
writeln('Hrany tvoriace minimalnu kostru Cestyu:');
for I:=1 to N do Komponent[I]:=I;
  {pociatocne jednoprvkove komponenty souvislosti}
I:=0;
K:=0;               {pocet ciest zaradenych do kostry}
while K<N-1 do
  begin
  I:=I+1;           {skumana cesta}
  K1:=Komponent[Cesty[I].V1];
  K2:=Komponent[Cesty[I].V2];
  if K1<>K2 then    {cestu I zaradime do kostry}
    begin
    K:=K+1;
    writeln(Cesty[I].V1:5,Cesty[I].V2:5);
    for J:=1 to N do
      if Komponent[J]=K2 then Komponent[J]:=K1
    end
  end

end.