數據結構課程設計---哈夫曼編碼器

1、<p>　　程序設計(大作業(yè))報告</p><p>　　課程名稱：數據結構課程設計 </p><p>　　設計題目：哈夫曼編碼器 </p><p>　　院 系：信息技術學院 </p><p>　　班 級：計算機科學與技術2 班</p><p>　　設 計 者：

2、 </p><p>　　學 號： </p><p>　　指導教師： </p><p>　　設計時間：2012.1.9-2012.1.11 </p><p>　　課程設計（大作業(yè)）任務書</p><p>　　課程設計題目：哈夫曼編碼器 &l

3、t;/p><p><b>　　課程設計要求：</b></p><p>　?。?）初始化：鍵盤輸入n個字符和n個權值，建立哈夫曼樹</p><p>　?。?）編碼：利用建好的huffman樹生成huffman編碼</p><p><b>　?。?）輸出編碼</b></p><p>

4、　　（4）字符和頻度如下：</p><p>　?、?字符：空格 A B C D E F G H I J K L M N O P Q</p><p>　　頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1</p><p>　?、?字符：R S T U V W X Y Z</p><p>

5、;　　頻度：48 51 80 23 8 18 1 16</p><p><b>　　工作計劃及安排</b></p><p>　?。?）在上機之前選題</p><p>　　（2）選擇合適的數據結構</p><p>　?。?）結點結構的設計</p><p>　　（4）算法設計與分析</p>

6、<p>　?。?）程序設計、實現、調試</p><p>　?。?）提交課程設計報告</p><p>　　指導教師簽字 </p><p>　　年 月 日 </p><p>　　課程設計（大作業(yè)）成績</p><p>　　學號： 姓名： 指導教師：

7、 老師</p><p>　　課程設計題目： 哈夫曼編碼器 </p><p><b>　　總結：</b></p><p>　　通過此次的課程設計使我認識了哈夫曼樹的建立與應用，復習了數據結構中的樹的存儲結構，怎樣構造哈夫曼樹以及用哈夫曼樹進行編碼。學習數據結構能使我們?yōu)槠渌n程打好基礎，而課程設計作為數據結構中一個重要環(huán)節(jié)能更好的使我們加深

8、對它的了解。</p><p><b>　　指導教師評語：</b></p><p><b>　　成績：</b></p><p>　　填表時間：</p><p><b>　　指導教師簽名： </b></p><p><b>　　目錄&

9、lt;/b></p><p>　　程序設計(大作業(yè))報告1</p><p>　　昆明學院課程設計（大作業(yè)）任務書2</p><p><b>　　1.問題描述5</b></p><p><b>　　2.基本要求5</b></p><p><b>　　3.

10、數據結構5</b></p><p><b>　　4.總體設計5</b></p><p><b>　　5.詳細設計6</b></p><p>　　5.1程序流程圖6</p><p>　　5.2初始化哈夫曼樹7</p><p>　　5.3輸入權值函數7&l

11、t;/p><p>　　5.4選擇根結點，存放權值最小和次小序號7</p><p>　　5.5構造哈夫曼樹7</p><p>　　5.6根據哈夫曼樹求哈夫曼編碼7</p><p><b>　　6.測試與調試7</b></p><p>　　6.1程序步驟演示7</p><p&

12、gt;　　6.1.1輸入各字符的權值7</p><p>　　6.1.2輸入字符8</p><p>　　6.1.3得到哈夫曼編碼8</p><p>　　6.2程序測試結果8</p><p>　　7.源程序清單10</p><p><b>　　8.實驗心得13</b></p>

13、<p><b>　　1.問題描述</b></p><p>　　構造一棵哈夫曼樹，根據所需輸入的字符數目，分別輸入字符的頻度和字符，得到它們相應的編碼，也就是設計一個哈夫曼編碼器。</p><p><b>　　2.基本要求</b></p><p>　　以字符的頻度為權值，建立哈夫曼樹，求哈夫曼編碼。根據字符及權值

14、得到其相應的編碼。</p><p><b>　　3.數據結構</b></p><p>　　typedef struct </p><p>　　{int weight; /*結點的權值*/</p><p>　　int lchild,rchild,parent;

15、 /*左、右孩子及雙親的下標*/</p><p><b>　　}htnode;</b></p><p>　　typedef htnode huffmantree[m+1]; /* huffmantree是結構數組類型,其0號單元不用，存儲哈夫曼樹 */</p><p>　　typedef struct</p><p>

