哈夫曼樹課程設(shè)計報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程設(shè)計題目： 哈夫曼編碼器 院 系： 專業(yè)班級： 學 號： 學生姓名： 指導教師： 2014年 1月 2日 課程設(shè)計需求分析報告一、分析問題和確定解決方案1.分析問題利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng),為這樣的信息收發(fā)站寫一個哈夫曼的編/譯碼系統(tǒng)。2.確定解決方案設(shè)計建立帶權(quán)的哈夫曼樹，確定哈夫曼樹的類與成員函數(shù)，以及各函數(shù)之間的調(diào)用關(guān)系，采用動態(tài)數(shù)組的存儲

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

3、符，建立哈夫曼樹存于ReadhfmTree, 輸出哈夫曼樹及各字符對應的編碼存于ReadhfmCode.(2)編碼。手動輸入一串大寫英文字符，該字符存于WriteToBeTron中，對字符進行編碼并將它存于WriteCodeFile中；從文件中讀取字符編碼并存于ReadCodeFile中。(3)印代碼文件。將文件ReadCodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的代碼碼寫入文件CodePrint中。(4)印哈夫曼樹。將初始化的哈夫曼樹以直觀的方式顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。各個功能數(shù)據(jù)輸出存儲位置（如表1所示）表1：各個功

4、能數(shù)據(jù)輸出存儲位置表功能字母二進制碼初始化WritehfmTree（手動）WritehfmCode（手動）ReadhfmTree（文本讀入）ReadhfmCode（文本讀入）hfmTree（默認文本讀入）hfmCode（默認文本讀入）編碼WriteToBeTron（手動）WriteCodeFile（手動）ReadCodeFile（文本讀入）印編碼代碼CodePrint印哈夫曼樹TreePrint6.測試數(shù)據(jù)(1)正確的輸入：1>輸入主菜單項中的英文字母I(i),E(e),D(d),P(p),Q(q)輸出結(jié)果：進入所選的功能界面2>輸入子菜單項中的數(shù)字1，2，3，(4) 輸出結(jié)果：執(zhí)

5、行所選的功能(2)含有錯誤的輸入：1>輸入除了主菜單項中的英文字母I(i),E(e),D(d),P(p),Q(q) 輸出結(jié)果：<您的輸入有誤，請重新輸入：> 2>輸入除了子菜單項中的數(shù)字1，2，3，(4) 輸出結(jié)果：<您的輸入有誤，請重新輸入：>7.程序說明(1)程序中數(shù)據(jù)類型的定義：用到三組結(jié)構(gòu)體，分別是哈夫曼樹的動態(tài)數(shù)組存儲結(jié)構(gòu)*HuffmanTree，哈夫曼編碼表的存儲結(jié)構(gòu)HuffmanCode，字符結(jié)點的動態(tài)數(shù)組存儲結(jié)構(gòu)wElem以及哈夫曼樹類定義class Huffman。(2)主程序的流程圖：用戶從主菜單中選擇所要進行的操作，如果輸入選項錯誤則提

6、示重新輸入選項，否則進入選中的操作項(如圖1所示)。 圖1：主程序流程圖(3)各程序模塊之間的層次(調(diào)用)關(guān)系：主函數(shù)main（）調(diào)用初始化，編碼，譯碼，打印二進制編碼，打印哈夫曼樹這五個子函數(shù)；進入初始化功能后調(diào)用手動輸入，文本讀入，默認文本這三個函數(shù)；進入編碼功能后調(diào)用手動編碼，文本讀入編碼這兩個函數(shù)；進入譯碼功能后調(diào)用手動譯碼，文本讀入譯碼這兩個函數(shù)(如圖2所示)。 圖2:：各程序模塊之間的層次(調(diào)用)關(guān)系(4)默認的哈夫曼樹：空格以及字母AZ頻度分別為186，64，13，22，32，103，21，15，47，57，1，5，32，20，57，63，15，1，48，51，80，23，8，1

7、8，1，16，1建立一棵默認的哈夫曼樹(如圖3所示)。 圖3：默認的哈夫曼樹二、詳細設(shè)計1、哈夫曼樹存儲及類的定義：#include <string>#include <iostream>#include <fstream>#include <iomanip>#include <conio.h>typedef struct /哈夫曼樹的存儲結(jié)構(gòu)int weight;/權(quán)值char HTch;/字符int parent,lchild,rchild;/雙親，左孩子，右孩子HTNode,*HuffmanTree; /動態(tài)數(shù)組存儲哈夫曼樹ty

