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

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)》</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p><b>　　計(jì)算機(jī)與信息工程系</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)評(píng)閱表</p><p><b>　　引言</b></

2、p><p>　　課程意義：《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性很強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課，每個(gè)學(xué)生必須在學(xué)習(xí)結(jié)束時(shí)完成一個(gè)較綜合的實(shí)驗(yàn)。通過(guò)本次哈夫曼編碼的課程設(shè)計(jì)，可以加深在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及實(shí)現(xiàn)等方面加深對(duì)課程基礎(chǔ)內(nèi)容的理解，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。</p><p>　　項(xiàng)目意義：利用哈夫曼樹編制哈夫曼編碼在數(shù)據(jù)通訊中有廣泛的

3、應(yīng)用。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。</p><p><b>　　二、設(shè)計(jì)過(guò)程</b></p><p><b>　　1.設(shè)計(jì)思想：</b></p><p>　　實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分：</p><p><b>　　1.構(gòu)造哈夫曼樹

4、。</b></p><p>　　2.在哈夫曼樹上求葉子結(jié)點(diǎn)的編碼。（在算法中設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffmanCode來(lái)存放各字符的哈夫曼編碼信息。）</p><p><b>　　2.功能實(shí)現(xiàn)：</b></p><p>　　實(shí)現(xiàn)哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中從葉子節(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根節(jié)點(diǎn)，得到一位哈夫曼碼值，由

5、于一個(gè)字符的哈夫曼編碼是從根節(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑上各分支所組成的0，1序列，而在建立的哈夫曼樹中先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼，所求得的0，1序列是所需編碼的倒序，之后再將其倒置即可。</p><p><b>　　3.流程圖：</b></p><p><b>　　↓</b></p>

6、<p><b>　　↓</b></p><p><b>　　↓</b></p><p><b>　　↓</b></p><p><b>　　↓</b></p><p><b>　　三、測(cè)試及運(yùn)行結(jié)果</b></p>

7、;<p>　?、牛幾g中常見(jiàn)錯(cuò)誤：</p><p><b>　　1.字符丟失</b></p><p>　　①.我們?cè)诔绦虻木幾g過(guò)程中最有可能犯的錯(cuò)誤就是字符丟失，比如圖中所示：missing ‘;’ before‘}’；</p><p>　?、?這時(shí)我們用鼠標(biāo)雙擊上述錯(cuò)誤，編程界面就會(huì)出現(xiàn)一個(gè)如上圖所示的小光標(biāo)，意思就是在這個(gè)‘}

8、’前面丟失了一個(gè)‘;’，我們根據(jù)這個(gè)提示來(lái)檢查很快會(huì)發(fā)現(xiàn)在‘}’上一行的if語(yǔ)句的句尾丟失了‘;’，然后我們將錯(cuò)誤改正。</p><p>　?、?改正完成后我們就會(huì)看到如上圖所示的界面，這就表示錯(cuò)誤已改正，程序可運(yùn)行。</p><p><b>　　2.字母大小寫</b></p><p><b>　　→</b></p&

9、gt;<p>　　有時(shí)我們?cè)诔绦蚓幾g過(guò)程中并未發(fā)現(xiàn)錯(cuò)誤，但是一點(diǎn)運(yùn)行按鈕，就會(huì)顯示有一個(gè)錯(cuò)誤，這很有可能是字母的大小寫問(wèn)題。如上圖；</p><p>　　我們找到錯(cuò)誤提示，根據(jù)提示我們知道錯(cuò)誤出在“CrtHuffmantree”。然后我們回到源程序檢查；</p><p>　　通過(guò)仔細(xì)的檢查，我們會(huì)發(fā)現(xiàn)如上圖所示的語(yǔ)句，在這個(gè)語(yǔ)句中，“CrtHuffmantree”讓我們錯(cuò)打成

