數(shù)據(jù)結構課程設計實驗報告哈夫曼樹的應用

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

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

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

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

5、式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。哈夫曼樹課用于構造使電文的編碼總長最短的編碼方案。其主要流程圖如下圖所示。開始結點數(shù)是否大于1將data和權值賦給ht輸出根結點和權值調用SELECT函數(shù)計算根結點函數(shù)父結點為兩子結點之和輸出兩子結點和已構造的結點是否為根結點？左子是否為空？此時編碼為0I<2*N?I+編碼為1結束否否否右子是否為空是是否否是是是哈夫曼樹編譯碼器流程圖三、詳細設計功能函數(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)/找兩個最小的權值（1）哈夫曼編碼：首先定義函數(shù)，找出全部權值中最小的兩個，然后定義一個變量，使他始終成為最小的那個。再將兩個函數(shù)最為葉子結點，并得到一個父親節(jié)點，此父親節(jié)點的權值為其葉子節(jié)點的權值之和。并將此父親節(jié)點的權值與其余權值進行比較，重新選出兩個最小的權值，再進行上述步驟，直到所有權值形成了一顆二叉樹，而此二叉樹就是我們所說的最優(yōu)二叉樹，即哈夫曼樹。以上為哈夫曼樹的建立過程，下面為哈夫曼編碼的過程，從葉子節(jié)點出發(fā)，若此葉子節(jié)點為其父親節(jié)點的左孩子，則將其編碼為0，若為右孩子，則將其編碼為1，然后為其父親節(jié)點編碼，若為祖先的左孩子，則變?yōu)?，為

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

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

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

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

12、; /父節(jié)點，左孩子結點，右孩子結點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)/找兩個最小的權值 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; /返回標識符/-使s1成為最小權值-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;/賦權值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);/調用建子樹的函數(shù)HTs1.parent=HTs2.parent=i;/i是s1和s2的父節(jié)點HTi.lchild=s1;HTi.rchild=s2;/s1和s2是i的兒子節(jié)點HTi.weight=HTs1.weight+HTs2.weight;/i的權值為s1和s2的和HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n個字符編碼的頭指針向量cd=(char*)malloc(n*siz

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

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

18、意:必須以回車結束："<<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<<"個權值(n注意:必須

19、以回車結束)："<<endl;for(i=0;i<=n-1;i+)/輸入權值cout<<endl<<"第"<<i+1<<"個字符的權值:"cin>>num2;*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/調用哈夫曼編碼/-打印編碼-cout<<"字符對應的編碼為:"<<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<<"已將字符與對應編碼寫入根目錄下文件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中的字符進行編碼"<<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中的字符進行譯碼"<<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+) /進入循環(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<<"打印工作結束"<<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