8、pedef struct /哈夫曼編碼表的存儲結(jié)構(gòu)char ch; /字符char* hufCh; /二進制碼HuffmanCode; /動態(tài)數(shù)組存儲哈夫曼編碼表typedef struct /字符結(jié)點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(Huffma

9、nTree &HT,HuffmanCode *HC,int &n,int v);/初始化，標準文件void Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n);/初始化，統(tǒng)計void EnCoding(HuffmanCode *HC,int hufnum); /手動編碼void EnCoding(HuffmanCode *HC,char*EnCodeFile); /文件讀入編碼void Print(char *);/打印二進制編碼void Treeprinting( HTNod

10、e T,HuffmanTree HT,int n );/打印哈夫曼樹;2、哈夫曼樹的基本操作：/手動輸入字符與權(quán)值并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n)/哈夫曼樹對象，編碼對象，字符數(shù)/從文件讀入標準哈夫曼樹并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/哈夫曼樹對象，編碼對象，字符數(shù),區(qū)分功能參數(shù)/從文件中統(tǒng)計字符與權(quán)值，構(gòu)造哈弗曼樹void Huff

11、man:Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n)/哈夫曼樹對象，編碼對象，文件名，字符數(shù)/編碼函數(shù),對用戶輸入的文件的正文進行編碼,然后將結(jié)果存入文件WriteCodeFile.txt中void Huffman:EnCoding(HuffmanCode *HC,int hufnum)/編碼數(shù)組對象，字符數(shù)/編碼函數(shù),從文件讀取void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/編碼數(shù)組對象，文件名/譯碼函數(shù)，對文件CodeFi

12、le中的代碼進行譯碼,結(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)/哈夫曼樹對象，編碼對象，字符數(shù)/打印函數(shù)，將文件CodePrint.txt中的內(nèi)容以每行個代碼顯示在屏幕上void Huffman:Print(char* cfileName) /文件名/打印哈夫曼樹v

13、oid coprint(HuffmanTree start,HuffmanTree HT) /哈夫曼樹對象，哈夫曼樹對象其中部分操作的偽代碼如下：(1)從文件讀入標準哈夫曼樹并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/哈夫曼樹對象，編碼對象，字符數(shù),區(qū)分功能參數(shù)定義一個動態(tài)數(shù)組存放空格和26個英文字母，把字符串" ABCDEFGHIJKLMNOPQRSTUVWXYZ"讀入文件"CharFile.txt"while(charRea

14、d.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é)點數(shù) int s1,s2;HuffmanTree p;/定義指針變量pif(n<=1) return;/小于2個字符，結(jié)束m=2*n-1;/n個葉子，2*n-1個結(jié)點HT=new HTNode(m+1)*sizeof(HTNode);HT0.parent=-1;HT0.lchild=-1;HT0.rchild=-1;HT0.weight=0;for(p=HT+1,i=1;i&l

15、t;=n;i+,p+,ww+)/初始化n個葉子結(jié)點(即n個字符)p->weight=www.wt; p->HTch=www.ch;p->parent=p->lchild=p->rchild=0;/跳出循環(huán)時i=n+1;for(;i<=m;i+,+p)/初始化葉子結(jié)點之外的其它所有結(jié)點p->weight=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個

16、結(jié)點中選擇parent為且權(quán)值weight最小的兩個結(jié)點,其序號分別為S1和S2;HTs1.parent=i;HTs2.parent=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-

17、start='0'elsecd-start='1'HCi.ch=wi-1.ch;/復制字符HCi.hufCh=new char (n-start)*sizeof(char);/為第i個字符編碼分配空間strcpy(HCi.hufCh,&cdstart);/從cd復制編碼(串)到HC/向屏幕輸出哈夫曼編碼,并把編碼保存在文件hfmCode.txt中;(2)編碼函數(shù),從文件讀取void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/編碼數(shù)組對象，文件名對文件進行編碼,并將編碼存于文件ReadCodeFil

