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

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

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

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

文檔簡介

1、　　《數(shù)據(jù)結構》　　課程設計報告　　設計題目哈夫曼 (Huffman) 編/譯碼器 　　學院名稱信息工程學院 &

2、lt;p>　　專業(yè) 班級 　　姓名 　　學號 ______<p

3、>　　題目：哈夫曼(Huffman)編/譯碼器　　一、問題描述　　利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)

4、。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。　　二、設計目標　　幫助學生熟練掌握樹的應用和基本操作，重點掌握二叉樹的存儲，這里以哈夫曼樹為設計目標進一步提高學生的設計能力及對樹的理解。　　三、任務要求<

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

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

7、;　　5) T：印哈夫曼樹（Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。　　四、需求分析　　利用哈夫曼樹(Huffman)編/譯碼　?。ㄒ唬⒊跏蓟蚵鼧?lt;/p

8、>　?。ǘ⒔⒐蚵鼧?lt;/p>　?。ㄈ?、對哈夫曼樹進行編碼　?。ㄋ模?、輸出對應字符的編碼　?。ㄎ澹?、譯碼過程　　五、概要設計

9、哈夫曼樹的存儲結構描述　　typedef struct　　{　　unsigned int weight;　　unsigned int parent, lchild, rchild;　　}HTN

10、ode, *HuffmanTree; 　　哈弗曼樹的算法　　void CreateHT(HTNode ht[],int n) //調用輸入的數(shù)組ht[],和節(jié)點數(shù)n　　{<p&g

11、t;　　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; //所有結點的相關域置初值-1

12、　　for (i=n;i<2*n-1;i++) //構造哈夫曼樹　　{　　min1=min2=32767; //int的范圍是-32768—32767　　lnode=rnode=-1;

13、 //lnode和rnode記錄最小權值的兩個結點位置　　for (k=0;k<=i-1;k++)　　{　　if (ht[k].parent==-1) //只在尚未構造二叉樹的結點中查找

14、　　{　　if (ht[k].weight<min1) //若權值小于最小的左節(jié)點的權值　　{　　min2=min1;rnode=lnode;　　min1=ht[k].w

15、eight;lnode=k;　　}　　else if (ht[k].weight<min2)　　{　　min2=ht[k].weight;rnode=k;<p&

16、gt;　　}　　}　　}　　ht[lnode].parent=i;ht[rnode].parent=i; //兩個最小節(jié)點的父節(jié)點是i<p&

17、gt;　　ht[i].weight=ht[lnode].weight+ht[rnode].weight; //兩個最小節(jié)點的父節(jié)點權值為兩個最小節(jié)點權值之和　　ht[i].lchild=lnode;ht[i].rchild=rnode; //父節(jié)點的左節(jié)點和右節(jié)點　　}&l

18、t;/p>　　}　　哈弗曼編碼　　void CreateHCode(HTNode ht[],HCode hcd[],int n)　　{<p&g

19、t;　　int i,f,c;　　HCode hc;　　for (i=0;i<n;i++) //根據(jù)哈夫曼樹求哈夫曼編碼　　{　　hc.s

20、tart=n;c=i;　　f=ht[i].parent;　　while (f!=-1) //循序直到樹根結點結束循環(huán)　　{　　if (ht[f].lchild==c)

21、 //處理左孩子結點　　hc.cd[hc.start--]='0';　　else //處理右孩子結點　　hc.cd[hc.start--]='1';&l

22、t;p>　　c=f;f=ht[f].parent;　　}　　hc.start++; //start指向哈夫曼編碼hc.cd[]中最開始字符　　hcd[i]=hc;<

23、;b>　　}　　}　　void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出哈夫曼編碼的列表　　{

24、　　int i,k;　　printf(" 輸出哈夫曼編碼:\n"); 　　for (i=0;i<n;i++) //輸出data中的所有數(shù)據(jù)，即A-Z　　{</p&

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

26、　　printf("%c",hcd[i].cd[k]); 　　}　　printf("\n");　　}

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

28、t;　　int i,j,k;　　scanf("%s",string); //把要進行編碼的字符串存入string數(shù)組中　　printf("\n輸出編碼結果:\n");　　for (i=0;string[i]!

29、='#';i++) //#為終止標志　　{　　for (j=0;j<n;j++)　　{　　if(string[i]==ht[j].data)

30、 //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼　　{　　for (k=hcd[j].start;k<=n;k++)　　{　　printf("%

