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

1、<p><b>　　計(jì)算機(jī)工程學(xué)院</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p>　　設(shè)計(jì)題目： 哈夫曼編碼器 </p><p>　　院 系：

2、 計(jì)算機(jī)工程學(xué)院 </p><p>　　班 級(jí)： </p><p>　　組 別： </p><p>　　學(xué)生姓名: 學(xué) 號(hào):

3、 </p><p>　　起止日期: 2011 年 12 月 26 日 ~ 31 日 </p><p><b>　　目 錄</b></p><p><b>　　1、設(shè)計(jì)目的2</b></p><p><b>　　2、需求分析3</b><

4、/p><p>　　2.1選題的意義及背景</p><p><b>　　2.2基本要求</b></p><p>　　2.3運(yùn)行環(huán)境及開發(fā)工具</p><p><b>　　3、概要設(shè)計(jì)4</b></p><p><b>　　3.1設(shè)計(jì)思想</b></p&

5、gt;<p><b>　　3.2程序框圖</b></p><p><b>　　3.3方法及原理</b></p><p><b>　　3.4主要數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　4、詳細(xì)設(shè)計(jì)7</b></p><p><b&

6、gt;　　4.1創(chuàng)建哈夫曼樹</b></p><p><b>　　4.2編碼</b></p><p><b>　　4.3源程序</b></p><p>　　5、調(diào)試與操作說明14</p><p>　　6、總結(jié)與體會(huì)15</p><p><b>　　7

7、、致謝16</b></p><p><b>　　設(shè)計(jì)目的</b></p><p>　　利用學(xué)過的數(shù)據(jù)結(jié)構(gòu)知識(shí)設(shè)計(jì)一個(gè)簡(jiǎn)單的哈夫曼編/譯碼器系統(tǒng)。</p><p>　　2、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　3、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序

8、編碼、測(cè)試等基本方法和技能；</p><p>　　4、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；</p><p>　　5、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p><b>　　2</b></p><p><b>　　需求分析&

9、lt;/b></p><p>　　2.1、選題的意義和背景</p><p>　　利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這是要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。</p><p><b&g

10、t;　　2.2、基本要求</b></p><p>　　(1)初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹；(2)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；(3)輸出編碼；(4)設(shè)字符集及頻度如下表：</p><p>　　2.3、運(yùn)行環(huán)境及開發(fā)工具</p><p>　　本程序采用Visual C++6.0編程實(shí)現(xiàn)。</p>

11、<p><b>　　3</b></p><p><b>　　概要設(shè)計(jì)</b></p><p><b>　　3.1設(shè)計(jì)思想</b></p><p>　　本程序的主要功能是實(shí)現(xiàn)對(duì)用戶輸入的字符編碼，然后再把編碼結(jié)果翻譯成原字符。但在進(jìn)行這些操作之前必須做一項(xiàng)工作，就是創(chuàng)建Huffman樹。哈

12、夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長(zhǎng)度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。哈夫曼在上世

13、紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長(zhǎng)度最短的編碼。它是一種變長(zhǎng)的編碼。在編碼中，若各碼字長(zhǎng)度嚴(yán)格按照碼字所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小的逆序排列，則編碼的平均長(zhǎng)度是最小的。</p><p><b>　　4</b></p><p>　　3.2程序框圖及流程圖</p><p>　　3.3 方法及原理</p>&l

14、t;p>　　3.3.1　創(chuàng)建Huffman樹</p><p>　　本文創(chuàng)建Huffman樹是在順序鏈表的基礎(chǔ)上進(jìn)行的，建樹原理如下：</p><p>　　1、根據(jù)給定的n個(gè)權(quán)值{w1,w2,w3,……,wn}，構(gòu)造具有n棵二叉樹的森林F={T1,T2,T3,……,Tn}，其中每棵二叉樹Ti只有一個(gè)帶權(quán)值wi的根結(jié)點(diǎn)，其左右子樹均為空。</p><p>　　2、

15、重復(fù)以下步驟，直到F中僅剩下一棵樹為止：</p><p>　　(1)在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹，作為左右子樹構(gòu)造一棵新的二叉樹。使新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。</p><p>　　(2)在F中刪去這兩棵二叉樹，把新的二叉樹加入F。</p><p>　　最后得到的就是Huffman樹。</p><p>&

