哈夫曼(huffman)編譯碼器課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：17 大?。?74.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　工學系課程設計報告　　設計題目：哈夫曼（huffman）編譯碼器 　　系別： 　　專業(yè) (方向)： 　　年

2、級、班： 　　學生姓名： 　　學生學號： 　　指導教師： 　　年月日<

3、/b>　　目錄　　哈夫曼(huffman )編譯碼器3　　一、編譯碼器開發(fā)的背景3　　二、系統(tǒng)的分析與設計3　?。ㄒ唬┫到y(tǒng)功能要求3<p&

4、gt;　　（二）系統(tǒng)模塊結構設計4　　三、系統(tǒng)的設計與實現(xiàn)6　?。ㄒ唬﹎ain()6　?。ǘ┻\算7　　1. 權值運算quanzhi()7　　2. 印二叉樹函數(shù)huffmantree

5、( )7　　3.編譯碼運算huffmancode()9　　4. 輸出運算 shuchu()9　　四、系統(tǒng)測試10　　（一）測試主函數(shù)10　?。ǘy試印二叉樹函數(shù)10</p&

6、gt;　　（三）測試譯碼運算函數(shù)11　　五、總結12　　六、附件（代碼、部分圖表）13　　哈夫曼(huffman )編譯碼器　　編譯碼器開發(fā)的背景 &

7、lt;/p>　　利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。　　二、系統(tǒng)的分析與設計　?。ㄒ唬┫到y(tǒng)功能要求

8、　　一個完整的系統(tǒng)應具有以下功能：　　I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。　　E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTr

9、an中的正文進行編碼，然后將結果存入文件CodeFile中。　　D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。　　P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。

10、　　T：印哈夫曼樹（Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　?。ǘ┫到y(tǒng)模塊結構設計　　通過對系統(tǒng)功能的分析，哈夫曼（huffman）編譯碼器功能如圖（1）所示。　　圖（1）哈夫

11、曼（huffman)編譯碼器功能圖　　通過上圖的功能分析，把整個系統(tǒng)分為四個模塊：　　1.初始化模塊，該模塊主要實現(xiàn)：輸入二叉樹的結點數(shù)，以及要加密的句子，建立哈夫曼樹。　　2.輸出二叉樹模塊，該運算模塊主要實現(xiàn)：將輸入的字符串中每個字符出現(xiàn)的次數(shù)當作權值，建立二叉樹，將二叉樹的parent,weight,lch

12、ild,rchild輸出。　　3.譯碼模塊，該操作主要實現(xiàn)：對編碼后的代碼進行譯碼，然后輸出。　　4.輸出模塊，該操作主要進行表頭的輸出。　　圖２　　流程圖　　三、系統(tǒng)的設計與實現(xiàn)<b&

13、gt;　　（一）main()　　輸出1.輸出二叉樹操作2.進行輸出二叉樹操作3.退出編譯碼操作系統(tǒng)，并讓用戶選擇所進行的操作，對其調用。　　該模塊的具體代碼如下所示：　　void main()　　{</p&g

14、t;　　int i,n,s=1; 　　hnodetype huffnode[maxnode];　　while(s)　　{　　shuchu();</b&

15、gt;　　scanf("%d",&i);　　switch(i)　　{　　case 1:&

16、lt;b>　　{　　haffmantree(huffnode,&n);　　break;　　}　　case 2:</p&

17、gt;　　{　　haffmancode();　　break;　　}　　case 3: </p

18、>　　s=0;　　break;　　}　　}　　}<

19、;/p>　　分析：首先輸出一個主菜單，方便用戶進行操作，用switch語句調用函數(shù)使用戶對其進行選擇要執(zhí)行的操作（1.輸出二叉樹操作，2.進行編譯碼操作，3.退出程序）。　?。ǘ┻\算　　該模塊的具體代碼如下所示：　　權值運算quanzhi()&

20、lt;/p>　　分析：此函數(shù)用于對一串字符進行求權值運算，利用循環(huán)將一串字符中每個字符的個數(shù)設定為權值。　　void quanzhi(int t[maxleaf],char s[maxleaf],int n)//求權值函數(shù)，將句子中的字符出現(xiàn)的個數(shù)當作權值　　{&l