31、c",hcd[j].cd[k]);　　}　　break; //輸出完成后跳出當前for循環(huán)　　}　　}&l

32、t;/p>　　}　　}　　哈弗曼譯碼　　void deHCode(HTNode ht[],HCode hcd[],int n) //譯碼函數(shù)

33、　　{　　char code[MAXSIZE];　　int i,j,l,k,m,x;　　scanf("%s",code); //把要進行譯碼的字符串存入code數(shù)組中

34、　　while(code[0]!='#')　　for (i=0;i<n;i++)　　{　　m=0; //m為想同編碼個數(shù)的計數(shù)器

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

36、b>　　}　　if(m==j) //當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)　　{　　printf(&

37、quot;%c",ht[i].data);　　for(x=0;code[x-1]!='#';x++) //把已經使用過的code數(shù)組里的字符串刪除　　{　　code[x]=code[x+j];<p&g

38、t;　　}　　}　　}　　}　　主函數(shù)

39、　void main()　　{　　int n=26,i;　　char orz,back,flag=1;　　char str[]={'A','B','C','D','

40、;E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W&#

41、39;,'X','Y','Z'}; //初始化　　int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}; //初始化　　HTNode ht[M];

42、 //建立結構體　　HCode hcd[N]; //建立結構體　　for (i=0;i<n;i++) //把初始化的數(shù)據(jù)存入ht結構體中　　{　　ht[i].data=str[

43、i];　　ht[i].weight=fnum[i];　　}　　while (flag) //菜單函數(shù)，當flag為0時跳出循環(huán)　　顯示部分源程序：

44、;　　{　　printf("\n");　　printf(" ********************************");　　printf("\n ** 1-------

45、--------顯示編碼 **");　　printf("\n ** 2---------------進行編碼 **");　　printf("\n ** 3---------------進行譯碼 **");　　printf("\

46、n ** 4---------------退出 **\n");　　printf(" * **********************************");　　printf("\n");　　printf("

47、請輸入選擇的編號:");　　scanf("%c",&orz);　　switch(orz)　　{　　case 'a':

48、;　　case 'A':　　system("cls"); //清屏函數(shù)　　CreateHT(ht,n);　　CreateHCode(ht,hcd,n);

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

50、eak;　　case 'b':　　case 'B':　　system("cls");　　printf("請輸入要進

51、行編碼的字符串(以#結束):\n");　　editHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");　　getch();　　system("cls");&

52、lt;/p>　　break;　　case 'c':　　case 'C':　　system("cls");</p&g

53、t;　　DispHCode(ht,hcd,n);　　printf("請輸入編碼(以#結束):\n");　　deHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");

54、　getch();　　system("cls");　　break;　　case 'd':　　case 'D'

55、;:　　flag=0;　　break;　　default:　　system("cls");&l

56、t;p>　　}}}　　六、詳細設計　　由上表畫出哈夫曼樹：　　由哈夫曼樹得出各字符的編碼：　　關系調用：<

57、;b>　　該程序的流程圖：　　七、測試分析　　白盒：　　查看代碼完整性　　白盒測試也稱結構測試或邏輯驅動測試，它是按照程序內部的結構

58、測試程序，通過測試來檢測產品內部動作是否按照設計規(guī)格說明書的規(guī)定正常進行，檢驗程序中的每條通路是否都能按預定要求正確工作。這一方法是把測試對象看作一個打開的盒子，測試人員依據(jù)程序內部邏輯結構相關信息，設計或選擇測試用例，對程序所有邏輯路徑進行測試，通過在不同點檢查程序的狀態(tài)，確定實際的狀態(tài)是否與預期的狀態(tài)一致。　　黑盒：<p&

59、gt;　　測試是否可以正確的創(chuàng)建，刪除，插入，打印，查找等操作　　黑盒測試也稱功能測試，它是通過測試來檢測每個功能是否都能正常使用。在測試中，把程序看作一個不能打開的黑盒子，在完全不考慮程序內部結構和內部特性的情況下，在程序接口進行測試，它只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當?shù)亟邮蛰斎霐?shù)據(jù)而產生正確的輸出信息。黑盒測試著眼于程序外部結構，不考慮內部邏輯結構，主要針對

60、軟件界面和軟件功能進行測試。　　八、使用說明　　1) 輸入n個字符的權值　　2) 輸入對應的字符　　3) 得出各字符的編碼　　九、測試數(shù)據(jù)</p&g