16、;　　{char ch; /*存儲字符*/</p><p>　　char code[n+1]; /*存放編碼位串*/</p><p>　　}codenode;</p><p>　　typedef codenode huffmancode[n+1]; /*huffmancode是結構數組

17、類型,其0號單元不用,存儲哈夫曼編碼*/</p><p><b>　　4.總體設計</b></p><p><b>　　功能模塊劃分</b></p><p>　　void main() //主函數</p><p>　　void inithuffmantree

18、(huffmantree ht) //初始化哈夫曼樹函數inithuffmantree()</p><p>　　void inputweight(huffmantree ht) //輸入權值函數 </p><p>　　void selectmin(huffmantree ht, int i, int *p1, int *p2)</p><p>　　vo

19、id createhuffmantree(huffmantree ht) //構造huffman樹，ht[m]為其根結</p><p>　　void huffmancodes(huffmantree ht,huffmancode hcd) /*根據huffman樹ht求huffman編</p><p><b>　　5.詳細設計</b></p><

20、;p><b>　　5.1程序流程圖</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p>　　5.2初始化哈夫曼樹</p><p>　　void inithuffmantree(huffmantree ht)</p&

21、gt;<p><b>　　5.3輸入權值函數</b></p><p>　　void inputweight(huffmantree ht)</p><p>　　5.4選擇根結點，存放權值最小和次小序號</p><p>　　void selectmin(huffmantree ht, int i, int *p1, int

22、*p2)</p><p><b>　　5.5構造哈夫曼樹</b></p><p>　　void createhuffmantree(huffmantree ht)</p><p>　　5.6根據哈夫曼樹求哈夫曼編碼</p><p>　　void huffmancodes(huffmantree ht,huffmanco

23、de hcd)</p><p><b>　　6.測試與調試</b></p><p><b>　　6.1程序步驟演示</b></p><p>　　6.1.1輸入各字符的權值</p><p><b>　　6.1.2輸入字符</b></p><p>　　6.

24、1.3得到哈夫曼編碼</p><p><b>　　6.2程序測試結果</b></p><p>　　字符：R S T U V W X Y Z</p><p>　　頻度：48 51 80 23 8 18 1 16 10</p><p>　　字符: A B C D E F G H I J K L M N O P Q</

25、p><p>　　頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1</p><p><b>　　7.源程序清單</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h>

26、 // 用到系統(tǒng)標準輸出函數的</p><p>　　#include<string.h></p><p>　　#include<conio.h> //用到像getch()這種鍵盤輸入函數</p><p>　　/* Huffman 樹的存儲結構*/</p><p>　　#defi

27、ne n 9 /*葉子數目根據需要設定*/</p><p>　　#define m 2*n-1 /* Huffman 樹中結點總數 */</p><p>　　/* Huffman 樹的存儲結構*/</p><p>　　typedef struct /*結構體定義*/</p><p>　　

28、{int weight; /*結點的權值*/</p><p>　　int lchild,rchild,parent; /*左、右孩子及雙親的下標*/</p><p>　　}htnode; /*哈夫曼樹結點類型*/</p><p>　　typedef htnode huffmantree[m+1]; /

29、* huffmantree是結構數組類型,其0號單元不用，存儲哈夫曼樹 */</p><p>　　typedef struct</p><p>　　{char ch; /*存儲字符*/</p><p>　　char code[n+1]; /*存放編碼位串*/</p><p>　　}codenode

30、; /*編碼結點類型*/</p><p>　　typedef codenode huffmancode[n+1]; /*huffmancode是結構數組類型,其0號單元不用,存儲哈夫曼編碼*/</p><p>　　void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹函數inithuffmantree

