《哈夫曼樹應(yīng)用課程設(shè)計報告》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼樹應(yīng)用課程設(shè)計報告（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目：哈夫曼樹應(yīng)用 專 業(yè) ： 軟件工程 班 級 ： 軟件 學(xué) 生 ： 學(xué) 號 ： 指導(dǎo)教師 ： 羅作民 / 張翔 起止時間 ：2011-07-042011-07-08 2011 年 春季 學(xué)期目 錄一具體任務(wù).2 1功能.2 2分步實施.2. 3要求.2二哈夫曼編碼21問題描述22.基本要求33實現(xiàn)提示3三設(shè)計流程圖4 1建立哈夫曼樹.4 2編碼.5 3譯碼.6 4主程序.7四設(shè)計概要81問題哈夫曼的定義.8.2所實現(xiàn)的功能函數(shù)如下.83功能模塊.8五源程序9六調(diào)試分析15七心得與體會18八參考文獻18一、任務(wù)題目：哈夫曼樹應(yīng)用1.功能： 1從終端讀入字符集大小n，以

2、及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；2利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。3利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。2.分步實施：1） 初步完成總體設(shè)計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2） 完成

3、最低要求：完成功能1；3） 進一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴充系統(tǒng)功能。3.要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計應(yīng)畫一流程圖3）程序要加必要的注釋4） 要提供程序測試方案5） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。二、哈夫曼編碼1. 問題描述利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編

4、/譯碼系統(tǒng)。2. 基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件Textfile中。3. 實現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲在文件Codefile中。(2) 用戶界面

5、可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I， D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。三、設(shè)計流程圖建立哈夫曼樹：開始n,=1Renturn 0m=2*n-1i=1;i=n;+iWhile(getchar()=”/n”輸入字符與權(quán)值HTi.ch=zHTi.weight=wHTi.parent=0HTi.lchild=0HTi.rchild=0編碼：開始cds

6、tart=”1”i=1;i=n;+istart=n-1cdstart=”0”c=I;f=HTi.parent; f!=0;f=HTf.parentHTf.child=l結(jié)束譯碼：開始L=k!output_file!cout”cant open file”Return 1Cout”cant open file”Strcmp(Hi.hlchild=0結(jié)束i=1;in;i+while(hk!=”0”)j=0;jstrlen(hi);j+;l+K=0hj=”0”輸出譯碼主程序：開始main建立哈夫曼樹choice=”I”|choice=”I”結(jié)束編碼return 0choice=”E”|choice=

7、”e”choice=”D”|choice=”d”choice=”Q”|choice=”q”編碼四、概要設(shè)計1）問題哈夫曼的定義：1.哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2）所實現(xiàn)的功能函數(shù)如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函

8、數(shù)。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點3、 int main()主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對文件中的正文進行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。4、Encoding 編碼功能：對輸入字符進行編碼5、Decoding譯碼功能： 利用已建

9、好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼，結(jié)果存入文件textfile.dat 中。Print() 打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。6.主函數(shù)的簡要說明，主函數(shù)主要設(shè)計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實現(xiàn)功能。3）功能模塊：哈夫曼編碼/譯碼器初始化哈夫曼樹編碼譯碼打印哈夫曼樹打印編碼五、源程序#include#include#include#include#includetypedef struct /哈夫曼樹的結(jié)構(gòu)體char ch;int weight;

10、 /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /選出最小的節(jié)點for(j=1;j=a;+j)if(HTj.parent

11、=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建哈夫曼樹HT，并求出n個字符的哈夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化n個葉子結(jié)點printf(請輸入第%d字符信息和權(quán)值：,i

12、);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立哈夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.

13、weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給n個字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);

14、int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 軟件092班 姓名:張耀飛 學(xué)號：3090921040n ;while(choice!=Q&choice!=q) /當choice的值不為q且不為Q時循環(huán)cout *哈夫曼編碼/譯碼器*n; cout I.Init E.Encoding D.Decoding Q.Exitn; coutchoice;

15、 if(choice=I|choice=i) /初始化赫夫曼樹coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant open file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!endl; else if(choice=E|choice=e) /進行編

16、碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf(請輸入字符：);gets(str);output_file.open(ToBeTree.txt);if(!output_file)coutcant open file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant open file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j

17、)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n;input_file.open(CodeFile.txt); /從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)coutcant open file!code;cout編碼碼值為：codeendl;input_file.close(); else if(choice=D|choice=d) /讀入CodeFile.txt中的編碼進行譯碼，將譯出來的字符放入Textfile.tx

18、t中input_file.open(CodeFile.txt);if(!input_file)coutcant open file!h;input_file.close();output_file.open(Textfile.txt);if(!output_file)coutcant open file!endl;return 1;k=0;while(hk!=0) /先用編碼中的前幾個和字符的編碼相比較，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_fileH

19、Ti.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt);if(!input_file)coutcant open file!h; couthendl;input_file.close();cout譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！endl; else if(choice=Q|choice=q) /退出程序 exit(0); else /如果選了選項之外的就讓用戶重新選擇cout您沒有輸入正確的步驟，請重新輸入！endl;coutendl;return 0;六、調(diào)試分析編碼譯碼

20、退出七、實驗心得與體會 在我自己課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；在執(zhí)行譯碼操作時，不知什么原因，總是不能把要編譯的二進制數(shù)與編譯成的字符用連接號連接起來，而是按順序直接放在一起，視覺效果不是很好。還有就是，很遺憾的是，我們的哈夫曼編碼/譯碼器沒有像老師要求的那樣完成編一個文件的功能，這是我們設(shè)計的失敗之處。 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上

21、課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。八參考文獻： 1 譚浩強. C 程序設(shè)計(第二版) M . 北京:清華大學(xué)出版社,1999. 161 - 163.2 譚浩強,張基溫,唐永炎. C 語言程序設(shè)計教程(第二版) M . 北京:高等教育出版社,1998. 113 - 115.3 嚴蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C 語言版) M . 北京:清華大學(xué)出版社,2002. 55 - 58.4 李士峰,張謝華,孫清滇. ActiveX文檔技術(shù)在VB 程序設(shè)計網(wǎng)絡(luò)課件制作中的應(yīng)用 5 王穎,王正洲. 漢諾塔問題迭代算法實現(xiàn)和分析J . 合肥聯(lián)合大學(xué)學(xué)報,1999 , 考核成績評定：簽字：年 月 日 19