61、t;　　用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。　　字符空格 A B C D E F G H I J K L M 　　頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20

62、　　字符 N O P Q R S T U V W X Y Z 　　　頻度 57 63 15 1 48 51 80 23 8 18 1 16 1　　注：學生在測試數(shù)據(jù)時，需要寫出測試用例和截圖　　十、該程序的源代碼

63、　#include <stdio.h>　　#include <stdlib.h> //要用system函數(shù)要調用的頭文件　　#include<conio.h> //用getch()要調用的頭文件　　#include <string.

64、h>　　#define N 50 //義用N表示50葉節(jié)點數(shù)　　#define M 2*N-1 //用M表示節(jié)點總數(shù) 當葉節(jié)點數(shù)位n時總節(jié)點數(shù)為2n-1　　#define MAXSIZE 100　　type

65、def struct　　{　　char data; //結點值　　int weight; //權值　　int parent; //雙親結

66、點　　int lchild; //左孩子結點　　int rchild; //右孩子結點　　}HTNode; 　　typedef struct<

67、;p>　　{　　char cd[N]; //存放哈夫曼碼　　int start; //從start開始讀cd中的哈夫曼碼　　}HCode;&l

68、t;p>　　void CreateHT(HTNode ht[],int n) //調用輸入的數(shù)組ht[],和節(jié)點數(shù)n　　{　　int i,k,lnode,rnode;　　int min1,min2;

69、　　for (i=0;i<2*n-1;i++) 　　ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有結點的相關域置初值-1　　for (i=n;i<2*n-1;i++) //構造哈夫曼樹

70、;　　{　　min1=min2=32767; //int的范圍是-32768—32767　　lnode=rnode=-1; //lnode和rnode記錄最小權值的兩個結點位置　　for (k=0;k<=i-1;k++)&l

71、t;/p>　　{　　if (ht[k].parent==-1) //只在尚未構造二叉樹的結點中查找　　{　　if (ht[k].weight<min1) /

72、/若權值小于最小的左節(jié)點的權值　　{　　min2=min1;rnode=lnode;　　min1=ht[k].weight;lnode=k;　　}　　el

73、se if (ht[k].weight<min2)　　{　　min2=ht[k].weight;rnode=k;　　}　　}&l

74、t;p>　　}　　ht[lnode].parent=i;ht[rnode].parent=i; //兩個最小節(jié)點的父節(jié)點是i　　ht[i].weight=ht[lnode].weight+ht[rnode].weight; //兩個最小節(jié)點的父節(jié)點權值為兩個最小節(jié)點權值

75、之和　　ht[i].lchild=lnode;ht[i].rchild=rnode; //父節(jié)點的左節(jié)點和右節(jié)點　　}　　}　　void CreateHCode(H

76、TNode ht[],HCode hcd[],int n)　　{　　int i,f,c;　　HCode hc;　　for (i=0;i<n;i++)

77、 //根據(jù)哈夫曼樹求哈夫曼編碼　　{　　hc.start=n;c=i;　　f=ht[i].parent;　　while (f!=-1) //循序直到樹根結點結束循環(huán)

78、　　{　　if (ht[f].lchild==c) //處理左孩子結點　　hc.cd[hc.start--]='0';　　else

79、 //處理右孩子結點　　hc.cd[hc.start--]='1';　　c=f;f=ht[f].parent;　　}　　hc.start++;

80、 //start指向哈夫曼編碼hc.cd[]中最開始字符　　hcd[i]=hc;　　}　　}　　void DispHCode(HTNode ht[],HCode hcd[],int n

81、) //輸出哈夫曼編碼的列表　　{　　int i,k;　　printf(" 輸出哈夫曼編碼:\n"); 　　for (i=0;i<n;i++)

82、 //輸出data中的所有數(shù)據(jù)，即A-Z　　{　　printf(" %c:\t",ht[i].data); 　　for (k=hcd[i].start;k<=n;k++)

83、 //輸出所有data中數(shù)據(jù)的編碼　　{　　printf("%c",hcd[i].cd[k]); 　　}<p&

84、gt;　　printf("\n");　　}　　}　　void editHCode(HTNode ht[],HCode hcd[],int n) //編碼函數(shù)<b&g

