數(shù)據(jù)結構--huffman編碼和譯碼

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

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

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

文檔簡介

1、　　《數(shù) 據(jù) 結構》　　課程設計說明書　　課程設計任務書　　目錄　　目錄III<p&

2、gt;　　第一章需求分析4　　1.1引言4　　1.2任務概述4　　1.3數(shù)據(jù)描述4　　1.4功能需求5　　1.5性能需求5

3、　1.6運行需求5　　第二章概要設計6　　2.1總體設計6　?。ㄒ唬?設計目的：6　　（二）函數(shù)劃分7　　2.2數(shù)據(jù)類型設計（或數(shù)據(jù)結構設計）7　　2.3接口設計

4、7　　2.4運行界面設計8　　第三章詳細設計9　　3.1輸入、創(chuàng)建模塊設計9　　3.2編碼模塊設計10　　3.3譯碼模塊設計11　　3.4主函數(shù)模塊設計13<

5、/p>　　第四章測試分析15　　4.1測試程序執(zhí)行情況15　　4.2出現(xiàn)的問題和解決的方法17　　第五章課程設計總結18　　附錄：程序代碼19　　參考文獻26<

6、;/b>　　第一章需求分析　　引言　　目前，進行快速遠距離通信的主要手段是電報，即將需傳送的文字轉(zhuǎn)化成由二級制的字符組成的字符串。　　利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼

7、。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個對應的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。因此，哈夫曼樹在通信、編碼和數(shù)據(jù)壓縮等技術領域有著廣泛的應用。<

8、;p>　　此設計說明書是對編碼/譯碼系統(tǒng)開發(fā)的一個初步的分析說明性文檔，旨在通過該文檔清晰的闡述系統(tǒng)的實際功能，方便系統(tǒng)開發(fā)人員對系統(tǒng)的理解以及與用戶的溝通。文檔相關說明部分在目錄部分已全部涵蓋，閱讀此文檔的相關人員可以通過目錄索引找到相應部分予以閱讀。　　任務概述　　Huffman編碼和譯碼

9、;　　根據(jù)給定的字符集和各字符的頻率值，求出其中給定字符Huffman編碼，并針對一段文本（定義在該字符集上）進行編碼和譯碼，實現(xiàn)一個Huffman編碼/譯碼系統(tǒng)。　　數(shù)據(jù)描述　　該哈夫曼編碼/譯碼系統(tǒng)程序中的數(shù)據(jù)主要有：哈夫曼樹、哈夫曼編碼，哈夫曼譯碼等。<p&g

10、t;　　功能需求　　輸入模塊：輸入各個元素，建立哈夫曼樹；　　編碼模塊：將輸入的各個元素建立哈夫曼樹，進行編碼；　　譯碼模塊：將電文以0或1輸入后，根據(jù)之前的哈夫曼樹進行譯碼；　　輸出模塊：建立好的哈夫曼樹、編碼、譯碼進行輸出。<

11、;/p>　　性能需求　　要求該編碼/譯碼系統(tǒng)具有一定的可擴展性以便適應發(fā)展，且便于維護；　　要求該編碼/譯碼系統(tǒng)便于使用，使用步驟簡易明了。　　運行需求　　基于wind

12、ows平臺下的窗口圖形界面軟件，運行主界面為windows的經(jīng)典運行界面，采用多文檔界面，從而使程序更加美觀，整齊有序，簡易操作。　　軟件運行基于windows平臺上的xp,Vista,win7等　　概要設計　　總體設計

13、;　　設計目的：　　掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力；　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；　　提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；<p

14、>　　訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。　　圖2.1：程序主體設計圖　　函數(shù)劃分　　該程序有一個主函數(shù)和多個子函數(shù)，主函數(shù)完成對子函數(shù)的調(diào)用，各子函數(shù)實現(xiàn)相應的功能。&

