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

1、<p>　　程序設(shè)計(jì)(大作業(yè))報(bào)告</p><p>　　課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　設(shè)計(jì)題目：哈夫曼編碼器 </p><p>　　院 系：信息技術(shù)學(xué)院 </p><p>　　班 級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)2 班</p><p>　　設(shè) 計(jì) 者：

2、 </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p>　　設(shè)計(jì)時(shí)間：2012.1.9-2012.1.11 </p><p>　　課程設(shè)計(jì)（大作業(yè)）任務(wù)書(shū)</p><p>　　課程設(shè)計(jì)題目：哈夫曼編碼器 &l

3、t;/p><p><b>　　課程設(shè)計(jì)要求：</b></p><p>　　（1）初始化：鍵盤(pán)輸入n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)</p><p>　?。?）編碼：利用建好的huffman樹(shù)生成huffman編碼</p><p><b>　　（3）輸出編碼</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>　　工作計(jì)劃及安排</b></p><p>　　（1）在上機(jī)之前選題</p><p>　?。?）選擇合適的數(shù)據(jù)結(jié)構(gòu)</p><p>　　（3）結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計(jì)</p><p>　?。?）算法設(shè)計(jì)與分析</p>

6、<p>　?。?）程序設(shè)計(jì)、實(shí)現(xiàn)、調(diào)試</p><p>　?。?）提交課程設(shè)計(jì)報(bào)告</p><p>　　指導(dǎo)教師簽字 </p><p>　　年 月 日 </p><p>　　課程設(shè)計(jì)（大作業(yè)）成績(jī)</p><p>　　學(xué)號(hào)： 姓名： 指導(dǎo)教師：

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

8、對(duì)它的了解。</p><p><b>　　指導(dǎo)教師評(píng)語(yǔ)：</b></p><p><b>　　成績(jī)：</b></p><p>　　填表時(shí)間：</p><p><b>　　指導(dǎo)教師簽名： </b></p><p><b>　　目錄&

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

10、數(shù)據(jù)結(jié)構(gòu)5</b></p><p><b>　　4.總體設(shè)計(jì)5</b></p><p><b>　　5.詳細(xì)設(shè)計(jì)6</b></p><p>　　5.1程序流程圖6</p><p>　　5.2初始化哈夫曼樹(shù)7</p><p>　　5.3輸入權(quán)值函數(shù)7&l

11、t;/p><p>　　5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)7</p><p>　　5.5構(gòu)造哈夫曼樹(shù)7</p><p>　　5.6根據(jù)哈夫曼樹(shù)求哈夫曼編碼7</p><p><b>　　6.測(cè)試與調(diào)試7</b></p><p>　　6.1程序步驟演示7</p><p&

12、gt;　　6.1.1輸入各字符的權(quán)值7</p><p>　　6.1.2輸入字符8</p><p>　　6.1.3得到哈夫曼編碼8</p><p>　　6.2程序測(cè)試結(jié)果8</p><p>　　7.源程序清單10</p><p><b>　　8.實(shí)驗(yàn)心得13</b></p>

13、<p><b>　　1.問(wèn)題描述</b></p><p>　　構(gòu)造一棵哈夫曼樹(shù)，根據(jù)所需輸入的字符數(shù)目，分別輸入字符的頻度和字符，得到它們相應(yīng)的編碼，也就是設(shè)計(jì)一個(gè)哈夫曼編碼器。</p><p><b>　　2.基本要求</b></p><p>　　以字符的頻度為權(quán)值，建立哈夫曼樹(shù)，求哈夫曼編碼。根據(jù)字符及權(quán)值

14、得到其相應(yīng)的編碼。</p><p><b>　　3.數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　typedef struct </p><p>　　{int weight; /*結(jié)點(diǎn)的權(quán)值*/</p><p>　　int lchild,rchild,parent;

15、 /*左、右孩子及雙親的下標(biāo)*/</p><p><b>　　}htnode;</b></p><p>　　typedef htnode huffmantree[m+1]; /* huffmantree是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */</p><p>　　typedef struct</p><p>

