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

1、<p><b>　　哈夫曼編碼譯碼</b></p><p><b>　　需求分析</b></p><p>　　在當今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長

2、度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上

3、的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串</p><p><b>　　二、其主要流程圖：</b></p><p>　　設(shè)計要求 ： （1）哈

4、夫曼樹的建立；</p><p>　?。?）哈夫曼編碼的生成</p><p>　　（3）編碼文件的譯碼</p><p><b>　　四、總結(jié)：</b></p><p>　　通過這次的課程設(shè)計了解課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過

5、程.隨著科學(xué)技術(shù)發(fā)展的日新日異，當今計算機應(yīng)用在生活中可以說得是無處不在。因此作為二十一世紀的大學(xué)來說掌握計算機開發(fā)技術(shù)是十分重要的。</p><p>　　回顧起此次課程設(shè)計，至今我仍感慨頗多，的確，自從拿到題目到完成整個編程，從理論到實踐，在整整一個星期的日子里，可以學(xué)到很多很多的的東西，同時不僅可以鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實際相結(jié)合是很

6、重要的，只有理論知識是遠遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，這畢竟獨立做的，難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固，比如說結(jié)構(gòu)體……通過這次課程設(shè)計之后，一定把以前所學(xué)過的知識重新溫故。我表示感謝！同時，對給過我?guī)椭乃型瑢W(xué)和各位指導(dǎo)老師再次

7、表示忠心的感謝！</p><p><b>　　五、源程序：</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h> //要用system函數(shù)要調(diào)用的頭文件</p><p>　　#include<conio

8、.h> //用getch()要調(diào)用的頭文件</p><p>　　#include <string.h></p><p>　　#define N 50 //義用N表示50葉節(jié)點數(shù)</p><p>　　#define M 2*N-1 //用M表示節(jié)點總數(shù) 當葉節(jié)點數(shù)位n時

9、總節(jié)點數(shù)為2n-1</p><p>　　#define MAXSIZE 100</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char data; //結(jié)點值</p><p>　　int weight

10、; //權(quán)值</p><p>　　int parent; //雙親結(jié)點</p><p>　　int lchild; //左孩子結(jié)點</p><p>　　int rchild; //右孩子結(jié)點</p><p>　　}H

11、TNode; </p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char cd[N]; //存放哈夫曼碼</p><p>　　int start; //從s

12、tart開始讀cd中的哈夫曼碼</p><p><b>　　}HCode;</b></p><p>　　void CreateHT(HTNode ht[],int n) //調(diào)用輸入的數(shù)組ht[],和節(jié)點數(shù)n</p><p><b>　　{</b></p><p>　　

13、int i,k,lnode,rnode;</p><p>　　int min1,min2;</p><p>　　for (i=0;i<2*n-1;i++) </p><p>　　ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有結(jié)點的相關(guān)域置初值-1</p><p>　　fo

14、r (i=n;i<2*n-1;i++) //構(gòu)造哈夫曼樹</p><p><b>　　{</b></p><p>　　min1=min2=32767; //int的范圍是-32768-32767</p><p>　　lnode=rnode=-1;

15、 //lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置</p><p>　　for (k=0;k<=i-1;k++)</p><p><b>　　{</b></p><p>　　if (ht[k].parent==-1) //只在尚未構(gòu)造二叉樹的結(jié)點中查找</p><p><