15、lt;b>　　結點的開辟。　　實現(xiàn)對輸入字符串中出現(xiàn)的不同字符及其出現(xiàn)字數(shù)的信息記錄。　　用葉子結點構造赫夫曼樹。　　獲得構造的赫夫曼樹中所有葉子結點的元素及其赫夫曼編碼。　　輸出各葉子結點元素及其對應的赫夫曼編碼。<

16、;p>　　輸出輸入的字符串的赫夫曼編碼。　　調(diào)用各子函數(shù)　　數(shù)據(jù)類型設計（或數(shù)據(jù)結構設計）　　表2.1：數(shù)據(jù)類型設計　　接口設計

17、　表2.1：函數(shù)列表　　運行界面設計　　圖2.1：運行界面設計　　詳細設計　　輸入、創(chuàng)建模塊設計

18、　　輸入、創(chuàng)建哈夫曼樹：　　int HuffmanCreate(HuffNode*ht)　　{　　int i,k,n,m1,m2,p1,p2;　　printf("請輸入元素個數(shù)\n");&l

19、t;p>　　scanf("%d",&n);　　for(i=1;i<=n;i++) //輸入結點值和信息　　{　　getchar();//接收回車

20、printf("第%d個元素的:\n結點值:",i);　　scanf("%c",&ht[i].data);　　printf("權值:");　　scanf("%d",&ht[i].weight);

21、　　}　　for(i=1;i<=2*n-1;i++) //對數(shù)組初始化　　ht[i].parent=ht[i].left=ht[i].right=0;　　for(i=n+1;i<=2*n-1