16、;　　{char ch; /*存儲(chǔ)字符*/</p><p>　　char code[n+1]; /*存放編碼位串*/</p><p>　　}codenode;</p><p>　　typedef codenode huffmancode[n+1]; /*huffmancode是結(jié)構(gòu)數(shù)組

17、類(lèi)型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/</p><p><b>　　4.總體設(shè)計(jì)</b></p><p><b>　　功能模塊劃分</b></p><p>　　void main() //主函數(shù)</p><p>　　void inithuffmantree

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

19、id createhuffmantree(huffmantree ht) //構(gòu)造huffman樹(shù)，ht[m]為其根結(jié)</p><p>　　void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹(shù)ht求huffman編</p><p><b>　　5.詳細(xì)設(shè)計(jì)</b></p><

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

21、gt;<p><b>　　5.3輸入權(quán)值函數(shù)</b></p><p>　　void inputweight(huffmantree ht)</p><p>　　5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)</p><p>　　void selectmin(huffmantree ht, int i, int *p1, int

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

23、de hcd)</p><p><b>　　6.測(cè)試與調(diào)試</b></p><p><b>　　6.1程序步驟演示</b></p><p>　　6.1.1輸入各字符的權(quán)值</p><p><b>　　6.1.2輸入字符</b></p><p>　　6.

24、1.3得到哈夫曼編碼</p><p><b>　　6.2程序測(cè)試結(jié)果</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)標(biāo)準(zhǔn)輸出函數(shù)的</p><p>　　#include<string.h></p><p>　　#include<conio.h> //用到像getch()這種鍵盤(pán)輸入函數(shù)</p><p>　　/* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/</p><p>　　#defi

27、ne n 9 /*葉子數(shù)目根據(jù)需要設(shè)定*/</p><p>　　#define m 2*n-1 /* Huffman 樹(shù)中結(jié)點(diǎn)總數(shù) */</p><p>　　/* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/</p><p>　　typedef struct /*結(jié)構(gòu)體定義*/</p><p>　　

28、{int weight; /*結(jié)點(diǎn)的權(quán)值*/</p><p>　　int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/</p><p>　　}htnode; /*哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)型*/</p><p>　　typedef htnode huffmantree[m+1]; /

29、* huffmantree是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */</p><p>　　typedef struct</p><p>　　{char ch; /*存儲(chǔ)字符*/</p><p>　　char code[n+1]; /*存放編碼位串*/</p><p>　　}codenode

30、; /*編碼結(jié)點(diǎn)類(lèi)型*/</p><p>　　typedef codenode huffmancode[n+1]; /*huffmancode是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/</p><p>　　void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹(shù)函數(shù)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) /*輸入權(quán)值函數(shù) */</p><p><b>　　{int i;</b></p><p>　　for(i=1

33、;i<=n;i++)</p><p><b>　　{</b></p><p>　　printf(" ……請(qǐng)輸入第[%d]個(gè)權(quán)值: ",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]中選兩個(gè)權(quán)值最小的

35、根結(jié)點(diǎn)，其序號(hào)為*p1和*p2，*p1中放權(quán)值最小的根結(jié)點(diǎn)的序號(hào)，*p2中放權(quán)值次小的根結(jié)點(diǎn)的序號(hào)*/</p><p>　　{int j,min1,min2; /* min1,min2分別是最小權(quán)值和次小權(quán)值*/</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 為根結(jié)點(diǎn)*/</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) /*構(gòu)造huffman樹(shù)，ht[m]為其根結(jié)點(diǎn)*/</p><p>　　{ </p><p>　　int i,p1,p2;</p><p>　　inithuffmantree(ht); /* 將ht初始化*/</p><p>　　inputweight(ht)

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

41、擇兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其序號(hào)分別為p1和p2*/</p><p>　　ht[p1].parent=ht[p2].parent=i;</p><p>　　ht[i].lchild=p1; /* 最小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子*/</p><p>　　ht[i].rchild=p2; /* 次小權(quán)值的根結(jié)點(diǎn)是新

42、結(jié)點(diǎn)的右孩子*/</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) /*根據(jù)huffman樹(shù)ht求huffman編碼*/</p><p><b>　　{</b></p><p>　　int c,p,i; /* c和p分別指示 ht中孩子和雙親的位置 */</p><p>　　char cd[n+1];

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

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

46、gt;<p>　　start=n; /* 編碼起始位置的初值*/</p><p>　　c=i; /* 從葉子ht [i]開(kāi)始上溯*/</p><p>　　while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是樹(shù)根為止*/</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]); /* 復(fù)制編碼位串*/</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("3.………哈夫曼編碼結(jié)果

49、為：……\n");</p><p>　　printf("\n");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf(" ……第[%d]個(gè)字符[%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.…………請(qǐng)輸入%d個(gè)權(quán)值:……\n",n);</p><p>　　printf("\n");</p><p>　　crea

53、tehuffmantree(t); /* 構(gòu)造huffman樹(shù)*/</p><p>　　huffmancodes(t,h); /* 構(gòu)造huffman編碼*/</p><p><b>　　}</b></p><p><b>　　8.實(shí)驗(yàn)心得&

54、lt;/b></p><p>　　通過(guò)這次課程設(shè)計(jì)，使我獲益匪淺。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于我們是非常重要的，能使我們?cè)谝院蟮某绦蛟O(shè)計(jì)方面給我們很大的幫助。以此同時(shí)，這門(mén)課程的學(xué)習(xí)也是非常艱辛的，因?yàn)樗容^抽象難懂，這需要我們?cè)趯?shí)踐中不斷的克服。</p><p>　　將近一個(gè)多星期的設(shè)計(jì)工作，讓我體會(huì)到作為一個(gè)編程人員是非常辛苦的。一個(gè)程序從算法到實(shí)現(xiàn)，再到應(yīng)用開(kāi)發(fā)是需要走很長(zhǎng)的一段路，不是一