哈夫曼樹(shù)課程設(shè)計(jì)報(bào)告

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

1、 閩江學(xué)院 課程設(shè)計(jì)說(shuō)明書(shū) 題目： 哈夫曼編譯碼器 院 系： 計(jì)算機(jī)科學(xué)系 專業(yè)班級(jí)： 10軟件工程 學(xué) 號(hào)： 學(xué)生姓名： 指導(dǎo)教師： 2011年 12 月 30 日 課程設(shè)計(jì)需求分析報(bào)告 一、分析問(wèn)題和確定解決方案 1.分析問(wèn)題 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用

2、率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng),為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編/譯碼系統(tǒng)。 2.確定解決方案 設(shè)計(jì)建立帶權(quán)的哈夫曼樹(shù)，確定哈夫曼樹(shù)的類與成員函數(shù)，以及各函數(shù)之間的調(diào)用關(guān)系，采用動(dòng)態(tài)數(shù)組的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)所需要的數(shù)據(jù)，通過(guò)不同的函數(shù)來(lái)實(shí)現(xiàn)編碼，譯碼以及打印二進(jìn)制編碼、哈夫曼樹(shù)，把不同的數(shù)據(jù)存入不同的txt文件中，通過(guò)主函數(shù)調(diào)用來(lái)實(shí)現(xiàn)功能檢測(cè)。 3.輸入的形式和輸入值的范圍 手動(dòng)或者從文本中讀入數(shù)據(jù)的形式初始化哈夫曼樹(shù)

3、，從鍵盤中或者文件中讀入數(shù)據(jù)，以字母A-Z代表結(jié)點(diǎn)，以自然數(shù)代表權(quán)值，字符串提示使用者所要執(zhí)行的操作。 4.輸出的形式 在顯示器界面上或者以文本的形式來(lái)實(shí)現(xiàn)程序調(diào)試的輸出。 5.程序所能達(dá)到的功能 (1)初始化。手動(dòng)輸入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件WritehfmTree中,輸出哈夫曼樹(shù)及各字符對(duì)應(yīng)的編碼存于WritehfmCode;從文本中讀入字符，建立哈夫曼樹(shù)存于ReadhfmTree, 輸出哈夫曼樹(shù)及各字符對(duì)應(yīng)的編碼存于ReadhfmCode. (2)編碼。手動(dòng)輸入一串大寫英文字符，該字符存于WriteToBeTron中，對(duì)字符進(jìn)行編碼并將

4、它存于WriteCodeFile中；從文件中讀取字符編碼并存于ReadCodeFile中。 (3)譯碼。先初始化默認(rèn)哈夫曼樹(shù)，手動(dòng)輸入二進(jìn)制代碼進(jìn)行譯碼存于WriteTextFile中；從文件中讀取二進(jìn)制代碼進(jìn)行譯碼存于ReadTextFile中。 (4)印代碼文件。將文件ReadCodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的代碼碼寫入文件CodePrint中。 (5)印哈夫曼樹(shù)。將初始化的哈夫曼樹(shù)以直觀的方式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件TreePrint中。 各個(gè)功能數(shù)據(jù)輸出存儲(chǔ)位置（如表1所示） 表1：各個(gè)功能數(shù)據(jù)輸出存儲(chǔ)位置表

5、功能 字母 二進(jìn)制碼 初始化 WritehfmTree（手動(dòng)） WritehfmCode（手動(dòng)） ReadhfmTree（文本讀入） ReadhfmCode（文本讀入） hfmTree（默認(rèn)文本讀入） hfmCode（默認(rèn)文本讀入） 編碼 WriteToBeTron（手動(dòng)） WriteCodeFile（手動(dòng)） ReadCodeFile（文本讀入） 譯碼 WriteTextFile（手動(dòng)） WriteCodeFile（手動(dòng)） ReadTextFile（文本讀入） 印編碼代碼 CodePrint 印哈夫曼樹(shù) TreePrint 6.測(cè)

