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

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　題目：哈夫曼編碼譯碼　　姓名：　　專業(yè)　　目錄<

2、p>　　一、系統(tǒng)開發(fā)的背景…………………………………………………… ………………….2　　二、系統(tǒng)分析與設(shè)計…………… ……………………………………………………………… 2　?。?）系統(tǒng)功能要求……………………………………………………………….…………2 （2）設(shè)計包含的幾個方面………… ………………………………………………………3</p

3、>　　三、詳細(xì)設(shè)計………………………………………………………………………….…………3　　四、流程圖…………………………………………………………………………….…………8　　五、調(diào)試結(jié)果……………………………………………………………………….…………10　　六、心得體會……………………

4、………………………………………………….…………11　　七、附錄（源代碼）……………………………………………………………….…………11　　哈夫曼編/譯碼器系統(tǒng)　　一、系統(tǒng)開發(fā)的背景　　為了提高信道利用率，縮短信息傳輸時間，降低傳輸成

5、本，且在信息發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在信息接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原），因此設(shè)計哈夫曼編碼/譯碼器系統(tǒng)。　　二、系統(tǒng)分析與設(shè)計　?。ㄒ唬┫到y(tǒng)功能要求：　　【任務(wù)要求】　　1

6、：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。　　2：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件To Be Tran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。　　3：譯碼（Decoding）。利用

7、已建好的哈夫曼樹將文件Code File中的代碼進(jìn)行譯碼，結(jié)果存入文件Text File中。　　4：印代碼文件（Print）。將文件Code File以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件Code Prin中。　　5：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終

8、端上，同時將此字符形式的哈夫曼樹寫入文件Tree Print中。　　【測試數(shù)據(jù)】　　利用教科書中的數(shù)據(jù)調(diào)試程序。　　用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。</p&

9、gt;　　（二）設(shè)計包含的幾個方面：　?、?哈夫曼樹的建立:　　哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進(jìn)行n－1次合并，所以共產(chǎn)生n－1個新結(jié)點，它們都是具有兩

