哈夫曼编码与译码 数据结构实验.docx
《哈夫曼编码与译码 数据结构实验.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码 数据结构实验.docx（14页珍藏版）》请在冰点文库上搜索。
哈夫曼编码与译码数据结构实验
实验报告
May21
2015
姓名：
陈斌学号：
E11314079专业：
13计算机科学与技术
数据结构第四次实验
学号E********专业计算机科学与技术姓名陈斌
实验日期2015.05.21教师签字成绩
实验报告
【实验名称】哈夫曼编/译码
【实验目的】
掌握哈弗曼编/译码算法。
1.掌握Huffman树的概念、特点和存储结构；
2.掌握Huffman树的构造方法；
3.学会灵活运用Huffman树解决编码问题。
【实验内容】
1.必做内容
哈夫曼编码
【问题描述】
某报文中共出现n个字符，各字符出现频度依次为w1,w2,…,wn。
要求设计一个不等长的编码方案，输出每个字符对应的编码，使得该编码系统的空间效率最好。
要求字符个数和相应的权值要从终端输入。
源代码：
head.h:
#include
#include
#include//malloc（）
#include//INT,MAX
#include//EOF,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/
/*求赫夫曼编码。
实现算法6.12的程序*/
intmin1（HuffmanTree&t,inti）
{/*函数voidselect（）调用*/
intj,flag;
unsignedintk=UINT_MAX;/*取k为不小于可能的值*/
for（j=1;j<=i;j++）
if（t[j].weightk=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
voidSelect（HuffmanTree&t,inti,int&s1,int&s2）
{/*s1为最小的两个值对应结点权值小的那个*/
intj;
s1=min1（t,i）;
s2=min1（t,i）;
if（t[s1].weight>t[s2].weight）
{
j=s1;
s1=s2;
s2=j;
}
}
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,int*w,intn）/*算法6.12*/
{/*w存放n个字符的权值（均>0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,s1,s2,start;
unsignedc,f;
HuffmanTreep;
char*cd;
if（n<=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/
for（p=HT+1,i=1;i<=n;++i,++p,++w）
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for（;i<=m;++i,++p）
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for（i=n+1;i<=m;++i）/*建赫夫曼树*/
{/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/
Select（HT,i-1,s1,s2）;
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/*从叶子到根逆向求每个字符的赫夫曼编码*/
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
/*分配n个字符编码的头指针向量（[0]不用）*/
cd=（char*）malloc（n*sizeof（char））;/*分配求编码的工作空间*/
cd[n-1]='\0';/*编码结束符*/
for（i=1;i<=n;i++）
{/*逐个字符求赫夫曼编码*/
start=n-1;/*编码结束符位置*/
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
/*从叶子到根逆向求编码*/
if（HT[f].lchild==c）
cd[--start]='0';
else
cd[--start]='1';
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
/*为第i个字符编码分配空间*/
strcpy（HC[i],&cd[start]）;/*从cd复制编码（串）到HC*/
}
free（cd）;/*释放工作空间*/
}
voidmain（）
{
intn;
HuffmanTreeHT;
HuffmanCodeHC;
do
{
cout<<"请输入权值的个数（n>1）:
n=";
cin>>n;
}while（n<=1）;
int*w=（int*）malloc（n*sizeof（int））;
cout<<"请依次输入"<"<for（inti=0;i<=n-1;i++）
cin>>*（w+i）;
HuffmanCoding（HT,HC,w,n）;
cout<<"赫夫曼编码为:
"<for（i=1;i<=n;i++）
cout<<*（w+i-1）<<"\t:
"<}
运行结果：
赫夫曼树的形状为：
2.选做内容
哈夫曼译码
【问题描述】
在前面必做内容的基础上，实现哈弗曼译码算法，对给定的一组编码（要求从终端输入），译出其对应的报文部分。
源代码：
head.h:
#include
#include
#include//malloc（）
#include//INT,MAX
#include//EOF,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
#definemaxsize100//哈夫曼编码的最大位数
typedefstruct
{
charch;
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/
/*求赫夫曼编码。
实现算法6.12的程序*/
intmin1（HuffmanTree&t,inti）
{/*函数voidselect（）调用*/
intj,flag;
unsignedintk=UINT_MAX;/*取k为不小于可能的值*/
for（j=1;j<=i;j++）
if（t[j].weightk=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
voidSelect（HuffmanTree&t,inti,int&s1,int&s2）
{/*s1为最小的两个值对应结点权值小的那个*/
intj;
s1=min1（t,i）;
s2=min1（t,i）;
if（t[s1].weight>t[s2].weight）
{
j=s1;
s1=s2;
s2=j;
}
}
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,char*ch,int*w,intn）/*算法6.12修改*/
{/*w存放n个字符的权值（均>0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,s1,s2,start;
unsignedc,f;
HuffmanTreep;
char*cd;
if（n<=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/
for（p=HT+1,i=1;i<=n;++i,++p,++w,++ch）
{
p->ch=*ch;
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for（;i<=m;++i,++p）
{
p->ch='0';
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for（i=n+1;i<=m;++i）/*建赫夫曼树*/
{/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/
Select（HT,i-1,s1,s2）;
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/*从叶子到根逆向求每个字符的赫夫曼编码*/
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
/*分配n个字符编码的头指针向量（[0]不用）*/
cd=（char*）malloc（n*sizeof（char））;/*分配求编码的工作空间*/
cd[n-1]='\0';/*编码结束符*/
for（i=1;i<=n;i++）
{/*逐个字符求赫夫曼编码*/
start=n-1;/*编码结束符位置*/
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
/*从叶子到根逆向求编码*/
if（HT[f].lchild==c）
cd[--start]='0';
else
cd[--start]='1';
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
/*为第i个字符编码分配空间*/
strcpy（HC[i],&cd[start]）;/*从cd复制编码（串）到HC*/
}
free（cd）;/*释放工作空间*/
}
voidHuffmanDecoding（HuffmanTree&HT,intn）//依次读入电文，根据哈夫曼树译码
{
inti,j=0,k=0,flag=0;
charc[maxsize]="\0";
charb[maxsize];
charendflag='2';//电文结束标志取2
i=2*n-1;//从根结点开始往下搜索
printf（"请输入译码（以'2'为结束标志）:
"）;
gets（b）;
while（b[j]!
='2'）
{
if（b[j]=='0'）
i=HT[i].lchild;//走向左孩子
elseif（b[j]=='1'）
i=HT[i].rchild;//走向右孩子
else
{
cout<<"输入译码有错."<flag=1;
break;
}
if（HT[i].lchild==0）//HT[k]是叶结点
{
c[k++]=HT[i].ch;
c[k]='\0';
i=2*n-1;
}
j++;
}
if（HT[i].lchild!
=0&&i!
=2*n-1&&b[j]=='2'）//译码读完，但尚未到叶子结点
cout<<"输入译码有错."<elseif（flag==0）
{
printf（"译码对应的报文为:
"）;
puts（c）;
}
}
voidmain（）
{
intn;
HuffmanTreeHT;
HuffmanCodeHC;
do
{
cout<<"请输入权值的个数（n>1）:
n=";
cin>>n;
}while（n<=1）;
int*w=（int*）malloc（n*sizeof（int））;
char*c=（char*）malloc（n*sizeof（char））;
cout<<"请依次输入"<"<for（inti=0;i<=n-1;i++）
{
printf（"输入第%d个字符和权值:
",i+1）;
scanf（"%c%d",c+i,w+i）;
getchar（）;
}
HuffmanCoding（HT,HC,c,w,n）;
cout<<"赫夫曼编码为:
"<for（i=1;i<=n;i++）
cout<<*（c+i-1）<<"\t:
"<cout<<"\n下面进行赫夫曼译码---->"<HuffmanDecoding（HT,n）;//依次读入电文，根据哈夫曼树译码
}
运行结果：
下面为译码输入错误的情况：
【小结或讨论】
通过本次实验，掌握了Huffman树的概念、特点和存储结构；并且掌握了Huffman树的构造方法；还学会了运用Huffman树解决编码问题。
能够用Huffman树实现编码和译码的功能。
必做内容里，用每个字符对应的权值代替了该字符，因为在定义Huffman树的存储结构时，没有添加存储字符的数据域。
这一点在选作内容里做了修改，可以在创建Huffman树的时候将权值连同字符一起输入。
在译码过程中，可能面对输入的译码有错的情况，这时候要添加程序段判断是何种出错类型，并作出相应处理操作。
比如有可能只输入了某个字符编码的前几位，这时候不能从Huffman树根结点访问到叶子结点，输入有错。
还有一种情况，就是输入的译码前面的部分是正确的，但是后面出错了，这时候整个译码是错误的，不用将前面正确的报文输出，所以程序中定义了一个char型数组用来存放翻译过的译文，如果译文结束了都没有出错，就将该数组里面的内容输出，否则不输出。
这里，在向char型数组里存放报文的时候，每存入一个就将该报文的下一个存储位置置为’\0’，以保证最后输出的全是译码对应的报文。
程序中是以字符’2’作为结束标记的，也可以以其他字符作为结束标记。
升级会员 