28.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
(13 intermediate revisions by 2 users not shown)
Riadok 7: Riadok 7:
  
  
pre spájaný zoznam
+
1. pre spájaný zoznam
 
{{Prog}}
 
{{Prog}}
  type
+
  TVrchol = class
  TVrchol = class
+
  Info: Integer;
    Info: Integer;
+
  Next: TVrchol;
    Next: TVrchol;
+
end;
    constructor Create(NoveInfo: Integer; NovyNext: TVrchol);
+
  end;
+
 
   
 
   
 
  TZoznam = class
 
  TZoznam = class
 
   Z: TVrchol;
 
   Z: TVrchol;
 +
  procedure Vymen(V1, V2:TVrchol);
 
  end;
 
  end;
 
|}
 
|}
1. metóda '''TZoznam.Vymen(V1, V2: TVrchol)''' navzájom vymení dva vrcholy (nie iba ich obsahy) - zrejme treba nájsť ich predchodcov
+
* napísať procedúru '''Vymen(V1, V2:TVrchol)''', ktorá dostane dva rôzne vrcholy zo zoznamu a vymení ich. Je zaručené, že ani jeden z nich nie je ani začiatok, ani koniec
 
+
2. metóda '''TZoznam.VyhodK''' vyhodí posledný vrchol zoznamu (smerník '''K''' na posledný vrchol by nám nepomohol)
+
  
  
Riadok 28: Riadok 25:
 
=== Cvičenie ===
 
=== Cvičenie ===
  
 +
* z daného binárneho stromu ručne vyrobiť preorder, inorder a postorder
 +
::: {{Obr|P28c.1.png|160px|daný binárny strom}}
 +
* tento strom má postupne po úrovniach zapísané písmená slova 'programovanie'
 +
preorder  = prgmonroaviea
 +
inorder  = mgnorrpiveaao
 +
postorder = mnogrrievaaop
  
* pre konkrétny strom (vo vrcholoch písmená napr. "programovanie") - ručne vypísať pre-, in- a post-order
+
* otestujeme v programe (môže byť v konzolovom režime) - napr. '''StromUnit.pas''' napr. už definované
 +
type
 +
  TStrom = class
 +
    Info: Char;
 +
    L, P: TStrom;
 +
    constructor Create(Z: Char);
 +
    constructor Create(Z: Char; LL, PP: TStrom);
 +
    function Text: string;
 +
  end;
 +
 
 +
constructor TStrom.Create(Z: Char);
 +
begin
 +
  Info := Z;
 +
end;
 +
 
 +
constructor Create(Z: Char; LL, PP: TStrom);
 +
begin
 +
  Info := Z;
 +
  L := LL;
 +
  P := PP;
 +
end;
  
* do daného nakresleného stromu zapíšte písmená "programovanie", aby pre-order (in-order, post-order) vypísal v poradí "programovanie"
+
* metóda '''PreOrder''' - podobne bude vyzerať väčšina stromových podprogramov
:* navrhnite trochu pozmenený strom tak, aby aj jeho pre-order vypísal v poradí "programovanie"
+
procedure TStrom.PreOrder;
 +
begin
 +
  Write(Text);
 +
  if L <> nil then
 +
    L.PreOrder;
 +
  if P <> nil then
 +
    P.PreOrder;
 +
end;
 +
 
 +
* otestujeme v hlavnom programe - najprv nejako zadefinujeme strom (postupne sa vystriedajú viacerí) - ako príklad sme definovali aj podstrom '''S1''' a ten sa vložil na správne miesto:
 +
var
 +
  S, S1: TStrom;
 +