6、試數(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)含有錯(cuò)誤的輸入：1>輸入除了主菜單項(xiàng)中的英文字母I(i),E(e),D(d),P(p),Q(q) 輸出結(jié)果：<您的輸入有誤，請(qǐng)重新輸入：> 2>輸入除了子菜單項(xiàng)中的數(shù)字1，2，3，(4) 輸出結(jié)果：<您的輸入有誤，請(qǐng)重新輸入：> 7.程序說(shuō)明

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

8、本這三個(gè)函數(shù)；進(jìn)入編碼功能后調(diào)用手動(dòng)編碼，文本讀入編碼這兩個(gè)函數(shù)；進(jìn)入譯碼功能后調(diào)用手動(dòng)譯碼，文本讀入譯碼這兩個(gè)函數(shù)(如圖2所示)。 圖2:：各程序模塊之間的層次(調(diào)用)關(guān)系 (4)默認(rèn)的哈夫曼樹(shù)： 空格以及字母A—Z頻度分別為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)的哈夫曼樹(shù)(如圖3所示)。 圖3：默認(rèn)的哈夫曼樹(shù) 二、詳細(xì)設(shè)計(jì) 1、哈夫曼樹(shù)存儲(chǔ)及

9、類的定義： #include #include #include #include #include typedef struct //哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu) { int weight; //權(quán)值 char HTch; //字符 int parent,lchild,rchild; //雙親，左孩子，右孩子 }HTNode,*HuffmanTree; //動(dòng)態(tài)數(shù)組存儲(chǔ)哈夫曼樹(shù) typedef struct //

10、哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu) { char ch; //字符 char* hufCh; //二進(jìn)制碼 }HuffmanCode; //動(dòng)態(tài)數(shù)組存儲(chǔ)哈夫曼編碼表 typedef struct //字符結(jié)點(diǎn) { char ch; //字符 int wt; //字符權(quán)值 }wElem; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)讀入字符與權(quán)值 class Huffman { public: Huffman(){}; //構(gòu)造函數(shù) ~Huffman(){}; //析構(gòu)函數(shù) void Initialization(HuffmanTree

11、 &HT,HuffmanCode *HC,int &n);//初始化，手動(dòng) void Initialization(HuffmanTree &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); //手動(dòng)編碼 void EnCoding(HuffmanCode *HC,char*

12、EnCodeFile); //文件讀入編碼 void DeCoding(HuffmanTree HT,HuffmanCode *HC,int n);//手動(dòng)譯碼 void DeCoding(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n); //文件讀入譯碼 void Print(char *);//打印二進(jìn)制編碼 void Treeprinting( HTNode T,HuffmanTree HT,int n );//打印哈夫曼樹(shù) }; 2、哈夫曼樹(shù)的基本操作： //手動(dòng)輸入字符與權(quán)值并初始化 void H

13、uffman::Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n)//哈夫曼樹(shù)對(duì)象，編碼對(duì)象，字符數(shù) //從文件讀入標(biāo)準(zhǔn)哈夫曼樹(shù)并初始化 void Huffman::Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)//哈夫曼樹(shù)對(duì)象，編碼對(duì)象，字符數(shù),區(qū)分功能參數(shù) //從文件中統(tǒng)計(jì)字符與權(quán)值，構(gòu)造哈弗曼樹(shù) void Huffman::Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int

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

15、(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n)//哈夫曼樹(shù)對(duì)象，編碼對(duì)象，文件名，字符數(shù) //譯碼函數(shù)，手動(dòng)輸入 void Huffman::DeCoding(HuffmanTree HT,HuffmanCode *HC,int n)//哈夫曼樹(shù)對(duì)象，編碼對(duì)象，字符數(shù) //打印函數(shù)，將文件CodePrint.txt中的內(nèi)容以每行個(gè)代碼顯示在屏幕上 void Huffman::Print(char* cfileName) //文件名 //打印哈夫曼樹(shù) void coprint(HuffmanTree start,Huffm

