數據結構課程設計---哈弗曼編碼譯碼

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

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

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

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

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

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

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

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

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

10、; //權值</p><p>　　int parent; //雙親結點</p><p>　　int lchild; //左孩子結點</p><p>　　int rchild; //右孩子結點</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) //調用輸入的數組ht[],和節(jié)點數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; //所有結點的相關域置初值-1</p><p>　　fo

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

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

16、b>　　{</b></p><p>　　if (ht[k].weight<min1) //若權值小于最小的左節(jié)點的權值</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é)點權值為兩個最小節(jié)點權值之和</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++) //根據哈夫曼樹求哈夫曼編碼</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) //循序直到樹根結點結束循環(huán)</p><p><b>　　{</b></p><p>　　if (ht[f].lchild==c) //處理左孩子結點</p><p>　　

23、hc.cd[hc.start--]='0';</p><p>　　else //處理右孩子結點</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中的所有數據，即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中數據的編碼</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) //編碼函數</p><p><b>　　{</b></p><p>　　char string[MAXSIZE]; </p><p>　　int i,j,k;</p><p>　　sca

30、nf("%s",string); //把要進行編碼的字符串存入string數組中</p><p>　　printf("\n輸出編碼結果:\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) //譯碼函數</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數組中</p><p>　　while(code[0]!='#')</p><p>　　for (i=0;i<n;i++)</p><

36、p><b>　　{</b></p><p>　　m=0; //m為想同編碼個數的計數器</p><p>　　for (k=hcd[i].start,j=0;k<=n;k++,j++) //j為記錄所存儲這個字符的編碼個數</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、 //當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據</p><p><b>　　{</b></p><p>　　printf("%c",ht[i].data);</p><p>　　for(x=0;code[x-1]!='#';x++) //把

39、已經使用過的code數組里的字符串刪除</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]; //建立結構體</p><p>　　HCode hcd[N]; //建立結構體</p><p>　　for (i=0;i<n;i++) //把初始化的數據存入ht結構體中<

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、/菜單函數，當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"); //清屏函數</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("請輸入要進行編碼的字符串(以#結束):\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("請輸入編碼(以#結束):\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