huffman(哈夫曼)樹編碼譯碼-課程設計報告.docx

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

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

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

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

4、哈夫曼樹中，從葉子結點開始，沿結點的父節(jié)點回退到根結點，每回退一步，就走過了哈夫曼的一個分支，從而得到一位哈夫曼編碼值。由于一個字符的哈夫曼編碼就是從根結點到相應葉子結點所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求的高位2、初始化為從鍵盤接受字符集大小n，以及n個字符和n個權值。3、建立哈夫曼編碼為使用2中得到的數(shù)據(jù)按照教材中的構造哈弗曼的算法構造哈弗曼樹，即將HuffNode數(shù)組中的各個位置的各個域都填上相關的值，并將這個結構體數(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<<"請輸入該字符的權值:"<>HaffNode[i].weight;}HaffNode[n-1].inf='';//最后一個為空格HaffNode[n-1].weight=120;//空格權值for(i=0;i

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