16、lt;b>　　3.3.2 編碼</b></p><p>　　編碼操作需在建立好Huffman樹的基礎(chǔ)上進(jìn)行。二叉樹的葉子結(jié)點(diǎn)標(biāo)記字符，由根結(jié)點(diǎn)沿著二叉樹路徑下行，左分支標(biāo)記為0，右分支標(biāo)記為1，則每條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑唯一表示了該葉結(jié)點(diǎn)的二進(jìn)制編碼。編碼的時(shí)候，我們采用從葉子結(jié)點(diǎn)向上回溯的方法編碼，如果當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，則編碼為0，如果是右孩子，則編碼為1，如此回溯，直到父結(jié)點(diǎn)

17、為空時(shí)，該字符的編碼就結(jié)束了，對(duì)應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就是該字符的編碼。如此操作，直到所有葉子結(jié)點(diǎn)都掃描一遍為止，即編碼結(jié)束。</p><p>　　3.4 主要的數(shù)據(jù)結(jié)構(gòu)</p><p>　　3.4.1 Huffman結(jié)點(diǎn)結(jié)構(gòu)</p><p>　　Huffman結(jié)點(diǎn)結(jié)構(gòu)是本程序的基本結(jié)構(gòu)，所有操作都在此上進(jìn)行。其中包括存儲(chǔ)字符的元素data，字符的權(quán)值weight

18、，以及左右孩子指針和父指針。</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char ch;//結(jié)點(diǎn)值</p><p>　　int weight;//權(quán)值</p><p>　　int parent;

19、//父結(jié)點(diǎn)指針</p><p>　　int lchild; //左孩子結(jié)點(diǎn)指針</p><p>　　int rchild;//右孩子結(jié)點(diǎn)指針</p><p>　　}huffnode;</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p>　　4.1 創(chuàng)建Huffman樹&

20、lt;/p><p>　　4.1.1 功能描述</p><p>　　Huffman樹是整個(gè)程序的核心部分，是編碼譯碼操作的前提。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長(zhǎng)度最短的編碼。它是一種變長(zhǎng)的編碼。在編碼中，若各碼字長(zhǎng)度嚴(yán)格按照碼字所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小的逆序排列，則編碼的平均長(zhǎng)度是最小的。</p><p>　　4.1.

21、2 算法原理</p><p>　　首先根據(jù)用戶輸入創(chuàng)建n棵子樹的森林，然后對(duì)所有子樹掃描，找出權(quán)值最小的兩個(gè)子樹，把它們合并成一棵新的子樹，同時(shí)把它們的權(quán)值之和作為新樹的權(quán)值。把這兩棵子樹刪掉，再把新樹加如到森林中，然后再掃描出權(quán)值最小的兩棵子樹，接著進(jìn)行同樣的操作，直到只剩下一棵樹即為Huffman樹。 </p><p>　　4.1.3 算法流程</p

22、><p><b>　　7</b></p><p><b>　　4.2 編碼</b></p><p>　　4.2.1 功能描述</p><p>　　編碼的功能就是把字符轉(zhuǎn)換成二進(jìn)制數(shù)來存儲(chǔ)</p><p>　　4.2.2 算法原理</p><p>　　編碼的

23、時(shí)候，我們采用從葉子結(jié)點(diǎn)向上回溯的方法編碼，如果當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，則編碼為0，如果是右孩子，則編碼為1，如此回溯，直到父結(jié)點(diǎn)為空時(shí)，該字符的編碼就結(jié)束了，對(duì)應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就是該字符的編碼。如此操作，直到所有葉子結(jié)點(diǎn)都掃描一遍為止，即編碼結(jié)束。</p><p>　　4.2.3 算法流程</p><p><b>　　4.4源程序</b></p>

24、;<p>　　#include<iostream.h></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<string.h></p><p>　　#include<fstre

25、am.h></p><p>　　typedef struct{ //哈夫曼樹的結(jié)構(gòu)體</p><p><b>　　char ch;</b></p><p>　　int weight; //權(quán)值</p><p>　　int parent,lchild,rchild;</

26、p><p>　　}htnode,*hfmtree;</p><p>　　typedef char **hfmcode;</p><p>　　void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)</p><p><b

