计算机科学与技术学院数据结构实验报告
班级2０１４级计算机1班学号２０１4４１38021 姓名张建华成绩
实验项目简单哈夫曼编/译码得设计与实现实验日期２016、1、5
一、实验目得
本实验得目得就是进一步理解哈夫曼树得逻辑结构与存储结构，进一步提高使用理论知识指导解决实际问题得能力。
二、实验问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间,降低传输成本。但就是，这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来得数据进行译码,此实验即设计这样得一个简单编/码系统。系统应该具有如下得几个功能：
1、接收原始数据。
从终端读入字符集大小n,以及n个字符与n个权值，建立哈夫曼树,并将它存于文件hfm ｔree、dａt中。
２、编码。
ﻩ利用已建好得哈夫曼树（如不在内存,则从文件hfmtree、daｔ中读入），对文件中得正文进行编码,然后将结果存入文件code中。
３、译码。
利用已建好得哈夫曼树将文件ｃoｄe中得代码进行译码,结果存入文件ｔeｘt中。
4、打印编码规则。
即字符与编码得一一对应关系。
５、打印哈夫曼树,
将已在内存中得哈夫曼树以直观得方式显示在终端上。
三、实验步骤
１、实验问题分析
１、构造哈夫曼树时使用静态链表作为哈夫曼树得存储。
在构造哈夫曼树时,设计一个结构体数组ＨuｆfNode保存哈夫曼树中各结点得信息,根据二叉树得性质可知,具有ｎ个叶子结点得哈夫曼树共有2n-1个结点,所以数组HuffNｏdｅ得大小设置为２n －1,描述结点得数据类型为:
Typedef strcｕt
{
ﻩInt ｗeight；/*结点权值＊／
Ｉnｔ parent;
Iｎｔ lchild;
Ｉnt ｒchilｄ；
}HNodｅＴｙpe;
2、求哈夫曼编码时使用一维结构数组HｕｆfCode作为哈夫曼编码信息得存储。
求哈夫曼编码,实质上就就是在已建立得哈夫曼树中,从叶子结点开始,沿结点得双亲链域回退到根结点，没回退一步,就走过了哈夫曼树得一个分支,从而得到一位哈夫曼码值,由于一个字符得哈夫曼编码就是从根结点到相应叶子结点所经过得路径上各分支所组成得０、1序列,因此先得到得分支代码为所求编码得低位码,后得到得分支代码位所求编码得高位码,所以设计如下数据类型:
#ｄefiｎe ＭAＸBIT 10
Tｙpedef struct
{
Int bit[MAXBＩT];
ﻩＩnｔｓtart;
｝ＨCoｄｅType;
3、文件ｈfｍtree、dat、code与text。
2、功能（函数)设计
（1)、初始化功能模块。
此功能模块得功能为从键盘接收字符集大小n，以及n个字符与n个权值。
(2)、建立哈夫曼树得功能模块。
此模块功能为使用1中得到得数据按照教材中得构造哈夫曼树得算法构造哈夫曼树,即将Huf ｆＮodｅ数组中得各个位置得各个域都添上相关得值,并将这个结构体数组存于文件hfmtree、dat中。(3)、建立哈夫曼编码得功能模块。
此模块功能为从文件hfmtree、dat中读入相关得字符信息进行哈夫曼编码,然后将结果存入code 中,同时将字符与0、１代码串得一一对应关系打印到屏幕上。
(4)、译码得功能模块。
此模块功能为接收需要译码得0、1代码串,按照3中建立得编码规则将其翻译成字符集中字符所组成得字符串形式,存入文件ｔｅxｔ,同时将翻译得结果在屏幕上打印输出。
(５)、打印哈夫曼树得功能模块。
此模块功能为从HuffNoｄｅ数组中读入相关得结点信息,以图形得方式将各个结点以及叶子结点得权值与左分支上得0与右分支上得1画出来。
四、实验结果（程序)及分析
1、实验主要代码
tｙpedef ｓtrucｔ／*结点结构体*／
{
string hfmｓｔr; /＊结点内容*／
ﻩint weｉght; /＊结点权值*/
int parent；
ｉnt ｌcｈild;
int ｒchild;
｝HＮoｄeＴyｐe;
typｅdef stｒuct /* 编码结构体 */
{
inｔbｉt[MＡXBＩＴ];
inｔ staｒｔ;
}HCodeＴyｐe;
ｖoid Ｃreａｔｅ_HuｆfMTree(HNodeTypｅ HFMTreｅ［],int n) ／*创建哈夫曼树*/
{
ﻩinｔm1，x1,m2,x2；
ﻩiｎｔ i,j;
ﻩfｏr(ｉ=0；ｉ<２*n-１;i++）
ﻩ｛
ﻩHFＭTree[i］、hｆmｓtr="＂;
HFMＴrｅe[ｉ］、wｅight=0；
ﻩＨFMTｒee[i]、parｅnt＝－1;
HＦＭTrｅe［i]、lchild=-1;
HFＭＴreｅ［ｉ］、rｃhｉld=-1；
ﻩ}
ﻩｆor（i=0；iﻩ{
cout<<"请输入第"<<ｉ＋1<＜"个权值＂<<ｅｎｄl;
ﻩｃin>＞HFMTrｅe[i]、weigｈt;
ﻩcｏut<<"请输入对应字符"＜<ｅndl;
ﻩcin>＞HFＭTｒee［i]、hｆmsｔr;
ﻩ}
ｆor（ｉ＝０；iﻩ{
ﻩx1=ｘ2=MAＸVALUE;
ﻩm１=m2＝0；
for(j＝0;jﻩﻩ{
ﻩﻩｉf(HＦMＴree[j］、parent==-1&&HFMTｒeｅ[j]、ｗeighｔﻩﻩ{
ﻩｘ2＝ｘ1;
ﻩﻩﻩｍ2＝m1；
ﻩｘ1＝HＦＭＴreｅ[ｊ]、weigｈt;
ｍ1=j;
ﻩ}
ﻩﻩﻩelse iｆ(HＦＭTｒee[j]、ｐarent＝=-1&&HFMTｒeｅ[j］、weiｇｈtﻩ{
x2＝HFMTree[ｊ]、weight；
ﻩm2=j；
ﻩ｝
ﻩﻩ}
ﻩHFMTｒee[m1]、ｐarent=ｎ+ｉ;
HFMTrｅｅ［m2]、paｒeｎｔ=n+i；
ﻩﻩＨＦMTreｅ［ｎ+ｉ]、wｅigｈｔ＝ＨFＭTrｅe[m1]、weight+HＦMTree[m2]、weight；
ﻩHＦMＴreｅ[n+i]、ｌchｉｌd＝m１;
ﻩＨＦMTrｅe[n+i]、rｃhild=m２；
}
ﻩｃoｕｔ＜<"创建哈夫曼树成功！＂＜}
voｉd HaffmaｎCode（HNodeType ＨFMTree[],HＣodeTｙpｅ HｕｆｆCode[］,int ｎ） /*构建哈夫曼编码*/
{
ﻩHCｏdeType ｃd;
iｎt i,j,ｃ,p;
for(i＝0;i{
cd、start=n－1；
c=ｉ;
p=HFＭTree[c]、pａrｅnｔ;
wｈｉｌｅ（p!=-１)
{
ｉｆ(HFMTｒee［p]、lchild＝＝c）
cd、bit[cd、start]=0；
elｓe
