數(shù)據(jù)結構課程設計--哈夫曼樹結構設計

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

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

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

文檔簡介

1、　　摘要　　利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。為實現(xiàn)這一功能可以利用現(xiàn)有數(shù)據(jù)結構及相關課程的知識編一個這樣的程序。　　需求分析

2、;　　1 建立哈夫曼樹。根據(jù)哈夫曼編碼技術，可以將已經(jīng)給出的字母的使用頻率建立一個哈夫曼樹，即以二叉樹的形式將英文字母和空格存儲。　　2 編碼。利用二叉樹的遍歷知識，左孩子用“0”表示，右孩子用“1”表示，將輸入的一組英文句子進行編碼。　　3測試和輸出。程序要求的測試的英文句子是：“knowledge is po

3、wer”，輸出每一個字母然后給出相應的哈夫曼編碼。本程序輸入字母以“#”結束。　　4譯碼。本程序要求對已編碼的數(shù)字能夠給以反編碼。　　詳細設計　　1 哈夫曼樹結構體設計　　對一個結點如果父親結點和兩個孩子結點知道那么這個結點就定位了，

4、考慮到葉子結點要有相應的值及相應的權重，結構體設計如下。　　typedef struct //定義哈夫曼樹的結點結構　　{　　char c; //結點的值　　double weight;//結點的權重

5、　　int parent; //雙親結點　　int lchild; //左孩子結點　　int rchild; //右孩子結點　　}HTNode;　　2構造哈夫曼樹設計<

6、;/p>　　void CreateHT(HTNode ht[],int n)//建立哈夫曼樹　　{　　int i,k,lnode,rnode;　　double min1,min2;　　for(i=0;i&l

7、t;2*n-1;i++) //所有結點的相關域置初值-1　　{　　ht[i].parent=ht[i].lchild=ht[i].rchild=-1;　　}　　for(i=n;i<2*n-1

8、;i++)　　{　　min1=min2=32767; //min1和min2分別存放最小的兩個權重　　lnode=rnode=-1; //lnode和rnode為最小權重的兩個結點位置　　for(k=0;k<=i-1;k++)

9、　　{　　if(ht[k].parent==-1) //只在尚未構造哈夫曼樹的結點中查找　　{　　if(ht[k].weight<min1)<

10、b>　　{　　min2=min1;　　rnode=lnode;　　min1=ht[k].weight;　　lnode=k;　　}

11、　　else if(ht[k].weight<min2)　　{　　min2=ht[k].weight;　　rnode=k;　　}&

12、lt;/b>　　}　　}　　ht[lnode].parent=i;　　ht[rnode].parent=i;　　ht[i].weight=ht[ln

13、ode].weight+ht[rnode].weight;　　ht[i].lchild=lnode;　　ht[i].rchild=rnode;　　}　　}

14、　　3構造哈夫曼編碼設計　　void CreateHCode(HTNode ht[],HCode hcd[],int n) //構造哈夫曼碼,n為哈夫曼樹的葉子結點數(shù)目。　　{　　int i,f,c;　　HCode

15、hc;　　for(i=0;i<n;i++)　　{　　hc.start=N-1; 　　c=i;　　f=ht[i].parent;

16、　　while(f!=-1)　　{　　if(ht[f].lchild==c)　　{　　hc.cd[hc.start--]='0';<

17、/p>　　}　　else　　{　　hc.cd[hc.start--]='1';　　}</b

18、>　　c=f;　　f=ht[f].parent;　　}　　hc.start++;　　hcd[i]=hc;&

19、lt;b>　　}　　}　　4主函數(shù)設計　　調試分析　　在調試過程中主要遇到如下問題　　1

20、在調試過程中編碼的輸出出現(xiàn)了問題，在沒有辦法的情況下借助了流程圖，最終使問題得到解決。　　2 在測試完字符后本以為已經(jīng)完成了程序編碼，經(jīng)過老師的指導我發(fā)現(xiàn)一個很嚴重的問題，沒有反編碼。經(jīng)過討論并查閱了相關資料最終得以攻破。　　3 剛開始程序的界面沒有提示信息，測試的英文字母在主函數(shù)中。也就是說程序的靈活性得到的了限制，在意識到這一問題后經(jīng)過努力得到了改進

