26.Prednaska/Cvicenie: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 3: Riadok 3:
  
  
...
+
 
 +
=== Rozcvička ===
 +
 
 +
 
 +
1. kopírovať binárny súbor '''integer.dat''' do '''real.dat'''
 +
* kde vstupný súbor obsahuje postupnosť celých čísel a výstupný súbor bude obsahovať tie isté čísla ale prekonvertované na reálne
 +
* nepoužívajte polia ani reťazce
 +
 
 +
 
 +
2. kopírovať binárny súbor '''real.dat''' do '''integer.dat'''
 +
* kde vstupný súbor obsahuje postupnosť reálných čísel a výstupný súbor bude obsahovať tie isté čísla ale prekonvertované ('''Round''') na celé
 +
* nepoužívajte polia ani reťazce
 +
 
 +
 
 +
 
 +
=== Cvičenie ===
 +
 
 +
 
 +
* budeme pracovať s takto zadeklarovaným spájaným zoznamom:
 +
type
 +
  PVrchol = ^TVrchol;
 +
  TVrchol = record
 +
    Info: Integer;
 +
    Next: PVrchol;
 +
  end;
 +
 
 +
var
 +
  Z, P: PVrchol;
 +
* do premennej '''P''' priradiť jeden vrchol s hodnotou 1
 +
 
 +
* teraz treba z neho urobiť jednoprvkový zoznam, t.j. v '''Z''' je na neho smerník a ďalej do '''P''' priradiť ďalší vrchol s hodnotou 2
 +
 
 +
* pripojiť nový vrchol '''P''' na koniec zoznamu '''Z''' a znovu do '''P''' priradiť ďalší vrchol s hodnotou 3
 +
 
 +
* pripojiť nový vrchol '''P''' na koniec zoznamu '''Z''' (ako 3. vrchol) a vypísať celý zoznam jedným '''WriteLn'''
 +
Z^.Next^.Next := P;
 +
 
 +
WriteLn(Z^.Info, ' -> ', Z^.Next^.Info, ' -> ', Z^.Next^.Next^.Info, ' -> nil');
 +
* dostali sme výpis
 +
{{Prog}}
 +
1 -> 2 -> 3 -> nil
 +
|}
 +
* v programe nechať výrobu vrcholov do '''P''' (tj. vytvárať vrcholy v poradí 1, 2, 3) a zmeniť len ďalšie priradenia tak aby vzniklo takéto nové poradie
 +
{{Prog}}
 +
2 -> 3 -> 1 -> nil
 +
|}
 +
* podobne realizovať napr. zmenu poradia (prípadne aj iné)
 +
{{Prog}}
 +
3 -> 1 -> 2 ->
 +
|}
 +
* procedúra '''Vypis''' - vypíše prvky zoznamu cyklom
 +
procedure Vypis(Z: Pvrchol);
 +
begin
 +
  while Z <> nil do
 +
  begin
 +
    Write(Z^.Info, ' -> ');
 +
    Z := Z^.Next;
 +
  end;
 +
  WriteLn('nil');
 +
end;
 +
:* upozorniť na to, čo by sa muselo zmeniť, keby '''Z''' bol '''var'''-parameter
 +
* čítať textový súbor s celými číslami a vyrábať z nich zoznam - najprv v opačnom poradí (otestovať na súbore s aspoň 5 číslami)
 +
var
 +
    T: TextFile;
 +
    Z, P: PVrchol;
 +
begin
 +
  AssignFile(T, 'cisla.txt');
 +
  Reset(T);
 +
  Z := nil;
 +
  while not SeekEOF(T) do
 +
  begin
 +
    New(P);
 +
    Read(T, P^.Info);
 +
    P^.Next := Z;
 +
    Z := P;
 +
  end;
 +
  CloseFile(T);
 +
  Vypis(Z);
 +
* potom čísla v správnom poradí (pridáva na koniec existujúceho zoznamu, máme ďalší smerník '''K''' na koniec zoznamu)
 +
var
 +
    T: TextFile;
 +
    Z, K, P: PVrchol;
 +
begin
 +
  AssignFile(T, 'cisla.txt');
 +
  Reset(T);
 +
  Z := nil;
 +
  K := nil;
 +
  while not SeekEOF(T) do
 +
  begin
 +
    New(P);
 +
    Read(T, P^.Info);
 +
    P^.Next := {{Blue|nil}};
 +
    if Z = nil then
 +
      Z := P
 +
    else
 +
      K^.Next := P;
 +
    K := P;
 +
  end;
 +
  CloseFile(T);
 +
  Vypis(Z);
 +