18、e.txt中while(ufileRead.get(charInbuf)for(int k=1;k<=27;k+)if(charInbuf=HCk.ch)codeWrite<<HCk.hufCh;break; 3、主函數(shù)：#include "Huffman.cpp"/主函數(shù)void main() int current_n=27; /全局變量，字符數(shù)char c; /功能選擇int hufnum=27; /默認字符數(shù)HuffmanTree HT; /哈夫曼樹對象HuffmanCode *HC=new HuffmanCode(hufnum+1)*sizeof

19、(HuffmanCode);/分配n 個 /字符編碼的頭指針向while(1)/主菜單 cout<<"請按順序選擇要實現(xiàn)的功能<I,E,D,P,T>:"int k=1; Huffman hf;/類對象while(k)/將小寫轉(zhuǎn)化為大寫switch(c)case'I':/進入初始化選擇界面/選擇初始化方式后，進入子菜單switch(c)case 1:hf.Initialization(HT,HC,current_n);break; /手動初始化case 2:/輸入需要初始化的文件名(需包含后綴名.txt)建立哈夫曼樹;/建立哈夫曼樹,并

20、把哈夫曼樹存放在ReadhfmTree.txt中 hf.Initialization(HT,HC,buf,current_n); break;/從文件讀入數(shù)據(jù)初始化case 3:hf.Initialization(HT,HC,current_n,0);/標準初始化 case 4:break;break;case'E':/進入編碼選擇界面/選擇字符序列讀入方式后進入子菜單switch(c)case '1':hf.EnCoding(HC,hufnum);break;/手動編碼 case '2':/輸入需要的文件名(需包含后綴名.txt) 進行編碼hf

21、.EnCoding(HC,buf); break;/文件讀入編碼 case '3':break;break;case'P':/進入打印二進制編碼界面 hf.Print("ReadCodeFile.txt");break;case'T':/進入打印哈夫曼樹界面 hf.Treeprinting(HT2*current_n-1,HT,current_n);break;case'Q':exit(-1);/退出default:exit(-1);三、系統(tǒng)調(diào)試與測試1、調(diào)試過程中遇到的問題及解決辦法:(1)逐個手動輸入字符和

22、權(quán)值進行編碼，若數(shù)據(jù)太大效率太低。解決辦法：后來增加一個新的功能從文本中讀入數(shù)據(jù)，這樣可大大提高效率。(2)初始化文本讀入時，若數(shù)據(jù)過大，會結(jié)束進程，無法進行操作。解決辦法：增加動態(tài)數(shù)組的最大上限，當超過上限，會提示“文本數(shù)據(jù)過大”，而且可以顯示范圍內(nèi)的數(shù)據(jù)。(3)只能讀取固定的文件進行編碼。解決辦法：可以手動輸入想要讀取的文件名。(4)只能打印默認的哈夫曼樹解決辦法：通過增加兩種初始化方式（手動初始化和文本讀入初始化），打印用戶當前初始化的哈夫曼樹。(5)進入子菜單后，輸入的選項必須為數(shù)字，否則會出現(xiàn)死循環(huán)。解決辦法：把輸入的數(shù)據(jù)類型由整型改為字符型。2、測試數(shù)據(jù)及其輸出結(jié)果：(1)進入主菜

23、單界面，用戶可以選擇所要執(zhí)行的操作，比如：初始化<建立哈夫曼樹>，編碼，譯碼，打印二進制編碼代碼，打印哈夫曼樹。在執(zhí)行編碼、譯碼操作前，請先初始化默認的哈夫曼樹(如圖4所示) 。 圖4：主菜單界面(2)進入初始化界面，用戶可以選擇執(zhí)行手動初始化(如圖5所示)，初始化結(jié)果存入WritehfmCode.txt，WritehfmTree.txt ；文本讀入初始化(如圖6所示)，初始化結(jié)果存入ReadhfmCode.txt，ReadhfmTree.txt；默認文本初始化(如圖7所示)，初始化結(jié)果存入hfmCode.txt，hfmTree.txt。 圖5：手動初始化哈夫曼樹 圖6：

24、文本讀入初始化哈夫曼樹 圖7：默認文本初始化(3)進入編碼界面，用戶可以選擇執(zhí)行手動編碼(如圖8所示)，編碼結(jié)果存入WriteCodeFile.txt；文本讀入編碼(如圖9所示)，編碼結(jié)果存入ReadCodeFile.txt。 圖8：手動編碼 圖9：文本讀入編碼(5)進入打印編碼代碼界面(如圖12所示)，打印結(jié)果存入CodePrint.txt。 圖12：打印編碼代碼(6)進入打印哈夫曼樹，打印結(jié)果存入TreePrint.txt。打印默認哈夫曼樹(如圖13所示)，打印頻度差距大的哈夫曼樹(如圖14所示)，打印頻度差距小的哈夫曼樹(如圖15所示) 圖13：打印默認哈夫曼樹 圖14：打印頻度差距大的

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

26、)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)改進設(shè)想：1當前使用的是一維動態(tài)數(shù)組存儲，當哈夫曼函數(shù)添加增加、刪除、修改這些功能時，可選用鏈式存儲哈夫曼樹，效率會更高。2、當前程序只能識別大寫英文字母和空格，可改進為輸入小寫字母時也可識別。3、當前程序是在先序遍歷哈夫曼樹時，采用遞歸算法，可以設(shè)計一個非遞歸算法遍歷哈夫曼樹，這樣可以降低時間復雜度，提高程序運行速率。2、經(jīng)驗和體會一周的課程設(shè)計結(jié)束了，在這次的課程設(shè)計中不僅檢驗了我們所學習的知識，也培養(yǎng)了我們?nèi)绾稳グ盐找患虑?，如何去做一件事情，又如何完成一件事情。在設(shè)計過程中，與組員分工設(shè)計，相互探討，相互學習，相互監(jiān)督，學會了合作，學會了運籌帷幄，學會了寬容，學會了理解