26.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 1: Riadok 1:
{{Nadpis| 26. Cvičenie}}
+
{{Nadpis| 27. Cvičenie}}
[[26.Prednaska|< 26.Prednáška]] | [[26.Prednaska/Ulohy|riešené úlohy]]
+
[[27.Prednaska|< 27.Prednáška]] | [[27.Prednaska/Ulohy|riešené úlohy]]
  
  
Riadok 7: Riadok 7:
  
  
1. kopírovať binárny súbor '''integer.dat''' do '''real.dat'''
+
1. pre spájaný zoznam
* kde vstupný súbor obsahuje postupnosť celých čísel a výstupný súbor bude obsahovať tie isté čísla ale prekonvertované na reálne
+
{{Prog}}
* 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
 
  type
 
   PVrchol = ^TVrchol;
 
   PVrchol = ^TVrchol;
Riadok 28: Riadok 15:
 
     Next: PVrchol;
 
     Next: PVrchol;
 
   end;
 
   end;
&nbsp;
 
var
 
  Z, P: PVrchol;
 
* do premennej '''P''' priradiť jeden vrchol s hodnotou 1
 
New(P);
 
P^.Info := 1;
 
P^.Next := nil;
 
* 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
 
Z := P;
 
&nbsp;
 
New(P);
 
P^.Info := 2;
 
P^.Next := nil;
 
* pripojiť nový vrchol '''P''' na koniec zoznamu '''Z''' a znovu do '''P''' priradiť ďalší vrchol s hodnotou 3
 
Z^.Next := P;
 
&nbsp;
 
New(P);
 
P^.Info := 3;
 
P^.Next := nil;
 
* pripojiť nový vrchol '''P''' na koniec zoznamu '''Z''' (ako 3. vrchol) a vypísať celý zoznam jedným '''WriteLn'''
 
Z^.Next^.Next := P;
 
