28.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 25: 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}}
 +
preorder  = prgmonroaviea
 +
inorder  = mgnorrpiveaao
 +
postorder = mnogrrievaaop
  
* nakresliť strom na tabuľu, do vrcholov písmena 'programovanie', vypísať pre-order usporiadanie vrcholov daného stromu
+
* otestujeme v programe (môže byť v konzolovom režime) - napr. '''StromUnit.pas''' napr. už definované
pre-order: prgmonroaviea
+
  type
in-order: mgnorrpiveaao
+
  TStrom = class
post-order: mnogrrievaaop
+
    Info: Char;
 
+
    L, P: TStrom;
* strom ako objekt - pracujeme s triedou '''TStrom''' - definujeme v '''Unit1.pas'''
+
    constructor Create(Z: Char);
  TStrom = class
+
    constructor Create(Z: Char; LL, PP: TStrom);
  Info: Char;
+
    function Text: string;
  L, P: TStrom;
+
  end;
  constructor Create(Z: Char);
+
  constructor Create(Z: Char; LL, PP: TStrom);
+
  function Text: string;
+
end;
+
 
   
 
   
 
  constructor TStrom.Create(Z: Char);
 
  constructor TStrom.Create(Z: Char);
Riadok 52: Riadok 53:
 
  end;
 
  end;
  
* metóda '''PreOrder'''
+
* metóda '''PreOrder''' - podobne bude vyzerať väčšina stromových funkcií
:podobne bude vyzerať väčšina stromových funkcií
+
 
  procedure TStrom.PreOrder;
 
  procedure TStrom.PreOrder;
 
  begin
 
  begin
Riadok 62: Riadok 62:
 
     P.Preorder;
 
     P.Preorder;
 
  end;
 
  end;
:otestujeme
+
* 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
 
  var
 
   S:TStrom;
 
   S:TStrom;
 
  begin
 
  begin
 +
var
 +
  S, S1: TStrom;
 +
begin
 +
  S1 := TStrom.Create('v',
 +
          TStrom.Create('i'),
 +
          TStrom.Create('e'));
 
   S := TStrom.Create('p',
 
   S := TStrom.Create('p',
    TStrom.Create('r',
+
          TStrom.Create('r',
      TStrom.Create('g',
+
            TStrom.Create('g',
        TStrom.Create('m'),
+
              TStrom.Create('m'),
        TStrom.Create('o')),
+
              TStrom.Create('o',
      TStrom.Create('r')),
+
                TStrom.Create('n'),
    TStrom.Create('o',
+
                nil)),
      TStrom.Create('a'),
+
            TStrom.Create('r')),
      nil));  
+
          TStrom.Create('o',
 +
            TStrom.Create('a',
 +
              {{Blue|S1}},
 +
              TStrom.Create('a')),
 +
            nil));
 +
  Write('prorder: ');
 
   S.PreOrder;
 
   S.PreOrder;
 +
  WriteLn;
 
  end;
 
  end;
 
* na definíciu stromu môžeme využiť podstromy
 
  
 
* metódy '''InOrder''' a '''PostOrder'''
 
* 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'''
+
* metóda '''VypisListov''' - vypíše len všetky listy stromu (je jedno, či používame pre- in- alebo post-order schému)
:je jedno, či používame pre- in- alebo post-order  
+
 
  procedure TStrom.VypisListov;
 
  procedure TStrom.VypisListov;
 
  begin
 
  begin
 +
  if (L = nil) and (P = nil) then
 +
    Write(Text);
 
   if L <> nil then
 
   if L <> nil then
 
     L.VypisListov;
 
     L.VypisListov;
 
   if P <> nil then
 
   if P <> nil then
 
     P.VypisListov;
 
     P.VypisListov;
  if (L = nil) and (P = nil) then
 
    Write(Text);
 
 
  end;
 
  end;
  
Riadok 105: Riadok 131:
 
     Result := Result + P.PocetListov;
 
     Result := Result + P.PocetListov;
 
  end;
 
  end;
+
 
 
* metódy '''Pocet''' a '''PocetVnutornych'''
 
* 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)
 
:budú počítať počet všetkých a počet vnútorných vrcholov stromu(tj. majú aspoň jedného syna)

Verzia zo dňa a času 16:57, 10. marec 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 nieje ani začiatok, ani koniec


Cvičenie

  • z daného binárneho stromu ručne vyrobiť preorder, inorder a postorder
daný binárny strom
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 funkcií
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:TStrom;
begin
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;
  • 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;
begin
  Result := 0;
  if (L = nil) and (P = nil) then
    Inc(Result);
  if L <> nil then
    Result := Result + L.PocetListov;
  if P <> nil then
    Result := 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)
  • nakresliť na tabuľu prázdny strom rovnakého tvaru ako predchádzajúci
zapísať do vrcholov písmena z 'programovanie', tak, aby výsledkom pre-order bolo 'programovanie'
  • máme pre-order a in-order, ako vyzerá strom, postorder
o pre-orderi vieme, že prvý element je koreň
v in-orderi zas, že koreň je medzi zápismi podstromov
pre ABCEFGD
in  ACFEGBD
výsledok
('A', nil, ('B', ('C', nil, ('E', (F), (G))), ('D'));
  • metóda Pokaz s parametrom Z
prejde celým stromom a do každého vrchola zapíše Z
function 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 parametrom S typu strimg
prejde celým stromom a do vrcholov zapíše písmena daného stringu, aby postorder bol rovnaký ako zadaný string
procedure TStrom.Naprav(S: string);
begin
  Info := S[1];
  S := Copy(S, 2, MaxInt);
  if L <> nil then
  begin
    L.Naprav(S);
    Delete(S, 1, L.Pocet);
  end;
  if P <> nil then
    P.Naprav(S);
end;
efektívnejšie
function TStrom.Naprav(var S: string);
begin
  Info := S[1];
  S := Copy(S, 2, MaxInt);
  if L <> nil then
  begin
    L.Naprav(S);
  end;
  if P <> nil then
    P.Naprav(S);
end;


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