Anonymní profil Honza – Programujte.com

Připojen obrázek.

zdravím, mám zadání na zápočet ale nějak s s tím nevím rad (spíš jakým způsobem to mám dělat) :
 

Výstup je (bez úprav na schématu úpravy barevně): 1 3 5 7 9 11

Po úpravách (na schématu barevně) je výstup: 1 2 3 5 9 11. Co ukazuje modrá barva?

Prvek 7 není dostupný (takže logicky neexistuje – odpad - garbage).

Poučení: program musí fungovat i pro mezní (či „odlehlé“) situace, např. zde když je seznam prázdný.

Domácí cvičení: kromě uvedené úlohy „vypiš“ naprogramujte i funkce „vlož“ a „zruš“ (prvek nemusí v seznamu být) – viz schematicky výše. Dále naprogramuje funkci „najdi“ (prvek rovněž nemusí v seznamu být).

Problémy pro DCV:

1. Funkce „vlož“: Hodnotu je třeba dát na správné místo (tj. i jako první či poslední prvek seznamu); jak se zachovat, když už prvek v seznamu je. Jsou 2 možnosti: dát tam prvek znovu nebo oznámit tuto skutečnost a už nic neukládat. Vyberte si některou (v databázi nemůže být duplicitní primární klíč). Pokud se rozhodnete ukládat prvky opakovaně, pak doplňte systém o funkci „najdivše“, která oznámí, kolikrát je prvek v seznamu uveden.

2. Funkce„zruš“: co když zamýšlený rušený prvek v seznamu vůbec není?

3. Jaký předpokládat výstup v případě funkce „najdi“?

Řešení: buď je volný seznam veden skutečně jako seznam s indexy pro následníky, nebo je možno použít setřásacích algoritmů kdy se platné informace přesouvají „nahoru“. V obou případech je algoritmus dvoufázový, kdy v první fázi je nutno nějak „označit“ platné (nepatné jsou totiž nedostupné. Je nutno použít “g-bit“.

Hlavní program pak může postupně vyvolávat výše zmíněné funkce podle zadání obsluhy.