10、“crtHuffmantree”，改正后方可運(yùn)行。</p><p><b>　?、疲\(yùn)行結(jié)果演示</b></p><p>　　1.編譯完成后來(lái)到運(yùn)行界面，首先我們先確定字符n的個(gè)數(shù)，例如：6個(gè)，這時(shí)，輸入“6”，按回車鍵；</p><p>　　2.然后我們依次輸入這6個(gè)字符的權(quán)值。例如我們給定的這六個(gè)權(quán)值依次為2，4，6，8，10，12.那么就

11、先輸入2，按回車；然后輸入4，按回車；接著輸入6，按回車，依此類推，直到輸入12，按回車；</p><p>　　3.這樣運(yùn)行的結(jié)果就出來(lái)了。</p><p><b>　　四、總結(jié)</b></p><p>　　時(shí)光荏苒，轉(zhuǎn)瞬間這個(gè)學(xué)期數(shù)據(jù)結(jié)構(gòu)的課程結(jié)束了，雖然我對(duì)上學(xué)期的C語(yǔ)言和本學(xué)期的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的都不是很透徹，但是通過(guò)一個(gè)學(xué)期的學(xué)習(xí)仍然讓我感

12、到受益匪淺。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象 ，以及他們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，是計(jì)算機(jī)專業(yè)的核心課程。它作為一門難學(xué)難懂的學(xué)科，一門計(jì)算機(jī)等級(jí)考試必考的學(xué)科，學(xué)好它是至關(guān)重要的。</p><p>　　為了更加透徹的學(xué)習(xí)好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，并將已掌握的知識(shí)學(xué)以致用，在本學(xué)期末，我們進(jìn)行了為期一周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，通過(guò)此次課程設(shè)計(jì)，讓我更加扎

13、實(shí)的掌握了有關(guān)數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)。在設(shè)計(jì)過(guò)程中雖然我遇到了很多的問(wèn)題與困難，但是通過(guò)老師的指導(dǎo)，向同學(xué)們請(qǐng)教，以及自己的思考，最后終于找到了原因的所在，并得到了順利的解決。也暴露了前期我在這方面知識(shí)的欠缺以及經(jīng)驗(yàn)的不足。實(shí)踐出真知，通過(guò)親自動(dòng)手制作，使我們掌握的知識(shí)不再是紙上談兵。</p><p>　　課程設(shè)計(jì)誠(chéng)然是一門專業(yè)課，給我很多專業(yè)知識(shí)以及專業(yè)技能上的提升，同時(shí)又是一門講道課，一門辯思課，給了我許多道，給

14、了我很多思，給了我莫大的空間。同時(shí)，設(shè)計(jì)讓我感觸很深。使我對(duì)抽象的理論有了具體的認(rèn)識(shí)。</p><p>　　我認(rèn)為，在這學(xué)期的實(shí)驗(yàn)中，不僅培養(yǎng)了獨(dú)立思考、動(dòng)手操作的能力，在各種其它能力上也都有了提高。更重要的是，在實(shí)驗(yàn)課上，我們學(xué)會(huì)了很多學(xué)習(xí)的方法。這是日后最實(shí)用的，以后我們還要面對(duì)許多社會(huì)的挑戰(zhàn)，只有不斷的學(xué)習(xí)、實(shí)踐，再學(xué)習(xí)、再實(shí)踐。才能得到最后的勝利。以后，不管有多苦，我想我們都能變苦為樂(lè)，找尋有趣的事情，發(fā)

15、現(xiàn)其中珍貴的事情。就像中國(guó)提倡的艱苦奮斗一樣，我們都可以在實(shí)驗(yàn)結(jié)束之后變的更加成熟，學(xué)會(huì)面對(duì)需要面對(duì)的事情。</p><p>　　回顧起此課程設(shè)計(jì)，至今我仍感慨頗多，從理論到實(shí)踐，在這段日子里，可以說(shuō)得是苦多于甜，但是可以學(xué)到很多很多的東西，同時(shí)不僅可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書本上所沒(méi)有學(xué)到過(guò)的知識(shí)。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論