21、。　　新得體會：　　經(jīng)過數(shù)據(jù)結構課程設計，對相關知識有了新的認識，提升了興趣。使我感觸最深的是在寫程序時時刻不忘畫流程圖，可以使你對真?zhèn)€程序或分支程序有個全面的把握。做課程設計時的細心，耐心很重要。　　測試結果&l

22、t;p>　　第一步編譯鏈接，屏幕上會提示“請輸入要編碼的英文字符，以‘#’結束：”。　　第二步輸入測試字符串“knowledge is power#”。　　第三步回車，屏幕上顯示：　　你輸入的句子各字符的哈夫曼編碼為：　　k:0111110

23、　　n:0110　　o:1001　　w:0111111　　l:0001<

24、;p>　　e:001　　d:01011　　g:110111　　e:001　　:1111</

25、b>　　i:1100　　s:0100　　:1111　　p:10000&l

26、t;b>　　o:1001　　w:0111111　　e:001　　r:1011　　輸入的反編碼為：011111001101001011

27、111100010010　　1011110111001111111000100111110000100101111110011011　　英文字符為：knowledge is power　　Press any key to continue　　附錄<

28、/b>　　#include <iostream>　　using namespace std;　　typedef struct //定義哈夫曼樹的結點結構　　{　　char

29、c; //結點的值　　double weight;//結點的權重　　int parent; //雙親結點　　int lchild; //左孩子結點　　int rchild; //右孩子結點　　}HT

30、Node;　　const int N=10; //定義存放哈夫曼編碼的數(shù)組長度　　typedef struct //定義存放哈夫曼編碼的結點　　{　　char cd[N]; //存放當前結點的哈夫曼碼的數(shù)組&l

31、t;/p>　　int start; //哈夫曼碼的起始位置　　}HCode;　　void CreateHT(HTNode ht[],int n)//建立哈夫曼樹　　{

32、　　int i,k,lnode,rnode;　　double min1,min2;　　for(i=0;i<2*n-1;i++) //所有結點的相關域置初值-1　　{　　ht[i].parent=ht[i].lchild=ht[i

33、].rchild=-1;　　}　　for(i=n;i<2*n-1;i++)　　{　　min1=min2=32767; //min1和min2分別存放最小的兩個權重&l

34、t;p>　　lnode=rnode=-1; //lnode和rnode為最小權重的兩個結點位置　　for(k=0;k<=i-1;k++)　　{　　if(ht[k].parent==-1) //只在尚未構造哈夫曼樹的結點中查找<p&g

35、t;　　{　　if(ht[k].weight<min1)　　{　　min2=min1;　　rnode=lnode;　　min1=ht[k].weig

36、ht;　　lnode=k;　　}　　else if(ht[k].weight<min2)　　{　　min2=h

37、t[k].weight;　　rnode=k;　　}　　}　　}　　ht[lno

38、de].parent=i;　　ht[rnode].parent=i;　　ht[i].weight=ht[lnode].weight+ht[rnode].weight;　　ht[i].lchild=lnode;　　ht[i].rchild=rnode;

39、　　}　　}　　void CreateHCode(HTNode ht[],HCode hcd[],int n) //構造哈夫曼碼,n為哈夫曼樹的葉子結點數(shù)目。　　{</p&g