begin
 +
  {{Blue|S1}} := TStrom.Create('v',
 +
          TStrom.Create('i'),
 +
          TStrom.Create('e'));
 +
  S := TStrom.Create('p',
 +
          TStrom.Create('r',
 +
            TStrom.Create('g',
 +
              TStrom.Create('m'),
 +
              TStrom.Create('o',
 +
                TStrom.Create('n'),
 +
                nil)),
 +
            TStrom.Create('r')),
 +
          TStrom.Create('o',
 +
            TStrom.Create('a',
 +
              {{Blue|S1}},
 +
              TStrom.Create('a')),
 +
            nil));
 +
  Write('prorder: ');
 +
  S.PreOrder;
 +
  WriteLn;
 +
end;
 +
 
 +
* '''PreOrder''' ako globálna procedúra
 +
procedure PreOrder(S: TStrom);
 +
begin
 +
  if S <> nil then
 +
  begin
 +
    Write(Text);
 +
    PreOrder(L);
 +
    PreOrder(P);
 +
  end;
 +
end;
 +
 
 +
* metóda '''PreOrder''' ale ako stringová funkcia
 +
function TStrom.PreOrder: string;
 +
begin
 +
  Result := Text;
 +
  if L <> nil then
 +
    Result := Result + L.PreOrder;
 +
  if P <> nil then
 +
    Result := Result + P.PreOrder;
 +
end;
 +
 
 +
* metódy '''InOrder''' a '''PostOrder'''
 +
procedure TStrom.InOrder;
 +
begin
 +
  if L <> nil then
 +
    L.InOrder;
 +
  Write(Text);
 +
  if P <> nil then
 +
    P.InOrder;
 +
end;
 +
&nbsp;
 +
procedure TStrom.PostOrder;
 +
begin
 +
  if L <> nil then
 +
    L.PostOrder;
 +
  if P <> nil then
 +
    P.PostOrder;
 +
  Write(Text);
 +
end;
 +
 
 +
* metóda '''VypisListov''' - vypíše len všetky listy stromu (je jedno, či používame pre- in- alebo post-order schému)
 +
procedure TStrom.VypisListov;
 +
begin
 +
  if (L = nil) and (P = nil) then
 +
    Write(Text);
 +
  if L <> nil then
 +
    L.VypisListov;
 +
  if P <> nil then
 +
    P.VypisListov;
 +
end;
 +
 
 +
* metóda '''PocetListov'''
 +
function TStrom.PocetListov: Integer;
 +
begin
 +
  Result := 0;
 +
  if (L = nil) and (P = nil) then
 +
    Inc(Result);
 +
  if L <> nil then
 +
    Inc(Result, L.PocetListov);
 +
  if P <> nil then
 +
    Inc(Result, P.PocetListov);
 +
end;
 +
 
 +
* metódy '''Pocet''' a '''PocetVnutornych''' - budú počítať počet všetkých a počet vnútorných vrcholov stromu(tj. majú aspoň jedného syna)
 +
function TStrom.PocetVnutornych: Integer;
 +
begin
 +
  Result := 0;
 +
  if (L <> nil) or (P <> nil) then
 +
    Inc(Result);
 +
  if L <> nil then
 +
    Inc(Result, L.PocetVnutornych);
 +
  if P <> nil then
 +
    Inc(Result, P.PocetVnutornych);
 +
end;
 +
* vyskúšať si niektorú z týchto funkcií zapísať ako globálnu funkciu s parametrom '''TStrom'''
 +
 
 +
* nakresliť na tabuľu prázdny strom rovnakého tvaru ako predchádzajúci
 +
::: {{Obr|P28c.2.png|160px|prázdny strom}}
 +
* zapísať do vrcholov písmena zo slova 'programovanie' tak, aby výsledkom preorder bolo 'programovanie'
 +
::: {{Obr|P28c.3.png|160px|dopísané písmená}}
 +
 
 +
* aby sa jednoduchšie definoval strom pomocou volaní '''TStrom.Create(...)''', môžeme zadefinovať pomocnú funkciu:
 +
function v(Z: char; LL: TStrom = nil; PP: TStrom = nil): TStrom;
 +