16、b>　　{</b></p><p>　　if (ht[k].weight<min1) //若權(quán)值小于最小的左節(jié)點的權(quán)值</p><p><b>　　{</b></p><p>　　min2=min1;rnode=lnode;</p><p>　　min1=ht[k].weigh

17、t;lnode=k;</p><p><b>　　}</b></p><p>　　else if (ht[k].weight<min2)</p><p><b>　　{</b></p><p>　　min2=ht[k].weight;rnode=k;</p><p>&

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

19、　ht[i].weight=ht[lnode].weight+ht[rnode].weight; //兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和</p><p>　　ht[i].lchild=lnode;ht[i].rchild=rnode; //父節(jié)點的左節(jié)點和右節(jié)點</p><p><b>　　}</b></p

20、><p><b>　　}</b></p><p>　　void CreateHCode(HTNode ht[],HCode hcd[],int n)</p><p><b>　　{</b></p><p>　　int i,f,c;</p><p><b>　　HCode

21、 hc;</b></p><p>　　for (i=0;i<n;i++) //根據(jù)哈夫曼樹求哈夫曼編碼</p><p><b>　　{</b></p><p>　　hc.start=n;c=i;</p><p>　　f=ht[i].parent;&l

22、t;/p><p>　　while (f!=-1) //循序直到樹根結(jié)點結(jié)束循環(huán)</p><p><b>　　{</b></p><p>　　if (ht[f].lchild==c) //處理左孩子結(jié)點</p><p>　　

23、hc.cd[hc.start--]='0';</p><p>　　else //處理右孩子結(jié)點</p><p>　　hc.cd[hc.start--]='1';</p><p>　　c=f;f=ht[f].parent;</p><p>&l

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

25、}</b></p><p>　　void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出哈夫曼編碼的列表</p><p><b>　　{</b></p><p><b>　　int i,k;</b></p><p>　　printf(&

26、quot; 輸出哈夫曼編碼:\n"); </p><p>　　for (i=0;i<n;i++) //輸出data中的所有數(shù)據(jù)，即A-Z</p><p><b>　　{</b></p><p>　　printf(" %c:\t",ht[i

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

28、 </p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void

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

30、nf("%s",string); //把要進行編碼的字符串存入string數(shù)組中</p><p>　　printf("\n輸出編碼結(jié)果:\n");</p><p>　　for (i=0;string[i]!='#';i++) //#為終止標志</p&g

31、t;<p><b>　　{</b></p><p>　　for (j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　if(string[i]==ht[j].data) //循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼</p>

32、;<p><b>　　{</b></p><p>　　for (k=hcd[j].start;k<=n;k++)</p><p><b>　　{</b></p><p>　　printf("%c",hcd[j].cd[k]);</p><p><b>

33、;　　}</b></p><p>　　break; //輸出完成后跳出當前for循環(huán)</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

34、<p><b>　　}</b></p><p>　　void deHCode(HTNode ht[],HCode hcd[],int n) //譯碼函數(shù)</p><p><b>　　{</b></p><p>　　char code[MAXSIZE];</p><p>　　i

35、nt i,j,l,k,m,x;</p><p>　　scanf("%s",code); //把要進行譯碼的字符串存入code數(shù)組中</p><p>　　while(code[0]!='#')</p><p>　　for (i=0;i<n;i++)</p><

36、p><b>　　{</b></p><p>　　m=0; //m為想同編碼個數(shù)的計數(shù)器</p><p>　　for (k=hcd[i].start,j=0;k<=n;k++,j++) //j為記錄所存儲這個字符的編碼個數(shù)</p><p><b>　　{&l

37、t;/b></p><p>　　if(code[j]==hcd[i].cd[k]) //當有相同編碼時m值加1</p><p><b>　　m++;</b></p><p><b>　　}</b></p><p>　　if(m==j)

38、 //當輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)</p><p><b>　　{</b></p><p>　　printf("%c",ht[i].data);</p><p>　　for(x=0;code[x-1]!='#';x++) //把

39、已經(jīng)使用過的code數(shù)組里的字符串刪除</p><p><b>　　{</b></p><p>　　code[x]=code[x+j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　

40、　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　int n=26,i;</p><p>　　char orz,back,flag=1;</p>

41、<p>　　char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',

42、9;Q','R','S','T','U','V','W','X','Y','Z'}; //初始化</p><p>　　int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,8

43、0,23,8,18,1,16}; //初始化</p><p>　　HTNode ht[M]; //建立結(jié)構(gòu)體</p><p>　　HCode hcd[N]; //建立結(jié)構(gòu)體</p><p>　　for (i=0;i<n;i++) //把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中<

44、/p><p><b>　　{</b></p><p>　　ht[i].data=str[i];</p><p>　　ht[i].weight=fnum[i];</p><p><b>　　}</b></p><p>　　while (flag) /

45、/菜單函數(shù)，當flag為0時跳出循環(huán)</p><p><b>　　{</b></p><p>　　printf("\n");</p><p>　　printf(" **************************************");</p><p>　　p

46、rintf("\n ** A---------------顯示編碼 **");</p><p>　　printf("\n ** B---------------進行編碼 **");</p><p>　　printf("\n ** C---------------進行譯碼 **");</p&

47、gt;<p>　　printf("\n ** D---------------退出 **\n");</p><p>　　printf(" ****************************************");</p><p>　　printf("\n");</p

48、><p>　　printf(" 請輸入選擇的編號:");</p><p>　　scanf("%c",&orz);</p><p>　　switch(orz)</p><p><b>　　{</b></p><p><b>　　ca

49、se 'a':</b></p><p><b>　　case 'A':</b></p><p>　　system("cls"); //清屏函數(shù)</p><p>　　CreateHT(ht,n);</p><p>

50、;　　CreateHCode(ht,hcd,n);</p><p>　　DispHCode(ht,hcd,n);</p><p>　　printf("\n按任意鍵返回...");</p><p><b>　　getch();</b></p><p>　　system("cls");

51、</p><p><b>　　break;</b></p><p><b>　　case 'b':</b></p><p><b>　　case 'B':</b></p><p>　　system("cls");</p&

52、gt;<p>　　printf("請輸入要進行編碼的字符串(以#結(jié)束):\n");</p><p>　　editHCode(ht,hcd,n);</p><p>　　printf("\n按任意鍵返回...");</p><p><b>　　getch();</b></p>&l

53、t;p>　　system("cls");</p><p><b>　　break;</b></p><p><b>　　case 'c':</b></p><p><b>　　case 'C':</b></p><p>

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

55、;);</p><p><b>　　getch();</b></p><p>　　system("cls");</p><p><b>　　break;</b></p><p><b>　　case 'd':</b></p>&

56、lt;p><b>　　case 'D':</b></p><p><b>　　flag=0;</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p><p>　　syst