數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告哈夫曼樹的應(yīng)用

1、 計算機(jī)學(xué)院信管專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目： 哈夫曼樹的應(yīng)用 班 級：姓 名：學(xué) 號：同組人：起迄日期：課程設(shè)計地點(diǎn):指導(dǎo)教師：評閱意見：成績評定：評閱人： 日期：完成日期：2012年12月目 錄一、 需求分析3二、 概要設(shè)計4三、 詳細(xì)設(shè)計6四、 調(diào)試分析和測試結(jié)果7五、 心得體會和總結(jié) 10六、 參考文獻(xiàn) 10七、 附錄 11一、 需求分析（一）實驗要求要求用到數(shù)據(jù)結(jié)構(gòu)課上學(xué)到的線性表的知識，所以就要充分而清晰的理解關(guān)于線性表的知識。要現(xiàn)的基本功能很簡單，只有刪除和插入，增加功能也不過是加上修改。這些在數(shù)據(jù)結(jié)構(gòu)課上已經(jīng)講過，只要能夠理解關(guān)于線性表的幾個相關(guān)的基本算法就可以了。問題是將輸入的

2、信息保存入文件和從文件輸出。這里基本是自學(xué)的容，而且要考慮到是否要自行選擇保存的磁盤。綜上，做這個課題，要具備的知識就是線性表的基本算法，文件的保存和讀取算法，必要的C或者C+知識（本次我將使用C+實現(xiàn)），以與豐富的程序調(diào)適經(jīng)驗。（二）實驗任務(wù)一個完整的系統(tǒng)應(yīng)具有以下功能：功能1從終端讀入字符集大小n，以與n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；功能2利用已經(jīng)建好的哈夫曼樹（如不在存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件Co

3、deFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。功能3利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。（三）實驗步驟分步實施：1） 初步完成總體設(shè)計，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：完成功能1；3） 進(jìn)一步要求：完成功能2和3。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。要 求 ：1）界面友好，函數(shù)功能要劃分好2） 總體設(shè)計應(yīng)畫一流程圖3） 程序要加必要的注釋4) 要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒

4、有價值的。二、概要設(shè)計（一） 設(shè)計思想哈夫曼樹用鄰接矩陣作為存儲結(jié)構(gòu)，借助靜態(tài)鏈表來實現(xiàn)遍歷。（二 ） 函數(shù)間的關(guān)系如圖所示：主函數(shù)顯示表頭初始化樹輸入字符編碼譯碼打印編碼打印哈夫曼樹選最小兩個權(quán)值Select()（三）數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡單的二進(jìn)制編碼方

5、式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。其主要流程圖如下圖所示。開始結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時編碼為0I<2*N?I+編碼為1結(jié)束否否否右子是否為空是是否否是是是哈夫曼樹編譯碼器流程圖三、詳細(xì)設(shè)計功能函數(shù)模塊劃分void main()void printhead()void printree(HuffmanTr

6、ee HT,int w) /打印赫夫曼樹void coprint(HuffmanTree start,HuffmanTree HT)/打印代碼文件void printcode() /打印代碼void decode() /完成譯碼功能void encode() /完成編碼功能void inputcode() void init()void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)void select(HuffmanTree t,int i,int &s1,int &s2)int min

7、(HuffmanTree t,int i)/找兩個最小的權(quán)值（1）哈夫曼編碼：首先定義函數(shù)，找出全部權(quán)值中最小的兩個，然后定義一個變量，使他始終成為最小的那個。再將兩個函數(shù)最為葉子結(jié)點(diǎn)，并得到一個父親節(jié)點(diǎn)，此父親節(jié)點(diǎn)的權(quán)值為其葉子節(jié)點(diǎn)的權(quán)值之和。并將此父親節(jié)點(diǎn)的權(quán)值與其余權(quán)值進(jìn)行比較，重新選出兩個最小的權(quán)值，再進(jìn)行上述步驟，直到所有權(quán)值形成了一顆二叉樹，而此二叉樹就是我們所說的最優(yōu)二叉樹，即哈夫曼樹。以上為哈夫曼樹的建立過程，下面為哈夫曼編碼的過程，從葉子節(jié)點(diǎn)出發(fā)，若此葉子節(jié)點(diǎn)為其父親節(jié)點(diǎn)的左孩子，則將其編碼為0，若為右孩子，則將其編碼為1，然后為其父親節(jié)點(diǎn)編碼，若為祖先的左孩子，則變?yōu)?，為

