Zápočtová písemka 1.2.2011

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
mrwep
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 13. 2. 2010 15:06
Typ studia: Informatika Bc.

Zápočtová písemka 1.2.2011

Příspěvek od mrwep »

Dnešní zadání bylo Huffmanovo kódování. Nikdo z 22 přítomných neuspěl.
Zadání je v příloze.
Přílohy
czapold.pdf
(346.7 KiB) Staženo 515 x
vojta_vorel
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 14. 1. 2011 15:10
Typ studia: Informatika Ph.D.

Re: Zápočtová písemka 1.2.2011

Příspěvek od vojta_vorel »

Dělal jsem to teďka cvičně a celkem to, s pužitím manuálu, šlo..
1) struktura pro uzel stromu (left,right,up,value,ch) + funktor/operátor < pro pointry na uzel
2) map uzlů indexovaná písmenky
3) priority_queue pointrů na uzel
4) načítat vstup po znacích (get), nové vkládat do mapy a zvyšovat číslo v uzlech v mapě. Pad naplnit forontu odkazy do mapy.
5) vybírat dva nejmenší uzly z fronty, vytvářet nový uzel (new) jako jejich rodič, ten vrátit do fronty. To celé dokud není ve frontě jeden uzel.
Tím máme hotový strom (kořen je ve frontě, listy v mapě).
6) vector<bool>, do něj procházením stromu od listů nacpat kódy všech znaků na vstupu.
7) Z toho vectoru brát osmice, z těch udělat char tak, že se osmice projde a k charu přičítá případné příslušné číslo z pole{1,2,4,8,16...128};
8) ten char šoupnout na výstup
9) Reprezentaci stromu jsem moc neřešil, udělal jem rekurzivní funkci, která ze stromu udělala "(podstrom)(podstrom)".

Měl jsem trable s tím, že fstream.get mi četlo i nějaké ukončovací znaky či co, prostě se tam zjevoval char s hodnotou -1. Vyřešil jsem to if(ch!=-1).

zdraví Vojta
Odpovědět

Zpět na „NPRG041 Programování v C++“