* logická funkcia '''Aspon1''' zistí, či má zoznam aspoň jeden vrchol
 +
function Aspon1(Z: PVrchol): Boolean;
 +
begin
 +
  Result := Z <> nil;
 +
end;
 +
* logická funkcia '''Aspon2''' zistí, či má zoznam aspoň dva vrcholy
 +
function Aspon2(Z: PVrchol): Boolean;
 +
begin
 +
  Result := (Z <> nil) and (Z^.Next <> nil);
 +
end;
 +
* alebo aj
 +
function Aspon2(Z: PVrchol): Boolean;
 +
begin
 +
  Result := Aspon1(Z) and Aspon1(Z^.Next);
 +
end;
 +
* logická funkcia '''Aspon3''' zistí, či má zoznam aspoň dva vrcholy, napr. aj takto
 +
function Aspon3(Z: PVrchol): Boolean;
 +
begin
 +
  Result := Aspon1(Z) and Aspon2(Z^.Next);
 +
end;
 +
* funkcia '''Min''' vráti minimálnu hodnotu v zozname (pre prázdny zoznam je jedno, čo vráti)
 +
function Min(Z: PVrchol): Integer;
 +
begin
 +
  Result := MaxInt;
 +
  while Z <> nil do
 +
  begin
 +
    if Z^.Info < Result then
 +
      Result := Z^.Info;
 +
    Z := Z^.Next;
 +
  end;
 +
end;
 +
&nbsp
 +
...
 +
  WriteLn('min = ', Min(Z));
 +
* funkcia '''MinP''' vráti smerník na minimálnu hodnotu (pre prázdny zoznam vráti '''nil''')
 +
function MinP(Z: PVrchol): PVrchol;
 +
begin
 +
  Result := nil;
 +
  while Z <> nil do
 +
  begin
 +
    if (Result = nil) or (Z^.Info < Result^.Info) then
 +
      Result := Z;
 +
    Z := Z^.Next;
 +
  end;
 +
end;
 +
&nbsp
 +
...
 +
  WriteLn('min = ', MinP(Z)^.Info);  ''// spadne pre prázdny zoznam''
 +
 
 +
 
 +
* ''ďalšie funkcie ako: súčet hodnôt, priemerná hodnota, počet nulových prvkov, ...''
 +
 
 +
 
 +
* funkcia '''Ity''' vráti smerník na I-ty vrchol (ak neexistuje, vráti '''nil''')
 +
function Ity(Z: PVrchol; I: Integer): PVrchol;
 +
begin
 +
  while (Z <> nil) and (I > 1) do
 +
  begin
 +
    Z := Z^.Next;
 +
    Dec(I);
 +
  end;
 +
  Result := Z;
 +
end;
 +
&nbsp
 +
...
 +
  P := Ity(Z, 5);
 +
  if P <> nil then
 +
    WriteLn('ity = ', P^.Info);
 +
* uvažujte o takomto využití '''Ity''' (prečo je to veľmi neefektívne)
 +
N := 1;
 +
repeat
 +
  P := Ity(Z, N);
 +
  if P <> nil then
 +
    WriteLn(N, '. prvok = ', P^.Info);
 +
until P = nil;
 +
 
 +
 
 +
* ''ďalšie funkcie ako: vráti smerník na prvý vrchol s danou hodnotou, vráti index vrcholu pre prvý výskyt hodnoty, smerník na stredný vrchol, zistiť, či sa v zozname nejaké číslo neopakuje, ...''
 +
 
 +
 
 +
* vložiť nový vrchol s hodnotou -7 za nájdený Ity:
 +
  P := Ity(Z, 5);
 +
  if P <> nil then
 +
  begin
 +
    New(Q);
 +
    Q^.Info := -7;
 +
    Q^.Next := P^.Next;
 +
    P^.Next := Q;
 +
  end;
 +
  Vypis(Z);
 +
* urobiť z toho procedú '''VlozZa''' - nezabudnúť na ''if P <> nil then''
 +
procedure VlozZa(P: PVrchol; X: Integer);
 +
var
 +
  Q: PVrchol;
 +
