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

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

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

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

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

5、于一個字符的哈夫曼編碼是從根節(jié)點到相應(yīng)葉子結(jié)點所經(jīng)過的路徑上各分支所組成的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>　　三、測試及運行結(jié)果</b></p>

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

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

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

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

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

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

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

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

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

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

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

18、版社；主編：程杰；出版日期：2011年6月。</p><p>　　《大話設(shè)計模式》;出版社：清華大學(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; //動態(tài)分配數(shù)組，存儲哈夫曼編碼</p><p>　　typedef struct</p><p><b>　　{</b></p><p&

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

21、t最小的結(jié)點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個權(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號存放葉子結(jié)點，初始化</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é)點初始化</p><p>　　printf("\n哈夫曼樹如下: \n");</p><p>　　for(i=n+1; i<=m; i++) //創(chuàng)建非葉子結(jié)點，建哈夫曼樹</p><p>　　{ //在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個parent為0</p>

32、<p>　　//且weight最小的結(jié)點，其序號分別賦值給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é)點到根，逆向求每個葉子結(jié)點對應(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個編碼的頭指針</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個葉子結(jié)點對應(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é)點求編碼</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個編碼分配空間</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個權(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、 *#*#*#*#*#*#*#*# 歡迎來到課程設(shè)計之--哈夫曼編碼 #*#*#*#*#*#*#*#*\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*#*#*#* 請您先輸入字符個數(shù)n： " );</p><p>　　scanf(&q

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

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