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

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

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

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

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

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

6、重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程中遇到問(wèn)題，這畢竟獨(dú)立做的，難免會(huì)遇到過(guò)各種各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，比如說(shuō)結(jié)構(gòu)體……通過(guò)這次課程設(shè)計(jì)之后，一定把以前所學(xué)過(guò)的知識(shí)重新溫故。我表示感謝！同時(shí)，對(duì)給過(guò)我?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é)點(diǎn)數(shù)</p><p>　　#define M 2*N-1 //用M表示節(jié)點(diǎn)總數(shù) 當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)

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

10、; //權(quán)值</p><p>　　int parent; //雙親結(jié)點(diǎn)</p><p>　　int lchild; //左孩子結(jié)點(diǎn)</p><p>　　int rchild; //右孩子結(jié)點(diǎn)</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開(kāi)始讀cd中的哈夫曼碼</p><p><b>　　}HCode;</b></p><p>　　void CreateHT(HTNode ht[],int n) //調(diào)用輸入的數(shù)組ht[],和節(jié)點(diǎn)數(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é)點(diǎn)的相關(guān)域置初值-1</p><p>　　fo

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

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

16、b>　　{</b></p><p>　　if (ht[k].weight<min1) //若權(quán)值小于最小的左節(jié)點(diǎn)的權(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; //兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i</p><p>　

19、　ht[i].weight=ht[lnode].weight+ht[rnode].weight; //兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和</p><p>　　ht[i].lchild=lnode;ht[i].rchild=rnode; //父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)</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ù)哈夫曼樹(shù)求哈夫曼編碼</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) //循序直到樹(shù)根結(jié)點(diǎn)結(jié)束循環(huán)</p><p><b>　　{</b></p><p>　　if (ht[f].lchild==c) //處理左孩子結(jié)點(diǎn)</p><p>　　

23、hc.cd[hc.start--]='0';</p><p>　　else //處理右孩子結(jié)點(diǎn)</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[]中最開(kāi)始字符</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); //把要進(jìn)行編碼的字符串存入string數(shù)組中</p><p>　　printf("\n輸出編碼結(jié)果:\n");</p><p>　　for (i=0;string[i]!='#';i++) //#為終止標(biāo)志</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)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼</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; //輸出完成后跳出當(dāng)前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); //把要進(jìn)行譯碼的字符串存入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為想同編碼個(gè)數(shù)的計(jì)數(shù)器</p><p>　　for (k=hcd[i].start,j=0;k<=n;k++,j++) //j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)</p><p><b>　　{&l

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

38、 //當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的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)使用過(guò)的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ù)，當(dāng)flag為0時(shí)跳出循環(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---------------進(jìn)行編碼 **");</p><p>　　printf("\n ** C---------------進(jìn)行譯碼 **");</p&

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

48、><p>　　printf(" 請(qǐng)輸入選擇的編號(hào):");</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("請(qǐng)輸入要進(jìn)行編碼的字符串(以#結(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("請(qǐng)輸入編碼(以#結(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