begin
 +
  if P <> nil then
 +
  begin
 +
    New(Q);
 +
    Q^.Info := X;
 +
    Q^.Next := P^.Next;
 +
    P^.Next := Q;
 +
  end;
 +
end;
 +
* otestovať, napr.
 +
  for I := 3 to 7 do
 +
    VlozZa(Ity(Z, I), I);
 +
* procedúra '''VyhodZa''' vyhodí vrchol za zadaným vrcholom, napr.
 +
procedure VyhodZa(P: PVrchol);
 +
var
 +
  Q: PVrchol;
 +
begin
 +
  if (P <> nil) and (P^.Next <> nil) then  ''// Aspon2(P)''
 +
  begin
 +
    Q := P^.Next;
 +
    P^.Next := Q^.Next;
 +
    Dispose(Q);
 +
  end;
 +
end;
 +
* vyhodiť vrchol so zadanou adresou (smerníkom) - najprv nechať rozmýšľať, ako to urobiť ...
 +
procedure Vyhod(P: PVrchol);
 +
* vyhodiť vrchol so zadanou adresou (smerníkom) - potrebujeme aj začiatok celého zoznamu - musíme nájsť predchodcu
 +
procedure Vyhod(var Z: PVrchol; P: PVrchol);
 +
var
 +
  Q: PVrchol;
 +
begin
 +
  if (Z = nil) or (P = nil) then
 +
    Exit;
 +
  if Z = P then
 +
  begin
 +
    Z := P^.Next;
 +
    Dispose(P);
 +
  end
 +
  else
 +
  begin
 +
    Q := Z;
 +
    while (Q^.Next <> nil) and (Q^.Next <> P) do
 +
      Q := Q^.Next;
 +
    if Q^.Next = P then
 +
    begin
 +
      Q^.Next := P^.Next;
 +
      Dispose(P);
 +
    end;
 +
  end;
 +
end;
 +
 
 +
Ďalšie úlohy
 +
* vyhodiť vrchol so zadanou hodnotou - treba nájsť nie samotný vyhadzovaný vrchol, ale jeho predchodcu
 +
* vyhodiť i-ty vrchol
 +
* za každý vrchol vložiť nový vrchol s nulovou hodnotou
 +
* medzi každé dva vrcholy vložiť nový vrchol s ich súčtom (na začiatku napr. 1 -> 1 -> a potom to spúšťať a vypisovať veľakrát)
 +
* procedúra '''VyhodNulove''' vyhodí zo zoznamu všetky vrcholy s nulovou hodnotou
 +
* funkcia vymení poradie dvoch nasledovníkov parametra '''P: PVrchol''', t.j. '''P^.Next''' a '''P^.Next^.Next'''
 +
* vložiť zadanú hodnotu na náhodne miesto v zozname (s rovnakou pravdepodobnosťou pre všetkých, aj pred prvý, aj za posledný)
 +
 
 +
 
  
 
=== Domáca úloha ===
 
=== Domáca úloha ===

Verzia zo dňa a času 15:05, 3. apríl 2013

26. Cvičenie


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


Rozcvička

1. kopírovať binárny súbor integer.dat do real.dat

  • kde vstupný súbor obsahuje postupnosť celých čísel a výstupný súbor bude obsahovať tie isté čísla ale prekonvertované na reálne
  • nepoužívajte polia ani reťazce


2. kopírovať binárny súbor real.dat do integer.dat

  • kde vstupný súbor obsahuje postupnosť reálných čísel a výstupný súbor bude obsahovať tie isté čísla ale prekonvertované (Round) na celé
  • nepoužívajte polia ani reťazce


Cvičenie

  • budeme pracovať s takto zadeklarovaným spájaným zoznamom:
type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;
    Next: PVrchol;
  end;
 
var
  Z, P: PVrchol;
  • do premennej P priradiť jeden vrchol s hodnotou 1
  • teraz treba z neho urobiť jednoprvkový zoznam, t.j. v Z je na neho smerník a ďalej do P priradiť ďalší vrchol s hodnotou 2
  • pripojiť nový vrchol P na koniec zoznamu Z a znovu do P priradiť ďalší vrchol s hodnotou 3
  • pripojiť nový vrchol P na koniec zoznamu Z (ako 3. vrchol) a vypísať celý zoznam jedným WriteLn
