MFF UK / Ústav teoretické fyziky / Tomáš Ledvinka
Přednášky
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
  Úvod
  Programy a algoritmy
  Píšeme program
  Píšeme program II
  Procedury a funkce
  Malujeme funkce
  Chyby. Typy I.
  Typy II. Pole a Záznamy
  Pole II.Řetězce.Soubory.
  Gnuplot.Interpolace...
  Matice. Velké O...
  Fronta,Zásobník. Postscript
  Bin. soubory, ...
    Neúplné vyh. log. výrazů
    Parametr typu funkce
    Otypované soubory
    Binární soubory
    Dyn. datové struktury
  Ukazatele,Objekty, ...
Počítačová algebra
Klasická elektrodynamika (2.r)
Vybrané partie OTR

Cvičení
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
Teoretická mechanika (2.r)
Klasická elektrodynamika (2.r)


Věda
. . . . . . . . . . . . . . . . . . . . . . . . . .
Diskové zdroje v OTR
Hyperbolické systémy v OTR


Kontakt
. . . . . . . . . . . . . . . . . . . . . . . . . .
Email
Konzultační hodiny


Ostatní
. . . . . . . . . . . . . . . . . . . . . . . . .
Mallorca
Ze společnosti

Dynamické datové struktury (poznámky povrchní)

Prozatím jsme se omezili jen na pole s proměnnou délkou, seznamy, fronty a zásobníky. Ve všech případech jde jen o velmi primitivní dynamické datové struktury.

Viděli jsme, na příkladu procházení souborového systému, že důležitou datovou strukturou jsou stromy, jako speciální případy tzv. grafů. (Pozn. při výkladu: Vrcholy a hrany grafu). V následujícím programu zavedeme takové typy a proměnné, že v nich dokážeme uložit libovolný strom. (Pozn. při výkladu: Graf v matici
   var     VedeHrana : array [tCisloVrcholu, tCisloVrcholu] of boolean
a proč ne (obzvlášť) u stromu.)

Zavedeme rodokmen hermafroditních organismů. Každý bude mít Jméno a seznam svých potomků. Pomocí vhodně definované funkce umožníme zapsat strukturu stromu jedním příkazem programu a ukážeme si práci se stromem pomocí dvou funkcí, první Jmeno2COP převede jméno na identifikační číslo organismu (index v seznmau t.j. pra-ukazatel) a druhá mi pro každého spočte počet potomků jako součet počtu potomků + počtu jejich potomků+....

program DynDa;

type tCOP = integer;

type tUzel = record
               Jmeno : string;
               Deti  : array of tCOP;
             end;

var  Pamet : record
               Prvky : array of tUzel;
               Pocet : tCOP;
             end;

function X(const NoveJmeno : string; const NoveDeti : array of tCOP): tCOP;
var k : integer;
    i : tCOP;
begin
  // Sileny trik: necham nulty prvek nastaveny na zadne jmeno, zadne deti
  {Nejdříve musím vyrobit NOVOU POLOŽKU i}
  i := Pamet.Pocet+1;
  Pamet.Pocet := i;
  if i>High(Pamet.Prvky) then begin SetLength(Pamet.Prvky,10+2*High(Pamet.Prvky)); end;
  {Nikdy nezvetsovat po jedne, vzdy geometrickou radou !!!}
  X := i;
  with Pamet.Prvky[i] do begin
    Jmeno := NoveJmeno;
    SetLength(Deti,High(NoveDeti)+1);
    for k:=Low(NoveDeti) to High(NoveDeti) do Deti[k] := NoveDeti[k];
  end;
end;

function Jmeno2COP(const Jmeno:string) : tCOP;
var i : tCOP;
begin
   Jmeno2COP := 0;
   for i := Low(Pamet.Prvky) to High(Pamet.Prvky) do
     if Pamet.Prvky[i].Jmeno = Jmeno then begin
       Jmeno2COP := i;
       exit;
     end;
end;

function PocetPotomku(const COP:tCOP) : integer;
var i,s : integer;
begin
   s := 0;
   with Pamet.Prvky[COP] do
     for i := Low(Deti) to High(Deti) do s:=s+1+PocetPotomku(Deti[i]);
   PocetPotomku := s;
end;


var Otec : tCOP;
begin

  Otec := X('Petr',[
                    X('Karel',[
                               X('Mirek',[]),
                               X('Zdenek',[])
                              ]),
                    X('Ivan',[
                               X('Hugo',[
                                         X('Rudolf',[]),
                                         X('Gustav',[
                                                     X('Cecil',[])
                                                    ]),
                                         X('Klement',[])
                                        ])
                             ])
                   ]);

  Writeln(PocetPotomku( Jmeno2COP('Ivan') ) );

  Readln;
end.

Příklady problémů, které vedou na uložení dat v podobě stromu.

  • aritmetický výraz
  • setříděná data

Cvičení: Napište proceduru, která vytiskne rodokmen. Nejjednodušší bude rekursivní varianta s parametry COP, a pořadím generace (= počet mezer).

Petr
  Karel
     Mirek
     Zdenek
  Ivan
     Hugo
        Rudolf
        Gustav
            Cecil
        Klement
Případně zksute i složitější podobu s čárkami
Petr
+ Ivan 
|   +  Hugo
|        + Rudolf
|        + Gustav
|        |    -  Cecil
|        - Klement
- Karel
    +  Mirek
    -  Zdenek

 

.