8、右孩子則為1，依次向上一層進(jìn)行遍歷，直到遍歷到根節(jié)點(diǎn)，停止編碼。（2）譯碼：對于已經(jīng)建好的哈夫曼樹，要對其進(jìn)行譯碼，首先從根出發(fā)如果編碼為0，則往左孩子遍歷，如果編碼為1，則往右孩子遍歷，直到遍歷到葉子節(jié)點(diǎn)，便求得該子串相應(yīng)的字符。（3）初始化哈夫曼鏈表:首先輸入結(jié)點(diǎn)個數(shù)，再將字符與權(quán)值輸入，調(diào)用編碼函數(shù)，得到每個字符編碼并將其輸出。最后將哈夫曼編碼寫入文件。（4）完成編碼功能：打開目錄下文件tobetran.txt，讀取里面的字符，對其進(jìn)行編碼后，將編碼寫入目錄下的codefile.txt中。（5）完成譯碼功能：打開根目錄下codefile.txt文件，讀取里面的編碼，對其中的編碼進(jìn)行譯碼，

9、并將得到的容寫入根目錄下的文件txtfile.txt中。（6）打印編碼（7）打印哈夫曼樹四、調(diào)試分析和測試結(jié)果（一）初始化哈夫曼鏈表（二）編碼字符（三）編碼（四）譯碼（五）打印編碼（六）打印哈夫曼函數(shù)五、心得體會與總結(jié)對于本次課程設(shè)計，主要是需要掌握哈夫曼樹建立、哈夫曼編碼以與哈夫曼譯碼的算法。并能將其熟練應(yīng)用于編譯碼器的完成。經(jīng)過這次的課程設(shè)計，使我們更加了解了數(shù)據(jù)結(jié)構(gòu)，也更深入地了解了哈夫曼編碼與譯碼算法，課程設(shè)計的題目比我們平常的實驗容要難，完成它不僅需要有厚實的語言基礎(chǔ)，而且還要熟練掌握哈夫曼編碼與譯碼的算法，另外對于文件的基本操作也需要熟悉。通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我的C+語言水平有了

10、比較大的提高其中。C+語言關(guān)于類的操作理解的比以前深刻不少。另外是數(shù)據(jù)結(jié)構(gòu)方面的提高對哈夫曼樹的構(gòu)造與哈夫曼碼方面也有不少的提高。 在項目中也出現(xiàn)了很多的問題,最大的問題就是對程序設(shè)計框架結(jié)構(gòu)的不了解,在實現(xiàn)代碼與功能的連接時經(jīng)常會出現(xiàn)各種不同的錯誤,在實現(xiàn)一些功能時系統(tǒng)常常會報錯。許多錯誤不知從哪修改以致拖了整個設(shè)計的后腿。課程設(shè)計中，既回顧了很多以前的東西，也發(fā)現(xiàn)了很多的問題以前都沒遇見過的，收獲很大。 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹與哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識。 此次哈夫曼樹的應(yīng)用系統(tǒng)的設(shè)計

11、讓自己對數(shù)據(jù)結(jié)構(gòu)的了解更深入。六、參考文獻(xiàn)C+面向?qū)ο蟪绦蛟O(shè)計教程（第三版） 維興 林小茶編著 清華大學(xué)數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚民 吳偉民編著 清華大學(xué)六、附錄源程序：#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>const int UINT_MAX=1000;typedef struct /哈夫曼樹的存儲表示 int weight; /權(quán)值int parent,lchild,rchild

