數(shù)據(jù)結(jié)構(gòu)前綴編碼課程設(shè)計(jì)

1、<p>　　數(shù) 據(jù) 結(jié) 構(gòu)</p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　題 目： </p><p>　　專 業(yè)： </p><p>　　班 級(jí)：

2、 </p><p>　　學(xué) 號(hào)： </p><p>　　姓 名： </p><p>　　指導(dǎo)老師： </p>&

3、lt;p>　　時(shí) 間： </p><p>　　一、課程設(shè)計(jì)題目及所涉及知識(shí)點(diǎn)</p><p>　　設(shè)計(jì)題目是：“前綴編碼問題”。</p><p>　　所涉及的知識(shí)點(diǎn)主要是：</p><p>　　本課程設(shè)計(jì)利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼，前綴編碼顧名思義就是任意一字符的編碼

4、都不是另一個(gè)字符的編碼的前綴，主要難點(diǎn)在于如何根據(jù)輸入的字符和使用頻度構(gòu)造出最優(yōu)二叉樹，并根據(jù)構(gòu)造的最優(yōu)二叉樹輸出每個(gè)字符的編碼，這主要設(shè)計(jì)到對(duì)每個(gè)字符的權(quán)值進(jìn)行冒泡排序找出最小的兩個(gè)權(quán)值作為左右孩子結(jié)點(diǎn)，以他們的和作為父母結(jié)點(diǎn)，并把父母結(jié)點(diǎn)作為新的權(quán)值數(shù)重新排序，最終構(gòu)造出完整的哈夫曼樹，以根的左右路徑分別代表值“0”與“1”連續(xù)存儲(chǔ)，得到每個(gè)字符的編碼。</p><p>　　二、課程設(shè)計(jì)思路及算法描述<

5、/p><p>　　設(shè)計(jì)思路：通過構(gòu)造哈夫曼樹的結(jié)構(gòu)體定義一個(gè)哈夫曼樹組，對(duì)用戶輸入的字符以及使用頻率進(jìn)行存儲(chǔ)和初始化，然后對(duì)字符進(jìn)行編譯處理，通過構(gòu)造哈夫曼樹編譯出每個(gè)字符的編碼，然后對(duì)每個(gè)編碼進(jìn)行存儲(chǔ)并與字符相關(guān)聯(lián)，并輸出每個(gè)字符以及對(duì)應(yīng)的編碼。最終根據(jù)用戶選擇的功能進(jìn)行編碼和譯碼操作。</p><p>　　問題一：哈夫曼樹的表示。</p><p>　　設(shè)計(jì)哈夫曼樹的

6、結(jié)構(gòu)體，其中包含使用頻率（權(quán)重）、左孩子、右孩子、雙親和要編碼的字符。用這個(gè)結(jié)構(gòu)體定義個(gè)一個(gè)哈夫曼數(shù)組。</p><p>　　哈夫曼結(jié)構(gòu)體定義如下：</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int weight;</p><p>

7、;　　int lchild;</p><p>　　int rchild;</p><p>　　int parent;</p><p><b>　　char key;</b></p><p><b>　　}htnode;</b></p><p>　　typedef htnode

8、 hfmt[MAXLEN];</p><p>　　問題二：對(duì)輸入字符進(jìn)行編碼。</p><p>　　初始化哈夫曼樹，每個(gè)節(jié)點(diǎn)的孩子及雙親默認(rèn)值為-1，使用頻率為0。根據(jù)用戶選擇輸入字符個(gè)數(shù)n，以及n個(gè)字符和n個(gè)權(quán)值，構(gòu)造出哈夫曼樹，并顯示出每個(gè)字符及對(duì)應(yīng)編碼。</p><p>　　1.void creathfmt(hfmt t)//創(chuàng)建哈夫曼樹的函數(shù)</p&g

9、t;<p>　　2.void selectmin(hfmt t,int i,int *p1,int *p2)//選出兩個(gè)最小的字符權(quán)值</p><p>　　3.void phfmnode(hfmt t)//對(duì)字符進(jìn)行初始編碼</p><p>　　問題三：對(duì)用戶輸入的電文進(jìn)行編碼。</p><p>　　用戶輸入一連串原本輸入的字符構(gòu)成電文，電文長度在10

