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; |