Z^.Next^.Next := P;
 
WriteLn(Z^.Info, ' -> ', Z^.Next^.Info, ' -> ', Z^.Next^.Next^.Info, ' -> nil');
  • dostali sme výpis
1 -> 2 -> 3 -> nil
  • v programe nechať výrobu vrcholov do P (tj. vytvárať vrcholy v poradí 1, 2, 3) a zmeniť len ďalšie priradenia tak aby vzniklo takéto nové poradie
2 -> 3 -> 1 -> nil
  • podobne realizovať napr. zmenu poradia (prípadne aj iné)
3 -> 1 -> 2 -> 
  • procedúra Vypis - vypíše prvky zoznamu cyklom
procedure Vypis(Z: Pvrchol);
begin
  while Z <> nil do
  begin
    Write(Z^.Info, ' -> ');
    Z := Z^.Next;
  end;
  WriteLn('nil');
end;
  • upozorniť na to, čo by sa muselo zmeniť, keby Z bol var-parameter
  • čítať textový súbor s celými číslami a vyrábať z nich zoznam - najprv v opačnom poradí (otestovať na súbore s aspoň 5 číslami)
var
   T: TextFile;
   Z, P: PVrchol;
begin
  AssignFile(T, 'cisla.txt');
  Reset(T);
  Z := nil;
  while not SeekEOF(T) do
  begin
    New(P);
    Read(T, P^.Info);
    P^.Next := Z;
    Z := P;
  end;
  CloseFile(T);
  Vypis(Z);
  • potom čísla v správnom poradí (pridáva na koniec existujúceho zoznamu, máme ďalší smerník K na koniec zoznamu)
var
   T: TextFile;
   Z, K, P: PVrchol;
begin
  AssignFile(T, 'cisla.txt');
  Reset(T);
  Z := nil;
  K := nil;
  while not SeekEOF(T) do
  begin
    New(P);
    Read(T, P^.Info);
    P^.Next := nil;
    if Z = nil then
      Z := P
    else
      K^.Next := P;
    K := P;
  end;
  CloseFile(T);
  Vypis(Z);
  • logická funkcia Aspon1 zistí, či má zoznam aspoň jeden vrchol
function Aspon1(Z: PVrchol): Boolean;
begin
  Result := Z <> nil;
end;
  • logická funkcia Aspon2 zistí, či má zoznam aspoň dva vrcholy
function Aspon2(Z: PVrchol): Boolean;
begin
  Result := (Z <> nil) and (Z^.Next <> nil);
end;
  • alebo aj
function Aspon2(Z: PVrchol): Boolean;
begin
  Result := Aspon1(Z) and Aspon1(Z^.Next);
end;
  • logická funkcia Aspon3 zistí, či má zoznam aspoň dva vrcholy, napr. aj takto
function Aspon3(Z: PVrchol): Boolean;
begin
  Result := Aspon1(Z) and Aspon2(Z^.Next);
end;
  • funkcia Min vráti minimálnu hodnotu v zozname (pre prázdny zoznam je jedno, čo vráti)
function Min(Z: PVrchol): Integer;
begin
  Result := MaxInt;
  while Z <> nil do
  begin
    if Z^.Info < Result then
      Result := Z^.Info;
    Z := Z^.Next;
  end;
end;
&nbsp
...
  WriteLn('min = ', Min(Z));
  • funkcia MinP vráti smerník na minimálnu hodnotu (pre prázdny zoznam vráti nil)
function MinP(Z: PVrchol): PVrchol;
begin
  Result := nil;
  while Z <> nil do
  begin
    if (Result = nil) or (Z^.Info < Result^.Info) then
      Result := Z;
    Z := Z^.Next;
  end;
end;
&nbsp
...
  WriteLn('min = ', MinP(Z)^.Info);   // spadne pre prázdny zoznam


  • ďalšie funkcie ako: súčet hodnôt, priemerná hodnota, počet nulových prvkov, ...


  • funkcia Ity vráti smerník na I-ty vrchol (ak neexistuje, vráti nil)
function Ity(Z: PVrchol; I: Integer): PVrchol;
begin
  while (Z <> nil) and (I > 1) do
  begin
    Z := Z^.Next;
    Dec(I);
  end;
  Result := Z;