10、個孩子的分支結(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n－1個結(jié)點，其中n個結(jié)點是初始森林的n個孤立結(jié)點。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可以利用一個大小為2n--1的一維數(shù)組來存儲哈夫曼樹中的結(jié)點。　?、?哈夫曼編碼: 　　要求電文的哈夫曼編碼，必須先定義哈夫曼編碼類型，根據(jù)設(shè)計要求和實際需要定義的類型

11、如下： 　　typedet struct { 　　char ch; // 存放編碼的字符 　　char bits[N＋1]; // 存放編碼位串 　　int len; // 編碼的長度 　　}CodeNode; // 編碼結(jié)構(gòu)體類

12、型 　?、?代碼文件的譯碼: 　　譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時，即取出其對應(yīng)的字符存入一個新串中。 　　三、詳細(xì)設(shè)計　?。?）①哈夫曼樹的存儲結(jié)構(gòu)描述為： <

13、;p>　　#define N 50 // 葉子結(jié)點數(shù) 　　#define M 2*N-1 // 哈夫曼樹中結(jié)點總數(shù) 　　typedef struct { 　　int weight; 　　int lchild, rchild, parent; // 左右孩子及雙親指針

14、 　　}HTNode; 　　typedef HTNode HuffmanTree[M+1]; 　　②哈弗曼樹的算法　　void CreateHT(HTNode ht[],int n)

15、 　　int i,k,lnode,rnode;　　int min1,min2;　　for (i=0;i<2*n-1;i++) 　　ht[i].parent=ht[i].lchild=ht[i].rchild=-1;

16、 　　for (i=n;i<2*n-1;i++) 　　{　　min1=min2=32767; 　　lnode=rnode=-1;

17、 　　for (k=0;k<=i-1;k++)　　{　　if (ht[k].parent==-1) {　　if (ht[k].weight<min1)

18、 　　{　　min2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}　　else if (ht[k].w

19、eight<min2)　　{　　min2=ht[k].weight;rnode=k;　　}　　}<b&g

20、t;　　}　　ht[lnode].parent=i;ht[rnode].parent=i; 　　ht[i].weight=ht[lnode].weight+ht[rnode].weight; 　　ht[i].lchild=lnode;ht[i].rch

21、ild=rnode; 　　}　　}　?。?）哈弗曼編碼　　void CreateHCode(HTNode ht[],HCode

22、 hcd[],int n)　　{　　int i,f,c;　　HCode hc;　　for (i=0;i<n;i++) {</p&

23、gt;　　hc.start=n;c=i;　　f=ht[i].parent;　　while (f!=-1) {　　if (ht[f].lchild==c) <

24、;p>　　hc.cd[hc.start--]='0';　　else 　　hc.cd[hc.start--]='1';　　c=f;f=ht[f].parent;<

25、;b>　　}　　hc.start++; //start指向哈夫曼編碼hc.cd[]中最開始字符　　hcd[i]=hc;　　}　　}

26、　　void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出哈夫曼編碼的列表　　{　　int i,k;　　printf(&q

27、uot; 輸出哈夫曼編碼:\n"); 　　for (i=0;i<n;i++) 　　{　　printf(" %c:\t",ht[i].data);

28、 　　for (k=hcd[i].start;k<=n;k++) //輸出所有data中數(shù)據(jù)的編碼　　{　　printf("%c",hcd[i].cd[k]); <

29、;/p>　　}　　printf("\n");　　}　　}　　void editHCode(HTNode ht[

30、],HCode hcd[],int n) 　　{　　char string[MAXSIZE]; 　　int i,j,k;　　scanf("%s",string);

31、 //把要進(jìn)行編碼的字符串存入string數(shù)組中　　printf("\n輸出編碼結(jié)果:\n");　　for (i=0;string[i]!='#';i++) 　　{

32、　　for (j=0;j<n;j++)　　{　　if(string[i]==ht[j].data) {　　for (k=hcd[j].start;k<=n;k++)<

33、p>　　{　　printf("%c",hcd[j].cd[k]);　　}　　break; 　　}</b&

34、gt;　　}　　}　　}　　（3）哈弗曼譯碼　　void deHCode(HT

35、Node ht[],HCode hcd[],int n) //譯碼函數(shù)　　{　　char code[MAXSIZE];　　int i,j,l,k,m,x;　　scanf("%s",code);

36、 //把要進(jìn)行譯碼的字符串存入code數(shù)組中　　while(code[0]!='#')　　for (i=0;i<n;i++)　　{　　m=0;

37、 　　for (k=hcd[i].start,j=0;k<=n;k++,j++) //j為記錄所存儲這個字符的編碼個數(shù)　　{　　if(code[j]==hcd[i].cd[k]) m++;

38、;　　}　　if(m==j) {　　printf("%c",ht[i].data);　　for(x=0;code[x-1]!='#';x++)

39、 　　{　　code[x]=code[x+j];　　}　　}　　}&l

40、t;/p>　　}　?。?）主函數(shù)　　void main()　　{　　int n=26,i;

41、;　　char orz,back,flag=1;　　char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','

42、N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; //初始化　　int fnum[]={186,64,13,22,32,103,21,15,

43、47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}; //初始化　　HTNode ht[M]; //建立結(jié)構(gòu)體　　HCode hcd[N]; 　　for (i=0;i<n;i++)

44、 　　{ht[i].data=str[i];　　ht[i].weight=fnum[i];　　}　　while (flag) 　?。?）顯示部分源程序

