哈夫曼树及其操作数据结构实验报告2.docx
《哈夫曼树及其操作数据结构实验报告2.docx》由会员分享，可在线阅读，更多相关《哈夫曼树及其操作数据结构实验报告2.docx（18页珍藏版）》请在冰点文库上搜索。
哈夫曼树及其操作数据结构实验报告2
电子科技大学
实验报告
课程名称：
数据结构与算法
学生：
*浩
学号：
*************
点名序号：
***
指导教师：
钱**
实验地点：
基础实验大楼
实验时间：
2015.5.7
2014-2015-2学期
信息与软件工程学院
实验报告
（二）
学生：
**浩学号：
*************指导教师：
钱**
实验地点：
科研教学楼A508实验时间：
2015.5.7
一、实验室名称：
软件实验室
二、实验项目名称：
数据结构与算法—树
三、实验学时：
4
四、实验原理：
霍夫曼编码（HuffmanCoding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。
1952年，DavidA.Huffman在麻省理工攻读博士时所发明的。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
例如，在英文中，e的出现机率最高，而z的出现概率则最低。
当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。
用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。
二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。
倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。
树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。
可以证明霍夫曼树的WPL是最小的。
五、实验目的：
本实验通过编程实现赫夫曼编码算法，使学生掌握赫夫曼树的构造方法，理解树这种数据结构的应用价值，并能熟练运用C语言的指针实现构建赫夫曼二叉树，培养理论联系实际和自主学习的能力，加强对数据结构的原理理解，提高编程水平。
六、实验容：
（1）实现输入的英文字符串输入，并设计算法分别统计不同字符在该字符串中出现的次数，字符要区分大小写；
（2）实现赫夫曼树的构建算法；
（3）遍历赫夫曼生成每个字符的二进制编码；
（4）显示输出每个字母的编码。
七、实验器材（设备、元器件）：
PC机一台，装有C或C++语言集成开发环境。
八、数据结构与程序：
/*******************************************************************
***程序名称：
哈夫曼树的相关操作*
***程序容：
生成哈夫曼树及其编码表、对字符串进行编码等*
***编写作者：
家浩*
***完成时间：
2015.5.15*
*******************************************************************/
#include
#include
#include
#defineMAXSIZE10000
charfile_address[100];//全局通用文件地址
typedefstructhnode//哈夫曼树的节点结构定义
{
intweight;
intlchild,rchild,parent;
}THNode,*TpHTree;
typedefstructhuffman_code//哈夫曼编码表的元素结构定义
{
intweight;//编码对应的权值
char*pcode;//指向编码字符串的指针
}THCode,*TpHcodeTab;
//*************************************************************
//****声明函数
//*************************************************************
TpHcodeTabbuild_codesheet（TpHTreepht,intleaves_num）;
//根据哈夫曼树得到编码表
TpHTreecreate_huffman_tree（intweights[],intn）;//构造哈夫曼树
voidselect_mintree（TpHTree,int,int*,int*）;//从森林中选择权值最小的两棵子树
voiddestroy_codesheet（TpHcodeTabcodesheet,intn）;//销毁哈夫曼编码表
intread_file（charfile_address[100],char*message）;//从文本文件读入字符串
intcalc_freq（chartext[],int**freq,char**dict,intn）;//统计字符串text中字符出现的频率
//*************************************************************
//****主函数
//*************************************************************
intmain（void）
{
inti,msg_num,choose;
chars;//清空缓存
intleaves_num=0;
do
{
TpHTreepht=NULL;//建立树根
TpHcodeTabcodesheet;//建立编码表
charmsg[MAXSIZE];//建立信息数组
int*weights=NULL;//建立频率数组
char*dict=NULL;//建立字符数组
printf（"--------\n""----------哈夫曼树----------\n""--------"）;
printf（"\n读取文件还是手动输入信息？
\n""1：
手动输入信息\n""2：
读取文件\n""请选择：
"）;
scanf（"%d",&choose）;
if（choose==1）
{
printf（"请输入信息：
\n"）;
scanf（"%c",&s）;//清理键盘缓存
gets（msg）;
msg_num=strlen（msg）;
}
else
{
printf（"输入文件地址（例如：
F:
\\\\filename.txt）:
\n"）;
scanf（"%c",&s）;//清理键盘缓存
gets（file_address）;//输入文件地址
msg_num=read_file（file_address,msg）;//读取文本文件
}
leaves_num=calc_freq（msg,&weights,&dict,msg_num）;//统计文本串中的字符频率，同时得到哈夫曼树的叶节点数
pht=create_huffman_tree（weights,leaves_num）;//创建哈夫曼树
codesheet=build_codesheet（pht,leaves_num）;//构造哈夫曼编码表
printf（"\n---字符频率编码表---\n"）;
printf（"符号--频率--编码\n"）;
for（i=0;iprintf（"%4c--%-3d--%-6s\n",dict[i],codesheet[i].weight,codesheet[i].pcode）;
printf（"--------------------\n"）;
destroy_codesheet（codesheet,leaves_num）;//销毁哈夫曼编码表
if（pht）//释放所有临时空间
free（pht）;
if（dict）
free（dict）;
if（weights）
free（weights）;
printf（"\n\t0：
结束\n\t1：
继续\n""\t请选择：
"）;
scanf（"%d",&choose）;
}while（choose）;
return0;
}
//*************************************************************
//****构造哈夫曼编码表
//*************************************************************
TpHcodeTabbuild_codesheet（TpHTreepht,intleaves_num）
{
inti,cid,pid,cursor,len;
TpHcodeTabsheet;
char*pch=（char*）malloc（leaves_num+1）;
if（!
pch）{
printf（"申请空间失败！
"）;
exit（0）;
}
memset（pch,0,（leaves_num+1））;//清零新分配的空间
sheet=（TpHcodeTab）malloc（sizeof（THCode）*leaves_num）;
if（!
sheet）
{
printf（"申请编码表存空间失败！
"）;
exit（0）;
}
for（i=0;isheet[i].weight=pht[i].weight;
}
for（i=0;i{
cursor=leaves_num;
cid=i;
pid=pht[cid].parent;
while（pid!
=-1）//不为根节点
{
if（pht[pid].lchild==cid）
pch[--cursor]='0';//左分支编码为'0'
else
pch[--cursor]='1';//右分支编码为'1'
cid=pid;
pid=pht[cid].parent;
}
len=leaves_num-cursor+1;
sheet[i].pcode=（char*）malloc（len）;
if（!
sheet[i].pcode）
{
printf（"为节点%d的编码申请存空间失败！
",i）;
exit（0）;
}
memset（sheet[i].pcode,0,len）;
strncpy（sheet[i].pcode,&pch[cursor],strlen（&pch[cursor]））;
}
free（pch）;
returnsheet;
}
//*************************************************************
//****构造哈夫曼树
//*************************************************************
TpHTreecreate_huffman_tree（intweights[],intn）
{
TpHTreepht;
intminA,minB;//用于保存权值最小的两棵子树的序号
inti,a=0;
if（n<1）{
printf（"没有叶子节点！
\n"）;
return0;
}
a=（2*n）-1;
pht=（TpHTree）malloc（sizeof（THNode）*a）;
if（!
pht）
{
printf（"分配数组空间失败！
\n"）;
exit（0）;
}
for（i=0;i{
pht[i].weight=（iweights[i]:
0;
pht[i].lchild=-1;
pht[i].rchild=-1;
pht[i].parent=-1;
}
for（i=n;i{
select_mintree（pht,（i-1）,&minA,&minB）;
pht[minA].parent=i;
pht[minB].parent=i;
pht[i].lchild=minA;
pht[i].rchild=minB;
pht[i].weight=pht[minA].weight+pht[minB].weight;
}
returnpht;
}
//*************************************************************
//****选出权值最小的两棵子树
//*************************************************************
voidselect_mintree（TpHTreepht,intn,int*minA,int*minB）
{
intid,min1=-1,min2=-1;//最小值，次小值
intmaxa=10000,maxb=10000;
for（id=0;id<=n;id++）{
if（pht[id].parent==-1）{
if（pht[id].weight{
min2=min1;
min1=id;
maxa=pht[id].weight;
}
elseif（pht[id].weight{
min2=id;
maxb=pht[id].weight;
}
}
}
*minA=min1;
*minB=min2;
return;
}
//*************************************************************
//****销毁哈夫曼编码表
//*************************************************************
voiddestroy_codesheet（TpHcodeTabsheet,intn）
{
inti;
for（i=0;ifree（sheet[i].pcode）;
free（sheet）;
return;
}
//*************************************************************
//****读取文本文件
//*************************************************************
intread_file（charfile_address[100],char*message）
{
intstr_len;//字符串长度
FILE*pFile=NULL;
pFile=fopen（file_address,"r"）;//打开文件
if（!
pFile）
{
printf（"打开文件失败!
\n"）;
exit（0）;
}
else{
printf（"打开文件成功!
\n"）;
}
memset（message,0,MAXSIZE）;//清除缓冲
if（fgets（message,MAXSIZE,pFile）==NULL）
{
printf（"fgetserror\n"）;
exit（0）;
}
else{
printf（"成功读取文件，容如下：
\n%s\n",message）;
}
str_len=strlen（message）;
fclose（pFile）;
returnstr_len;
}
//*************************************************************
//****统计字符出现的频率
//*************************************************************
intcalc_freq（chartext[],int**freq,char**dict,intn）//n为字符串长度
{
inti,k;
intchar_num=0;
int*chars;//不同种类的字符
char*fre;//字符的出现频率
inttimes[256]={0};
for（i=0;itimes[text[i]]++;
for（i=0;i<256;i++）//不同字符的个数
if（times[i]>0）
char_num++;
chars=（int*）malloc（sizeof（int）*char_num）;
if（!
chars）
{
printf（"为频率数组分配空间失败！
\n"）;
exit（0）;
}
fre=（char*）malloc（sizeof（char）*char_num）;
if（!
fre）
{
printf（"为字符数组分配空间失败！
\n"）;
exit（0）;
}
k=0;
for（i=0;i<256;++i）
{
if（times[i]>0）
{
chars[k]=times[i];
fre[k]=（char）i;
k++;
}
}
*freq=chars;
*dict=fre;
returnchar_num;//不同种类的字符个数
}
九、程序运行结果：
一、手动输入信息
二、从文件读取信息
十、实验结论：
本实验通过编程实现赫夫曼编码算法，在实验中掌握了赫夫曼树的构造方法，理解了树这种数据结构的应用价值，并且已经能够熟练运用指针实现构建赫夫曼二叉树，理论联系实际和自主学习的能力得到了培养，对数据结构的原理理解更加深刻，也提高了编程水平。
十一、总结及心得体会：
1、虽然算法很多事现有的，可以用来做参考，不宜照抄。
2、使用指针存储信息之前应为其分配存空间；
3、scanf（）函数读取到空格会自动停止，而gets（）函数读取到回车即停止；
4、需要读取单个字符时要考虑到键盘的缓冲区；
5、双重指针的问题应特别注意；
6、文件地址如果输入错误的解决方案没有考虑到；
7、申请了存的空间应该在程序结束时进行释放，否则可能造成空间浪费；
8、应养成对代码进行注释的习惯，不久之后可能自己的程序自己都不知道是什么意思；
9、实验是培养独立思考、作业的过程，要多思考，不应过多依赖他人。
升级会员 