《哈夫曼樹課程設(shè)計(jì)報(bào)告》由會員分享，可在線閱讀，更多相關(guān)《哈夫曼樹課程設(shè)計(jì)報(bào)告（18頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、閩江學(xué)院課程設(shè)計(jì)說明書題目： 哈夫曼編譯碼器 院 系： 計(jì)算機(jī)科學(xué)系 專業(yè)班級： 10軟件工程 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 2011年 12 月 30 日 課程設(shè)計(jì)需求分析報(bào)告一、分析問題和確定解決方案1.分析問題利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng),為這樣的信息收發(fā)站寫一個哈夫曼的編/譯碼系統(tǒng)。2.確定解決方案設(shè)計(jì)建立帶權(quán)的哈夫曼樹，確定哈夫曼樹的類與成員函數(shù)，以及各函數(shù)之間的調(diào)

2、用關(guān)系，采用動態(tài)數(shù)組的存儲結(jié)構(gòu)存儲所需要的數(shù)據(jù)，通過不同的函數(shù)來實(shí)現(xiàn)編碼，譯碼以及打印二進(jìn)制編碼、哈夫曼樹，把不同的數(shù)據(jù)存入不同的txt文件中，通過主函數(shù)調(diào)用來實(shí)現(xiàn)功能檢測。3.輸入的形式和輸入值的范圍手動或者從文本中讀入數(shù)據(jù)的形式初始化哈夫曼樹，從鍵盤中或者文件中讀入數(shù)據(jù)，以字母A-Z代表結(jié)點(diǎn)，以自然數(shù)代表權(quán)值，字符串提示使用者所要執(zhí)行的操作。4.輸出的形式在顯示器界面上或者以文本的形式來實(shí)現(xiàn)程序調(diào)試的輸出。5.程序所能達(dá)到的功能(1)初始化。手動輸入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件WritehfmTree中,輸出哈夫曼樹及各字符對應(yīng)的編碼存于Writehf

3、mCode;從文本中讀入字符，建立哈夫曼樹存于ReadhfmTree, 輸出哈夫曼樹及各字符對應(yīng)的編碼存于ReadhfmCode.(2)編碼。手動輸入一串大寫英文字符，該字符存于WriteToBeTron中，對字符進(jìn)行編碼并將它存于WriteCodeFile中；從文件中讀取字符編碼并存于ReadCodeFile中。(3)譯碼。先初始化默認(rèn)哈夫曼樹，手動輸入二進(jìn)制代碼進(jìn)行譯碼存于WriteTextFile中；從文件中讀取二進(jìn)制代碼進(jìn)行譯碼存于ReadTextFile中。(4)印代碼文件。將文件ReadCodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的代碼碼寫入文件Code

4、Print中。(5)印哈夫曼樹。將初始化的哈夫曼樹以直觀的方式顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。各個功能數(shù)據(jù)輸出存儲位置（如表1所示）表1：各個功能數(shù)據(jù)輸出存儲位置表功能字母二進(jìn)制碼初始化WritehfmTree（手動）WritehfmCode（手動）ReadhfmTree（文本讀入）ReadhfmCode（文本讀入）hfmTree（默認(rèn)文本讀入）hfmCode（默認(rèn)文本讀入）編碼WriteToBeTron（手動）WriteCodeFile（手動）ReadCodeFile（文本讀入）譯碼WriteTextFile（手動）WriteCodeFile（手動）Re