45、：　　{ printf("\n");　　printf("\n **班級：2012級信本（1）班姓名：王政銳學(xué)號：20120651144 **");　　printf("\n *******************************

46、****************************");　　printf("\n ************ A---------------顯示編碼 ************");　　printf("\n ************ B---------------進(jìn)

47、行編碼 ************");　　printf("\n ************ C---------------進(jìn)行譯碼 ************");　　printf("\n ************ D---------------退出

48、 ************");　　printf("\n ***********************************************************");　　printf("\n");　　printf("

49、請輸入要選擇的編號:");　　scanf("%c",&orz);　　switch(orz)　　{ case 'a':　　case 'A':</p&g

50、t;　　system("cls"); //清屏函數(shù)　　CreateHT(ht,n);　　CreateHCode(ht,hcd,n);　　DispHCode(ht,hcd,n);　　p

51、rintf("\n按任意鍵返回...");　　getch();　　system("cls");　　break;　　case 'b&

52、#39;:　　case 'B':　　system("cls");　　printf("請輸入要進(jìn)行編碼的字符串(以#結(jié)束):\n");　　editHCode(h

53、t,hcd,n);　　printf("\n按任意鍵返回...");　　getch();　　system("cls");　　break;

54、　　case 'c':　　case 'C':　　system("cls");　　DispHCode(ht,hcd,n);

55、printf("請輸入編碼(以#結(jié)束):\n");　　deHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");　　getch();　　system("cls

56、");　　break;　　case 'd':　　case 'D':　　flag=0;</b&

57、gt;　　break;　　default:　　system("cls");}}}　　四、流程圖如下：<p&g

58、t;　　五、調(diào)試結(jié)果　　進(jìn)入主菜單:　　選A時的顯示結(jié)果：　　選擇B時的顯示結(jié)果：　　選C時的顯示結(jié)果：</p&g

59、t;　　六、心得體會　　通過這次課程設(shè)計，讓我對一個程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進(jìn)一步的認(rèn)識，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當(dāng)，也能達(dá)到相同的效果，甚至更佳，就如這次的課程設(shè)計，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復(fù)

60、習(xí)了之前學(xué)的基本語法，哈夫曼樹最小路徑的求取，哈夫曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題它使我對數(shù)據(jù)結(jié)構(gòu)改變了看法。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。　　七、附錄：<

61、b>　　源程序如下：　　#include <stdio.h>　　#include <stdlib.h> 　　#include<conio.h> 　　#include &l

62、t;string.h>　　#define N 50 　　#define M 2*N-1 　　#define MAXSIZE 100　　typedef struct&l

63、t;b>　　{　　char data; 　　int weight; 　　int parent; //雙親結(jié)點　　int lchild;

64、 　　int rchild; //右孩子結(jié)點　　}HTNode; 　　typedef struct　　{<p

65、>　　char cd[N]; 　　int start; 　　}HCode;　　void CreateHT(HTNode ht[],int n) <

66、p>　　{　　int i,k,lnode,rnode;　　int min1,min2;　　for (i=0;i<2*n-1;i++) 　　ht[i].parent=ht[i].lchild=ht[i].rchi

67、ld=-1; //所有結(jié)點的相關(guān)域置初值-1　　for (i=n;i<2*n-1;i++) //構(gòu)造哈夫曼樹　　{　　min1=min2=32767;

68、lnode=rnode=-1; 　　for (k=0;k<=i-1;k++)　　{　　if (ht[k].parent==-1) //只在尚未構(gòu)造二叉樹的結(jié)點中查找&l

69、t;b>　　{　　if (ht[k].weight<min1) {　　min2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}

70、　　else if (ht[k].weight<min2)　　{　　min2=ht[k].weight;rnode=k;　　}

71、}　　}　　ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; 　　ht[i]

72、.lchild=lnode;ht[i].rchild=rnode; 　　}　　}　　void CreateHCode(HTNode ht[],HCode hcd[],int n)<

73、;p>　　{　　int i,f,c;　　HCode hc;　　for (i=0;i<n;i++) //根據(jù)哈夫曼樹求哈夫曼編碼&l

74、t;b>　　{　　hc.start=n;c=i;　　f=ht[i].parent;　　while (f!=-1) 　　{<

75、;p>　　if (ht[f].lchild==c) 　　hc.cd[hc.start--]='0';　　else 　　hc.cd[hc.start--]='1'

76、;　　c=f;f=ht[f].parent;　　}　　hc.start++; 　　hcd[i]=hc;　　}<

77、;/b>　　}　　void DispHCode(HTNode ht[],HCode hcd[],int n) 　　{　　int i,k;<

78、/p>　　printf(" 輸出哈夫曼編碼:\n"); 　　for (i=0;i<n;i++) 　　{　　printf(" %c:\t&qu

79、ot;,ht[i].data); 　　for (k=hcd[i].start;k<=n;k++) //輸出所有data中數(shù)據(jù)的編碼　　{　　printf("%c",hcd[i].cd[

80、k]); 　　}　　printf("\n");　　}　　}