10、00字符以內(nèi)，由程序進(jìn)行編碼轉(zhuǎn)換。并輸出轉(zhuǎn)換后的編碼。</p><p>　　void encoding(hfmt t)//對(duì)用戶輸入的電文進(jìn)行編碼 </p><p><b>　　{ </b></p><p>　　char r[1000];//用來存儲(chǔ)輸入的字符串 </p><p><b>　　int i,j;&

11、lt;/b></p><p>　　printf("\n請(qǐng)輸入需要編碼的字符:");</p><p><b>　　gets(r);</b></p><p>　　printf("編碼結(jié)果為:"); </p><p>　　for(j=0;r[j]!='\0';j++

12、)</p><p>　　for(i=0;i<n;i++)</p><p>　　if(r[j]==t[i].key)</p><p>　　hfmtpath(t,i,j); </p><p>　　printf("\n");</p><p><b>　　}</b></p&

13、gt;<p>　　問題四：對(duì)用戶輸入的密文進(jìn)行譯碼。</p><p>　　用戶輸入一連串二進(jìn)制代碼字符構(gòu)成密文，電文長度在100個(gè)二進(jìn)制代碼以內(nèi)，由程序進(jìn)行編碼轉(zhuǎn)換。并輸出轉(zhuǎn)換后的譯碼。</p><p>　　void decoding(hfmt t)//對(duì)用戶輸入的密文進(jìn)行譯碼</p><p><b>　　{</b></p&

14、gt;<p>　　char r[100];</p><p>　　int i,j,len;</p><p>　　j=2*n-2;//j初始從樹的根節(jié)點(diǎn)開始</p><p>　　printf("\n請(qǐng)輸入需要譯碼的字符串:");</p><p><b>　　gets(r);</b></

