赫夫曼編碼譯碼

《赫夫曼編碼譯碼》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、赫夫曼編碼/譯碼1.問題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。2.基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：(1)I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。(2)E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)

2、存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。(3)D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。以下為選做：(4)P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。(5)T：印赫夫曼樹（Treeprinting）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePrint中。3.測

3、試要求(1)已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計(jì)赫夫曼編碼。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THISPROGRAMEISMYFAVORITE”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811614.實(shí)現(xiàn)提示(1)編碼結(jié)果以文本方式存儲在文件Codefile中。(2)用戶界面可以設(shè)計(jì)為“菜單”方式：

4、顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。(3)在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。概要設(shè)計(jì)1)問題分析哈夫曼樹的定義91.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedefstruct{//赫夫曼樹的結(jié)構(gòu)體charch;intweight;//權(quán)值intparent,lchild,rchild;}htnode,*hfmtree;2）所實(shí)現(xiàn)的功能函數(shù)如下1、void

5、hfmcoding(hfmtree&HT,hfmcode&HC,intn)初始化哈夫曼樹，處理InputHuffman(HuffmanHfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)。2、voidSelect(hfmtree&HT,inta,int*p1,int*p2)//Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)2、intmain()主函數(shù)：利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼

6、的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。3、Encoding編碼功能：對輸入字符進(jìn)行編碼4、Decoding譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。Print()打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。5.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。2)系統(tǒng)結(jié)

7、構(gòu)圖（功能模塊圖）五．程序說明1）.哈夫曼編碼/譯碼器源代碼9#include#include#include#include#includetypedefstruct{//赫夫曼樹的結(jié)構(gòu)體charch;intweight;//權(quán)值intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;voidSelect(hfmtree&HT,inta,int*p1,int*p2)/