27、>　　{</b></p><p>　　int i,j,x,y;</p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[j].parent==0){</p><p><b>　　x=j;</b></p><p><b>　　bre

28、ak;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i){</p><p>　　if(HT[i].weight<HT[x].weight&&HT[i].paren

29、t==0){</p><p>　　x=i; //選出最小的節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(j=1;j<=a;++j){</p><p>　　if(HT[

30、j].parent==0&&x!=j)</p><p><b>　　{</b></p><p><b>　　y=j;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>&

31、lt;p><b>　　}</b></p><p>　　for(i=j+1;i<=a;++i)</p><p><b>　　{</b></p><p>　　if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)</p&g

32、t;<p><b>　　{</b></p><p>　　y=i; //選出次小的節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(x>y){&l

33、t;/b></p><p><b>　　*p1=y;</b></p><p><b>　　*p2=x;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b&

34、gt;　　{</b></p><p><b>　　*p1=x;</b></p><p><b>　　*p2=y;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　

35、　void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //構(gòu)建哈夫曼樹HT，并求出n個(gè)字符的哈夫曼編碼HC</p><p><b>　　{</b></p><p>　　int i,start,c,f,m,w;</p><p>　　int p1,p2;</p><p>

36、;　　char *cd,z;</p><p><b>　　if(n<=1){</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　m=2*n-1;</b></p>

37、<p>　　HT=(hfmtree)malloc((m+1)*sizeof(htnode));</p><p>　　for(i=1;i<=n;++i) //初始化n個(gè)葉子結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入第%d字符信息和權(quán)值：",

38、i);</p><p>　　scanf("%c%d",&z,&w);</p><p>　　while(getchar()!='\n')</p><p><b>　　{</b></p><p><b>　　continue;</b></p>

39、;<p><b>　　}</b></p><p>　　HT[i].ch=z;</p><p>　　HT[i].weight=w;</p><p>　　HT[i].parent=0;</p><p>　　HT[i].lchild=0;</p><p>　　HT[i].rchild=0;

40、</p><p><b>　　}</b></p><p>　　for(;i<=m;++i) //初始化其余的結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　HT[i].ch='0';</p><p>　　HT[i].wei

41、ght=0;</p><p>　　HT[i].parent=0;</p><p>　　HT[i].lchild=0;</p><p>　　HT[i].rchild=0;</p><p><b>　　}</b></p><p>　　for(i=n+1;i<=m;++i) //建立

42、哈夫曼樹</p><p><b>　　{</b></p><p>　　Select(HT,i-1,&p1,&p2);</p><p>　　HT[p1].parent=i;HT[p2].parent=i;</p><p>　　HT[i].lchild=p1;HT[i].rchild=p2;</p>

43、;<p>　　HT[i].weight=HT[p1].weight+HT[p2].weight;</p><p><b>　　}</b></p><p>　　HC=(hfmcode)malloc((n+1)*sizeof(char *));</p><p>　　cd=(char *)malloc(n*sizeof(char));&

44、lt;/p><p>　　cd[n-1]='\0';</p><p>　　for(i=1;i<=n;++i) //給n個(gè)字符編碼</p><p><b>　　{</b></p><p>　　start=n-1;</p><p>　　for(c=i,f=HT

45、[i].parent;f!=0;c=f,f=HT[f].parent)</p><p><b>　　{</b></p><p>　　if(HT[f].lchild==c)</p><p><b>　　{</b></p><p>　　cd[--start]='0';</p>

46、<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cd[--start]='1';</p><p><b>　　}</b></p&g

47、t;<p><b>　　}</b></p><p>　　HC[i]=(char*)malloc((n-start)*sizeof(char));</p><p>　　strcpy(HC[i],&cd[start]);</p><p><b>　　}</b></p><p>&l