15、p><p>　　len=strlen(r);</p><p>　　printf("譯碼的結(jié)果是:");</p><p>　　for(i=0;i<len;i++)</p><p><b>　　{</b></p><p>　　if(r[i]=='0')</p

16、><p><b>　　{</b></p><p>　　j=t[j].lchild;</p><p>　　if(t[j].lchild==-1)</p><p><b>　　{</b></p><p>　　printf("%c",t[j].key);</p

17、><p><b>　　j=2*n-2;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else if(r[i]=='1')</p><p><b>　　{</b&g

18、t;</p><p>　　j=t[j].rchild;</p><p>　　if(t[j].rchild==-1)</p><p><b>　　{</b></p><p>　　printf("%c",t[j].key);</p><p><b>　　j=2*n-2;&

19、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}<

20、;/b></p><p>　　三、課程設(shè)計(jì)中遇到的難點(diǎn)及解決辦法</p><p>　　在程序設(shè)計(jì)中遇到的問題主要是如何根據(jù)輸入的字符頻率構(gòu)造哈夫曼樹，這其中涉及到對(duì)哈夫曼樹的存儲(chǔ)，以及根據(jù)樹的左孩子路徑為“0”右孩子路徑“1”對(duì)字符進(jìn)行二級(jí)制編碼，在參考課文和網(wǎng)絡(luò)資源后進(jìn)行整理和加工，設(shè)計(jì)出了構(gòu)造哈夫曼樹的程序。由于事先不知道用戶要輸入幾個(gè)字符，所以無法判斷最終二進(jìn)制編碼的長度，通過

21、定義一個(gè)比較大的存儲(chǔ)空間存儲(chǔ)編碼。在對(duì)每個(gè)字符構(gòu)造出編碼后根據(jù)用戶選擇進(jìn)行編碼和譯碼，這其中遇到的難點(diǎn)主要是根據(jù)用戶輸入的信息進(jìn)行翻譯，特別是譯碼過程，主要難點(diǎn)的解決時(shí)上網(wǎng)百度和詢問老師解決的。</p><p><b>　　總結(jié)</b></p><p>　　通過這次課程設(shè)計(jì)，我對(duì)前綴編碼問題有了深刻的認(rèn)識(shí)，對(duì)哈夫曼樹的優(yōu)越性也有了深刻的了解，利用哈夫曼編碼可以極大的縮

22、短編碼長度，提高信息的傳輸時(shí)間，在社會(huì)的實(shí)際應(yīng)用時(shí)很廣泛的，同時(shí)通過程序設(shè)計(jì)中對(duì)哈夫曼樹的構(gòu)造，對(duì)我的編程思想有了很大的提高，我對(duì)數(shù)據(jù)結(jié)構(gòu)也有了更好的掌握，雖然距離完全的掌握每一個(gè)功能操作還有一定的差距，但是我相信通過不斷地學(xué)習(xí)和努力，我一定能做的更好更完善。</p><p>　　附錄—主要源程序代碼及運(yùn)行結(jié)果</p><p>　　#include <stdio.h></

23、p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　#define MAXLEN 100</p><p>　　typedef struct</p><p><b>　　{</b></p&g

24、t;<p>　　int weight;</p><p>　　int lchild;</p><p>　　int rchild;</p><p>　　int parent;</p><p><b>　　char key;</b></p><p><b>　　}htnode;&

25、lt;/b></p><p>　　typedef htnode hfmt[MAXLEN];</p><p><b>　　int n;</b></p><p>　　void selectmin(hfmt t,int i,int *p1,int *p2)//選中兩個(gè)權(quán)值最小的函數(shù) </p><p><b>　

26、　{</b></p><p>　　long min1=999999;</p><p>　　long min2=999999;</p><p><b>　　int j;</b></p><p>　　for(j=0;j<=i;j++)//選擇最小權(quán)值字符的下標(biāo)返回 </p><p>

27、　　if(t[j].parent==-1)</p><p>　　if(min1>t[j].weight)</p><p><b>　　{</b></p><p>　　min1=t[j].weight;</p><p><b>　　*p1=j;</b></p><p>&

28、lt;b>　　}</b></p><p>　　for(j=0;j<=i;j++)//選擇次小權(quán)值字符的下標(biāo)還回</p><p>　　if(t[j].parent==-1)</p><p>　　if(min2>t[j].weight&&j!=(*p1))</p><p><b>　　{&l

29、t;/b></p><p>　　min2=t[j].weight;</p><p><b>　　*p2=j;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void creathfmt(

30、hfmt t)//創(chuàng)建哈夫曼樹的函數(shù) </p><p><b>　　{</b></p><p>　　int i,w,p1,p2;</p><p>　　char k;//k表示獲取的字符</p><p>　　printf("\n");</p><p>　　printf("

31、;------------------------------------------------\n");</p><p>　　printf("*********************輸入?yún)^(qū)*********************\n");</p><p>　　printf("\n請(qǐng)輸入字符個(gè)數(shù)：");</p><

32、p>　　scanf("%d",&n);</p><p>　　getchar();</p><p>　　for(i=0;i<2*n-1;i++)//對(duì)結(jié)構(gòu)體進(jìn)行初始化 </p><p><b>　　{</b></p><p>　　t[i].weight=0;</p>&

33、lt;p>　　t[i].lchild=-1;</p><p>　　t[i].rchild=-1;</p><p>　　t[i].parent=-1;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　for(i=0

34、;i<n;i++)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入第%d個(gè)字符:",i+1);</p><p>　　scanf("%c",&k);</p><p>　　getchar();</p><p>　

35、　t[i].key=k;</p><p>　　printf("請(qǐng)輸入第%d個(gè)字符的權(quán)值:",i+1);</p><p>　　scanf("%d",&w);</p><p>　　getchar();</p><p>　　t[i].weight=w;</p><p>　　pr

36、intf("\n");</p><p><b>　　} </b></p><p>　　for(i=n;i<2*n-1;i++)</p><p><b>　　{</b></p><p>　　selectmin(t,i-1,&p1,&p2);</p>

37、<p>　　t[p1].parent=i;</p><p>　　t[p2].parent=i;</p><p>　　t[i].lchild=p1;</p><p>　　t[i].rchild=p2;</p><p>　　t[i].weight=t[p1].weight+t[p2].weight; </p><

38、p><b>　　}</b></p><p><b>　　}</b></p><p>　　void hfmtpath(hfmt t,int i,int j)//編碼的重要哈夫曼樹路徑遞歸算法 </p><p><b>　　{</b></p><p><b>　　i

39、nt a,b;</b></p><p><b>　　a=i;</b></p><p>　　b=j=t[i].parent;</p><p>　　if(t[j].parent!=-1) </p><p><b>　　{</b></p><p><b>　　

40、i=j;</b></p><p>　　hfmtpath(t,i,j);</p><p><b>　　}</b></p><p>　　if(t[b].lchild==a)</p><p>　　printf("0");</p><p><b>　　else&l

41、t;/b></p><p>　　printf("1");</p><p><b>　　}</b></p><p>　　void phfmnode(hfmt t)//對(duì)字符進(jìn)行初始編碼</p><p><b>　　{</b></p><p><b