5、adTextFile（文本讀入）印編碼代碼CodePrint印哈夫曼樹TreePrint6.測試數(shù)據(jù)(1)正確的輸入：1輸入主菜單項(xiàng)中的英文字母I(i),E(e),D(d),P(p),Q(q)輸出結(jié)果：進(jìn)入所選的功能界面2輸入子菜單項(xiàng)中的數(shù)字1，2，3，(4) 輸出結(jié)果：執(zhí)行所選的功能(2)含有錯誤的輸入：1輸入除了主菜單項(xiàng)中的英文字母I(i),E(e),D(d),P(p),Q(q) 輸出結(jié)果： 2輸入除了子菜單項(xiàng)中的數(shù)字1，2，3，(4) 輸出結(jié)果：7.程序說明(1)程序中數(shù)據(jù)類型的定義：用到三組結(jié)構(gòu)體，分別是哈夫曼樹的動態(tài)數(shù)組存儲結(jié)構(gòu)*HuffmanTree，哈夫曼編碼表的存儲結(jié)構(gòu)Huff

6、manCode，字符結(jié)點(diǎn)的動態(tài)數(shù)組存儲結(jié)構(gòu)wElem以及哈夫曼樹類定義class Huffman。(2)主程序的流程圖：用戶從主菜單中選擇所要進(jìn)行的操作，如果輸入選項(xiàng)錯誤則提示重新輸入選項(xiàng)，否則進(jìn)入選中的操作項(xiàng)(如圖1所示)。 圖1：主程序流程圖(3)各程序模塊之間的層次(調(diào)用)關(guān)系：主函數(shù)main（）調(diào)用初始化，編碼，譯碼，打印二進(jìn)制編碼，打印哈夫曼樹這五個子函數(shù)；進(jìn)入初始化功能后調(diào)用手動輸入，文本讀入，默認(rèn)文本這三個函數(shù)；進(jìn)入編碼功能后調(diào)用手動編碼，文本讀入編碼這兩個函數(shù)；進(jìn)入譯碼功能后調(diào)用手動譯碼，文本讀入譯碼這兩個函數(shù)(如圖2所示)。 圖2:：各程序模塊之間的層次(調(diào)用)關(guān)系(4)默認(rèn)

7、的哈夫曼樹：空格以及字母AZ頻度分別為186，64，13，22，32，103，21，15，47，57，1，5，32，20，57，63，15，1，48，51，80，23，8，18，1，16，1建立一棵默認(rèn)的哈夫曼樹(如圖3所示)。 圖3：默認(rèn)的哈夫曼樹二、詳細(xì)設(shè)計(jì)1、哈夫曼樹存儲及類的定義：#include #include #include #include #include typedef struct /哈夫曼樹的存儲結(jié)構(gòu)int weight;/權(quán)值char HTch;/字符int parent,lchild,rchild;/雙親，左孩子，右孩子HTNode,*HuffmanTree; /

8、動態(tài)數(shù)組存儲哈夫曼樹typedef struct /哈夫曼編碼表的存儲結(jié)構(gòu)char ch; /字符char* hufCh; /二進(jìn)制碼HuffmanCode; /動態(tài)數(shù)組存儲哈夫曼編碼表typedef struct /字符結(jié)點(diǎn)char ch; /字符int wt; /字符權(quán)值wElem; /動態(tài)分配數(shù)組存儲讀入字符與權(quán)值class Huffmanpublic:Huffman();/構(gòu)造函數(shù)Huffman();/析構(gòu)函數(shù)void Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n);/初始化，手動void Initialization(Hu

9、ffmanTree &HT,HuffmanCode *HC,int &n,int v);/初始化，標(biāo)準(zhǔn)文件void Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n);/初始化，統(tǒng)計(jì)void EnCoding(HuffmanCode *HC,int hufnum); /手動編碼void EnCoding(HuffmanCode *HC,char*EnCodeFile); /文件讀入編碼void DeCoding(HuffmanTree HT,HuffmanCode *HC,int n);/手動譯碼void D

10、eCoding(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n);/文件讀入譯碼void Print(char *);/打印二進(jìn)制編碼void Treeprinting( HTNode T,HuffmanTree HT,int n );/打印哈夫曼樹;2、哈夫曼樹的基本操作：/手動輸入字符與權(quán)值并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n)/哈夫曼樹對象，編碼對象，字符數(shù)/從文件讀入標(biāo)準(zhǔn)哈夫曼樹并初始化void Huffman:Initial