begin
 +
  Result := TStrom.Create(Z, LL, PP);
 +
end;
 +
 
 +
* potom pôvodný strom zapíšeme
 +
S := v('p', v('r', v('g', v('m'), v('o', v('n'), nil)), v('r')), v('o', v('a', v('v', v('i'), v('e')), v('a')), nil));
 +
* ak si všimneme poradie znakov v tomto zápise - je to preorder - ľahko sa vyrobí strom, ktorého preorder je 'programovanie':
 +
S := v('p', v('r', v('o', v('g'), v('r', v('a'), nil)), v('m')), v('o', v('v', v('a', v('n'), v('i')), v('e')), nil));
 +
 
 +
* takýto zápis môžeme vytvoriť aj upraveným výpisom '''PreOrder''':
 +
procedure TStrom.PreOrderCreate;
 +
begin
 +
  if (L = nil) and (P = nil) then
 +
    Write('v(', Text, ')')
 +
  else
 +
  begin
 +
    Write('v(', Text, ', ');
 +
    if L = nil then
 +
      Write('nil')
 +
    else
 +
      L.PreOrderCreate;
 +
    Write(', ');
 +
    if P = nil then
 +
      Write('nil')
 +
    else
 +
      P.PreOrderCreate;
 +
    Write(')');
 +
  end;
 +
end;
 +
* môžeme to zapísať aj ako funkciu:
 +
function TStrom.PreOrderCreate: string;
 +
begin
 +
  if (L = nil) and (P = nil) then
 +
    Result := 'v(' + Text + ')'
 +
  else
 +
  begin
 +
    Result := 'v(' + Text + ', ';
 +
    if L = nil then
 +
      Result := Result + 'nil'
 +
    else
 +
      Result := Result + L.PreOrderCreate;
 +
    Result := Result + ', ';
 +
    if P = nil then
 +
      Result := Result + 'nil'
 +
    else
 +
      Result := Result + P.PreOrderCreate;
 +
    Result := Result + ')';
 +
  end;
 +
end;
 +
 
 +
* opačná úloha: máme '''preorder''' a '''inorder''', treba zistiť, ako vyzerá strom, a tiež '''postorder'''
 +
:o preorderi vieme, že prvý znak je koreň stromu
 +
:v inorderi zase, že koreň je medzi zápismi ľavého a pravého podstromu
 +
preorder: ABCEFGD
 +
inorder: ACFEGBD
 +
:výsledný strom
 +
S := v('A', nil, v('B', v('C', nil, v('E', v('F'), v('G'))), v('D')));
 +
::: {{Obr|P28c.4.png|160px|binárny strom}}
 +
* postorder tohto stromu je
 +
postorder = FGECDBA
 +
 
 +
* metóda '''Pokaz(Z: Char)''' - prejde celým stromom a do každého vrchola zapíše znak '''Z'''
 +
procedure TStrom.Pokaz(Z: Char);
 +
begin
 +
  Info := Z
 +
  if L <> nil then
 +
    L.Pokaz(Z);
 +
  if P <> nil then
 +
    P.Pokaz(Z);
 +
end;
 +
 
 +
* metóda '''Naprav(S: string)''' - prejde celým stromom a do vrcholov zapíše písmena daného stringu tak, aby '''postorder''' bol rovnaký ako zadaný string, napr. volanie S.Naprav('programovanie')
 +
procedure TStrom.Naprav(S: string);
 +
begin
 +
  Info := S[1];
 +
  Delete(S, 1, 1);              ''// vyhodí prvý znak''
 +
  if L <> nil then
 +
  begin
 +
    L.Naprav(S);
 +
    Delete(S, 1, L.Pocet);      ''// vyhodí toľko znakov, koľko je ich v ľavom podstrome''
 +
  end;
 +
  if P <> nil then
 +
    P.Naprav(S);
 +
end;
 +
 
 +
