數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼樹結(jié)構(gòu)設(shè)計(jì)

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

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

4、考慮到葉子結(jié)點(diǎn)要有相應(yīng)的值及相應(yīng)的權(quán)重，結(jié)構(gòu)體設(shè)計(jì)如下。　　typedef struct //定義哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)　　{　　char c; //結(jié)點(diǎn)的值　　double weight;//結(jié)點(diǎn)的權(quán)重

5、　　int parent; //雙親結(jié)點(diǎn)　　int lchild; //左孩子結(jié)點(diǎn)　　int rchild; //右孩子結(jié)點(diǎn)　　}HTNode;　　2構(gòu)造哈夫曼樹設(shè)計(jì)<

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++) //所有結(jié)點(diǎn)的相關(guān)域置初值-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分別存放最小的兩個(gè)權(quán)重　　lnode=rnode=-1; //lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置　　for(k=0;k<=i-1;k++)

9、　　{　　if(ht[k].parent==-1) //只在尚未構(gòu)造哈夫曼樹的結(jié)點(diǎn)中查找　　{　　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構(gòu)造哈夫曼編碼設(shè)計(jì)　　void CreateHCode(HTNode ht[],HCode hcd[],int n) //構(gòu)造哈夫曼碼,n為哈夫曼樹的葉子結(jié)點(diǎ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ù)設(shè)計(jì)　　調(diào)試分析　　在調(diào)試過程中主要遇到如下問題　　1

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

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

22、t;p>　　第一步編譯鏈接，屏幕上會(huì)提示“請輸入要編碼的英文字符，以‘#’結(jié)束：”。　　第二步輸入測試字符串“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 //定義哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)　　{　　char

29、c; //結(jié)點(diǎn)的值　　double weight;//結(jié)點(diǎn)的權(quán)重　　int parent; //雙親結(jié)點(diǎn)　　int lchild; //左孩子結(jié)點(diǎn)　　int rchild; //右孩子結(jié)點(diǎn)　　}HT

30、Node;　　const int N=10; //定義存放哈夫曼編碼的數(shù)組長度　　typedef struct //定義存放哈夫曼編碼的結(jié)點(diǎn)　　{　　char cd[N]; //存放當(dāng)前結(jié)點(diǎ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++) //所有結(jié)點(diǎn)的相關(guān)域置初值-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分別存放最小的兩個(gè)權(quán)重&l

34、t;p>　　lnode=rnode=-1; //lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置　　for(k=0;k<=i-1;k++)　　{　　if(ht[k].parent==-1) //只在尚未構(gòu)造哈夫曼樹的結(jié)點(diǎn)中查找<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) //構(gòu)造哈夫曼碼,n為哈夫曼樹的葉子結(jié)點(diǎ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個(gè)結(jié)點(diǎn)(27個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2*27-1個(gè)結(jié)點(diǎn))*/　　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]; /*哈夫曼編碼的結(jié)點(diǎn)數(shù)組*/　　CreateHCode(HT,hc,27);/*構(gòu)造哈夫曼編碼*/　　cout<<"請輸入要編碼的英文字

57、符,以“#”結(jié)束:"<<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è)設(shè)計(jì)

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼樹結(jié)構(gòu)設(shè)計(jì)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼樹結(jié)構(gòu)設(shè)計(jì)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載