40、t;　　int i,f,c;　　HCode hc;　　for(i=0;i<n;i++)　　{　　hc.start=N-1;

41、　　c=i;　　f=ht[i].parent;　　while(f!=-1)　　{　　if(ht[f].lchild==c)　　{<

42、/b>　　hc.cd[hc.start--]='0';　　}　　else　　{　　hc.cd[

43、hc.start--]='1';　　}　　c=f;　　f=ht[f].parent;　　}　　hc.

44、start++;　　hcd[i]=hc;　　}　　}　　void main()　　{ char a[50];

45、;　　HTNode HT[53]; /*建立53個結點(27個葉子結點的哈夫曼樹共有2*27-1個結點)*/　　HT[0].c='a';　　HT[0].weight=0.0856;　　HT[1].c='b';　　HT[1].we

46、ight=0.0212;　　HT[2].c='c';　　HT[2].weight=0.0474;　　HT[3].c='d';　　HT[3].weight=0.0313;　　HT[4].c='

47、e';　　HT[4].weight=0.1142;　　HT[5].c='f';　　HT[5].weight=0.0147;　　HT[6].c='g';　　HT[6].weight=0.023

48、0;　　HT[7].c='h';　　HT[7].weight=0.0276;　　HT[8].c='i';　　HT[8].weight=0.0794;　　HT[9].c='j';<

49、;/p>　　HT[9].weight=0.0015;　　HT[10].c='k';　　HT[10].weight=0.0084;　　HT[11].c='l';　　HT[11].weight=0.0552;<

50、/p>　　HT[12].c='m';　　HT[12].weight=0.0322;　　HT[13].c='n';　　HT[13].weight=0.0641;　　HT[14].c='o';<

51、/p>　　HT[14].weight=0.0712;　　HT[15].c='p';　　HT[15].weight=0.0327;　　HT[16].c='q';　　HT[16].weight=0.0023;<

52、/p>　　HT[17].c='r';　　HT[17].weight=0.0751;　　HT[18].c='s';　　HT[18].weight=0.0555;　　HT[19].c='t';<

53、/p>　　HT[19].weight=0.0746;　　HT[20].c='u';　　HT[20].weight=0.0366;　　HT[21].c='v';　　HT[21].weight=0.0107;<

54、;/p>　　HT[22].c='w';　　HT[22].weight=0.0094;　　HT[23].c='x';　　HT[23].weight=0.0035;　　HT[24].c='y';<

55、;/p>　　HT[24].weight=0.0200;　　HT[25].c='z';　　HT[25].weight=0.0024;　　HT[26].c=' ';　　HT[26].weight=0.1003;<

56、;/p>　　CreateHT (HT,27); /*建立哈夫曼樹*/　　HCode hc[27]; /*哈夫曼編碼的結點數(shù)組*/　　CreateHCode(HT,hc,27);/*構造哈夫曼編碼*/　　cout<<"請輸入要編碼的英文字

57、符,以“#”結束:"<<endl;　　for(int i=0;i<50;i++)　　{　　cin>>a[i];　　if(a[i]=='#')break;

58、　　}　　cout<<endl<<"你輸入的句子各字符的哈夫曼編碼為:"<<endl;　　for(int n=0;n<i;n++)　　{

59、　　for(int j=0;j<27;j++)　　{　　if(a[n]==HT[j].c)　　{　　break;

60、;　　}　　}　　cout<<HT[j].c<<": ";　　for(int k=hc[j].start;k<N;k++)

61、　cout<<hc[j].cd[k];　　cout<<endl;　　}　　char *s1="0111110011010010111111000100101011110111001111111000100111110000100101111

62、110011011";　　int m=0;　　cout<<"輸入的反編碼是：0111110011010010111111000100101011110111001111111000100111110000100101111110011011"<<endl;<

63、/p>　　cout<<"英文字符為："<<endl;　　while (HT[m].parent!=-1)　　{ 　　m++;

64、　　}　　int f=m;　　int j=-1;　　while(j<200)　　{ if(HT[f].lchild!=-1)&l

65、t;p>　　{ j++;　　if(s1[j]=='0')　　{ f=HT[f].lchild;}　　else　　{ f=HT[f].rchild;}

66、　　}　　else　　{ cout<<HT[f].c;　　f=m; 　　}</p

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

溫馨提示

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

數(shù)據(jù)結構課程設計--哈夫曼樹結構設計

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計--哈夫曼樹結構設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載