16、anTree HT) //哈夫曼樹(shù)對(duì)象，哈夫曼樹(shù)對(duì)象 其中部分操作的偽代碼如下： (1)從文件讀入標(biāo)準(zhǔn)哈夫曼樹(shù)并初始化 void Huffman::Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)//哈夫曼樹(shù)對(duì)象，編碼對(duì)象，字符數(shù),區(qū)分功能參數(shù) {定義一個(gè)動(dòng)態(tài)數(shù)組存放空格和26個(gè)英文字母，把字符串" ABCDEFGHIJKLMNOPQRSTUVWXYZ"讀入文件"CharFile.txt" while(charRead.get(inbuf)) { w[j].ch=inbuf; w[j].wt=cw[j]

17、; j++; } //w存放n字符及其權(quán)值(從0號(hào)單元開(kāi)始),構(gòu)造哈夫曼樹(shù)HT,并求出n個(gè)字符的哈夫曼編碼HC. int i,m,ww=0; //n:字符數(shù) m:樹(shù)結(jié)點(diǎn)數(shù) int s1,s2; HuffmanTree p; //定義指針變量p if(n<=1) return; //小于2個(gè)字符，結(jié)束 m=2*n-1; //n個(gè)葉子，2*n-1個(gè)結(jié)點(diǎn) HT=new HTNode[(m+1)*sizeof(HTNode)]; HT[0].parent=-1;HT[0].lchild=-1;HT[0].rchild=-1;HT[0].weight=

18、0; for(p=HT+1,i=1;i<=n;i++,p++,ww++)//初始化n個(gè)葉子結(jié)點(diǎn)(即n個(gè)字符) { p->weight=w[ww].wt; p->HTch=w[ww].ch; p->parent=p->lchild=p->rchild=0; }//跳出循環(huán)時(shí)i=n+1; for(;i<=m;i++,++p)//初始化葉子結(jié)點(diǎn)之外的其它所有結(jié)點(diǎn) { p->weight=0; p->HTch=#; p->parent=p->lchild=p->rchild=0; } for(i=n+1;i<=

19、m;i++)//建立哈夫曼樹(shù) { Select(HT,i-1,s1,s2);//在HT數(shù)組的至i-1個(gè)結(jié)點(diǎn)中選擇parent為且權(quán)值weight最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為S1和S2; HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } char *cd=new char[n];//分配編碼的存儲(chǔ)空間 cd[n-1]=\0;//編碼結(jié)束符 int c,f,start;

20、 for(i=1;i<=n;i++)//逐個(gè)字符求哈夫曼編碼 { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start]=0; else cd[--start]=1; } HC[i].ch=w[i-1].ch;//復(fù)制字符 HC[i].hufCh=new char [(n-start)*sizeof(char)];//為第i個(gè)字符編碼分配空間 strcpy(HC[i].hufCh,&

21、cd[start]);//從cd復(fù)制編碼(串)到HC } //向屏幕輸出哈夫曼編碼,并把編碼保存在文件hfmCode.txt中; ｝ (2)編碼函數(shù),從文件讀取 void Huffman::EnCoding(HuffmanCode *HC,char*EnCodeFile)//編碼數(shù)組對(duì)象，文件名 {對(duì)文件進(jìn)行編碼,并將編碼存于文件ReadCodeFile.txt中 while(ufileRead.get(charInbuf)) { for(int k=1;k<=27;k++) { if(charInbuf==HC[k].ch) { codeW

22、rite<

23、 //字符編碼的頭指針向 while(1) {//主菜單 cout<<"請(qǐng)按順序選擇要實(shí)現(xiàn)的功能:"; int k=1; Huffman hf; //類對(duì)象 while(k) {//將小寫轉(zhuǎn)化為大寫} switch(c) { caseI: //進(jìn)入初始化選擇界面 { //選擇初始化方式后，進(jìn)入子菜單 switch(c){ case ‘1’:{hf.Initialization(HT,HC,current_n);break;

24、 }//手動(dòng)初始化 case ‘2’:{//輸入需要初始化的文件名(需包含后綴名.txt)建立哈夫曼樹(shù); //建立哈夫曼樹(shù),并把哈夫曼樹(shù)存放在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:

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