11、ization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/哈夫曼樹對象，編碼對象，字符數(shù),區(qū)分功能參數(shù)/從文件中統(tǒng)計(jì)字符與權(quán)值，構(gòu)造哈弗曼樹void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n)/哈夫曼樹對象，編碼對象，文件名，字符數(shù)/編碼函數(shù),對用戶輸入的文件的正文進(jìn)行編碼,然后將結(jié)果存入文件WriteCodeFile.txt中void Huffman:EnCoding(HuffmanCode *HC,int hufnum)/編碼數(shù)組對

12、象，字符數(shù)/編碼函數(shù),從文件讀取void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/編碼數(shù)組對象，文件名/譯碼函數(shù)，對文件CodeFile中的代碼進(jìn)行譯碼,結(jié)果存入文件ReadTextFile.txt中void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n)/哈夫曼樹對象，編碼對象，文件名，字符數(shù)/譯碼函數(shù)，手動輸入void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,int n)/哈夫曼樹對

13、象，編碼對象，字符數(shù)/打印函數(shù)，將文件CodePrint.txt中的內(nèi)容以每行個代碼顯示在屏幕上void Huffman:Print(char* cfileName) /文件名/打印哈夫曼樹void coprint(HuffmanTree start,HuffmanTree HT) /哈夫曼樹對象，哈夫曼樹對象其中部分操作的偽代碼如下：(1)從文件讀入標(biāo)準(zhǔn)哈夫曼樹并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/哈夫曼樹對象，編碼對象，字符數(shù),區(qū)分功能參數(shù)定義一個動態(tài)數(shù)組存放空格和26個英