* efektívnejšie, ak parameter bude typu '''var'''
 +
procedure TStrom.Naprav({{Blue|var}} S: string);
 +
begin
 +
  Info := S[1];
 +
  Delete(S, 1, 1);              ''// vyhodí prvý znak''
 +
  if L <> nil then
 +
    L.Naprav(S);
 +
  if P <> nil then
 +
    P.Naprav(S);
 +
end;
 +
* a volanie
 +
var
 +
  R: string;
 +
...
 +
  R := 'programovanie';
 +
  S.Naprav(R);
  
  
Riadok 38: Riadok 278:
  
  
* ...
+
* metóda '''TStrom.VypisNaUrovni(K: Integer)''' vypíše všetky vrcholy na úrovni '''K'''
 +
* metóda funkcia '''TStrom.PocetNaUrovni(K: Integer): Integer''' zistí počet vrcholov na úrovni '''K'''
 +
* metóda '''TStrom.VypisPoUrovniach''' vypíše všetky vrcholy po úrovniach, napr. 0. úroveň (koreň), potom do druhého riadku vrcholy na 1. úrovni, ...
 +
* metóda '''TStrom.PriradPoUrovniach(S: string)''' postupne zapíše do vrcholov znaky z reťazca po úrovniach
  
  
 
=== Domáca úloha ===
 
=== Domáca úloha ===
 +
  
 
1. vygenerovať a nakresliť náhodný strom s číslami vo vrcholoch od 1 do 20
 
1. vygenerovať a nakresliť náhodný strom s číslami vo vrcholoch od 1 do 20
:* klikaním myšou na vrcholy zvýši číslo vo vrchole o 1
+
:* klikanie myšou na ľubovoľný vrchol zvýši číslo v tomto vrchole o 1 (a prekreslí vrchol alebo celý strom)
 +
 
 +
2. konštruktor '''TStrom.Create(Preorder, Inorder: string)''' skonštruuje celý strom (vo vrcholoch sú znaky), ktorého parameter '''Preorder''' je preorderovský výstup a '''Inorder''' je inorderovský výstup

Aktuálna revízia z 03:14, 3. máj 2013

28. Cvičenie


< 28.Prednáška | riešené úlohy


Rozcvička

1. pre spájaný zoznam

TVrchol = class
  Info: Integer;
  Next: TVrchol;
end;
 
TZoznam = class
  Z: TVrchol;
  procedure Vymen(V1, V2:TVrchol);
end;
  • napísať procedúru Vymen(V1, V2:TVrchol), ktorá dostane dva rôzne vrcholy zo zoznamu a vymení ich. Je zaručené, že ani jeden z nich nie je ani začiatok, ani koniec


Cvičenie

  • z daného binárneho stromu ručne vyrobiť preorder, inorder a postorder
daný binárny strom
  • tento strom má postupne po úrovniach zapísané písmená slova 'programovanie'
preorder  = prgmonroaviea
inorder   = mgnorrpiveaao
postorder = mnogrrievaaop
  • otestujeme v programe (môže byť v konzolovom režime) - napr. StromUnit.pas napr. už definované
type
  TStrom = class
    Info: Char;
    L, P: TStrom;
    constructor Create(Z: Char);
    constructor Create(Z: Char; LL, PP: TStrom);
    function Text: string;
  end;
 
constructor TStrom.Create(Z: Char);
begin
  Info := Z;
end;
 
constructor Create(Z: Char; LL, PP: TStrom);
begin
  Info := Z;
  L := LL;
  P := PP;
end;
  • metóda PreOrder - podobne bude vyzerať väčšina stromových podprogramov
procedure TStrom.PreOrder;
begin
  Write(Text);
  if L <> nil then
    L.PreOrder;
  if P <> nil then
    P.PreOrder;
end;
  • otestujeme v hlavnom programe - najprv nejako zadefinujeme strom (postupne sa vystriedajú viacerí) - ako príklad sme definovali aj podstrom S1 a ten sa vložil na správne miesto:
var
  S, S1: TStrom;
begin
  S1 := TStrom.Create('v',
          TStrom.Create('i'),
          TStrom.Create('e'));
  S := TStrom.Create('p',
          TStrom.Create('r',
            TStrom.Create('g',
              TStrom.Create('m'),
              TStrom.Create('o',
                TStrom.Create('n'),
                nil)),
            TStrom.Create('r')),
          TStrom.Create('o',
            TStrom.Create('a',
              S1,
              TStrom.Create('a')),
            nil));
  Write('prorder: ');
  S.PreOrder;
  WriteLn;
end;
  • PreOrder ako globálna procedúra
procedure PreOrder(S: TStrom);
begin
  if S <> nil then
  begin
    Write(Text);
    PreOrder(L);
    PreOrder(P);
  end;
end;
  • metóda PreOrder ale ako stringová funkcia
function TStrom.PreOrder: string;
begin
  Result := Text;
  if L <> nil then
    Result := Result + L.PreOrder;
  if P <> nil then
    Result := Result + P.PreOrder;
end;
  • metódy InOrder a PostOrder
procedure TStrom.InOrder;
begin
  if L <> nil then
    L.InOrder;
  Write(Text);
  if P <> nil then
    P.InOrder;
end;
 
procedure TStrom.PostOrder;
begin
  if L <> nil then
    L.PostOrder;
  if P <> nil then
    P.PostOrder;
  Write(Text);
end;
  • metóda VypisListov - vypíše len všetky listy stromu (je jedno, či používame pre- in- alebo post-order schému)
procedure TStrom.VypisListov;
begin
  if (L = nil) and (P = nil) then
    Write(Text);
  if L <> nil then
    L.VypisListov;
  if P <> nil then
    P.VypisListov;
end;
  • metóda PocetListov
function TStrom.PocetListov: Integer;
begin
  Result := 0;
  if (L = nil) and (P = nil) then
    Inc(Result);
  if L <> nil then
    Inc(Result, L.PocetListov);
  if P <> nil then
    Inc(Result, P.PocetListov);
end;
  • metódy Pocet a PocetVnutornych - budú počítať počet všetkých a počet vnútorných vrcholov stromu(tj. majú aspoň jedného syna)
function TStrom.PocetVnutornych: Integer;
begin
  Result := 0;
  if (L <> nil) or (P <> nil) then
    Inc(Result);
  if L <> nil then
    Inc(Result, L.PocetVnutornych);
  if P <> nil then
    Inc(Result, P.PocetVnutornych);
end;
  • vyskúšať si niektorú z týchto funkcií zapísať ako globálnu funkciu s parametrom TStrom
  • nakresliť na tabuľu prázdny strom rovnakého tvaru ako predchádzajúci
prázdny strom
  • zapísať do vrcholov písmena zo slova 'programovanie' tak, aby výsledkom preorder bolo 'programovanie'
dopísané písmená
  • aby sa jednoduchšie definoval strom pomocou volaní TStrom.Create(...), môžeme zadefinovať pomocnú funkciu:
function v(Z: char; LL: TStrom = nil; PP: TStrom = nil): TStrom;
begin
  Result := TStrom.Create(Z, LL, PP);
end;
  • potom pôvodný strom zapíšeme
S := v('p', v('r', v('g', v('m'), v('o', v('n'), nil)), v('r')), v('o', v('a', v('v', v('i'), v('e')), v('a')), nil));
  • ak si všimneme poradie znakov v tomto zápise - je to preorder - ľahko sa vyrobí strom, ktorého preorder je 'programovanie':
S := v('p', v('r', v('o', v('g'), v('r', v('a'), nil)), v('m')), v('o', v('v', v('a', v('n'), v('i')), v('e')), nil));
  • takýto zápis môžeme vytvoriť aj upraveným výpisom PreOrder:
