赫夫曼編碼器數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)》</b></p><p><b>　　課程設(shè)計報告</b></p><p>　　專 業(yè) 計算機(jī)科學(xué)與技術(shù) </p><p>　　班 級 (1) </p><p>　　姓 名

2、 </p><p>　　學(xué) 號 </p><p>　　指導(dǎo)教師 </p><p>　　起止時間 2011.10~2011.12 </p><p>　　課程設(shè)計:赫夫曼編碼器</p><p&g

3、t;<b>　　任務(wù)描述</b></p><p>　?。?）建立一個文本文件，統(tǒng)計該文件中各字符頻率，對各字符進(jìn)行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成原文件。</p><p>　?。?）“壓縮文件”即：讀文件、統(tǒng)計文件中的字符個數(shù)、對文件進(jìn)行哈夫曼編碼和譯碼、并將編碼譯碼后的字符存儲在文件中。</p>

4、<p>　　要求：根據(jù)以上任務(wù)說明，設(shè)計程序完成功能。</p><p><b>　　二、問題分析</b></p><p><b>　　1、功能分析</b></p><p>　　分析設(shè)計課題的要求，要求編程實現(xiàn)以下功能：</p><p>　　(1) I：初始化（Initialization

5、）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。</p><p>　　(2) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　　(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件Co

6、deFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。</p><p><b>　　三、數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><p>　　.哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：</p><p>　　typedef struct{ //赫夫曼樹的結(jié)構(gòu)體</p><p><b>　　char ch;&

7、lt;/b></p><p>　　int weight; //權(quán)值</p><p>　　int parent,lchild,rchild;</p><p>　　}htnode,*hfmtree;</p><p><b>　　四、功能設(shè)計</b></p><p>&l

8、t;b>　?。ㄒ唬┲骺夭藛卧O(shè)計</b></p><p>　　為實現(xiàn)通信錄管理的操作功能，首先設(shè)計一個含有多個菜單項的主控菜單程序，然后再為這些菜單項配上相應(yīng)的功能。</p><p>　　程序運行后，給出6個菜單項的內(nèi)容和輸入提示，如下：</p><p>　　一個功能函數(shù)對ASCII碼的初始化并需要一個數(shù)組來保存它們；</p><

9、p>　　定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的過程當(dāng)中保存被選中的字符，即給定報文中出現(xiàn)的字符,模擬哈夫曼樹選取和刪除左右子樹的過程；</p><p>　　自底而上地創(chuàng)建哈夫曼樹，保存根的地址和每個葉節(jié)點的地址，即字符的地址，然后自底而上檢索，首尾對換調(diào)整為哈夫曼樹實現(xiàn)哈弗曼編碼；</p><p>　　從哈弗曼編碼文件當(dāng)中讀入字符，根據(jù)當(dāng)前字符為0或者1的狀況訪問左子樹或者右孩子，實現(xiàn)

10、解碼；</p><p>　　使用文件讀寫操作哈夫曼編碼和解碼結(jié)果的寫入；</p><p><b>　?。ǘ┏绦蚰K結(jié)構(gòu)</b></p><p>　　由課題要求可將程序劃分為以下幾個模塊（即實現(xiàn)程序功能所需的函數(shù)）：</p><p>　　(1) int main()</p><p>　　主函數(shù)：

11、利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）</p><p>　　對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。</p><p>　　(2) Encoding </p>&

12、lt;p>　　編碼功能：對輸入字符進(jìn)行編碼</p><p>　　(3) 、Decoding</p><p>　　譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。</p><p><b>　?。ㄈ┖瘮?shù)調(diào)用關(guān)系</b></p><p>　　程序

13、的主要結(jié)構(gòu)（函數(shù)調(diào)用關(guān)系）如下圖所示。 </p><p>　　其中main()是主函數(shù)，它進(jìn)行菜單驅(qū)動，根據(jù)選擇項0~5調(diào)用相應(yīng)的函數(shù)。main()函數(shù)使用for循環(huán)實現(xiàn)重復(fù)選擇。其循環(huán)結(jié)構(gòu)如下：</p><p>　　int main(){</p><p>　　char code[100],h[100],hl[100];</p>

14、<p>　　int n,i,j,k,l;</p><p>　　ifstream input_file; //文件輸入輸出流</p><p>　　ofstream output_file;</p><p>　　char choice,str[100];</p><p>　　hfmtree HT;</p><

15、;p>　　hfmcode HC;</p><p>　　cout<<"\n";</p><p>　　cout<<" "<<"計算機(jī)（3）班"<<" "<<"Q07620307"<<"

16、 "<<"XXX\n";</p><p>　　while(choice!='Q'&&choice!='q') //當(dāng)choice的值不為q且不為Q時循環(huán)</p><p><b>　　{</b></p><p>　　cou

17、t<<" "<<"*************************赫夫曼編碼/譯碼器*************************\n";</p><p>　　cout<<" "<<"I.Init"<<" &qu

18、ot;<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";</p><p>　　cout<<"請輸入您要操作的步驟：";</p>&

19、lt;p>　　cin>>choice;</p><p>　　if(choice=='I'||choice=='i') //初始化赫夫曼樹</p><p><b>　　{</b></p><p>　　cout<<"請輸入字符個數(shù)：";<

20、;/p><p><b>　　cin>>n;</b></p><p>　　hfmcoding(HT,HC,n);</p><p>　　for(i=1;i<=n;++i)</p><p><b>　　{</b></p><p>　　cout<<HT[i]

21、.ch<<":"<<HC[i]<<endl;</p><p><b>　　}</b></p><p>　　output_file.open("hfmTree.txt");</p><p>　　if(!output_file){</p><p>　

22、　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b

23、>　　{</b></p><p>　　output_file<<"("<<HT[i].ch<<HC[i]<<")";</p><p><b>　　}</b></p><p>　　output_file.close();</p>

24、<p>　　cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl;</p><p><b>　　}</b></p><p>　　else if(choice=='E'||choice=='e') //進(jìn)行編碼，并將字符放入

25、ToBeTran.txt，碼值放入CodeFile.txt中</p><p><b>　　{</b></p><p>　　printf("請輸入字符：");</p><p>　　gets(str);</p><p>　　output_file.open("ToBeTran.txt"

26、);</p><p>　　if(!output_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p

27、><p><b>　　}</b></p><p>　　output_file<<str<<endl;</p><p>　　output_file.close();</p><p>　　output_file.open("CodeFile.txt");</p><

28、p>　　if(!output_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　

29、for(i=0;i<strlen(str);i++){</p><p>　　for(j=0;j<=n;++j)</p><p><b>　　{</b></p><p>　　if(HT[j].ch==str[i])</p><p><b>　　{</b></p><p&

30、gt;　　output_file<<HC[j];</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&

31、lt;p>　　output_file.close();</p><p>　　cout<<"\n";</p><p>　　cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！\n";</p><p>　　input_file.open("CodeFile.txt")

32、; //從CodeFile.txt中讀入編碼，輸出在終端</p><p>　　if(!input_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><

33、;b>　　return 1;</b></p><p><b>　　}</b></p><p>　　input_file>>code;</p><p>　　cout<<"編碼碼值為："<<code<<endl;</p><p>　　inp

34、ut_file.close();</p><p><b>　　}</b></p><p>　　else if(choice=='D'||choice=='d') //讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來的字符放入Textfile.txt中</p><p><b>　　{<

35、/b></p><p>　　input_file.open("CodeFile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　

36、　return 1;</b></p><p><b>　　}</b></p><p>　　input_file>>h;</p><p>　　input_file.close();</p><p>　　output_file.open("Textfile.txt");</p

37、><p>　　if(!output_file)</p><p><b>　　{</b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p>&l

38、t;p><b>　　}</b></p><p><b>　　k=0;</b></p><p>　　while(h[k]!='\0') //先用編碼中的前幾個和字符的編碼相比較，然后往后移</p><p><b>　　{</b></p><p

39、>　　for(i=1;i<=n;i++){</p><p><b>　　l=k;</b></p><p>　　for(j=0;j<strlen(HC[i]);j++,l++){</p><p>　　hl[j]=h[l];</p><p><b>　　}</b></p>

40、<p>　　hl[j]='\0';</p><p>　　if(strcmp(HC[i],hl)==0)</p><p><b>　　{</b></p><p>　　output_file<<HT[i].ch;</p><p>　　k=k+strlen(HC[i]);</p&g

41、t;<p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.close();</p&g

42、t;<p>　　input_file.open("Textfile.txt");</p><p>　　if(!input_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;<

43、/b></p><p><b>　　}</b></p><p>　　input_file>>h; </p><p>　　cout<<h<<endl;</p><p>　　input_file.close();</p><p>　　cout<<&

44、quot;譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中！"<<endl;</p><p><b>　　}</b></p><p>　　else if(choice=='Q'||choice=='q') //退出程序</p><p><b>　　{ &l

45、t;/b></p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　else //如果選了選項之外的就讓用戶重新選擇</p><p><b>　　{</b></p><

46、;p>　　cout<<"您沒有輸入正確的步驟，請重新輸入！"<<endl;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　

47、return 0;</b></p><p><b>　　}</b></p><p><b>　　（四）文件結(jié)構(gòu)</b></p><p>　　1、linklist.h：赫夫曼樹相關(guān)的定義與聲明</p><p>　　2、linklist.cpp：單鏈表運算的實現(xiàn)</p><

48、;p>　　3、menu.h：主菜單函數(shù)的聲明</p><p>　　4、menu.cpp：主菜單函數(shù)的實現(xiàn)</p><p>　　5、mn.cpp：主函數(shù)</p><p>　?。ㄎ澹└骱瘮?shù)的算法設(shè)計</p><p><b>　　1selete、</b></p><p>　　算法原理：選出HT樹到

49、a為止，權(quán)值最小且parent為0的2個節(jié)點</p><p><b>　　流程圖：</b></p><p>　　代碼描述：void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點</p><p><b>　　{&

50、lt;/b></p><p>　　int i,j,x,y;</p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].parent==0){</p><p><b>　　x=j;</b></p><p><b>　　break;</

51、b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i){</p><p>　　if(HT[i].weight<HT[x].weight&&HT[i].parent==0){&l

52、t;/p><p>　　x=i; //選出最小的節(jié)點</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].paren

53、t==0&&x!=j)</p><p><b>　　{</b></p><p><b>　　y=j;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>

54、<b>　　}</b></p><p>　　for(i=j+1;i<=a;++i)</p><p><b>　　{</b></p><p>　　if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)</p><

55、p><b>　　{</b></p><p>　　y=i; //選出次小的節(jié)點</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(x>y){</b>

56、</p><p><b>　　*p1=y;</b></p><p><b>　　*p2=x;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{&l

57、t;/b></p><p><b>　　*p1=x;</b></p><p><b>　　*p2=y;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　算法的時間復(fù)雜

58、度分析：O(a)</p><p>　　2、hfmcoding</p><p>　　算法原理：構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC</p><p><b>　　流程圖：</b></p><p>　　代碼描述：void hfmcoding(hfmtree &HT,hfmcode &HC,int n

59、) //構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC</p><p><b>　　{</b></p><p>　　int i,start,c,f,m,w;</p><p>　　int p1,p2;</p><p>　　char *cd,z;</p><p><b>　　if(n<

60、;=1){</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　算法的時間復(fù)雜度分 O(n)</p><p><b>　　五、測試數(shù)據(jù)和結(jié)果</b></p><p><

61、b>　　1、測試數(shù)據(jù)</b></p><p>　　自定義一組如下的測試數(shù)據(jù)，包含三個人員：</p><p><b>　　字符 權(quán)值</b></p><p>　　A 1</p><p>　　B 12</p><p>　　C 3

62、</p><p>　　D 7</p><p>　　E 8</p><p>　　F 14</p><p>　　G 31</p><p>　　H 23 U 41</p><p>　　J 9&l

63、t;/p><p>　　K 18</p><p><b>　　2、測試結(jié)果</b></p><p>　　本程序在VC++環(huán)境下實現(xiàn)，下面是對以上測試數(shù)據(jù)的運行結(jié)果。</p><p>　　(1) 主菜單顯示如下：</p><p><b>　　(2) 編碼：</b>&l

64、t;/p><p><b>　　譯碼</b></p><p><b>　　退出 </b></p><p><b>　　六、結(jié)束語</b></p><p>　　本設(shè)計完成了課題要求的任務(wù)，哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的