85、t;　　{　　char string[MAXSIZE]; 　　int i,j,k;　　scanf("%s",string); //把要進行編碼的字符串存入string數(shù)組中</p

86、>　　printf("\n輸出編碼結果:\n");　　for (i=0;string[i]!='#';i++) //#為終止標志　　{　　for (j=0;j<n;j++)

87、　　{　　if(string[i]==ht[j].data) //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼　　{　　for (k=hcd[j].start;k

88、<=n;k++)　　{　　printf("%c",hcd[j].cd[k]);　　}　　break; //輸出完成后跳出當前fo

89、r循環(huán)　　}　　}　　}　　}　　void deHCode(HTNode ht

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

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

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

93、值加1　　m++;　　}　　if(m==j) //當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)

94、　　{　　printf("%c",ht[i].data);　　for(x=0;code[x-1]!='#';x++) //把已經使用過的code數(shù)組里的字符串刪除　　{<

95、p>　　code[x]=code[x+j];　　}　　}　　}　　}

96、void main()　　{　　int n=26,i;　　char orz,back,flag=1;　　char str[]={'A','B','C','D','

97、E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W

98、9;,'X','Y','Z'}; //初始化　　int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}; //初始化　　HTNode ht[M];

99、 //建立結構體　　HCode hcd[N]; //建立結構體　　for (i=0;i<n;i++) //把初始化的數(shù)據(jù)存入ht結構體中　　{　　ht[i].data=str[i

100、];　　ht[i].weight=fnum[i];　　}　　while (flag) //菜單函數(shù)，當flag為0時跳出循環(huán)　　{<p

101、>　　printf("\n");　　printf(" **************************************");　　printf("\n ** A---------------顯示編碼 **");

102、printf("\n ** B---------------進行編碼 **");　　printf("\n ** C---------------進行譯碼 **");　　printf("\n ** D---------------退出 **\n");&l

103、t;/p>　　printf(" ****************************************");　　printf("\n");　　printf(" 請輸入選擇的編號:");

104、scanf("%c",&orz);　　switch(orz)　　{　　case 'a':　　case 'A':<

105、/b>　　system("cls"); //清屏函數(shù)　　CreateHT(ht,n);　　CreateHCode(ht,hcd,n);　　DispHCode(ht,hcd,n);

106、　　printf("\n按任意鍵返回...");　　getch();　　system("cls");　　break;

107、　　case 'b':　　case 'B':　　system("cls");　　printf("請輸入要進行編碼的字符串(以#結束):\n");

108、;　　editHCode(ht,hcd,n);　　printf("\n按任意鍵返回...");　　getch();　　system("cls");　　break;</b&

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

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

111、stem("cls");　　break;　　case 'd':　　case 'D':

112、flag=0;　　break;　　default:　　system("cls");　　}<

113、;p>　　}　　}　?。?lt;/b>　　該程序的截圖：　　初始化界面截圖如下</p

114、>　　選A時的顯示結果截圖如下　　選擇B時的顯示結果截圖如下　　選C時的顯示結果截圖如下　　十一、使用說明（給出軟件如何使用，使用時的注意事項）　　VC++6.0編程環(huán)境使用　　1、 VC++

115、6.0程序啟動 　　2、新建工程Project　　3、設定工程Project名稱、保存位置 　　4、設定工程Project的類型 　　5、工程Project的描述信息生成<p&

116、gt;　　6、空工程Project建立完畢　　7）向工程Project中添加(新建)源代碼文件的類型、名稱、保存位置 　　8、設定源代碼文件的類型、名稱　　9、源代碼文件被添加到工程中 　　10、在源代碼文件中添加程

117、序代碼　　11、程序代碼編譯完成后編譯、鏈接過程　　注意事項： 　　（1）一個工程project中可以有多個源文件(.cpp)、多個頭文件（.h）；　　但這些源代碼文件中只能出現(xiàn)一個main函數(shù)，作為整個程序運&

118、lt;/p>　　行的入口； 　?。?）必須關閉前一次程序運行結果窗口，才能進行下一次程序運行； 　?。?）書寫標識符時，忽略了大小寫字母的區(qū)別。 　?。? ) 忘記加分號

119、　　（5）多加分號　　十二、課程設計總結　　本次課程設計的題目是：哈夫曼(Huffman)編/譯碼器。通過這次課程設計，我了解到自己在編寫程序方面還有很多不足，在實踐過程中老師給了我很大的幫助。在這次課程設計中，雖然不會成功的編寫一個完整的程序，但是在看程序的

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載