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

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

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

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

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

5、于一個字符的哈夫曼編碼是從根節(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>　　三、測試及運行結果</b></p>

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

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>　　通過仔細的檢查，我們會發(fā)現(xiàn)如上圖所示的語句，在這個語句中，“CrtHuffmantree”讓我們錯打成

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

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

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

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

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

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

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

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

18、版社；主編：程杰；出版日期：2011年6月。</p><p>　　《大話設計模式》;出版社：清華大學出版社；主編：程杰；出版日期：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; //用來存放各個結點的權值</p><p>　　unsigned int parent,LChild,RChild; //指向雙親、孩子結點的指針</p><p>　　} HTNode, *HuffmanTree; //動態(tài)分配數(shù)組，存儲哈夫曼樹</p><p>　　//選擇兩個parent為0，且weigh

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

32、<p>　　//且weight最小的結點，其序號分別賦值給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>　　//從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼</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)); //分配求當前編碼的工作空間</p><p>　　cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結束符</p><p>　　for(i=1; i<=n; i++)

37、 //求n個葉子結點對應的哈夫曼編碼</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) //從葉子到根結點求編碼</p><p>

38、　　if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支標0</p><p>　　else cd[--start]='1'; //右分支標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個權值為%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、 *#*#*#*#*#*#*#*# 歡迎來到課程設計之--哈夫曼編碼 #*#*#*#*#*#*#*#*\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個字符的權值:\n",n); </p><p>　　for(i=1; i<=n; i++){ </p><p

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