12、; /父節(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)HTNode,* HuffmanTree; /動態(tài)分配數(shù)組存儲哈夫曼樹typedef char *HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表/-全局變量-HuffmanTree HT; /代表哈夫曼樹HuffmanCode HC; /代表哈夫曼編碼int *w,i,j,n; char *z;int flag=0; int numb=0;/ -求哈夫曼編碼-void line()/畫分割線的函數(shù)cout<<"n-n"int min(HuffmanTree t,int i)/找兩個最小的權(quán)值 int j,flag;in

13、t k=UINT_MAX; / 取k為不小于可能的值for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0)k=tj.weight,flag=j; tflag.parent=1; return flag; /返回標(biāo)識符/-使s1成為最小權(quán)值-void select(HuffmanTree t,int i,int &s1,int &s2) int j;s1=min(t,i);s2=min(t,i);if(s1>s2)/ s1為最小的兩個值中序號較小的那個j=s1;s1=s2;s2=j;void HuffmanCod

14、ing(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int m,i,s1,s2,start;int c,f;HuffmanTree p;char *cd;if(n<=1)return;m=2*n-1;/申請2n-1個存單元HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號單元未用for(p=HT+1,i=1;i<=n;+i,+p,+w)p->weight=*w;/賦權(quán)值p->parent=0;p->lchild=0;p->rchild=0;for(;i

15、<=m;+i,+p)/初始化 p->parent=0; for(i=n+1;i<=m;+i) / 建哈夫曼樹 select(HT,i-1,s1,s2);/調(diào)用建子樹的函數(shù)HTs1.parent=HTs2.parent=i;/i是s1和s2的父節(jié)點(diǎn)HTi.lchild=s1;HTi.rchild=s2;/s1和s2是i的兒子節(jié)點(diǎn)HTi.weight=HTs1.weight+HTs2.weight;/i的權(quán)值為s1和s2的和HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n個字符編碼的頭指針向量cd=(char*)malloc(n*siz

16、eof(char); /分配求編碼的工作空間cdn-1='0' /編碼結(jié)束符for(i=1;i<=n;i+)/逐個字符求哈夫曼編碼start=n-1; /編碼結(jié)束符位置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);/為第i個字符編碼分配空間strcpy(HCi,&cdstart); /從cd復(fù)制編碼（串

17、）到HCfree(cd);/釋放工作空間/-初始化哈夫曼鏈表-void init() flag=1;int num;int num2;cout<<"下面初始化哈夫曼鏈表"<<endl<<"請輸入結(jié)點(diǎn)的個數(shù)n："cin>>num;/輸入結(jié)點(diǎn)個數(shù)n=num;w=(int*)malloc(n*sizeof(int);/權(quán)值z=(char*)malloc(n*sizeof(char);/字符cout<<"n請依次輸入"<<n<<"個字符(字符型)n注

18、意:必須以回車結(jié)束："<<endl;char temp2;for(i=0;i<n;i+)/輸入字符 cout<<"第"<<i+1<<"個字符:"<<endl; gets(temp); *(z+i)=*temp;line();for(i=0;i<=n-1;i+)/輸出字符cout<<setw(6)<<*(z+i);line();cout<<"n請依次輸入"<<n<<"個權(quán)值(n注意:必須

19、以回車結(jié)束)："<<endl;for(i=0;i<=n-1;i+)/輸入權(quán)值cout<<endl<<"第"<<i+1<<"個字符的權(quán)值:"cin>>num2;*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/調(diào)用哈夫曼編碼/-打印編碼-cout<<"字符對應(yīng)的編碼為:"<<endl;for(i=1;i<=n;i+)/輸出所有編碼puts(HCi);/-將哈夫曼編碼寫入文件-cout<&l

20、t;"下面將赫夫曼編碼寫入文件"<<endl;FILE *htmTree;char r=' ','0' if(htmTree=fopen("htmTree.txt","w")=NULL)cout<<"文件打開失敗"<<endl;return;fputs(z,htmTree);for(i=0;i<n+1;i+)fprintf(htmTree,"%6d",*(w+i);fputs(r,htmTree);for(i=1;i<

21、;=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmTree);cout<<"已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;/init/-獲取字符并寫入文件-void inputcode() FILE *virttran,*tobetran;char str100;if(tobetran=fopen("tobetran.txt","w")=NULL)cout<<"不能打開文件"

22、;<<endl;return;cout<<"請輸入你想要編碼的字符"<<endl;gets(str);fputs(str,tobetran);cout<<"獲取字符成功"<<endl;fclose(tobetran);/-void encode() /完成編碼功能cout<<"下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl;FILE *tobetran,*codefile;if(tobetran=fopen("tobe

23、tran.txt","rb")=NULL)cout<<"不能打開文件"<<endl;if(codefile=fopen("codefile.txt","wb")=NULL)cout<<"不能打開文件"<<endl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char); /為tran分配100個字節(jié)while(i=99)if(fgets(tran,100,tobetran)=NULL)cou

24、t<<"不能打開文件"<<endl;break;for(i=0;*(tran+i)!='0'i+)for(j=0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,codefile);puts(HCj);if(j>n)cout<<"字符錯誤，無法編碼!"<<endl;break;cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<&

25、lt;endl<<endl;fclose(tobetran);fclose(codefile);free(tran);/-void decode() /完成譯碼功能cout<<"下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl;FILE *codef,*txtfile;if(txtfile=fopen("Textfile.txt","w")=NULL)cout<<"不能打開文件"<<endl;if (codef=fopen(&quo

26、t;codefile.txt","r")=NULL)cout<<"不能打開文件"<<endl;char *tbdc,*outext,i2;int io=0,i,m;unsigned long length=10000;tbdc=(char*)malloc(length*sizeof(char); /分配空間fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char); /分配空間m=2*n-1;for(i=0;*(tbdc+i)!='0'

27、;i+) /進(jìn)入循環(huán)i2=*(tbdc+i);if(HTm.lchild=0) *(outext+io)=*(z+m-1);io+;m=2*n-1;i-;else if(i2='0') m=HTm.lchild;else if(i2='1') m=HTm.rchild;*(outext+io)='0'fputs(outext,txtfile);cout<<"譯碼完成"<<endl<<"容寫入根目錄下的文件txtfile.txt中"<<endl<<e

28、ndl;free(tbdc);free(outext);fclose(txtfile);fclose(codef);/-void printcode() /打印代碼cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl<<"-n"FILE * CodePrin,* codefile;if(CodePrin=fopen("CodePrin.txt","w")=NULL)cout<<"不能打開文件"<<endl;

29、return;if(codefile=fopen("codefile.txt","r")=NULL)cout<<"不能打開文件"<<endl;return;char *work3;work3=(char*)malloc(51*sizeof(char);doif(fgets(work3,51,codefile)=NULL)cout<<"不能讀取文件"<<endl;break;fputs(work3,CodePrin);puts(work3);while(strlen(w

30、ork3)=50);free(work3);cout<<"打印工作結(jié)束"<<endl<<endl;fclose(CodePrin); fclose(codefile);void coprint(HuffmanTree start,HuffmanTree HT)/打印代碼文件char t=' 'if(start!=HT)FILE * TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<<"創(chuàng)建文件

31、失敗"<<endl;return; numb+;/該變量為已被聲明為全局變量coprint(HT+start->rchild,HT);if(start->lchild!=NULL&&start->rchild!=NULL) t='<'cout<<setw(5*numb)<<start->weight<<t<<endl; fprintf(TreePrint,"%dn",start->weight);coprint(HT+start->lchild,HT);numb-;fclose(TreePrint);void printree(HuffmanTree HT,int w) /打印赫夫曼樹HuffmanTree p;p=HT+w;cout<<"下面打印赫夫曼樹"<<endl