31、()*/</p><p><b>　　{int i;</b></p><p>　　for(i=0;i<=m;i++)</p><p>　　{ht[i].weight=0;</p><p>　　ht[i].lchild=ht[i].rchild=ht[i].parent=0;</p><p>

32、<b>　　}</b></p><p><b>　　}</b></p><p>　　void inputweight(huffmantree ht) /*輸入權值函數 */</p><p><b>　　{int i;</b></p><p>　　for(i=1

33、;i<=n;i++)</p><p><b>　　{</b></p><p>　　printf(" ……請輸入第[%d]個權值: ",i);</p><p>　　scanf("%d",&ht[i].weight);</p><p><b>　　}</

34、b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void selectmin(huffmantree ht, int i, int *p1, int *p2)</p><p>　　/* 在ht[1..i]中選兩個權值最小的

35、根結點，其序號為*p1和*p2，*p1中放權值最小的根結點的序號，*p2中放權值次小的根結點的序號*/</p><p>　　{int j,min1,min2; /* min1,min2分別是最小權值和次小權值*/</p><p>　　min1=min2=32767;</p><p>　　*p1=*p2=0;</p&

36、gt;<p>　　for(j=1;j<=i;j++)</p><p>　　{if(ht[j].parent==0) /* j 為根結點*/</p><p>　　if(ht[j].weight<min1||min1==32767)</p><p><b>　　{</b></p>&l

37、t;p>　　if(min1!=32767) {min2=min1; *p2=*p1;}</p><p>　　min1=ht[j].weight; *p1=j;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(ht[j].

38、weight<min2||min2==32767)</p><p>　　{min2=ht[j].weight; *p2=j;}</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void createhuffmantree(huffmantr

39、ee ht) /*構造huffman樹，ht[m]為其根結點*/</p><p>　　{ </p><p>　　int i,p1,p2;</p><p>　　inithuffmantree(ht); /* 將ht初始化*/</p><p>　　inputweight(ht)

40、; /* 輸入葉子權值至ht [1..n]的weight域*/</p><p>　　for(i=n+1;i<=m;i++) /* 共進行n-1次合并，新結點依次存于ht[i]中*/</p><p>　　{selectmin(ht,i-1,&p1,&p2); /*在ht [1.. i-1]中選

41、擇兩個權值最小的根結點，其序號分別為p1和p2*/</p><p>　　ht[p1].parent=ht[p2].parent=i;</p><p>　　ht[i].lchild=p1; /* 最小權值的根結點是新結點的左孩子*/</p><p>　　ht[i].rchild=p2; /* 次小權值的根結點是新

42、結點的右孩子*/</p><p>　　ht[i].weight=ht[p1].weight+ht[p2].weight;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void huffmancodes(huffmantree ht,huffma

43、ncode hcd) /*根據huffman樹ht求huffman編碼*/</p><p><b>　　{</b></p><p>　　int c,p,i; /* c和p分別指示 ht中孩子和雙親的位置 */</p><p>　　char cd[n+1];

44、 /* 臨時存放編碼*/</p><p>　　int start; /* 指示編碼在cd 中的起始位置*/</p><p>　　cd[n]='\0'; </p><p>　　getchar(); /* 編碼結束符*/

45、</p><p>　　printf("2.……請依次輸入字符……:");</p><p>　　for(i=1;i<=n;i++) /* 依次求葉子ht [i]的編碼*/</p><p>　　{ hcd[i].ch=getchar(); /* 讀入葉子ht [i]對應的字符*/</p&

46、gt;<p>　　start=n; /* 編碼起始位置的初值*/</p><p>　　c=i; /* 從葉子ht [i]開始上溯*/</p><p>　　while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是樹根為止*/</p>&

47、lt;p>　　{ cd[--start]=(ht[p].lchild==c)?'0':'1'; /*若ht [ c]是ht[p]的左孩子，則生成代碼0，否則生成代碼1*/</p><p>　　c=p; /* 繼續(xù)上溯*/</p><p><b>　　}<

48、/b></p><p>　　strcpy(hcd[i].code,&cd[start]); /* 復制編碼位串*/</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("3.………哈夫曼編碼結果

49、為：……\n");</p><p>　　printf("\n");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf(" ……第[%d]個字符[%c]的編碼為：%s\n",i,hcd[i].ch,hcd[i].code);</p><p><

50、;b>　　}</b></p><p>　　void main()</p><p>　　{huffmantree t;</p><p>　　huffmancode h;</p><p>　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^

51、^^^^^^^^^^^^^^^^^|\n");</p><p>　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*歡迎使用哈弗曼編碼系統(tǒng)！*^^^^^^^^^^^^^^^^^^^|\n");</p><p>　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*###################

52、#####*^^^^^^^^^^^^^^^^^^^|\n");</p><p>　　printf("\n");</p><p>　　printf("1.…………請輸入%d個權值:……\n",n);</p><p>　　printf("\n");</p><p>　　crea

53、tehuffmantree(t); /* 構造huffman樹*/</p><p>　　huffmancodes(t,h); /* 構造huffman編碼*/</p><p><b>　　}</b></p><p><b>　　8.實驗心得&

54、lt;/b></p><p>　　通過這次課程設計，使我獲益匪淺。學好數據結構對于我們是非常重要的，能使我們在以后的程序設計方面給我們很大的幫助。以此同時，這門課程的學習也是非常艱辛的，因為它比較抽象難懂，這需要我們在實踐中不斷的克服。</p><p>　　將近一個多星期的設計工作，讓我體會到作為一個編程人員是非常辛苦的。一個程序從算法到實現，再到應用開發(fā)是需要走很長的一段路，不是一