北邮第三次 哈夫曼树.docx
- 文档编号:4818513
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:18
- 大小:807.24KB
北邮第三次 哈夫曼树.docx
《北邮第三次 哈夫曼树.docx》由会员分享,可在线阅读,更多相关《北邮第三次 哈夫曼树.docx(18页珍藏版)》请在冰点文库上搜索。
北邮第三次哈夫曼树
数据结构实验报告
实验名称:
实验三-------哈夫曼树
学生姓名:
李雨薇
班级:
201221116
班内序号:
24
学号:
2012210178
日期:
2013年12月1日
1.实验要求
利用二叉树结构实现赫夫曼编/解码器。
基本要求:
1、初始化(Init):
能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立赫夫曼树
2、建立编码表(CreateTable):
利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出。
3、编码(Encoding):
根据编码表对输入的字符串进行编码,并将编码后的字符串输出。
4、译码(Decoding):
利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。
5、打印(Print):
以直观的方式打印赫夫曼树(选作)
6、计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。
测试数据:
IlovedataStructure,IloveComputer。
IwilltrymybesttostudydataStructure.
提示:
1、用户界面可以设计为“菜单”方式:
能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的
字符一律不用编码。
2.程序分析
2.1存储结构
(1)二叉树
template
classBiTree
{
public:
BiTree();//构造函数,其前序序列由键盘输入
~BiTree(void);//析构函数
BiNode
protected:
BiNode
};
//声明类BiTree及定义结构BiNode
Data:
二叉树是由一个根结点和两棵互不相交的左右子树构成。
二叉树中的结点具有相同数据类型及层次关系。
示意图:
root
lchildparentrchild
(2)静态三叉链表
structHNode//哈夫曼树的静态三叉链表
{
unsignedintweight;//结点权值
unsignedintparent;//双亲指针
unsignedintLchild;//左孩子指针
unsignedintRchild;//右孩子指针
};
示意图:
(3)编码表的节点结构
structHCode//字符及其编码结构
{
chardata;
charcode[100];
};
示意图:
2.2关键算法分析
一:
关键算法
(一)创建哈夫曼树
(1)算法自然语言
1.创建一个长度为2*letter-1的三叉链表
2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域,并将对应结点的孩子域和双亲域赋为空
3.从三叉链表的第n个结点开始,i=n
3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其下标x,y。
3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
3.3将下标为x的结点设置为i结点的左孩子,将下标为y的结点设置为i结点的右孩子,i结点的权值为x结点的权值加上y结点的权值,i结点的双亲设置为空
4.根据哈夫曼树创建编码表
(2)源代码
voidHuffman:
:
HTree()//建立哈弗曼树
{
LNode*p=lroot;
inti=0;
troot=newTNode[2*Letter-1];
while(p=p->next)//建立叶子节点
{
troot[i].weight=p->weight;
troot[i].Parent=-1;
troot[i].Lchild=-1;
troot[i].Rchild=-1;
i++;
};
for(inti=Letter;i<2*Letter-1;i++)
troot[i].Parent=-1;
intx,y,begin=0;//是两个最小值的角标
for(intj=Letter;j<2*Letter-1;j++)
{
while(troot[begin].Parent!
=-1)
begin++;
SelectMin(x,y,begin,j);
troot[j].weight=troot[x].weight+troot[y].weight;
troot[j].Lchild=x;
troot[j].Rchild=y;
troot[j].Parent=-1;
troot[x].Parent=j;
troot[y].Parent=j;
}
};
(3)时间复杂度
在选取两个权值最小的结点的函数中要遍历链表,时间复杂度为O(n),故该函数的时间复杂度为O(n^2)
(二)选择两个最小权值的函数
(1)算法自然语言
1.先暂时将前两个叶子结点作为权值最小的两个结点t1,t2
2.从第三个叶子结点开始,每一个结点的权值与t1,t2进行比较,如果此结点权值比t1权值要小,则将t1结点赋给t2,此结点赋给t1。
3.如果此结点权值比t2要小,此结点赋给t2。
4.每进行一次循环,总结点个数-1.(两个结点进行权值合并)
5.继续执行循环,直到循环到根结点,循环结束。
(2)源代码
voidHuffman:
:
SelectMin(int&x,int&y,intbegin,intend)//选择两个最小的
{
intt1,b,t2;//分别表示临时最小值、对应角标、从b开始比较
t1=troot[begin].weight,b=t2=begin;
for(;b { if(troot[b].weight { t1=troot[b].weight; t2=b; } } x=t2; troot[x].Parent=100;//临时为该最小的双亲赋值,防止再次被找出 if(t2! =begin)//判断最小是否是第一个 b=begin; else { b=begin; while(troot[++b].Parent! =-1); } t1=troot[b].weight;t2=b; for(;b { if(troot[b].weight { t1=troot[b].weight; t2=b; } } y=t2; }; (3)时间复杂度 在选取两个权值最小的结点的函数中要遍历链表,时间复杂度为O(n),故该函数的时间复杂度为O(n^2) (三)统计字符出现频度的代码 (1)算法自然语言 1.从第一个字符一直循环到终止符 2.查找链表中有没有该字符 3.如果有该字符,计数加1 4.如果没有该字符,创建节点 (2)源代码 voidHuffman: : List(chara[])//统计字符的频率 { LNode*p=lroot; inti=0;//第i个字符 while(a[i]! ='\0') { while(p&&p->ch! =a[i])//查找链表中没有该字符或者找到该字符 p=p->next; if(! p)//如果没有该字符,创建节点。 { p=newLNode; p->ch=a[i]; p->weight=1; p->next=lroot->next; lroot->next=p; Letter++; } else p->weight++; i++; p=lroot->next; }; }; (3)时间复杂度 若输入的字符串长度为n,则时间复杂度为O(n) (四)创建编码表 (1)算法自然语言 1.生成一个编码表 2.从终端结点开始,如果此结点是其父结点的左孩子,则标“0”;如果是其父结点的右孩子,则标“1”。 3.将父结点赋给孩子结点,并将新的孩子结点的父结点作为当前父结点,重复2操作。 4.继续循环,直到根结点,即不满足循环条件时,将编码表的最后一位置0. 5.将编码字符逆置。 将编码串的最后一位置换成新编码串的第一位,倒数第二位置换成新编码串的第二位,直到置换完毕。 6.将新的编码串重新赋给编码表。 (2)源代码 voidHuffman: : CreateTable()//建立码表,并将信息存在链表 { LNode*p=lroot;//letter inti=0,j,k;//将letter个字符都编码,与p相对应 while(p=p->next) { j=i,k=0; while(troot[j].Parent! =-1) { if(troot[troot[j].Parent].Lchild==j) p->code[k++]='0'; else p->code[k++]='1'; j=troot[j].Parent; } p->code[k]='\0'; reverse(p->code); i++; } } (3)时间复杂度 若输入的字符串长度为n,则时间复杂度为O(n)。 (五)编码算法 (1)算法自然语言 1.从字符串的起始位置开始,将每个字符与编码表中的字符进行比对。 2.当两字符相等时,输出编码表中字符对应的编码。 (2)源代码 voidHuffman: : Encoding() { intk=0;//输入字符串的脚标 LNode*p; while(astr[k]! ='\0')//所有字符编码完为止 { p=lroot; while((p=p->next)->ch! =astr[k]);//找到字符的码值为止 strcat(bstr,p->code); k++; } } (3)时间复杂度 设待编码字符串长度为n,编码表中字符个数为m,则复杂度为O(n*m)。 (六)解码算法 (1)算法自然语言 1.从根节点开始,如果编码串为0,则下溯到此结点的左孩子结点;如果编码串为1,则下溯到此结点的右孩子结点。 2.执行循环,直到不满足while循环条件,即追溯到叶子结点。 输出叶子结点的字符。 (2)源代码 voidHuffman: : Decoding()//解码函数 { cout<<"对码值"< cout<<"编码结果为: \t"; intk=0,parent=2*Letter-2; while(bstr[k]! ='\0')//码值读取结束 { if(bstr[k]=='0') parent=troot[parent].Lchild; else parent=troot[parent].Rchild; if(troot[parent].Lchild==-1) { LNode*p=lroot; for(inti=0;i p=p->next; cout< parent=2*Letter-2; } k++; } cout< } (3)时间复杂度 若输入的字符串长度为n,则时间复杂度为O(n)。 (七)计算压缩比函数 (1)算法自然语言 获得编码前字符串的长度,即其占用的字节数(float类型)。 1.获得编码后的字符串的长度,将其除以8,得到其占用的字节数(float类型)。 2.压缩比将两个相除。 (2)源代码 voidHuffman: : Calculate()//计算压缩率 { cout<<"*****************************************\n"; cout<<"编码前大小: "< cout<<"编码后大小: "< cout<<"压缩率为: "<<100*float(strlen(bstr))/strlen(astr)/8<<"%"< cout<<"*****************************************\n"; } (3)时间复杂度 时间复杂度为O (1)。 3.程序运行结果 3.1测试主函数流程: 流程图如图所示 3.2测试结果 4.总结 1、调试时出现的问题及解决方法 因为哈夫曼树编码老师上课讲了许多,照抄下来后,发现不能运行,之中产生很多Bug,后来上网查询了许多相关资料及程序代码,在理解了哈夫曼树的基础上,重新编写了代码.但是调试的发现输出结果和当初编码预期的不一致,后来采用设置断点,对变量添加监视,重复调试.最终达到了理想的程序结果. 2、心得体会 这是第三次实验编程,相比前两次实验的相对生疏来说,这次对于基本语句的运用差不多能熟练掌握。 而且老师在课上也讲了许多相应的哈夫曼树德编码.但是还是出现了不少的问题,比如在基本代码以及主程序敲定完成以后,编译并没有出现错误,但是一运行,编码就输出为无限循环,反复调试也找不出关键所在,后来与大神一起讨论一下程序代码,找到了错误,原来是循环条件写错,编码逆置和逆置后的代码重新赋给数组没有做到两层分别循环,导致整个语句块未能正常调用。 修改之后一切运行正常。 当一个人解决不了问题的时候,要懂得和他人交流讨论,在这之中不仅能解决问题,也能获得个人能力的提升. 这次实验,总结说来,让我更好地掌握了哈夫曼树的创建过程,了解了一种不等长编码的方法,用设断点调试的方法更加熟练,对C++更加熟悉。 3.下一步改进 可以直观输出哈夫曼树,但是打印树需要考虑到结点所在的层次和需要打印空格的个数,难度有点大。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北邮 第三次 哈夫曼树