16、知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。</p><p>　　在今后社會(huì)的發(fā)展和學(xué)習(xí)實(shí)踐過(guò)程中，一定要不懈努力，不能遇到問(wèn)題就想到要退縮，一定要不厭其煩的發(fā)現(xiàn)問(wèn)題所在，然后一一進(jìn)行解決，只有這樣，才能成功的做成想做的事，才能在今后的道路上劈荊斬棘，而不是知難而退，那樣永遠(yuǎn)不可能收獲成功，收獲喜悅，也永遠(yuǎn)不可能得到社會(huì)及他人對(duì)你的認(rèn)可！</p&g

17、t;<p><b>　　五、參考文獻(xiàn)</b></p><p><b>　　書籍：</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）》；出版社：中國(guó)水利水電出版社；主編：馬秋菊；</p><p>　　出版日期：2006年9月。</p><p>　　《大話數(shù)據(jù)結(jié)構(gòu)》；出版社：清華大學(xué)出

18、版社；主編：程杰；出版日期：2011年6月。</p><p>　　《大話設(shè)計(jì)模式》;出版社：清華大學(xué)出版社；主編：程杰；出版日期：2007年12月。</p><p><b>　　六、附錄</b></p><p>　　#include <stdio.h></p><p>　　#include <stdli

19、b.h></p><p>　　#include <string.h></p><p>　　typedef char *HuffmanCode; //動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼</p><p>　　typedef struct</p><p><b>　　{</b></p><p&

20、gt;　　unsigned int weight; //用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值</p><p>　　unsigned int parent,LChild,RChild; //指向雙親、孩子結(jié)點(diǎn)的指針</p><p>　　} HTNode, *HuffmanTree; //動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹</p><p>　　//選擇兩個(gè)parent為0，且weigh

