# Zápočtová písemka 1.2.2011

<{ForumPost(poster="mrwep", timestamp=2011-02-01 16:25:41)}>
Dnešní zadání bylo Huffmanovo kódování. Nikdo z 22 přítomných neuspěl.  
Zadání je v příloze.

*Attachments:*

- *[czapold.pdf](/Forum%20archiv/Attachments/5017_c71e31a30e61b39fa07729b884cc8b4b)*

<{/ForumPost}>

<{ForumPost(poster="vojta_vorel", timestamp=2012-01-16 15:38:29)}>
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
<{/ForumPost}>