哈夫曼树 实验报告
更新时间:2023-09-26 09:29:01 阅读量: 综合文库 文档下载
- 哈夫曼树推荐度:
- 相关推荐
计算机科学与技术学院 数据结构 实验报告
班级 2014级计算机1班 学号 20144138021 姓名 张建华 成绩 实验项目 简单哈夫曼编/译码的设计与实现 实验日期 2016.1.5
一、实验目的
本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。
二、实验问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能:
1、接收原始数据。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmtree.dat中。
2、编码。
利用已建好的哈夫曼树(如不在内存,则从文件hfmtree.dat中读入),对文件中的正文进行编码,然后将结果存入文件codefile.dat中。
3、译码。
利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码,结果存入文件textfile.dat中。
4、打印编码规则。
即字符与编码的一一对应关系。 5、打印哈夫曼树,
将已在内存中的哈夫曼树以直观的方式显示在终端上。
三、实验步骤 1、实验问题分析
1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,描述结点的数据类型为:
Typedef strcut {
Int weight;/*结点权值*/ Int parent; Int lchild; Int rchild; }HNodeType;
2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位码,所以设计如下数据类型:
#define MAXBIT 10
共 页 第 页
Typedef struct {
Int bit[MAXBIT]; Int start; }HCodeType;
3、文件hfmtree.dat、codefile.dat和textfile.dat。
2、功能(函数)设计 (1)、初始化功能模块。 此功能模块的功能为从键盘接收字符集大小n,以及n个字符和n个权值。 (2)、建立哈夫曼树的功能模块。
此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树,即将HuffNode数组中的各个位置的各个域都添上相关的值,并将这个结构体数组存于文件hfmtree.dat中。 (3)、建立哈夫曼编码的功能模块。
此模块功能为从文件hfmtree.dat中读入相关的字符信息进行哈夫曼编码,然后将结果存入codefile.dat中,同时将字符与0、1代码串的一一对应关系打印到屏幕上。 (4)、译码的功能模块。
此模块功能为接收需要译码的0、1代码串,按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件textfile.dat,同时将翻译的结果在屏幕上打印输出。 (5)、打印哈夫曼树的功能模块。 此模块功能为从HuffNode数组中读入相关的结点信息,以图形的方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的1画出来。
四、实验结果(程序)及分析
1、实验主要代码
typedef struct /*结点结构体*/ {
string hfmstr; /*结点内容*/ int weight; /*结点权值*/ int parent; int lchild; int rchild; }HNodeType;
typedef struct /* 编码结构体 */ {
int bit[MAXBIT]; int start; }HCodeType;
void Create_HuffMTree(HNodeType HFMTree[],int n) /*创建哈夫曼树*/ {
int m1,x1,m2,x2; int i,j;
for(i=0;i<2*n-1;i++)
共 页 第 页
{
HFMTree[i].hfmstr=\ HFMTree[i].weight=0; HFMTree[i].parent=-1; HFMTree[i].lchild=-1; HFMTree[i].rchild=-1; }
for(i=0;i cout<<\请输入第\个权值\ cin>>HFMTree[i].weight; cout<<\请输入对应字符\ cin>>HFMTree[i].hfmstr; } for(i=0;i x1=x2=MAXVALUE; m1=m2=0; for(j=0;j if(HFMTree[j].parent==-1&&HFMTree[j].weight x2=x1; m2=m1; x1=HFMTree[j].weight; m1=j; } else if(HFMTree[j].parent==-1&&HFMTree[j].weight x2=HFMTree[j].weight; m2=j; } } HFMTree[m1].parent=n+i; HFMTree[m2].parent=n+i; HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight; HFMTree[n+i].lchild=m1; HFMTree[n+i].rchild=m2; } cout<<\创建哈夫曼树成功!\} void HaffmanCode(HNodeType HFMTree[],HCodeType HuffCode[],int n) /*{ HCodeType cd; int i,j,c,p; for(i=0;i 共 页 第 页 构建哈夫曼编码*/ { cd.start=n-1; c=i; p=HFMTree[c].parent; while(p!=-1) { if(HFMTree[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HFMTree[c].parent; } for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; } } void decodeing(char string[],HNodeType HFMTree[],int n) /*解码*/ { int i,tmp=0,code[1024]; int m=2*n-1; char *nump; char num[1024]; for(i=0;i if(string[i]=='0') num[i]=0; else num[i]=1; } i=0; nump=&num[0]; while(nump<(&num[strlen(string)])) { tmp=m-1; while((HFMTree[tmp].lchild!=-1)&&(HFMTree[tmp].rchild!=-1)) { if(*nump==0) { tmp=HFMTree[tmp].lchild ; } else tmp=HFMTree[tmp].rchild; 共 页 第 页 nump++; } cout< cout< 2、测试数据与输出 共 页 第 页
正在阅读:
哈夫曼树 实验报告09-26
美在其中作文700字07-05
检验科SOP文件编写06-07
湖南大学操作系统作业(3) - 图文11-04
重症监护室(NICU)发展纪要11-14
六下数集体备课 - 图文05-01
落实德育课情况说明09-15
宏事达电子称重仪表T100S中文说明书04-30
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 哈夫曼
- 实验
- 报告
- 《长方体的表面积》教学设计
- 工程项目招投标与合同管理 - 自学考试课本课后习题汇集
- 山门学区“领雁工程”骨干教师培训人员名单(17人)
- 交通工程试题(03)
- 冬瓜凹煤矿安全生产攻坚实施方案
- 韩礼德:系统功能语法导读
- 煤矿雨季三防试题
- 多媒体能帮助实现课堂教学的
- office2007全部快捷键
- 2011年资产评估师考试《资产评估》模拟试题(1)-中大网校
- 环境监测与评价考卷及答案
- 大学体验英语综合教程1(第二版)课后答案
- 2014运动会开幕式主持词
- 电工电子复习题
- 动物解剖学试题
- 山西省孝义市2018届高三数学下学期一模考试试题理(含解析)(1)
- 发展心理学历年真题及答案解析(三级)
- 齐乡学校—第一封给陌生人的信
- 电信本地网线路维护管理办法
- 奶牛全混合日粮