42、>　　int i,j;</b></p><p>　　printf("------------------------------------------------\n");</p><p>　　printf("*******************哈夫曼編碼*******************\n");</p>&

43、lt;p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p><b>　　j=0;</b></p><p>　　printf("\n");</p><p>　　printf("\t\t%c\t\t",t[i

44、].key,t[i].weight);</p><p>　　hfmtpath(t,i,j);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void encoding(hfmt t)//對(duì)用戶輸入的電文進(jìn)行編碼 </p><p

45、><b>　　{ </b></p><p>　　char r[1000];//用來存儲(chǔ)輸入的字符串 </p><p><b>　　int i,j;</b></p><p>　　printf("\n請(qǐng)輸入需要編碼的字符:");</p><p><b>　　gets(

46、r);</b></p><p>　　printf("編碼結(jié)果為:"); </p><p>　　for(j=0;r[j]!='\0';j++)</p><p>　　for(i=0;i<n;i++)</p><p>　　if(r[j]==t[i].key)</p><p&g

47、t;　　hfmtpath(t,i,j); </p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void decoding(hfmt t)//對(duì)用戶輸入的密文進(jìn)行譯碼</p><p><b>　　{</b></p>

48、;<p>　　char r[100];</p><p>　　int i,j,len;</p><p>　　j=2*n-2;//j初始從樹的根節(jié)點(diǎn)開始</p><p>　　printf("\n請(qǐng)輸入需要譯碼的字符串:");</p><p><b>　　gets(r);</b></p&

49、gt;<p>　　len=strlen(r);</p><p>　　printf("譯碼的結(jié)果是:");</p><p>　　for(i=0;i<len;i++)</p><p><b>　　{</b></p><p>　　if(r[i]=='0')</p&g

50、t;<p><b>　　{</b></p><p>　　j=t[j].lchild;</p><p>　　if(t[j].lchild==-1)</p><p><b>　　{</b></p><p>　　printf("%c",t[j].key);</p&g

51、t;<p><b>　　j=2*n-2;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else if(r[i]=='1')</p><p><b>　　{</b>

52、</p><p>　　j=t[j].rchild;</p><p>　　if(t[j].rchild==-1)</p><p><b>　　{</b></p><p>　　printf("%c",t[j].key);</p><p><b>　　j=2*n-2;<

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

54、b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　hfmt ht;</b></p><p>　　char flag;</p><p>　　printf("-------------------

55、-----------------------------\n");</p><p>　　printf(" **********說明********** \n"); </p><p>　　printf(" * 11級(jí)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) * \n");</p><p>　　prin

56、tf(" * 哈夫曼編碼 * \n");</p><p>　　printf(" * 科學(xué)與技術(shù)專業(yè) 邵帥 * \n");</p><p>　　printf(" ************************ \n"); </p>&l

57、t;p>　　creathfmt(ht);//創(chuàng)建哈夫曼樹的函數(shù)</p><p>　　phfmnode(ht); //對(duì)字符進(jìn)行初始編碼 </p><p>　　printf("\n------------------------------------------------\n");</p><p><b>　　do{</b

58、></p><p>　　printf("********************功能選擇********************\n");</p><p>　　printf("【1】編碼\t【2】譯碼\t【0】退出\n");</p><p>　　printf("您的選擇：");</p>

59、<p>　　flag=getchar();</p><p>　　getchar();</p><p>　　if(flag=='1')</p><p>　　encoding(ht);</p><p>　　else if(flag=='2')</p><p>　　decoding(

60、ht);</p><p>　　else if(flag=='0')</p><p><b>　　return;</b></p><p><b>　　else</b></p><p>　　printf("您的輸入有誤，請(qǐng)重新輸入。\n"); </p>