28.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
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 nieje 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 29: Riadok 26:
  
  
* pre konkrétny strom (vo vrcholoch písmená napr. "programovanie") - ručne vypísať pre-, in- a post-order
+
* nakresliť strom na tabuľu, do vrcholov písmena 'programovanie', vypísať pre-order usporiadanie vrcholov daného stromu
 +
pre-order: prgmonroaviea
 +
in-order: mgnorrpiveaao
 +
post-order: mnogrrievaaop
  
* do daného nakresleného stromu zapíšte písmená "programovanie", aby pre-order (in-order, post-order) vypísal v poradí "programovanie"
+
* strom ako objekt - pracujeme s triedou '''TStrom''' - definujeme v '''Unit1.pas'''
:* navrhnite trochu pozmenený strom tak, aby aj jeho pre-order vypísal v poradí "programovanie"
+
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
 +
var
 +
  S:TStrom;
 +
begin
 +
  S := TStrom.Create('p',
 +
    TStrom.Create('r',
 +
      TStrom.Create('g',
 +
        TStrom.Create('m'),
 +
        TStrom.Create('o')),
 +
      TStrom.Create('r')),
 +
    TStrom.Create('o',
 +
      TStrom.Create('a'),
 +
      nil));
 +
  S.PreOrder;
 +
end;
  
{{Podnadpis|ďalšie námety}}
+
* na definíciu stromu môžeme využiť podstromy
  
 +
* metódy '''InOrder''' a '''PostOrder'''
  
* ...
+
* metóda '''VypisListov'''
 +
:je jedno, či používame pre- in- alebo post-order
 +
procedure TStrom.VypisListov;
 +
begin
 +
  if L <> nil then
 +
    L.VypisListov;
 +
  if P <> nil then
 +
    P.VypisListov;
 +
  if (L = nil) and (P = nil) then
 +
    Write(Text);
 +
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 ===
 
=== 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
 
:* klikanie myšou na ľubovoľný vrchol zvýši číslo v tomto vrchole o 1 (a prekreslí vrchol alebo celý strom)
 
:* klikanie myšou na ľubovoľný vrchol zvýši číslo v tomto vrchole o 1 (a prekreslí vrchol alebo celý strom)

Verzia zo dňa a času 09:47, 8. 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

  • nakresliť strom na tabuľu, do vrcholov písmena 'programovanie', vypísať pre-order usporiadanie vrcholov daného stromu
pre-order: prgmonroaviea
in-order: mgnorrpiveaao
post-order: mnogrrievaaop
  • strom ako objekt - pracujeme s triedou TStrom - definujeme v Unit1.pas
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
var
  S:TStrom;
begin
  S := TStrom.Create('p',
    TStrom.Create('r',
      TStrom.Create('g',
        TStrom.Create('m'),
        TStrom.Create('o')),
      TStrom.Create('r')),
    TStrom.Create('o',
      TStrom.Create('a'),
      nil)); 
  S.PreOrder;
end;
  • na definíciu stromu môžeme využiť podstromy
  • metódy InOrder a PostOrder
  • metóda VypisListov
je jedno, či používame pre- in- alebo post-order
procedure TStrom.VypisListov;
begin
  if L <> nil then
    L.VypisListov;
  if P <> nil then
    P.VypisListov;
  if (L = nil) and (P = nil) then
    Write(Text);
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)