48、t;b>　　free(cd);</b></p><p><b>　　}</b></p><p>　　int main(){</p><p>　　char code[100],h[100],hl[100];</p><p>　　int n,i,j,k,l;</p><p>　　if

49、stream input_file; //文件輸入輸出</p><p>　　ofstream output_file;</p><p>　　char choice,str[100];</p><p>　　hfmtree HT;</p><p>　　hfmcode HC;</p><p>　　cout<<

50、;"\n";</p><p>　　cout<<" "<<"軟件1102班"<<" "<<"1101306229"<<" "<<"吳超\n";</p><p

51、>　　while(choice!='Q'&&choice!='q') //當(dāng)choice的值不為q且不為Q時(shí)循環(huán)</p><p><b>　　{</b></p><p>　　cout<<" "<<"***********

52、**************哈夫曼編碼器*************************\n";</p><p>　　cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<"

53、 "<<"Q.Exit\n";</p><p>　　cout<<"請(qǐng)輸入您要操作的步驟：";</p><p>　　cin>>choice;</p><p>　　if(choice=='I'||choice=='i')

54、//初始化哈夫曼樹</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入字符個(gè)數(shù)：";</p><p><b>　　cin>>n;</b></p><p>　　hfmcoding(HT,HC,n);</p><

55、;p>　　for(i=1;i<=n;++i)</p><p><b>　　{</b></p><p>　　cout<<HT[i].ch<<":"<<HC[i]<<endl;</p><p><b>　　}</b></p><

56、p>　　output_file.open("hfmTree.txt");</p><p>　　if(!output_file){</p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b>&

57、lt;/p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　output_file<<"("<<HT[i].ch<<HC[i]<<

58、")";</p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　cout<<"哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl;</p><p><b&g

59、t;　　}</b></p><p>　　else if(choice=='E'||choice=='e') //進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中</p><p><b>　　{</b></p><p>　　printf("

60、請(qǐng)輸入字符：");</p><p>　　gets(str);</p><p>　　output_file.open("ToBeTran.txt");</p><p>　　if(!output_file)</p><p><b>　　{</b></p><p>　　co

61、ut<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　output_file<<str<<endl;</p>&l

62、t;p>　　output_file.close();</p><p>　　output_file.open("CodeFile.txt");</p><p>　　if(!output_file){</p><p>　　cout<<"can't open file!"<<endl;</

63、p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　for(i=0;i<strlen(str);i++){</p><p>　　for(j=0;j<=n;++j)</p><p><b>　　{&l

64、t;/b></p><p>　　if(HT[j].ch==str[i])</p><p><b>　　{</b></p><p>　　output_file<<HC[j];</p><p><b>　　break;</b></p><p><b>

65、　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　output_file.close();</p><p>　　cout<<"\n";</p><p>　　cout&

66、lt;<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！\n";</p><p>　　input_file.open("CodeFile.txt"); //從CodeFile.txt中讀入編碼，輸出在終端</p><p>　　if(!input_file)</p><p><b>　　{&

67、lt;/b></p><p>　　cout<<"can't oen file!"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　input_file>&

68、gt;code;</p><p>　　cout<<"編碼碼值為："<<code<<endl;</p><p>　　input_file.close();</p><p><b>　　}</b></p><p>　　else //如果選了選

69、項(xiàng)之外的就讓用戶重新選擇</p><p><b>　　{</b></p><p>　　cout<<"您沒有輸入正確的步驟，請(qǐng)重新輸入！"<<endl;</p><p><b>　　}</b></p><p>　　cout<<endl;</

70、p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　14</b></p><p><b>　　調(diào)試與操作說明</

71、b></p><p>　　在運(yùn)行程序時(shí)，需先輸入需要編碼的字符串，然后根據(jù)輸入的字符的權(quán)重創(chuàng)建Huffman樹，接著再進(jìn)行編碼操作，最后再把所得的編，各步操作之間存在先后關(guān)系，因此在運(yùn)行程序時(shí)必須注意所選擇的操作的先后順序。</p><p><b>　　15</b></p><p><b>　　總結(jié)與體會(huì)</b>&l

72、t;/p><p>　　在當(dāng)今的信息化時(shí)代，先進(jìn)的技術(shù)成為了科技的主流。哈夫曼是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。這次課程設(shè)計(jì)我做的是哈夫曼編碼和譯碼器。由于自身對(duì)數(shù)據(jù)結(jié)構(gòu)的掌握有限，我只能做哈夫曼樹的建立，編碼和譯碼這部分內(nèi)容。但是通過這次課程設(shè)計(jì)，我看到了自身的不足，讓我有機(jī)會(huì)進(jìn)一步學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)的知識(shí)。平時(shí)的學(xué)習(xí)中，我們不能單單地只學(xué)習(xí)理論知識(shí)，而應(yīng)當(dāng)把理論知識(shí)與實(shí)踐結(jié)合起來。不然如果只有理論知識(shí)，而不能把理