21、t;p>　　int i,j,h;　　for(i=0;i<n;i++)　　{　　for(j=0;j<n;j++)　　if(s[i]==s[j])　　h++;&

22、lt;/b>　　t[i]=h;　　}　　}　　印二叉樹函數(shù)huffmantree( )　　void haffm

23、antree(hnodetype huffnode[maxnode],int *m)　　{　　int i,j,n,k;　　int m1,m2,x1,x2;　　char s[maxleaf],t[maxleaf];

24、　　printf("輸入葉子結點個數(shù)：");　　scanf("%d",&n);　　for(i=0;i<2*n-1;i++)//數(shù)組huffnode[]初始化　　{

25、;　　huffnode[i].weight=0;　　huffnode[i].parent=-1;　　huffnode[i].lchild=-1;　　huffnode[i].rchild=-1;　　}<p&

26、gt;　　printf("輸入要編譯的句子的\n");　　for(i=0;i<n;i++){　　printf("第%d個結點",i+1);　　scanf("%d",&huffnode[i].weight);<p

27、>　　getchar();　　}　　printf("印二叉樹：\n"); 　　for(i=0;i<n;i++)　　{

28、;　　quanzhi(t,s,n);　　k=huffnode[i].weight;　　}　　for(i=0;i<n-1;i++)　　{//構造哈夫曼樹

29、;　　m1=m2=maxvalue;　　x1=x2=0;　　for(j=0;j<n+i;j++)　　{//選取最小和次小兩個權值　　if(huffnode[j].parent==-1&&huffnode[j].w

30、eight<m1)　　{　　m2=m1;　　x2=x1;　　m1=huffnode[j].weight;<

31、;b>　　x1=j;　　}　　else　　if(huffnode[j].parent==-1&&huffnode[j].weight<m2)<

32、b>　　{　　m2=huffnode[j].weight;　　x2=j;　　}　　}//將找出的兩棵子樹合并為一顆子樹　　huf

33、fnode[x1].parent=n+i;　　huffnode[x2].parent=n+i;　　huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;　　huffnode[n+i].lchild=x1;

34、　　huffnode[n+i].rchild=x2;　　}　　for(i=0;i<2*n-1;i++)　　{　　printf(" %4d",k);</

35、p>　　printf(" %4d",huffnode[i].lchild);　　printf(" %4d",huffnode[i].rchild);　　printf(" %4d\n",huffnode[i].parent);&

36、lt;/p>　　}　　*m=n;　　}　　3.編譯碼運算huffmancode()　　void haffmancode()<

37、/p>　　{　　hnodetype huffnode[maxnode];　　hcodetype huffcode[maxleaf],cd;　　int i,j,c,p,n=0;　　haffmantree(hu

38、ffnode,&n);　　for(i=0;i<n;i++)　　{　　cd.start=n-1;　　c=i;　　p=huffnode[c].p

39、arent;　　while(p!=-1)　　{　　if(huffnode[p].lchild==c)　　cd.bit[cd.start]=0;　　else

40、　　cd.bit[cd.start]=1;　　cd.start--;　　c=p;　　p=huffnode[c].parent;　　}

41、　　for(j=cd.start+1;j<n;j++)　　huffcode[i].bit[j]=cd.bit[j];　　huffcode[i].start=cd.start;　　}　　for(i=0;i<

42、;n;i++)　　{　　printf("第%d個譯碼為：",i+1);　　for(j=huffcode[i].start+1;j<n;j++)　　printf("%4d",huffcode

43、[i].bit[j]);　　printf("\n");　　}　　}　　輸出運算 shuchu()　　void shuchu()<

