huffman(哈夫曼)樹編碼譯碼-課程設(shè)計(jì)報(bào)告.docx

《huffman(哈夫曼)樹編碼譯碼-課程設(shè)計(jì)報(bào)告.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)院：信息科學(xué)與工程學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：計(jì)卓1601學(xué)號(hào)：學(xué)生姓名：指導(dǎo)教師：年月日題目名稱一、實(shí)驗(yàn)內(nèi)容哈夫曼編碼譯碼系統(tǒng)【問題描述】用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。【基本要求】1）初始化。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹。2）編碼。利用已建好的哈夫曼

2、樹對(duì)輸入英文進(jìn)行編碼，編碼結(jié)果存儲(chǔ)在數(shù)組中。3）譯碼。利用已建好的哈夫曼樹將數(shù)組中的代碼進(jìn)行譯碼，結(jié)果存入一個(gè)字符數(shù)組。4）輸出編碼。將編碼結(jié)果顯示在終端上，每行50個(gè)代碼。5）輸出哈夫曼樹。將哈夫曼樹以直觀的方式（樹或凹入表形式）顯示出來?！緦?shí)現(xiàn)提示】用戶界面可以設(shè)計(jì)為“菜單”方式，再加上一個(gè)“退出”功能。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“退出”為止。參考教材P240-246【選做內(nèi)容】將哈夫曼樹保存到文件中，編碼和譯碼的結(jié)果也分別存放在兩個(gè)文本文件中。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)儲(chǔ)存結(jié)構(gòu)structHNodeType{//字符結(jié)構(gòu)體

3、類型intweight;//權(quán)intparent;//雙親位置intlchild;//左孩子intrchild;//右孩子charinf;//字符};structHcodeType{intbit[MaxBit];//存儲(chǔ)編碼intstart;//起始位置};三、算法設(shè)計(jì)1、在構(gòu)造哈夫曼樹時(shí)，設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n-1。求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲(chǔ)。求哈夫曼編碼實(shí)際上就是在已建立的

4、哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的父節(jié)點(diǎn)回退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼的一個(gè)分支，從而得到一位哈夫曼編碼值。由于一個(gè)字符的哈夫曼編碼就是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求的高位2、初始化為從鍵盤接受字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。3、建立哈夫曼編碼為使用2中得到的數(shù)據(jù)按照教材中的構(gòu)造哈弗曼的算法構(gòu)造哈弗曼樹，即將HuffNode數(shù)組中的各個(gè)位置的各個(gè)域都填上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件nodedata.dat中。voidCreat_Haffmantre

5、e(int&n){//建樹并輸出樹n++;HNodeType*HaffNode=newHNodeType[2*n-1];inti,j;intm1,m2,x1,x2;for(i=0;i<2*n-1;i++){//賦初值HaffNode[i].weight=0;HaffNode[i].parent=-1;HaffNode[i].lchild=-1;HaffNode[i].rchild=-1;HaffNode[i].inf='0';}for(i=0;i>HaffNode[i].inf;

6、cout<<"請(qǐng)輸入該字符的權(quán)值:"<>HaffNode[i].weight;}HaffNode[n-1].inf='';//最后一個(gè)為空格HaffNode[n-1].weight=120;//空格權(quán)值for(i=0;i

7、(HaffNode[j].parent==-1&&HaffNode[j].weight