26、菜單 switch(c){ case ‘1’:{hf.DeCoding(HT,HC,hufnum); break; //手動(dòng)譯碼 } case ‘2’:{//輸入需要的文件名(需包含后綴名.txt) 進(jìn)行譯碼 hf.DeCoding(HT,HC,buf,hufnum); break;//文件譯碼 } case ‘3’: break; //返回 } break; } caseP: //進(jìn)入打印二進(jìn)制編碼界面 { hf.Print("ReadCodeFi

27、le.txt"); break;} caseT: //進(jìn)入打印哈夫曼樹(shù)界面 { hf.Treeprinting(HT[2*current_n-1],HT,current_n);break;} caseQ:exit(-1); //退出 default:exit(-1); } } } 三、系統(tǒng)調(diào)試與測(cè)試 1、調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法: (1)逐個(gè)手動(dòng)輸入字符和權(quán)值進(jìn)行編碼，若數(shù)據(jù)太大效率太低。 解決辦法：后來(lái)增加一個(gè)新的功能從文本中讀入數(shù)據(jù)，這樣可大大提高效率。 (2)初始化文本讀入時(shí)，若數(shù)據(jù)過(guò)大，會(huì)結(jié)束進(jìn)程，無(wú)法進(jìn)行操作。 解決辦法：增加動(dòng)

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

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

30、 圖7：默認(rèn)文本初始化 (3)進(jìn)入編碼界面，用戶可以選擇執(zhí)行手動(dòng)編碼(如圖8所示)，編碼結(jié)果存入WriteCodeFile.txt；文本讀入編碼(如圖9所示)，編碼結(jié)果存入ReadCodeFile.txt。 圖8：手動(dòng)編碼 圖9：文本讀入編碼 (4)進(jìn)入譯碼界面，用戶可以選擇執(zhí)行手動(dòng)譯碼(如圖10所示)，譯碼結(jié)果存入WriteTextFile.txt；文本讀入譯碼(如圖11所示)，譯碼結(jié)果存入ReadTextFile.txt。

31、 圖10：手動(dòng)譯碼 圖11：文本譯碼 (5)進(jìn)入打印編碼代碼界面(如圖12所示)，打印結(jié)果存入CodePrint.txt。 圖12：打印編碼代碼 (6)進(jìn)入打印哈夫曼樹(shù)，打印結(jié)果存入TreePrint.txt。打印默認(rèn)哈夫曼樹(shù)(如圖13所示)，打印頻度差距大的哈夫曼樹(shù)(如圖14所示)，打印頻度差距小的哈夫曼樹(shù)(如圖15所示) 圖13：打印默認(rèn)哈夫曼樹(shù) 圖14：打印頻度差距大的哈夫曼樹(shù)

32、 圖15：打印頻度差距小的哈夫曼樹(shù) 四、結(jié)果分析 1、算法的時(shí)空分析和改進(jìn)設(shè)想(選取主要函數(shù)) (1)程序算法分析： 經(jīng)過(guò)對(duì)程序中哈夫曼樹(shù)的基本操作函數(shù)及其他相關(guān)算法的時(shí)空間復(fù)雜度的分析可知本程序中哈夫曼樹(shù)的基本操作函數(shù)及相關(guān)算法的空間復(fù)雜度良好，但哈夫曼

33、樹(shù)的Initialization以及DeCoding操作函數(shù)的時(shí)間復(fù)雜度比較復(fù)雜，不過(guò)從總體的算法效率看，哈夫曼樹(shù)的基本操作函數(shù)及其他相關(guān)算法時(shí)間及空間復(fù)雜度良好，總體效率良好。 (2)主要函數(shù)時(shí)空分析（n代表字符種類數(shù)）(如表2所示)： 表2：主要函數(shù)時(shí)空分析表 基本操作 時(shí)間復(fù)雜度分析 空間復(fù)雜度分析 Initialization O(n*n) S(n) EnCoding O(n) S(n) O(n) S(n) DeCoding O(n*n) S(n) O(n*n) S(n) Print O(n) S(n) Treeprinting O(n)

34、 S(n) (3)改進(jìn)設(shè)想： 1當(dāng)前使用的是一維動(dòng)態(tài)數(shù)組存儲(chǔ)，當(dāng)哈夫曼函數(shù)添加增加、刪除、修改這些功能時(shí)，可選用鏈?zhǔn)酱鎯?chǔ)哈夫曼樹(shù)，效率會(huì)更高。 2、當(dāng)前程序只能識(shí)別大寫英文字母和空格，可改進(jìn)為輸入小寫字母時(shí)也可識(shí)別。 3、當(dāng)前程序是在先序遍歷哈夫曼樹(shù)時(shí)，采用遞歸算法，可以設(shè)計(jì)一個(gè)非遞歸算法遍歷哈夫曼樹(shù)，這樣可以降低時(shí)間復(fù)雜度，提高程序運(yùn)行速率。 2、經(jīng)驗(yàn)和體會(huì) 一周的課程設(shè)計(jì)結(jié)束了，在這次的課程設(shè)計(jì)中不僅檢驗(yàn)了我們所學(xué)習(xí)的知識(shí)，也培養(yǎng)了我們?nèi)绾稳グ盐找患虑椋绾稳プ鲆患虑?，又如何完成一件事情。在設(shè)計(jì)過(guò)程中，與組員分工設(shè)