81、;　　void editHCode(HTNode ht[],HCode hcd[],int n) //編碼函數(shù)　　{　　char string[MAXSIZE]; 　　int i,j,k;<p&

82、gt;　　scanf("%s",string); 　　printf("\n輸出編碼結(jié)果:\n");　　for (i=0;string[i]!='#';i++) //#為終止標(biāo)志&l

83、t;b>　　{　　for (j=0;j<n;j++)　　{　　if(string[i]==ht[j].data) {　　for (k=hcd[j].start;k<=n

84、;k++)　　{　　printf("%c",hcd[j].cd[k]);　　}　　break; //輸出完成后跳出當(dāng)前for循環(huán)<

85、;/p>　　}　　}　　}　　}　　void deHCode(HTNode ht[],HCo

86、de hcd[],int n) //譯碼函數(shù)　　{　　char code[MAXSIZE];　　int i,j,l,k,m,x;　　scanf("%s",code);

87、 //把要進(jìn)行譯碼的字符串存入code數(shù)組中　　while(code[0]!='#')　　for (i=0;i<n;i++)　　{　　m=0;

88、　　for (k=hcd[i].start,j=0;k<=n;k++,j++) 　　{　　if(code[j]==hcd[i].cd[k]) 　　m++;</

89、p>　　}　　if(m==j) 　　{　　printf("%c",ht[i].data);

90、;　　for(x=0;code[x-1]!='#';x++) 　　{　　code[x]=code[x+j];　　}　　}&

91、lt;/p>　　}　　}　　void main()　　{　　int n=26,i;　　c

92、har orz,back,flag=1;　　char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N

93、9;,'O','P','Q','R','S','T','U','V','W','X','Y','Z'}; //初始化　　int fnum[]={186,64,13,22,32,103,21,15,47,5

94、7,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}; //初始化　　HTNode ht[M]; //建立結(jié)構(gòu)體　　HCode hcd[N]; 　　for (i=0;i<n;i++)

95、 　　{ht[i].data=str[i];　　ht[i].weight=fnum[i];　　}　　while (flag) 　　{ printf(&qu

96、ot;\n");　　printf(" **************************************");　　printf("\n ** A---------------顯示編碼 **");　　printf("\n

97、 ** B---------------進(jìn)行編碼 **");　　printf("\n ** C---------------進(jìn)行譯碼 **");　　printf("\n ** D---------------退出 **\n");<p&

98、gt;　　printf(" ****************************************");　　printf("\n");　　printf(" 請輸入選擇的編號:");　　scanf("%c&q

99、uot;,&orz);　　switch(orz)　　{ case 'a':　　case 'A':　　system("cls");

100、 　　CreateHT(ht,n);　　CreateHCode(ht,hcd,n);　　DispHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");　　get

101、ch();　　system("cls");　　break;　　case 'b':　　case 'B':&l

102、t;/b>　　system("cls");　　printf("請輸入要進(jìn)行編碼的字符串(以#結(jié)束):\n");　　editHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");&l

103、t;/p>　　getch();　　system("cls");　　break;　　case 'c':<p&

104、gt;　　case 'C':　　system("cls");　　DispHCode(ht,hcd,n);　　printf("請輸入編碼(以#結(jié)束):\n");　　deHCode(

105、ht,hcd,n);　　printf("\n按任意鍵返回...");　　getch();　　system("cls");　　break;

106、　　case 'd':　　case 'D':　　flag=0;　　break;<

107、;p>　　default:　　system("cls");　　}　　}　　}

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載