44、/p>　　{　　printf("********************************************************************************\n");　　printf("***

45、 |** 哈夫曼樹的編譯碼 ** | ***\n");　　printf("*** |** 1.輸出二叉樹操作 ** | ***\n");　　printf("**

46、* |** 2.進行編譯碼操作 ** | ***\n");　　printf("*** |** 3.退出編譯碼操作系統(tǒng)** | ***\n");

47、　　printf("********************************************************************************\n");　　printf("請選擇要進行的操作:");　　}<p&

48、gt;　　四、系統(tǒng)測試　　（一）測試主函數(shù)main（）函數(shù)　　該測試主要進行對主函數(shù)調用以及輸出的測試，測試的結果：　　（二）測試印二叉樹函數(shù)　　測試選擇1，選擇1操作首先輸入葉子節(jié)點數(shù)，然后輸入要編譯的句子，分別輸入第n+1個節(jié)點，

49、然后系統(tǒng)會將輸入字符的個數(shù)當作權值進行編譯輸出二叉樹，測試結果為：　　測試譯碼運算函數(shù)　　測試選擇2，輸入要選擇的操作2，然后按要求依次輸入需要的值，系統(tǒng)會根據(jù)輸入的數(shù)據(jù)進行譯碼操作，最后輸出譯碼。輸出結果為： 　　測試退出函數(shù)&l

50、t;/p>　　測試選擇3進行退出，測試結果為:　　五、總結　　系統(tǒng)功能：系統(tǒng)完成了將一段字符串進行哈夫曼加密，用戶將自己的選擇輸入程序，然后按照程序的提示進行輸入，系統(tǒng)將根據(jù)輸入進行編碼、譯碼操作，然后印出編譯的二叉樹，以及每個字符的譯碼。　　不足

51、：系統(tǒng)沒有將印哈夫曼樹操作完成，系統(tǒng)沒有將字符的權值根據(jù)大小將左孩子設為最小權值，將次小權值設為右孩子，導致加密有許多種，哈夫曼樹也創(chuàng)建了許多種，輸出的譯碼不唯一。　　收獲：通過一學期數(shù)據(jù)結構的學習，我發(fā)現(xiàn)數(shù)據(jù)結構比較難，沒有完整的自己獨立完成一個程序。但也學到了許多東西，學會了以前不會的函數(shù)調用，在編程時，有許多小問題還是不能夠及時的發(fā)現(xiàn)，老是被一點小問題卡住導致程序不執(zhí)行或輸出死循環(huán)，一些程

52、序的指針還不太熟悉。　　通過這次程序設計，我發(fā)現(xiàn)了許多自己的不足，對一些算法還不能熟練運用，不能將所學的運用到程序中，一些語句還是不太懂；同時，也有一些收獲，對函數(shù)調用能夠熟練運用，也明白了結構體的作用，掌握了最優(yōu)二叉樹的建立和原理，對哈夫曼樹有了更深一步的了解。　　六、附件（代碼、部分圖表）

53、　/*哈弗曼樹*/　　#include <stdio.h>　　#define maxvalue 1000//定義最大權值　　#define maxleaf 50//定義哈夫曼樹中葉子結點個數(shù)　　#define maxnode maxleaf

54、*2-1//定義哈夫曼樹中結點個數(shù)整數(shù)常量maxnode　　#define maxbit 100//定義哈夫曼樹的最大長度整數(shù)常量　　typedef struct//定義結構體　　{　　int weight;&

55、lt;p>　　int parent;　　int lchild;　　int rchild;　　}hnodetype;　　typedef struct　　{<p

56、>　　int bit[maxbit];　　int start;　　}hcodetype;　　//求權值函數(shù)　　void quanzhi(int t[maxleaf],char s[maxleaf],int n)//求權值函數(shù)，將

57、句子中的字符出現(xiàn)的個數(shù)當作權值　　{　　int i,j,h;　　for(i=0;i<n;i++)　　{　　for(j=0;j<n;j++)&l

58、t;/p>　　if(s[i]==s[j])　　h++;　　t[i]=h;　　}　　}<

59、/p>　　//印二叉樹函數(shù)　　void haffmantree(hnodetype huffnode[maxnode],int *m)　　{　　int i,j,n,k;

60、　　int m1,m2,x1,x2;　　char s[maxleaf],t[maxleaf];　　printf("輸入葉子結點個數(shù)：");　　scanf("%d",&n);　　for(i=0;i<2*n-1;i++)/