22、;i++)　　{　　m1=m2=32767; //初始化，令m1,m2為整數(shù)最大值　　p1=p2=1;　　for(k=1;k<=i-1;k++)

23、 //從數(shù)組中找　　if(ht[k].parent==0) //parent為零切權值最小的兩個結點　　if(ht[k].weight<m1)　　{　　m2=m1

24、; //令m1為最小權值　　p2=p1; //p1 為最小權值的位置　　m1=ht[k].weight; //m1存放最小權值　　p1=k;　　}<

25、;/b>　　else if(ht[k].weight<m2)　　{　　m2=ht[k].weight; //m2 為次小權值　　p2=k; //p2為次小權值所在位置

26、　　}　　ht[p1].parent=i; //i分別付給下標為p1，p2的數(shù)組中　　ht[p2].parent=i;　　ht[i].weight=m1+m2; //新節(jié)點權值為最小權值和次小權值之和

27、　　ht[i].left=p1; //p1為新節(jié)點的左孩子　　ht[i].right=p2; //p2為新節(jié)點的右孩子　　}　　printf("哈夫曼樹已成功建立!\n");<

28、;p>　　return n; //返回結點數(shù)　　}　　編碼模塊設計　　根據(jù)創(chuàng)建好的哈夫曼樹，進行編碼：　　void Encoding(HuffNode

29、 ht[],HuffCode hcd[],int n)　　{　　HuffCode d;　　int i,k,f,c;　　for(i=1;i<=n;i++)//對所有節(jié)點循環(huán)

30、;　　{　　d.start=n+1; //起始地點　　c=i; //從葉結點開始向上　　f=ht[i].parent;　　while(f!=0) //到樹根結束

31、　　{　　if(ht[f].left==c)　　d.cd[--d.start]='0'; //規(guī)定左數(shù)代碼為零　　else<p

32、>　　d.cd[--d.start]='1'; //規(guī)定右樹代碼為一　　c=f;//c為孩子位置　　f=ht[f].parent; //f指雙親位置　　}<p&g

33、t;　　hcd[i]=d;　　}　　printf("輸出哈夫曼編碼:\n");　　for(i=1;i<=n;i++)　　{</

34、p>　　printf("%c:",ht[i].data); 　　//先輸出結點　　for(k=hcd[i].start;k<=n;k++) //在輸出對應編碼　　printf("

35、%c",hcd[i].cd[k]);　　printf("\n");　　}　　}　　譯碼模塊設計<p

36、>　　根據(jù)已有的哈夫曼樹和提供的電文，進行譯碼：　　void Decoding(HuffNode ht[],HuffCode hcd[],int n)　　{　　int f,m,k;　　DataType c,ch[200];

37、 //c接收文件,ch存儲　　printf("請輸入電文(0 or 1),以#結束\n");　　c=getchar();　　k=1;　　while(c!='#')

38、 //單字符循環(huán)輸入，以#結束　　{　　ch[k]=c; //單字符一次存入ch字串中　　c=getchar();　　k=k+1;

39、 //ch 下地址后移　　}　　m=k; //標記數(shù)組存儲末位位置　　f=2*n-1;　　k=1;//k

40、記錄電文字符個數(shù)　　printf("輸出哈夫曼譯碼:\n");　　while(k<m) //k循環(huán)到數(shù)組末尾結束　　{　　whi

41、le(ht[f].left!=0) //直到左孩子結點為零結束　　{　　if(ch[k]=='0') //若接收字符為0，則存為左孩子　　f=ht[f].left;</p&g

42、t;　　if(ch[k]=='1') //若接收字符為1，則存為右孩子　　f=ht[f].right;　　k++; //ch數(shù)組下標后移　　}&l

43、t;p>　　printf("%c",ht[f].data);　　f=2*n-1; //每次都從根節(jié)點開始查找　　}　　printf("\n");<p&g

44、t;　　}　　主函數(shù)模塊設計　　主函數(shù)的設計：　　int main(int argc,char*argv[])　　{&l

45、t;/p>　　int n,select,flag=FALSE; //flag為零標記第一次選擇功能　　HuffNode ht[2*MAXNUM]; //定義存放哈夫曼的數(shù)組　　HuffCode hcd[MAXNUM]; //定義存放編碼的數(shù)

46、組　　while(TRUE)　　{　　printf("\n——————歡迎進入赫夫曼編碼譯碼——————\n\n");　　printf("1.建立哈夫曼樹 \n");

47、　　printf("2.編碼 \n");　　printf("3.譯碼 \n");　　printf("4.退出程序 \n\n");　　printf("請選擇您要實現(xiàn)的功能:(請輸入1-4)

48、\n");　　scanf("%d",&select);　　if(select>=1&&select<=4){　　if(select!=1&&select!=4&&flag==0)<p&g

49、t;　　{　　printf("請先建立哈夫曼樹在選擇其他功能!\n");　　continue;　　}　　flag=TRUE;</p&

50、gt;　　switch(select) 　　{　　case 1:　　n=HuffmanCreate(ht);　　break;&

51、lt;/p>　　case 2:　　Encoding(ht,hcd,n);　　break;　　case 3:　　Decoding(h

52、t,hcd,n);　　break;　　case 4:　　exit(0);　　}

53、　　}else{　　printf("請重新輸入!\n");　　}　　}　　return 0;<

54、/p>　　}　　測試分析　　測試程序執(zhí)行情況　　圖4.1：選擇建立哈夫曼樹　　圖4.2：輸入需建立哈夫曼樹的元素個數(shù)</p&

55、gt;　　圖4.3：成功建立哈夫曼樹　　圖4.4：根據(jù)建立好的哈夫曼樹，進行編碼　　圖4.5：根據(jù)建立好的哈夫曼樹以及輸入的電文，進行譯碼　　出現(xiàn)的問題和解決的方法　　程序的語句結束后，忘記打分號：程序運行出現(xiàn)錯誤后，加上分號；

56、　　輸入電文時，誤將0和1輸成其他數(shù)據(jù)，結果程序出現(xiàn)將其他數(shù)據(jù)隨機當做0或1。　　課程設計總結　　在課程設計過程中，我們每個人選擇一個課題，認真研究，根據(jù)課堂教授內(nèi)容，借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強我們的獨立思考能力和動手能力；通過編寫實驗代碼和調(diào)試運行

57、，我們可以逐步積累調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。　　在課程設計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我們完成系統(tǒng)。更為重要的是，我們同學之間加強了交流，在對問題的認識方面可以交換不同的意見。　　在寫代碼前，首先，對問題進行了分析，明確了目標，列出了大的框架，然后逐漸細化，劃分出不同的功能模塊，由

58、具體的子函數(shù)去實現(xiàn)，先在紙上編寫代碼，寫好后進行了反復的邏輯推理，發(fā)現(xiàn)并解決邏輯問題，然后，上機調(diào)試，方法是：一個一個功能模塊分開進行調(diào)試，主要看調(diào)試的模塊能否達到預期的結果，這樣可以縮小排錯的范圍，便以糾錯和提高編程的效率，當每個功能模塊都調(diào)試好后，就把各個部分組合起來，再進行調(diào)試，主要檢查各函數(shù)接口是否正確，當達到預期的結果，調(diào)試結束，編程部分完成，然后按實驗要求完成實驗報告。　　數(shù)據(jù)結構課

59、程具有比較強的理論性，同時也具有較強的可應用性和實踐性。課程設計是一個重要的教學環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略實驗的總結，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學生必須嚴格訓練分析總結能力、書面表達能力。需要逐步培養(yǎng)書寫科學實驗報告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。　　附錄：程序代碼</

60、p>　　#include<stdio.h>　　#include<malloc.h>　　#include<limits.h>　　#include<string.h>　　#include<std

61、lib.h>　　#include<io.h>　　#include<math.h>　　#include<process.h>　　#define TRUE 1　　#define FALSE 0

62、　　#define OK 1　　#define ERROR -1　　#define INFEASIBLE -1　　typedef char DataType;　　#define MAXNUM 50<p

63、>　　typedef struct //huffman 樹結點的結構定義　　{　　DataType data; //數(shù)據(jù)用字符表示　　int weight; //權值</p&g

64、t;　　int parent; //雙親　　int left; //左孩子　　int right; //右孩子　　}HuffNode;　　typedef stru

65、ct//huffman 樹結點的存儲定義　　{　　DataType cd[MAXNUM]; //存放編碼位串　　int start; //編碼起始位置</p&

66、gt;　　}HuffCode;　　int HuffmanCreate(HuffNode*ht)　　{　　int i,k,n,m1,m2,p1,p2;　　printf("請輸入元素個數(shù)\n");

67、　　scanf("%d",&n);　　for(i=1;i<=n;i++) //輸入結點值和信息　　{　　getchar();

68、 //接收回車　　printf("第%d個元素的:\n結點值:",i);　　scanf("%c",&ht[i].data);　　printf("權值:");　　scanf("%d"

69、,&ht[i].weight);　　}　　for(i=1;i<=2*n-1;i++) //對數(shù)組初始化　　ht[i].parent=ht[i].left=ht[i].right=0;<p&g

70、t;　　for(i=n+1;i<=2*n-1;i++)　　{　　m1=m2=32767; //初始化，令m1,m2為整數(shù)最大值　　p1=p2=1;

71、for(k=1;k<=i-1;k++) //從數(shù)組中找　　if(ht[k].parent==0) //parent為零切權值最小的兩個結點　　if(ht[k].weight<m1)　　{&l

72、t;p>　　m2=m1; //令m1為最小權值　　p2=p1; //p1 為最小權值的位置　　m1=ht[k].weight; //m1存放最小權值　　p1=k;<p

73、>　　}　　else if(ht[k].weight<m2)　　{　　m2=ht[k].weight; //m2 為次小權值　　p2=k;

74、 //p2為次小權值所在位置　　}　　ht[p1].parent=i; //i分別付給下標為p1，p2的數(shù)組中　　ht[p2].parent=i;　　ht[i].weight=m1+m2;

75、 //新節(jié)點權值為最小權值和次小權值之和　　ht[i].left=p1;//p1為新節(jié)點的左孩子　　ht[i].right=p2;//p2為新節(jié)點的右孩子　　}　　printf("哈夫曼樹已成功建立!\n&quo

76、t;);　　return n; //返回結點數(shù)　　}　　//編碼　　void Encoding(HuffNode ht[],HuffCode hcd[],int n)

77、　　{　　HuffCode d;　　int i,k,f,c;　　for(i=1;i<=n;i++) //對所有節(jié)點循環(huán)　　{

78、　　d.start=n+1; //起始地點　　c=i; //從葉結點開始向上　　f=ht[i].parent;　　while(f!=0) //到樹根結束&

79、lt;/p>　　{　　if(ht[f].left==c)　　d.cd[--d.start]='0'; //規(guī)定左數(shù)代碼為零　　else<

80、;p>　　d.cd[--d.start]='1'; //規(guī)定右樹代碼為一　　c=f; //c為孩子位置　　f=ht[f].parent; //f指雙親位置<

81、;/p>　　}　　hcd[i]=d;　　}　　printf("輸出哈夫曼編碼:\n");　　for(i=1;i

82、<=n;i++)　　{　　printf("%c:",ht[i].data); //先輸出結點　　for(k=hcd[i].start;k<=n;k++) //在輸出對應編碼<p

83、>　　printf("%c",hcd[i].cd[k]);　　printf("\n");　　}　　}　　//譯碼

