26.Prednaska/Cvicenie

26. Cvičenie

---

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

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(Z: Pvrchol) - vypíše prvky zoznamu cyklom

• upozorniť na to, čo by sa muselo zmeniť, keby Z bol var-parameter a v zozname sa posúvali pomocou Z := Z^.Next;

• čí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)

• potom čísla v správnom poradí (pridáva na koniec existujúceho zoznamu, máme ďalší smerník K na koniec zoznamu)

• logická funkcia Aspon1 zistí, či má zoznam aspoň jeden vrchol

• logická funkcia Aspon2 zistí, či má zoznam aspoň dva vrcholy

• s využitím aj bez využitia Aspon1

• logická funkcia Aspon3 zistí, či má zoznam aspoň tri vrcholy

• funkcia Min(Z: PVrchol): Integer vráti minimálnu hodnotu v zozname (pre prázdny zoznam je jedno, čo vráti)

• funkcia MinP(Z: PVrchol): PVrchol vráti smerník na minimálnu hodnotu (pre prázdny zoznam vráti nil)

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

• funkcia Ity(Z: PVrchol; I: Integer): PVrchol vráti smerník na I-ty vrchol (ak neexistuje, vráti nil)

  funkcia vlastne preskáče na I-ty vrchol

• 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:

• urobiť z toho procedú VlozZa(P: PVrchol; X: Integer)

• nezabudnúť na if P <> nil then

• procedúra VyhodZa(P: PVrchol) vyhodí vrchol za zadaným vrcholom, napr.

• vyhodiť vrchol so zadanou adresou (smerníkom)

procedure Vyhod(P: PVrchol);

• potrebujeme aj začiatok celého zoznamu - musíme nájsť predchodcu

procedure Vyhod(var Z: PVrchol; P: PVrchol);

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