27.Prednaska/Cvicenie0
Z Pascal
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 := Z.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 while Z <> nil do VyhodZ; end;
- trieda TZoznam môže mať viac konštruktorov - zatiaľ sme používali bez parametrov, ak chceme aj s parametrom (a aby fungoval aj bez parametrov) musíme zadefinovať oba
class TZoznam constructor Create; constructor Create(N: Integer); // vytvorí zoznam čísel 1 -> 2 -> ... N -> ... constructor TZoznam.Create; begin end; constructor TZoznam.Create(N: Integer); begin while N > 0 do begin PridajZ(N); Dec(N); end; end;
- chceme to otestovať pre veľké N - aby mal zmysel výpis metódou Vypis aj pre veľké N (napr. 1000000), upravíme túto metódu - výpis maximálne prvých 100 prvkov (ak pridlhý zoznam, tak len prvých 100)
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 then Write('...'); Writeln; end;
- metóda Pocet zistí počet prvkov zoznamu
function TZoznam.Pocet: Integer; var P:TVrchol; begin P := Z; Result := 0; while P <> nil do begin P := P.Next; Inc(Result); end; end;
- otestujeme
Z := TZoznam.Create(1000000); Z.Vypis; Z.PridajZ(9); Z.Vypis; Writeln('Pocet = ', Z.Pocet);
- konštruktor s parametrom otvoreným poľom
constructor TZoznam.Create(A: array of Integer); var I: Integer; begin for I := 0 to High(A) do PridajK(A[I]); end;
- iná možnosť napísať for-cyklus
constructor TZoznam.Create(A: array of Integer); var I: Integer; begin for I in A do PridajK(I); end;
- konštruktor, ktorý dostáva iný zoznam ako parameter a vytvorí kópiu tohto 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;
- otestujeme, napr.
Z := TZoznam.Create([2, 3, 5, 7, 11, 13]); R := TZoznam.Create(Z); R.PridajK(17); Z.Vypis; R.Vypis;
- procedúra Append - pripojí iný zoznam na koniec svojho - robí pritom kópiu prvkov
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;
- druhá verzia procedury Append - nerobí kópi prvkov, ale priamo si ho pripojí - iný zoznam pri tom zruší
procedure TZoznam.Append(A: TZoznam); begin if A.Z <> nil then begin if Z = nil then Z := A.Z else K.Next := A.Z; K := A.K; A.Z := nil; A.K := nil; end; end;
ďalšie námety
- ďalšie konštruktory: textový/binárny súbor, reťazec s číslami oddelenými medzerami, iný zoznam v opačnom poradí prvkov
- deštruktor uloží zoznam do súboru
- funkcia VyrobPole 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
- VyhodK - vyhodí posledný prvok
- VyhodIty(Index: Integer) - vyhodí prvok s indexom Index
- Vyhod(I: Integer) - vyhodí prvok s daným Info
- Prevrat - prevráti poradie prvkov v zozname
- Najdi(I: Integer): Integer - zistí index
- procedurálny typ ...
- metódy dvojsmerného spájaného zoznamu
- metódy cyklického spájaného zoznamu
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; |