84、　　void Decoding(HuffNode ht[],HuffCode hcd[],int n)　　{　　int f,m,k;　　DataType c,ch[200]; //c接收文件,ch

85、存儲　　printf("請輸入電文(0 or 1),以#結束\n");　　c=getchar();　　k=1;　　while(c!='#') //單字符循

86、環(huán)輸入，以#結束　　{　　ch[k]=c; //單字符一次存入ch字串中　　c=getchar();　　k=k+1; //ch下地址后移

87、　　}　　m=k; //標記數(shù)組存儲末位位置　　f=2*n-1;　　k=1; //k記錄電文字符個數(shù)

88、printf("輸出哈夫曼譯碼:\n");　　while(k<m) //k循環(huán)到數(shù)組末尾結束　　{　　while(ht[f].left!=0) //直到左孩子結點為零結束</p&

89、gt;　　{　　if(ch[k]=='0') //若接收字符為0，則存為左孩子　　f=ht[f].left;　　if(ch[k]=='1') //若接收字符為1，

90、則存為右孩子　　f=ht[f].right;　　k++; //ch數(shù)組下標后移　　}　　printf("%c",ht[f].data);

91、　　f=2*n-1; //每次都從根節(jié)點開始查找　　}　　printf("\n");　　}　　int

92、 main(int argc,char*argv[])　　{　　int n,select,flag=FALSE; //flag為零標記第一次選擇功能　　HuffNode ht[2*MAXNUM]; //定義存放哈夫曼的數(shù)組&

93、lt;/p>　　HuffCode hcd[MAXNUM]; //定義存放編碼的數(shù)組　　while(TRUE)　　{　　printf("\n——————歡迎進入赫夫曼編碼譯碼——————\n\n");

94、　　printf("1.建立哈夫曼樹 \n");　　printf("2.編碼 \n");　　printf("3.譯碼 \n");　　printf("4.退出程序

95、 \n\n");　　printf("請選擇您要實現(xiàn)的功能:(請輸入1-4)\n");　　scanf("%d",&select);　　if(select>=1&&select<=4){

96、　if(select!=1&&select!=4&&flag==0)　　{　　printf("請先建立哈夫曼樹在選擇其他功能!\n");　　continue;&l

97、t;p>　　}　　flag=TRUE;　　switch(select)　　{　　case 1:　　n=Huff

98、manCreate(ht);　　break;　　case 2:　　Encoding(ht,hcd,n);　　break;<p&g

99、t;　　case 3:　　Decoding(ht,hcd,n);　　break;　　case 4:　　exit(0);&

100、lt;/p>　　}　　}else{　　printf("請重新輸入!\n");　　}　　}&l

101、t;/b>　　return 0;　　}　　參考文獻　　《數(shù)據(jù)結構（C語言版）》嚴蔚敏、吳偉民主編清華大學出版社 <

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

溫馨提示

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

數(shù)據(jù)結構--huffman編碼和譯碼

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構--huffman編碼和譯碼

文檔簡介

溫馨提示

最新文檔

評論

免費下載