21、t最小的結(jié)點(diǎn)s1和s2</p><p>　　void Select(HuffmanTree *ht,int n,int *s1,int *s2){</p><p>　　int i,min;</p><p>　　for(i=1; i<=n; i++){</p><p>　　if((*ht)[i].parent==0){</p>

22、<p><b>　　min=i;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1; i<=n; i++){&l

23、t;/p><p>　　if((*ht)[i].parent==0) {</p><p>　　if((*ht)[i].weight<(*ht)[min].weight)</p><p><b>　　min=i;</b></p><p><b>　　}</b></p><p>

24、;<b>　　}</b></p><p><b>　　*s1=min;</b></p><p>　　for(i=1; i<=n; i++){</p><p>　　if((*ht)[i].parent==0 && i!=(*s1)){</p><p><b>　　min

25、=i;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1; i<=n; i++){</p><p>　　if((

26、*ht)[i].parent==0 && i!=(*s1)){</p><p>　　if((*ht)[i].weight<(*ht)[min].weight) min=i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><

27、b>　　*s2=min;</b></p><p><b>　　}</b></p><p>　　//構(gòu)造哈夫曼樹ht。w存放已知的n個(gè)權(quán)值</p><p>　　void CrtHuffmanTree(HuffmanTree *ht,int *w,int n){</p><p>　　int m,i,s1,s

28、2;</p><p><b>　　m=2*n-1;</b></p><p>　　*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));</p><p>　　for(i=1; i<=n; i++) //1--n號(hào)存放葉子結(jié)點(diǎn)，初始化</p><p><b>　　{&l

29、t;/b></p><p>　　(*ht)[i].weight=w[i];</p><p>　　(*ht)[i].LChild=0;</p><p>　　(*ht)[i].parent=0;</p><p>　　(*ht)[i].RChild=0;</p><p><b>　　}</b>&l

30、t;/p><p>　　for(i=n+1; i<=m; i++) {</p><p>　　(*ht)[i].weight=0;</p><p>　　(*ht)[i].LChild=0;</p><p>　　(*ht)[i].parent=0;</p><p>　　(*ht)[i].RChild=0;</p>

31、;<p>　　} //非葉子結(jié)點(diǎn)初始化</p><p>　　printf("\n哈夫曼樹如下: \n");</p><p>　　for(i=n+1; i<=m; i++) //創(chuàng)建非葉子結(jié)點(diǎn)，建哈夫曼樹</p><p>　　{ //在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個(gè)parent為0</p>

32、<p>　　//且weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給s1、s2</p><p>　　Select(ht,i-1,&s1,&s2);</p><p>　　(*ht)[s1].parent=i;</p><p>　　(*ht)[s2].parent=i;</p><p>　　(*ht)[i].LChild=s1

33、;</p><p>　　(*ht)[i].RChild=s2;</p><p>　　(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;</p><p>　　printf("\n%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].wei

34、ght);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　} //哈夫曼樹建立完畢</p><p>　　//從葉子結(jié)點(diǎn)到根，逆向求每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼</p><p>　　void CrtHuffmanCod

35、e(HuffmanTree *ht, HuffmanCode *hc, int n){</p><p><b>　　char *cd;</b></p><p>　　int i,start,p;</p><p>　　unsigned int c;</p><p>　　hc=(HuffmanCode *)malloc((n+

36、1)*sizeof(char *)); //分配n個(gè)編碼的頭指針</p><p>　　cd=(char *)malloc(n*sizeof(char)); //分配求當(dāng)前編碼的工作空間</p><p>　　cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結(jié)束符</p><p>　　for(i=1; i<=n; i++)

37、 //求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼</p><p><b>　　{</b></p><p>　　start=n-1; //初始化編碼起始指針</p><p>　　for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //從葉子到根結(jié)點(diǎn)求編碼</p><p>

38、　　if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支標(biāo)0</p><p>　　else cd[--start]='1'; //右分支標(biāo)1</p><p>　　hc[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個(gè)編碼分配空間</p><p&

39、gt;　　strcpy(hc[i],&cd[start]);</p><p><b>　　}</b></p><p><b>　　free(cd);</b></p><p>　　for(i=1; i<=n; i++)</p><p>　　printf("\n第%d個(gè)權(quán)值為%d

40、的字符是%s\n",i,(*ht)[i].weight,hc[i]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void main(){</p><p>　　HuffmanTree HT;</p><p&

41、gt;　　HuffmanCode HC;</p><p>　　int *w,i,n,wei,m;</p><p>　　printf("\n *#*#*#*#*#*# #*#*#*#*#*#* \n");</p><p>　　printf("\n

42、 *#*#*#*#*#*#*#*# 歡迎來(lái)到課程設(shè)計(jì)之--哈夫曼編碼 #*#*#*#*#*#*#*#*\n");</p><p>　　printf("\n *#*#*#*#*#*# #*#*#*#*#*#* \n");</p><p>　　printf(&qu

43、ot;\n\n*#*#*#* Are you ready???\n");</p><p>　　printf("\n\n*#*#*#* OK,Let's GO!!!\n");</p><p>　　printf("\n\n*#*#*#* 請(qǐng)您先輸入字符個(gè)數(shù)n： " );</p><p>　　scanf(&q

44、uot;%d",&n);</p><p>　　w=(int *)malloc((n+1)*sizeof(int)); </p><p>　　printf("\n*#*#*#* 然后分別輸入這%d個(gè)字符的權(quán)值:\n",n); </p><p>　　for(i=1; i<=n; i++){ </p><p

45、>　　printf("\n*#*#*#* 第%d個(gè)字符的權(quán)值: ",i); </p><p>　　fflush(stdin);</p><p>　　scanf("%d",&wei);</p><p><b>　　w[i]=wei;</b></p><p><b