14、文字母，把字符串 ABCDEFGHIJKLMNOPQRSTUVWXYZ讀入文件CharFile.txtwhile(charRead.get(inbuf)wj.ch=inbuf;wj.wt=cwj;j+;/w存放n字符及其權(quán)值(從0號單元開始),構(gòu)造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HC.int i,m,ww=0;/n:字符數(shù) m:樹結(jié)點(diǎn)數(shù) int s1,s2;HuffmanTree p;/定義指針變量pif(n=1) return;/小于2個字符，結(jié)束m=2*n-1;/n個葉子，2*n-1個結(jié)點(diǎn)HT=new HTNode(m+1)*sizeof(HTNode);HT0.parent=-1

15、;HT0.lchild=-1;HT0.rchild=-1;HT0.weight=0;for(p=HT+1,i=1;iweight=www.wt; p-HTch=www.ch;p-parent=p-lchild=p-rchild=0;/跳出循環(huán)時i=n+1;for(;iweight=0;p-HTch=#;p-parent=p-lchild=p-rchild=0; for(i=n+1;i=m;i+)/建立哈夫曼樹Select(HT,i-1,s1,s2);/在HT數(shù)組的至i-1個結(jié)點(diǎn)中選擇parent為且權(quán)值weight最小的兩個結(jié)點(diǎn),其序號分別為S1和S2;HTs1.parent=i;HTs2.p

16、arent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;char *cd=new charn;/分配編碼的存儲空間cdn-1=0;/編碼結(jié)束符int c,f,start;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.ch=wi-1.ch;/復(fù)制字符HCi.hufCh=new char (n-start)*si

17、zeof(char);/為第i個字符編碼分配空間strcpy(HCi.hufCh,&cdstart);/從cd復(fù)制編碼(串)到HC/向屏幕輸出哈夫曼編碼,并把編碼保存在文件hfmCode.txt中;(2)編碼函數(shù),從文件讀取void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/編碼數(shù)組對象，文件名對文件進(jìn)行編碼,并將編碼存于文件ReadCodeFile.txt中while(ufileRead.get(charInbuf)for(int k=1;k=27;k+)if(charInbuf=HCk.ch)codeWriteHCk.hufCh;b

18、reak; 3、主函數(shù)：#include Huffman.cpp/主函數(shù)void main() int current_n=27; /全局變量，字符數(shù)char c; /功能選擇int hufnum=27; /默認(rèn)字符數(shù)HuffmanTree HT; /哈夫曼樹對象HuffmanCode *HC=new HuffmanCode(hufnum+1)*sizeof(HuffmanCode);/分配n 個 /字符編碼的頭指針向while(1)/主菜單 cout請按順序選擇要實(shí)現(xiàn)的功能:;int k=1; Huffman hf;/類對象while(k)/將小寫轉(zhuǎn)化為大寫switch(c)caseI:/進(jìn)

19、入初始化選擇界面/選擇初始化方式后，進(jìn)入子菜單switch(c)case 1:hf.Initialization(HT,HC,current_n);break; /手動初始化case 2:/輸入需要初始化的文件名(需包含后綴名.txt)建立哈夫曼樹;/建立哈夫曼樹,并把哈夫曼樹存放在ReadhfmTree.txt中 hf.Initialization(HT,HC,buf,current_n); break;/從文件讀入數(shù)據(jù)初始化case 3:hf.Initialization(HT,HC,current_n,0);/標(biāo)準(zhǔn)初始化 case 4:break;break;caseE:/進(jìn)入編碼選擇界

20、面/選擇字符序列讀入方式后進(jìn)入子菜單switch(c)case 1:hf.EnCoding(HC,hufnum);break;/手動編碼 case 2:/輸入需要的文件名(需包含后綴名.txt) 進(jìn)行編碼hf.EnCoding(HC,buf); break;/文件讀入編碼 case 3:break;break;caseD:/進(jìn)入譯碼選擇界面/選擇譯碼方式后進(jìn)入子菜單switch(c)case 1:hf.DeCoding(HT,HC,hufnum); break;/手動譯碼 case 2:/輸入需要的文件名(需包含后綴名.txt) 進(jìn)行譯碼 hf.DeCoding(HT,HC,buf,hufnu

21、m);break;/文件譯碼case 3:break;/返回break;caseP:/進(jìn)入打印二進(jìn)制編碼界面 hf.Print(ReadCodeFile.txt);break;caseT:/進(jìn)入打印哈夫曼樹界面 hf.Treeprinting(HT2*current_n-1,HT,current_n);break;caseQ:exit(-1);/退出default:exit(-1);三、系統(tǒng)調(diào)試與測試1、調(diào)試過程中遇到的問題及解決辦法:(1)逐個手動輸入字符和權(quán)值進(jìn)行編碼，若數(shù)據(jù)太大效率太低。解決辦法：后來增加一個新的功能從文本中讀入數(shù)據(jù)，這樣可大大提高效率。(2)初始化文本讀入時，若數(shù)據(jù)過大

22、，會結(jié)束進(jìn)程，無法進(jìn)行操作。解決辦法：增加動態(tài)數(shù)組的最大上限，當(dāng)超過上限，會提示“文本數(shù)據(jù)過大”，而且可以顯示范圍內(nèi)的數(shù)據(jù)。(3)只能讀取固定的文件進(jìn)行編碼。解決辦法：可以手動輸入想要讀取的文件名。(4)只能打印默認(rèn)的哈夫曼樹解決辦法：通過增加兩種初始化方式（手動初始化和文本讀入初始化），打印用戶當(dāng)前初始化的哈夫曼樹。(5)進(jìn)入子菜單后，輸入的選項(xiàng)必須為數(shù)字，否則會出現(xiàn)死循環(huán)。解決辦法：把輸入的數(shù)據(jù)類型由整型改為字符型。2、測試數(shù)據(jù)及其輸出結(jié)果：(1)進(jìn)入主菜單界面，用戶可以選擇所要執(zhí)行的操作，比如：初始化，編碼，譯碼，打印二進(jìn)制編碼代碼，打印哈夫曼樹。在執(zhí)行編碼、譯碼操作前，請先初始化默認(rèn)的

23、哈夫曼樹(如圖4所示) 。 圖4：主菜單界面(2)進(jìn)入初始化界面，用戶可以選擇執(zhí)行手動初始化(如圖5所示)，初始化結(jié)果存入WritehfmCode.txt，WritehfmTree.txt；文本讀入初始化(如圖6所示)，初始化結(jié)果存入ReadhfmCode.txt，ReadhfmTree.txt；默認(rèn)文本初始化(如圖7所示)，初始化結(jié)果存入hfmCode.txt，hfmTree.txt。 圖5：手動初始化哈夫曼樹 圖6：文本讀入初始化哈夫曼樹 圖7：默認(rèn)文本初始化(3)進(jìn)入編碼界面，用戶可以選擇執(zhí)行手動編碼(如圖8所示)，編碼結(jié)果存入WriteCodeFile.txt；文本讀入編碼(如圖9所示

24、)，編碼結(jié)果存入ReadCodeFile.txt。 圖8：手動編碼 圖9：文本讀入編碼(4)進(jìn)入譯碼界面，用戶可以選擇執(zhí)行手動譯碼(如圖10所示)，譯碼結(jié)果存入WriteTextFile.txt；文本讀入譯碼(如圖11所示)，譯碼結(jié)果存入ReadTextFile.txt。 圖10：手動譯碼 圖11：文本譯碼(5)進(jìn)入打印編碼代碼界面(如圖12所示)，打印結(jié)果存入CodePrint.txt。 圖12：打印編碼代碼(6)進(jìn)入打印哈夫曼樹，打印結(jié)果存入TreePrint.txt。打印默認(rèn)哈夫曼樹(如圖13所示)，打印頻度差距大的哈夫曼樹(如圖14所示)，打印頻度差距小的哈夫曼樹(如圖15所示) 圖1

25、3：打印默認(rèn)哈夫曼樹 圖14：打印頻度差距大的哈夫曼樹 圖15：打印頻度差距小的哈夫曼樹 四、結(jié)果分析1、算法的時空分析和改進(jìn)設(shè)想(選取主要函數(shù))(1)程序算法分析：經(jīng)過對程序中哈夫曼樹的基本操作函數(shù)及其他相關(guān)算法的時空間復(fù)雜度的分析可知本程序中哈夫曼樹的基本操作函數(shù)及相關(guān)算法的空間復(fù)雜度良好，但哈夫曼樹的Initialization以及DeCoding操作函數(shù)的時間復(fù)雜度比較復(fù)雜，不過從總體的算法效率看，哈夫曼樹的基本操作函數(shù)及其他相關(guān)算法時間及空間復(fù)雜度良好，總體效率良好。(2)主要函數(shù)時空分析（n代表字符種類數(shù)）(如表2所示)：表2：主要函數(shù)時空分析表基本操作時間復(fù)雜度分析空間復(fù)雜度分析

26、InitializationO(n*n)S(n)EnCodingO(n)S(n)O(n)S(n)DeCodingO(n*n)S(n)O(n*n)S(n)PrintO(n)S(n)TreeprintingO(n)S(n) (3)改進(jìn)設(shè)想：1當(dāng)前使用的是一維動態(tài)數(shù)組存儲，當(dāng)哈夫曼函數(shù)添加增加、刪除、修改這些功能時，可選用鏈?zhǔn)酱鎯蚵鼧洌蕰摺?、當(dāng)前程序只能識別大寫英文字母和空格，可改進(jìn)為輸入小寫字母時也可識別。3、當(dāng)前程序是在先序遍歷哈夫曼樹時，采用遞歸算法，可以設(shè)計(jì)一個非遞歸算法遍歷哈夫曼樹，這樣可以降低時間復(fù)雜度，提高程序運(yùn)行速率。2、經(jīng)驗(yàn)和體會一周的課程設(shè)計(jì)結(jié)束了，在這次的課程設(shè)計(jì)

27、中不僅檢驗(yàn)了我們所學(xué)習(xí)的知識，也培養(yǎng)了我們?nèi)绾稳グ盐找患虑?，如何去做一件事情，又如何完成一件事情。在設(shè)計(jì)過程中，與組員分工設(shè)計(jì)，相互探討，相互學(xué)習(xí)，相互監(jiān)督，學(xué)會了合作，學(xué)會了運(yùn)籌帷幄，學(xué)會了寬容，學(xué)會了理解，也學(xué)會了做人與處世。完成這次的課程設(shè)計(jì)任務(wù)，我們要做好以下準(zhǔn)備：(1)首先要熟練掌握二叉樹的性質(zhì)、先序遍歷二叉樹、最優(yōu)二叉樹的構(gòu)建、字符串匹配等，然后在此基礎(chǔ)上掌握理解huffman樹和編碼和譯碼。(2) 完成哈夫曼編譯器，我們要考慮如何把文件當(dāng)中的英文字母編成二進(jìn)制代碼，如何將二進(jìn)制代碼翻譯成英文字母以及如何構(gòu)建一棵哈夫曼樹。在這次的課程設(shè)計(jì)任務(wù)中，我們遇到的問題和困難：(1)起初功

28、能太簡單，經(jīng)過討論，我們增加了一些必要的選擇功能，比如：讀入方式分為文本讀入和手動讀入。(2)逐個手動輸入字符和權(quán)值進(jìn)行編碼，若數(shù)據(jù)太大效率太低。后來增加一個新的功能從文本中讀入數(shù)據(jù)，這樣可大大提高效率。(3)初始化文本讀入時，若數(shù)據(jù)過大，會結(jié)束進(jìn)程，無法進(jìn)行操作。后來增加動態(tài)數(shù)組的最大上限，當(dāng)超過上限，會提示“文本數(shù)據(jù)過大”，而且可以顯示范圍內(nèi)的數(shù)據(jù)。每次出現(xiàn)問題我們都一起討論，研究解決和改進(jìn)的方法。這次課程設(shè)計(jì)的成功，可以說是我們五個人一起努力的成果。我們小組由五個人組成，每個人都有自己在小組中的作用，黃志發(fā)：編寫代碼，設(shè)計(jì)界面 ，調(diào)試程序 / 施鴻俊、賴玉丹：測試數(shù)據(jù) / 邱琳娜、胡明麗

29、：文檔編寫和整理。 我們總是在不斷地調(diào)試程序和改進(jìn)程序的功能，皇天不負(fù)有心人，我們終于在自己的努力和老師的辛勤指導(dǎo)下順利完成了課程設(shè)計(jì)。五、參考文獻(xiàn)1 數(shù)據(jù)結(jié)構(gòu)（c+語言描述），殷人昆主編，清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)題集，嚴(yán)蔚敏編著，清華大學(xué)出版社六、附錄1、源程序文件：Huffman.h：包含哈夫曼樹結(jié)構(gòu)體、哈夫曼編碼結(jié)構(gòu)體、結(jié)點(diǎn)結(jié)構(gòu)體，哈夫曼樹的類定義Huffman.cpp：哈夫曼樹類的成員函數(shù)實(shí)現(xiàn)main.cpp：程序的入口，包含主界面和各個功能函數(shù)的調(diào)用2、輸入數(shù)據(jù)文本：News.txt：存儲了一篇較大規(guī)模的大寫英文文章，用于文件讀入編碼和文件讀入初始化123.txt：存儲了較小規(guī)模的大寫英文文章，用于文件讀入編碼和文件讀入初始化321.txt:存儲了較小規(guī)模的0,1代碼，用于文件讀入進(jìn)行譯碼3、小組成員及分工表(如表3所示)：