end;
&nbsp
...
  P := Ity(Z, 5);
  if P <> nil then
    WriteLn('ity = ', P^.Info);
  • uvažujte o takomto využití Ity (prečo je to veľmi neefektívne)
N := 1;
repeat
  P := Ity(Z, N);
  if P <> nil then
    WriteLn(N, '. prvok = ', P^.Info);
until P = nil;


  • ďalšie funkcie ako: vráti smerník na prvý vrchol s danou hodnotou, vráti index vrcholu pre prvý výskyt hodnoty, smerník na stredný vrchol, zistiť, či sa v zozname nejaké číslo neopakuje, ...


  • vložiť nový vrchol s hodnotou -7 za nájdený Ity:
  P := Ity(Z, 5);
  if P <> nil then
  begin
    New(Q);
    Q^.Info := -7;
    Q^.Next := P^.Next;
    P^.Next := Q;
  end;
  Vypis(Z);
  • urobiť z toho procedú VlozZa - nezabudnúť na if P <> nil then
procedure VlozZa(P: PVrchol; X: Integer);
var
  Q: PVrchol;
begin
  if P <> nil then
  begin
    New(Q);
    Q^.Info := X;
    Q^.Next := P^.Next;
    P^.Next := Q;
  end;
end;
  • otestovať, napr.
  for I := 3 to 7 do
    VlozZa(Ity(Z, I), I);
  • procedúra VyhodZa vyhodí vrchol za zadaným vrcholom, napr.
procedure VyhodZa(P: PVrchol);
var
  Q: PVrchol;
begin
  if (P <> nil) and (P^.Next <> nil) then   // Aspon2(P)
  begin
    Q := P^.Next;
    P^.Next := Q^.Next;
    Dispose(Q);
  end;
end;
  • vyhodiť vrchol so zadanou adresou (smerníkom) - najprv nechať rozmýšľať, ako to urobiť ...
procedure Vyhod(P: PVrchol);
  • vyhodiť vrchol so zadanou adresou (smerníkom) - potrebujeme aj začiatok celého zoznamu - musíme nájsť predchodcu
procedure Vyhod(var Z: PVrchol; P: PVrchol);
var
  Q: PVrchol;
begin
  if (Z = nil) or (P = nil) then
    Exit;
  if Z = P then
  begin
    Z := P^.Next;
    Dispose(P);
  end
  else
  begin
    Q := Z;
    while (Q^.Next <> nil) and (Q^.Next <> P) do
      Q := Q^.Next;
    if Q^.Next = P then
    begin
      Q^.Next := P^.Next;
      Dispose(P);
    end;
  end;
end;

Ďalšie úlohy

  • vyhodiť vrchol so zadanou hodnotou - treba nájsť nie samotný vyhadzovaný vrchol, ale jeho predchodcu
  • vyhodiť i-ty vrchol
  • za každý vrchol vložiť nový vrchol s nulovou hodnotou
  • medzi každé dva vrcholy vložiť nový vrchol s ich súčtom (na začiatku napr. 1 -> 1 -> a potom to spúšťať a vypisovať veľakrát)
  • procedúra VyhodNulove vyhodí zo zoznamu všetky vrcholy s nulovou hodnotou
  • funkcia vymení poradie dvoch nasledovníkov parametra P: PVrchol, t.j. P^.Next a P^.Next^.Next
  • vložiť zadanú hodnotu na náhodne miesto v zozname (s rovnakou pravdepodobnosťou pre všetkých, aj pred prvý, aj za posledný)


Domáca úloha

1. napíšte podprogram Otoc, ktorý otočí poradie prvkov zadaného zoznamu

procedure Otoc(var Z: PVrchol);
  • pritom sa nemajú vytvárať nové ani rušiť pôvodné vrcholy, len sa presmerníkujú


2. napíšte podprogram Vymen, ktorý rozsekne zoznam v strede na dva zoznamy a tie potom zlepí, ale najprv druhý a potom prvý

procedure Vymen(var Z: PVrchol);
  • pritom sa nemajú vytvárať nové ani rušiť pôvodné vrcholy, len sa presmerníkujú
  • napr. pre zoznam
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 
po výmene dostávame zoznam
4 -> 5 -> 6 -> 1 -> 2 -> 3 -> 


3. procedúra VyhodDuplikaty vyhodí zo zoznamu všetky ďalšie výskyty tej iste hodnoty

procedure VyhodDuplikaty(Z: PVrchol);