&nbsp;
 
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''' a zmeniť len ďalšie priradenia tak aby vzniklo takéto nové poradie
+
* napísať procedúru '''Urob(Z: PVrchol)''', ktorá za každý vrchol s párnou hodnotou vloží nový vrchol s nulovou hodnotou, napr. zo zoznamu
 
{{Prog}}
 
{{Prog}}
  2 -> 3 -> 1 -> nil
+
  4 -> 5 -> 6 -> 7 -> 8 -> nil
 
|}
 
|}
* riešenie
+
:vyrobí zoznam
''// P => 1''
+
Z := P;
+
''// P => 2''
+
P^.Next := Z;
+
Z := P;
+
''// P => 3''
+
P^.Next := Z^.Next;
+
Z^.Next := P;
+
''// výpis''
+
* podobne realizovať napr. zmenu poradia (prípadne aj iné)
+
 
{{Prog}}
 
{{Prog}}
  3 -> 1 -> 2 ->  
+
  4 -> 0 -> 5 -> 6 -> 0 -> 7 -> 8 -> 0 -> nil
 
|}
 
|}
* procedúra '''Vypis''' - vypíše prvky zoznamu cyklom
+
 
  procedure Vypis(Z: Pvrchol);
+
 
 +
 
 +
=== Cvičenie ===
 +
 
 +
 
 +
* vrchol ako objekt
 +
 
 +
* pracujeme s triedou '''TVrchol''' - definujeme v '''Unit1.pas'''
 +
  TVrchol = class
 +
  Info: Integer;
 +
  Next: TVrchol;
 +
  constructor Create(I: Integer; N: TVrchol);
 +
  function Text: string;
 +
end;
 +
&nbsp;
 +
function TVrchol.Text: string
 +
begin
 +
  Result := ' ' + IntToStr(Info);
 +
end;
 +
 
 +
* otestujeme - vytvoriť premennú typu '''TVrchol''', vložiť trojprvkový zoznam a vypísať
 +
var
 +
  Z: TVrchol;
 +
begin
 +
  Z := TVrchol.Create(5, TVrchol.Create(7, TVrchol.Create(11, nil)));
 +
  Writeln(Z.Text, Z.Next.Text, Z.Next.Next.Text);
 +
 
 +
* definovať triedu '''TZoznam''' (v Unit1.pas) okrem '''Z''' a '''K''' aj metódu '''PridajZ''' - pridá vrchol na začiatok
 +
TZoznam = class
 +
  Z, K: TVrchol;
 +
  procedure PridajZ(I: Integer);
 +
end;
 +
&nbsp;
 +
procedure TZoznam.PridajZ(I: Integer);
 +
begin
 +
  Z := Vrchol.Create(I, Z);
 +
  if Z.Next = nil then
 +
    K := Z;
 +
end;
 +
 
 +
* definovať metódu '''Vypis''' (u nás sa podarilo takéto chybné riešenie, tak sme ho ďalej takéto testovali)
 +
procedure TZoznam.Vypis;
 
  begin
 
  begin
 
   while Z <> nil do
 
   while Z <> nil do
 
   begin
 
   begin
     Write(Z^.Info, ' -> ');
+
     Write(Z.Text, ' -> ');
     Z := Z^.Next;
+
     Z := P.Next;
 
   end;
 
   end;
   WriteLn('nil');
+
   Writeln;
 
  end;
 
  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)
+
* test metód
 
  var
 
  var
    T: TextFile;
+
  Zoznam: TZoznam;
    Z, P: PVrchol;
+
  I: Integer;
 
  begin
 
  begin
   AssignFile(T, 'cisla.txt');
+
   Zoznam := TZoznam.Create;
   Reset(T);
+
  for I := 1 to 8 do
   Z := nil;
+
    Zoznam.PridajZ(I);
   while not SeekEOF(T) do
+
  Zoznam.Vypis;
 +
  Zoznam.PridajZ(9);
 +
   Zoznam.Vypis;
 +
 
 +
* po prvom výpise zoznamu je tento už prázdny (metóda '''Vypis''' okrem výpisu ho vyprázdni), treba si to zapamätať a teda opraviť
 +
procedure TZoznam.Vypis;
 +
var
 +
   P: TVrchol;
 +
begin
 +
  P := Z;
 +
   while P <> nil do
 
   begin
 
   begin
     New(P);
+
     Write(P.Text, ' -> ');
    Read(T, P^.Info);
+
     P := P.Next;
     P^.Next := Z;
+
    Z := P;
+
 
   end;
 
   end;
   CloseFile(T);
+
   Writeln;
  Vypis(Z);
+
end;
* potom čísla v správnom poradí (pridáva na koniec existujúceho zoznamu, máme ďalší smerník '''K''' na koniec zoznamu)
+
 
 +
* metóda TZoznam.PridajK - pridá vrchol na koniec (aby sme predišli chybám, je dobre si situáciu nakresliť)
 +
procedure TZoznam.PridajK(I: Integer);
 
  var
 
  var
    T: TextFile;
+
  R: TVrchol;
    Z, K, P: PVrchol;
+
 
  begin
 
  begin
   AssignFile(T, 'cisla.txt');
+
   R := Vrchol.Create(I, nil);
   Reset(T);
+
   if K = nil then
  Z := nil;
+
  K := nil;
+
  while not SeekEOF(T) do
+
 
   begin
 
   begin
     New(P);
+
     Z := R;
     Read(T, P^.Info);
+
     K := R;
    P^.Next := {{Blue|nil}};
+
  end
    if Z = nil then
+
  else
      Z := P
+
  begin
     else
+
     K.Next := R;
      K^.Next := P;
+
     K := R;
     K := P;
+
 
   end;
 
   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;
 
  end;
* logická funkcia '''Aspon2''' zistí, či má zoznam aspoň dva vrcholy
+
 
  function Aspon2(Z: PVrchol): Boolean;
+
* metóda TZoznam.VyhodZ - vyhodí prvý vrchol
 +
  procedure TZoznam.VyhodZ;
 +
var
 +
  P: TVrchol;
 
  begin
 
  begin
   Result := (Z <> nil) and (Z^.Next <> nil);
+
   if Z <> nil then
 +
  begin
 +
    P := Z.Next;
 +
    Z.Free;
 +
    Z := P;
 +
    if Z.Next = nil then
 +
      K := P;
 +
  end
 
  end;
 
  end;
* alebo aj
+
 
  function Aspon2(Z: PVrchol): Boolean;
+
* deštruktor '''Dispose''' (aj pomocou '''VyhodZ''')
 +
  destructor TZoznam.Destroyô
 
  begin
 
  begin
   Result := Aspon1(Z) and Aspon1(Z^.Next);
+
   ...
 
  end;
 
  end;
* logická funkcia '''Aspon3''' zistí, či má zoznam aspoň dva vrcholy, napr. aj takto
+
function Aspon3(Z: PVrchol): Boolean;
+
** rôzne konštruktory: otvorené pole, textový/binárny súbor, reťazec, iný zoznam
begin
+
** konštruktor generuje postupnosť
   Result := Aspon1(Z) and Aspon2(Z^.Next);
+
** deštruktor uloží do súboru
 +
** funkcia vráti dynamické pole z hodnôt zoznamu
 +
* udržiavať zoznam utriedený - pridávať na správne miesto (za menší pred väčší)
 +
* minimálny prvok presťahuje na začiatok
 +
* procedurálny typ
 +
* metódy dvojsmerného spájaného zoznamu
 +
* metódy cyklického spájaného zoznamu
 +
 
 +
Ďalšie námety na metódy pre triedu '''TZoznam''':
 +
* procedure VyhodZ;                    ''// vyhodí prvý prvok''
 +
* procedure VyhodK;                    ''// vyhodí posledný prvok''
 +
* procedure VyhodIty(Index: Integer);  ''// vyhodí prvok s indexom Index''
 +
* procedure Vyhod(I: Integer);        ''// vyhodí prvok s Info I''
 +
* procedure Prevrat;                  ''// prevráti poradie prvkov v zozname''
 +
* function Najdi(I: Integer): Integer; ''// zistí index''
 +
* procedure Utried;
 +
** nájde minimum, dá ho na začiatok, znovu nájde minimum zo zvyšku, dá ho za minimum, ...
 +
* procedure zarad(I: Integer);
 +
** zaradí prvok do zoznamu, aby ostal zoznam utriedený
 +
* procedure VyhodDuplikaty;
 +
** vyhodí vrcholy s rovnakým Info - nechá len prvý z nich
 +
* function Ity(I: Integer): TVrchol;   ''// vráti í-ty prvok''
 +
* constructor Citaj(Stream: TStream);  ''// načíta zoznam z prúdu''
 +
 
 +
 
 +
 
 +
 
 +
=== Domáca úloha ===
 +
 
 +
1. Vytvorte triedu '''TSlovnik''', ktorá do spájaného zoznamu načíta zo súboru (napr. '''slovnik.txt''') zoznam dvojíc slov (slovenské anglické), napr.
 +
{{Prog}}
 +
pes dog
 +
macka cat
 +
...
 +
|}
 +
* trieda '''TSlovnik''' je spájaným zoznamom, ktorý bude mať vrcholy utriedené podľa anglických slovíčok, napr.
 +
{{Prog}}
 +
TVrchol = class
 +
  Slov, Angl: string;
 +
  Next: TVrchol;
 +
  ...
 
  end;
 
  end;
* funkcia '''Min''' vráti minimálnu hodnotu v zozname (pre prázdny zoznam je jedno, čo vráti)
+
&nbsp;
  function Min(Z: PVrchol): Integer;
+
TSlovnik = class
 +
  Z: Tvrchol;
 +
  constructor Create(Subor: string);
 +
  procedure Vloz(S, A: string);    ''// vloží do zoznamu na správne miesto ďalšiu dvojicu slov''
 +
  ...
 +
end;
 +
|}
 +
 
 +
 
 +
 
 +
 
 +
----
 +
 
 +
 
 +
 
 +
* konstruktor - bez parametra aj s parametrom
 +
class TZoznam
 +
  constructor Create;
 +
  constructor Create(N:integer);
 +
  ...
 +
  &nbsp;
 +
constructor TZoznam.Create(N: Integer);
 
  begin
 
  begin
  Result := MaxInt;
+
   while N > 0 do
   while Z <> nil do
+
 
   begin
 
   begin
     if Z^.Info < Result then
+
     PridajZ(N);
      Result := Z^.Info;
+
     Dec(N);
     Z := Z^.Next;
+
 
   end;
 
   end;
 
  end;
 
  end;
&nbsp
+
* v testovacom module mozeme for cyklus nahradit konstruktorom
  ...
+
  Z := TZoznam.Create(8);
  WriteLn('min = ', Min(Z));
+
 
* funkcia '''MinP''' vráti smerník na minimálnu hodnotu (pre prázdny zoznam vráti '''nil''')
+
8. Limitovať výpis na prvých 100 prvkov (ak pridlhý zoznam, tak len prvých 100 a ...)
  function MinP(Z: PVrchol): PVrchol;
+
  procedure TZoznam.Vypis;
 +
var
 +
  P: TVrchol;
 +
  i: integer;
 
  begin
 
  begin
   Result := nil;
+
   P:=Z;
   while Z <> nil do
+
  i:=0;
 +
   while (P <> nil) and (i < 100) do
 
   begin
 
   begin
     if (Result = nil) or (Z^.Info < Result^.Info) then
+
     Write(P.Text, ' -> ');
      Result := Z;
+
     P:=P.Next;
     Z := Z^.Next;
+
    Inc(i);
 
   end;
 
   end;
 +
  if (P <> nil)
 +
    Write('...');
 +
  Writeln;
 
  end;
 
  end;
&nbsp
 
...
 
  WriteLn('min = ', MinP(Z)^.Info);  ''// spadne pre prázdny zoznam''
 
  
 
+
9. metoda TZoznam.pocet
* ''ďalšie funkcie ako: súčet hodnôt, priemerná hodnota, počet nulových prvkov, ...''
+
  function TZoznam.Pocet :integer;
 
+
var
 
+
  P:TVrchol;
* funkcia '''Ity''' vráti smerník na I-ty vrchol (ak neexistuje, vráti '''nil''')
+
  i:integer;
  function Ity(Z: PVrchol; I: Integer): PVrchol;
+
 
  begin
 
  begin
   while (Z <> nil) and (I > 1) do
+
  P:=Z;
 +
  i:=0;
 +
   while (P <> nil) do
 
   begin
 
   begin
     Z := Z^.Next;
+
     P:=P.Next;
     Dec(I);
+
     Inc(i);
 
   end;
 
   end;
   Result := Z;
+
   result := i;
 
  end;
 
  end;
&nbsp
+
* test
  ...
+
  Z:=TZoznam.Create(1000000);
  P := Ity(Z, 5);
+
Z.Vypis;
  if P <> nil then
+
Z.Pridaj(9);
    WriteLn('ity = ', P^.Info);
+
  Z.Vypis;
* uvažujte o takomto využití '''Ity''' (prečo je to veľmi neefektívne)
+
Writeln('Pocet = ', Z.Pocet);
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, ...''
+
  
 +
10. konstruktor s otvorenym polom ako parametrom
 +
constructor TZoznam.Create(A:array of integer);
 +
var i:integer;
 +
begin
 +
  for i := 0 to high(A) do
 +
    PridajK(A[i]);
 +
end;
 +
* ina moznost napisat for cyklus
 +
constructor TZoznam.Create(A:array of integer);
 +
var i:integer;
 +
begin
 +
  for i in A do
 +
    PridajK(i);
 +
end;
  
* vložiť nový vrchol s hodnotou -7 za nájdený Ity:
+
11. konstruktor, ktory dostava iny zoznam ako parameter a vytvori kopiu zoznamu
  P := Ity(Z, 5);
+
constructor TZoznam.Create(A:TZoznam);
  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
 
  var
   Q: PVrchol;
+
   P:TVrchol;
 
  begin
 
  begin
   if P <> nil then
+
   P:=A.Z;
 +
  while P <> nil do
 
   begin
 
   begin
     New(Q);
+
     PridajK(P.Info);
    Q^.Info := X;
+
     P := P.Next;
     Q^.Next := P^.Next;
+
    P^.Next := Q;
+
 
   end;
 
   end;
 
  end;
 
  end;
* otestovať, napr.
+
* test
  for I := 3 to 7 do
+
Z:=TZoznam.Create([2,3,5,7,11,13]);
    VlozZa(Ity(Z, I), I);
+
R:=TZoznam.Create(Z);
* procedúra '''VyhodZa''' vyhodí vrchol za zadaným vrcholom, napr.
+
R.PridajK(17);
  procedure VyhodZa(P: PVrchol);
+
Z.Vypis;
 +
R.Vypis;
 +
 
 +
12. procedura append
 +
  procedure TZoznam.Append(A:TZoznam);
 
  var
 
  var
   Q: PVrchol;
+
   P:TVrchol;
 
  begin
 
  begin
   if (P <> nil) and (P^.Next <> nil) then  ''// Aspon2(P)''
+
   P:=A.Z;
 +
  while P <> nil do
 
   begin
 
   begin
     Q := P^.Next;
+
     PridajK(P.Info);
     P^.Next := Q^.Next;
+
     P := P.Next;
    Dispose(Q);
+
 
   end;
 
   end;
 
  end;
 
  end;
* vyhodiť vrchol so zadanou adresou (smerníkom) - najprv nechať rozmýšľať, ako to urobiť ...
+
 
  procedure Vyhod(P: PVrchol);
+
13. procedura append rychlejsie
* vyhodiť vrchol so zadanou adresou (smerníkom) - potrebujeme aj začiatok celého zoznamu - musíme nájsť predchodcu
+
  procedure TZoznam.Append(A:TZoznam);
procedure Vyhod(var Z: PVrchol; P: PVrchol);
+
 
  var
 
  var
   Q: PVrchol;
+
   P:TVrchol;
 
  begin
 
  begin
   if (Z = nil) or (P = nil) then
+
   if (z<>nil) and (Q.Z <> nil) then
    Exit;
+
  if Z = P then
+
 
   begin
 
   begin
     Z := P^.Next;
+
     K.next:=A.Z;
    Dispose(P);
+
     K:=Q.K;
  end
+
     Q.Z:=nil;
  else
+
     Q.K:=nil;
  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;
 +
  ... zvysne kombinacie testov na nil
 
  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
 
{{Prog}}
 
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ý
 
{{Prog}}
 
procedure Vymen(var Z: PVrchol);
 
|}
 
* pritom sa nemajú vytvárať nové ani rušiť pôvodné vrcholy, len sa presmerníkujú
 
* napr. pre zoznam
 
{{Prog}}
 
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
 
|}
 
: po výmene dostávame zoznam
 
{{Prog}}
 
4 -> 5 -> 6 -> 1 -> 2 -> 3 ->
 
|}
 
 
 
 
3. procedúra '''VyhodDuplikaty''' vyhodí zo zoznamu všetky ďalšie výskyty tej iste hodnoty
 
{{Prog}}
 
procedure VyhodDuplikaty(Z: PVrchol);
 
|}
 

Verzia zo dňa a času 16:10, 4. marec 2013

27. Cvičenie


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


Rozcvička

1. pre spájaný zoznam

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;
    Next: PVrchol;
  end;
  • napísať procedúru Urob(Z: PVrchol), ktorá za každý vrchol s párnou hodnotou vloží nový vrchol s nulovou hodnotou, napr. zo zoznamu
4 -> 5 -> 6 -> 7 -> 8 -> nil
vyrobí zoznam
4 -> 0 -> 5 -> 6 -> 0 -> 7 -> 8 -> 0 -> nil


Cvičenie

  • vrchol ako objekt
  • pracujeme s triedou TVrchol - definujeme v Unit1.pas
TVrchol = class
  Info: Integer;
  Next: TVrchol;
  constructor Create(I: Integer; N: TVrchol);
  function Text: string;
end;
 
function TVrchol.Text: string
begin
  Result := ' ' + IntToStr(Info);
end;
  • otestujeme - vytvoriť premennú typu TVrchol, vložiť trojprvkový zoznam a vypísať
var
  Z: TVrchol;
begin
  Z := TVrchol.Create(5, TVrchol.Create(7, TVrchol.Create(11, nil)));
  Writeln(Z.Text, Z.Next.Text, Z.Next.Next.Text);
  • definovať triedu TZoznam (v Unit1.pas) okrem Z a K aj metódu PridajZ - pridá vrchol na začiatok
TZoznam = class
  Z, K: TVrchol;
  procedure PridajZ(I: Integer);
end;
 
procedure TZoznam.PridajZ(I: Integer);
begin
  Z := Vrchol.Create(I, Z);
  if Z.Next = nil then
    K := Z;
end;
  • definovať metódu Vypis (u nás sa podarilo takéto chybné riešenie, tak sme ho ďalej takéto testovali)
procedure TZoznam.Vypis;
begin
  while Z <> nil do
  begin
    Write(Z.Text, ' -> ');
    Z := P.Next;
  end;
  Writeln;
end;
  • test metód
var
  Zoznam: TZoznam;
  I: Integer;
begin
  Zoznam := TZoznam.Create;
  for I := 1 to 8 do
    Zoznam.PridajZ(I);
  Zoznam.Vypis;
  Zoznam.PridajZ(9);
  Zoznam.Vypis;
  • po prvom výpise zoznamu je tento už prázdny (metóda Vypis okrem výpisu ho vyprázdni), treba si to zapamätať a teda opraviť
procedure TZoznam.Vypis;
var
  P: TVrchol;
begin
  P := Z;
  while P <> nil do
  begin
    Write(P.Text, ' -> ');
    P := P.Next;
  end;
  Writeln;
end;
  • metóda TZoznam.PridajK - pridá vrchol na koniec (aby sme predišli chybám, je dobre si situáciu nakresliť)
procedure TZoznam.PridajK(I: Integer);
var
  R: TVrchol;
begin
  R := Vrchol.Create(I, nil);
  if K = nil then
  begin
    Z := R;
    K := R;
  end
  else
  begin
    K.Next := R;
    K := R;
  end;
end;
  • metóda TZoznam.VyhodZ - vyhodí prvý vrchol
procedure TZoznam.VyhodZ;
var
  P: TVrchol;
begin
  if Z <> nil then
  begin
    P := Z.Next;
    Z.Free;
    Z := P;
    if Z.Next = nil then
      K := P;
  end
end;
  • deštruktor Dispose (aj pomocou VyhodZ)
destructor TZoznam.Destroyô
begin
  ...
end;

    • rôzne konštruktory: otvorené pole, textový/binárny súbor, reťazec, iný zoznam
    • konštruktor generuje postupnosť
    • deštruktor uloží do súboru
    • funkcia vráti dynamické pole z hodnôt zoznamu
  • udržiavať zoznam utriedený - pridávať na správne miesto (za menší pred väčší)
  • minimálny prvok presťahuje na začiatok
  • procedurálny typ
  • metódy dvojsmerného spájaného zoznamu
  • metódy cyklického spájaného zoznamu

Ďalšie námety na metódy pre triedu TZoznam:

  • procedure VyhodZ; // vyhodí prvý prvok
  • procedure VyhodK; // vyhodí posledný prvok
  • procedure VyhodIty(Index: Integer); // vyhodí prvok s indexom Index
  • procedure Vyhod(I: Integer); // vyhodí prvok s Info I
  • procedure Prevrat; // prevráti poradie prvkov v zozname
  • function Najdi(I: Integer): Integer; // zistí index
  • procedure Utried;
    • nájde minimum, dá ho na začiatok, znovu nájde minimum zo zvyšku, dá ho za minimum, ...
  • procedure zarad(I: Integer);
    • zaradí prvok do zoznamu, aby ostal zoznam utriedený
  • procedure VyhodDuplikaty;
    • vyhodí vrcholy s rovnakým Info - nechá len prvý z nich
  • function Ity(I: Integer): TVrchol; // vráti í-ty prvok
  • constructor Citaj(Stream: TStream); // načíta zoznam z prúdu



Domáca úloha

1. Vytvorte triedu TSlovnik, ktorá do spájaného zoznamu načíta zo súboru (napr. slovnik.txt) zoznam dvojíc slov (slovenské anglické), napr.

pes dog
macka cat
...
  • trieda TSlovnik je spájaným zoznamom, ktorý bude mať vrcholy utriedené podľa anglických slovíčok, napr.
TVrchol = class
  Slov, Angl: string;
  Next: TVrchol;
  ...
end;
 
TSlovnik = class
  Z: Tvrchol;
  constructor Create(Subor: string);
  procedure Vloz(S, A: string);     // vloží do zoznamu na správne miesto ďalšiu dvojicu slov
  ...
end;





  • konstruktor - bez parametra aj s parametrom
class TZoznam
  constructor Create;
  constructor Create(N:integer);
  ...
 
constructor TZoznam.Create(N: Integer);
begin
  while N > 0 do
  begin
    PridajZ(N);
    Dec(N);
  end;
end;
  • v testovacom module mozeme for cyklus nahradit konstruktorom
Z := TZoznam.Create(8);

8. Limitovať výpis na prvých 100 prvkov (ak pridlhý zoznam, tak len prvých 100 a ...)

procedure TZoznam.Vypis;
var
  P: TVrchol;
  i: integer;
begin
  P:=Z;
  i:=0;
  while (P <> nil) and (i < 100) do
  begin
    Write(P.Text, ' -> ');
    P:=P.Next;
    Inc(i);
  end;
  if (P <> nil)
    Write('...');
  Writeln;
end;

9. metoda TZoznam.pocet

function TZoznam.Pocet :integer;
var
  P:TVrchol;
  i:integer;
begin
  P:=Z;
  i:=0;
  while (P <> nil) do
  begin
    P:=P.Next;
    Inc(i);
  end;
  result := i;
end;
  • test
Z:=TZoznam.Create(1000000);
Z.Vypis;
Z.Pridaj(9);
Z.Vypis;
Writeln('Pocet = ', Z.Pocet);

10. konstruktor s otvorenym polom ako parametrom

constructor TZoznam.Create(A:array of integer);
var i:integer;
begin
  for i := 0 to high(A) do
    PridajK(A[i]);
end;
  • ina moznost napisat for cyklus
constructor TZoznam.Create(A:array of integer);
var i:integer;
begin
  for i in A do
    PridajK(i);
end;

11. konstruktor, ktory dostava iny zoznam ako parameter a vytvori kopiu zoznamu

constructor TZoznam.Create(A:TZoznam);
var
  P:TVrchol;
begin
  P:=A.Z;
  while P <> nil do
  begin
    PridajK(P.Info);
    P := P.Next;
  end;
end;
  • test
Z:=TZoznam.Create([2,3,5,7,11,13]);
R:=TZoznam.Create(Z);
R.PridajK(17);
Z.Vypis;
R.Vypis;

12. procedura append

procedure TZoznam.Append(A:TZoznam);
var
  P:TVrchol;
begin
  P:=A.Z;
  while P <> nil do
  begin
    PridajK(P.Info);
    P := P.Next;
  end;
end;

13. procedura append rychlejsie

procedure TZoznam.Append(A:TZoznam);
var
  P:TVrchol;
begin
  if (z<>nil) and (Q.Z <> nil) then
  begin
    K.next:=A.Z;
    K:=Q.K;
    Q.Z:=nil;
    Q.K:=nil;
  end;
  ... zvysne kombinacie testov na nil
end;