35、計(jì)，相互探討，相互學(xué)習(xí)，相互監(jiān)督，學(xué)會(huì)了合作，學(xué)會(huì)了運(yùn)籌帷幄，學(xué)會(huì)了寬容，學(xué)會(huì)了理解，也學(xué)會(huì)了做人與處世。 完成這次的課程設(shè)計(jì)任務(wù)，我們要做好以下準(zhǔn)備： (1)首先要熟練掌握二叉樹(shù)的性質(zhì)、先序遍歷二叉樹(shù)、最優(yōu)二叉樹(shù)的構(gòu)建、字符串匹配等，然后在此基礎(chǔ)上掌握理解huffman樹(shù)和編碼和譯碼。 (2) 完成哈夫曼編譯器，我們要考慮如何把文件當(dāng)中的英文字母編成二進(jìn)制代碼，如何將二進(jìn)制代碼翻譯成英文字母以及如何構(gòu)建一棵哈夫曼樹(shù)。 在這次的課程設(shè)計(jì)任務(wù)中，我們遇到的問(wèn)題和困難： (1)起初功能太簡(jiǎn)單，經(jīng)過(guò)討論，我們?cè)黾恿艘恍┍匾倪x擇功能，比如：讀入方式分為文本讀入和手動(dòng)讀入。 (2)逐個(gè)手動(dòng)

36、輸入字符和權(quán)值進(jìn)行編碼，若數(shù)據(jù)太大效率太低。后來(lái)增加一個(gè)新的功能從文本中讀入數(shù)據(jù)，這樣可大大提高效率。 (3)初始化文本讀入時(shí)，若數(shù)據(jù)過(guò)大，會(huì)結(jié)束進(jìn)程，無(wú)法進(jìn)行操作。后來(lái)增加動(dòng)態(tài)數(shù)組的最大上限，當(dāng)超過(guò)上限，會(huì)提示“文本數(shù)據(jù)過(guò)大”，而且可以顯示范圍內(nèi)的數(shù)據(jù)。 每次出現(xiàn)問(wèn)題我們都一起討論，研究解決和改進(jìn)的方法。這次課程設(shè)計(jì)的成功，可以說(shuō)是我們五個(gè)人一起努力的成果。我們小組由五個(gè)人組成，每個(gè)人都有自己在小組中的作用，黃志發(fā)：編寫代碼，設(shè)計(jì)界面 ，調(diào)試程序 / 施鴻俊、賴玉丹：測(cè)試數(shù)據(jù) / 邱琳娜、胡明麗：文檔編寫和整理。 我們總是在不斷地調(diào)試程序和改進(jìn)程序的功能，皇天不負(fù)有心人，我們終

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