procedure TStrom.PreOrderCreate;
begin
  if (L = nil) and (P = nil) then
    Write('v(', Text, ')')
  else
  begin
    Write('v(', Text, ', ');
    if L = nil then
      Write('nil')
    else
      L.PreOrderCreate;
    Write(', ');
    if P = nil then
      Write('nil')
    else
      P.PreOrderCreate;
    Write(')');
  end;
end;
  • môžeme to zapísať aj ako funkciu:
function TStrom.PreOrderCreate: string;
begin
  if (L = nil) and (P = nil) then
    Result := 'v(' + Text + ')'
  else
  begin
    Result := 'v(' + Text + ', ';
    if L = nil then
      Result := Result + 'nil'
    else
      Result := Result + L.PreOrderCreate;
    Result := Result + ', ';
    if P = nil then
      Result := Result + 'nil'
    else
      Result := Result + P.PreOrderCreate;
    Result := Result + ')';
  end;
end;
  • opačná úloha: máme preorder a inorder, treba zistiť, ako vyzerá strom, a tiež postorder
o preorderi vieme, že prvý znak je koreň stromu
v inorderi zase, že koreň je medzi zápismi ľavého a pravého podstromu
preorder: ABCEFGD
inorder: ACFEGBD
výsledný strom
S := v('A', nil, v('B', v('C', nil, v('E', v('F'), v('G'))), v('D')));
binárny strom
  • postorder tohto stromu je
postorder = FGECDBA
  • metóda Pokaz(Z: Char) - prejde celým stromom a do každého vrchola zapíše znak Z
procedure TStrom.Pokaz(Z: Char);
begin
  Info := Z
  if L <> nil then
    L.Pokaz(Z);
  if P <> nil then
    P.Pokaz(Z);
end;
  • metóda Naprav(S: string) - prejde celým stromom a do vrcholov zapíše písmena daného stringu tak, aby postorder bol rovnaký ako zadaný string, napr. volanie S.Naprav('programovanie')
procedure TStrom.Naprav(S: string);
begin
  Info := S[1];
  Delete(S, 1, 1);              // vyhodí prvý znak
  if L <> nil then
  begin
    L.Naprav(S);
    Delete(S, 1, L.Pocet);      // vyhodí toľko znakov, koľko je ich v ľavom podstrome
  end;
  if P <> nil then
    P.Naprav(S);
end;
  • efektívnejšie, ak parameter bude typu var
procedure TStrom.Naprav(var S: string);
begin
  Info := S[1];
  Delete(S, 1, 1);              // vyhodí prvý znak
  if L <> nil then
    L.Naprav(S);
  if P <> nil then
    P.Naprav(S);
end;
  • a volanie
var
  R: string;
...
  R := 'programovanie';
  S.Naprav(R);



ďalšie námety



  • metóda TStrom.VypisNaUrovni(K: Integer) vypíše všetky vrcholy na úrovni K
  • metóda funkcia TStrom.PocetNaUrovni(K: Integer): Integer zistí počet vrcholov na úrovni K
  • metóda TStrom.VypisPoUrovniach vypíše všetky vrcholy po úrovniach, napr. 0. úroveň (koreň), potom do druhého riadku vrcholy na 1. úrovni, ...
  • metóda TStrom.PriradPoUrovniach(S: string) postupne zapíše do vrcholov znaky z reťazca po úrovniach


Domáca úloha

1. vygenerovať a nakresliť náhodný strom s číslami vo vrcholoch od 1 do 20

  • klikanie myšou na ľubovoľný vrchol zvýši číslo v tomto vrchole o 1 (a prekreslí vrchol alebo celý strom)

2. konštruktor TStrom.Create(Preorder, Inorder: string) skonštruuje celý strom (vo vrcholoch sú znaky), ktorého parameter Preorder je preorderovský výstup a Inorder je inorderovský výstup