61、/數(shù)組huffnode[]初始化　　{　　huffnode[i].weight=0;　　huffnode[i].parent=-1;　　huffnode[i].lchild=-1;　　huff

62、node[i].rchild=-1;　　}　　printf("輸入要編譯的句子的\n");　　for(i=0;i<n;i++){　　printf("第%d個結點",i+1);</p&

63、gt;　　scanf("%d",&huffnode[i].weight);　　getchar();　　}　　printf("印二叉樹：\n"); 　　for

64、(i=0;i<n;i++)　　{　　quanzhi(t,s,n);　　k=huffnode[i].weight;　　}　　for(i=0;i<

65、n-1;i++)　　{//構造哈夫曼樹　　m1=m2=maxvalue;　　x1=x2=0;　　for(j=0;j<n+i;j++)　　{//選取最

66、小和次小兩個權值　　if(huffnode[j].parent==-1&&huffnode[j].weight<m1)　　{　　m2=m1;　　x2=x1;

67、　　m1=huffnode[j].weight;　　x1=j;　　}　　else　　if(huf

68、fnode[j].parent==-1&&huffnode[j].weight<m2)　　{　　m2=huffnode[j].weight;　　x2=j;

69、　}　　}//將找出的兩棵子樹合并為一顆子樹　　huffnode[x1].parent=n+i;　　huffnode[x2].parent=n+i;　　huffnode[n+i].weight=huffnode[x1].weight+huffnode[

70、x2].weight;　　huffnode[n+i].lchild=x1;　　huffnode[n+i].rchild=x2;　　}　　for(i=0;i<2*n-1;i++)<b

71、>　　{　　printf(" %4d",k);　　printf(" %4d",huffnode[i].lchild);　　printf(" %4d",huffnode[i].rchild

72、);　　printf(" %4d\n",huffnode[i].parent);　　}　　*m=n;　　}

73、;　　//編譯碼函數(shù)　　void haffmancode()　　{　　hnodetype huffnode[maxnode];　　hcodetype huffcode[max

74、leaf],cd;　　int i,j,c,p,n=0;　　haffmantree(huffnode,&n);　　for(i=0;i<n;i++)　　{　　cd.start=n-1

75、;　　c=i;　　p=huffnode[c].parent;　　while(p!=-1)　　{　　if(huffnode[p].lchild==c)<

76、;/p>　　cd.bit[cd.start]=0;　　else　　cd.bit[cd.start]=1;　　cd.start--;　　c=p;&

77、lt;p>　　p=huffnode[c].parent;　　}　　for(j=cd.start+1;j<n;j++)　　huffcode[i].bit[j]=cd.bit[j];　　huffcode[i].start=cd

78、.start;　　}　　for(i=0;i<n;i++)　　{　　printf("第%d個譯碼為：",i+1);　　for(j=

79、huffcode[i].start+1;j<n;j++)　　printf("%4d",huffcode[i].bit[j]);　　printf("\n");　　}　　}&

80、lt;/b>　　//輸出主菜單函數(shù)　　void shuchu()　　{　　printf("*********************************************

81、***********************************\n");　　printf("*** |** 哈夫曼樹的編譯碼 ** | ***\n");　　printf("***

82、 |** 1.輸出二叉樹操作 ** | ***\n");　　printf("*** |** 2.進行編譯碼操作 ** | ***\n");　　printf("***

83、 |** 3.退出編譯碼操作系統(tǒng)** | ***\n");　　printf("********************************************************************************\n");<

84、;p>　　printf("請選擇要進行的操作:");　　}　　//主函數(shù)　　void main()　　{&l

85、t;p>　　int i,n,s=1; 　　hnodetype huffnode[maxnode];　　while(s)　　{　　shuchu();<

86、;/p>　　scanf("%d",&i);　　switch(i)　　{　　case 1:<b&g

87、t;　　{　　haffmantree(huffnode,&n);　　break;　　}　　case 2:&

88、lt;p>　　{　　haffmancode();　　break;　　}　　case 3:

89、　　s=0;　　break;　　}　　}　　}

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

哈夫曼(huffman)編譯碼器課程設計

文檔簡介

溫馨提示

最新文檔

評論

哈夫曼(huffman)編譯碼器課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載