3. Jednosmerný lineárny zoznam
3.7 Usporiadaný zoznam
Každý "rozumný" programátor (tým myslím samozrejme aj čitateľa :-), si určite uvedomuje výhody práce s usporiadanými zoznamami. Ak máme uzly zoznamu usporiadané podľa určitého kľúča, môžeme v ňom vyhľadávať efektívne, napríklad ukončiť vyhľadávanie po dosiahnutí hodnoty väčšej ako je hľadaná (v prípade zoznamu uporiadaného podľa hodnoty kľúča vzostupne).
Ako dosiahnuť, aby bol zoznam usporiadaný?
Jednou z možností je pridávať nové prvky do zoznamu na správne miesto hneď pri ich vytvorení. Alebo inak povedané: vytvárať usporiadaný zoznam. Tento (v mnohých úlohách používaný) postup, si môžeme precvičiť v prvej z nasledujúcich dvoch úloh.
Usporiadať už existujúci (neusporiadaný) zoznam je o niečo ťažšie. (Samozrejme ako pre koho :-). Pri riešení tohto problému môžme použiť niektorý zo známych triediacich algoritmov (napr. triedenie priamym výberom). Pri triedení môžme vymieňať hodnoty uzlov, alebo presmerovávať ukazovatele v týchto uzloch. Meniť hodnoty ukazovateľov je často výhodnejšie ako vymieňať hodnotové časti uzlov, ktoré zväčša zaberajú v pamäti oveľa viac miesta.
Precvičme si
|
| [Riešenie] |
|
| [Riešenie] |
Vytvorte
program, ktorý vytvorí pre zadané N usporiadaný lineárny zoznam celých
čísel, ktoré načítame zo vstupu (prípadane zo súboru). Čísla nie sú na
vstupe usporiadané, v zozname však budú usporiadané podľa veľkosti
(vzostupne - t.j. od najmenšieho po najväčšie). Usporiadaný zoznam
vypíšte na obrazovku (resp. uložte do súboru).
