



版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构哈夫曼编码实验报告毕业用资料 数据结构实验报告 实验五 简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验,阶段性实验时可以选择其中的几个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能: 1、接收原始数据。 从终端读入字符集大小 n,以及 n 个字符和 n 个权值,建立哈夫曼
2、树,并将它存于文件 nodedata.dat 中。 2、编码。 利用已建好的哈夫曼树(如不在内存,则从文件 nodedata.dat 中读入),对文件中的正文进行编码,然后将结果存入文件 code.dat 中。 3、译码。利用已建好的哈夫曼树将文件 code.dat 中的代码进行译码,结果存入文件 textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组 huffnode 保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有 n 个叶子结点的哈夫曼树共有 2
3、n-1 个结点,所以数组 huffnode 的大小设置为 2n-1,描述结点的数据类型为: typedef struct int weight;/结点权值 int parent; int lchild; int rchild; char inf; hnodetype; 2、求哈夫曼编码时使用一维结构数组 huffcode 作为哈夫曼编码信息的存储。 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的 0、1 序列,
4、因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位码,所以设计如下数据类型: #define maxbit 10 typedef struct int bitmaxbit; int start; hcodetype; 3、文件 nodedata.dat、code.dat 和 textfile.dat。 三、【功能(函数)设计】 1、初始化功能模块。 此功能模块的功能为从键盘接收字符集大小 n,以及 n 个字符和 n个权值。 2、建立哈夫曼树的功能模块。 此模块功能为使用 1 中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树,即将 huffnode 数组中的各个位置的
5、各个域都添上相关的值,并将这个结构体数组存于文件 hfmtree.dat 中。 3、建立哈夫曼编码的功能模块。 此模块功能为从文件 nodedata.dat 中读入相关的字符信息进行哈夫曼编码,然后将结果存入 code.dat 中,同时将字符与 0、1 代码串的一一对应关系打印到屏幕上。 4、译码的功能模块。 此模块功能为接收需要译码的 0、1 代码串,按照 3 中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件 textfile.dat,同时将翻译的结果在屏幕上打印输出。 四、【编码实现】 #includeiostream.h #includefstream.h #inclu
6、destring.h #includestdlib.h #define maxbit 10 #define maxvalue 100/应该大于权重之和 #define maxleaf 100 #define maxnode maxleaf*2-1 typedef struct int weight; int parent; int lchild; int rchild; char inf; hnodetype; struct hcodetype int bitmaxbit; int start; ; void creat_haffmantree(int n) hnodetype *haffno
7、de=new hnodetype2*n-1; int i,j; int m1,m2,x1,x2; for(i=0;i2*n-1;i+) haffnodei.weight=0; haffnodei.parent=-1; haffnodei.lchild=-1; haffnodei.rchild=-1; haffnodei.inf="0" for(i=0;in;i+) cout请输入字符endl; cinhaffnodei.inf; cout请输入该字符的权值endl; cinhaffnodei.weight; for(i=0;in-1;i+)/构造哈夫曼树 m1=m2=max
8、value; x1=x2=0; for(j=0;jn+i;j+)/选取最小和次小 if(haffnodej.parent=-1haffnodej.weightm1) m2=m1; x2=x1; m1=haffnodej.weight; x1=j; else if(haffnodej.parent=-1haffnodej.weightm2) m2=haffnodej.weight; x2=j; /将找出的最小和次小合并,创造其父母结点 haffnodex1.parent=n+i; haffnodex2.parent=n+i; haffnoden+i.weight=haffnodex1.weigh
9、t+haffnodex2.weight; haffnoden+i.lchild=x1; haffnoden+i.rchild=x2; haffnoden+i.inf=null; cout显示存储的哈弗曼树信息:endl; cout权值 左孩子 右孩子 双亲endl; for(i=0;i2*n-1;i+) couthaffnodei.weight ; couthaffnodei.lchild ; couthaffnodei.rchild ; couthaffnodei.parent ; couthaffnodei.infendl; /写入文件 fstream outfile1; outfile1
10、.open(e:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件 if(!outfile1) /没有创建成功则显示相应信息 coutnodedata.dat 文件不能打开endl; abort(); for(i=0;i2*n-1;i+) /将内存中从 haffnodei地址开始的sizeof(haffnodei)的内容写入文件中 outfile1.write(char*)haffnodei,sizeof(haffnodei); outfile1.close ();/关闭文件 delete haffnode; void haffcode(
11、int n)/哈夫曼编码 hnodetype *haffnode=new hnodetypemaxnode; hcodetype *haffcode=new hcodetypemaxleaf; hcodetype cd; int i,j,c,p; fstream in(e:nodedata.dat,ios:in|ios:binary); in.read(char*)haffnode,(2*n-1)*sizeof(hnodetype); in.close(); fstream outfile; outfile.open(e:codedata.dat,ios:out|ios:binary);/建立
12、进行写入的文件 for(i=0;in;i+) cd.start=n-1; c=i; p=haffnodec.parent; while(p!=-1) if(haffnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=haffnodec.parent; for(j=cd.start+1;jn;j+) haffcodei.bitj=cd.bitj; haffcodei.start=cd.start; for(i=0;in;i+) outfilehaffnodei.inf; for(j=haffcode
13、i.start+1;jn;j+) outfilehaffcodei.bitj; cout字符信息-编码信息endl; for(i=0;in;i+) couthaffnodei.inf-; for(j=haffcodei.start+1;jn;j+) couthaffcodei.bitj; coutendl; outfile.close (); cout请输入要编码的字符串,基本元素为(; for(i=0;in;i+) couthaffnodei.inf,; cout)endl; char inf100; cininf; int f=strlen(inf); fstream outfile1;
14、outfile1.open(e:code.dat,ios:out|ios:binary);/ 建立进行写入的文件 if(!outfile1) coutcode.dat 文件不能打开!endl; abort(); else coutendl; cout字符串编码后为:; for(int x=0;xf;x+) for(i=0;in;i+) if(infx=haffnodei.inf) for(j=haffcodei.start+1;jn;j+) outfile1.write(char*)haffcodei.bitj,sizeof(haffcodei.bitj); couthaffcodei.bit
15、j; coutendl; cout编译后的代码串已经存入 code.dat 文件中!endl; coutendl; outfile1.close(); delete haffnode; delete haffcode; void decode( int n)/解码 int i; hnodetype *haffnode=new hnodetype2*n-1; fstream infile1; infile1.open(e:nodedata.dat,ios:in|ios:binary);/读出哈夫曼树 if(!infile1) coutnodedata.dat 文件不能打开endl; abort(
16、); for(i=0;i2*n-1;i+) infile1.read(char*)haffnodei,sizeof(hnodetype); infile1.close(); int tempcode100; int num=0; for(i=0;i100;i+) tempcodei=-1; hcodetype *code=new hcodetypen; fstream infile2;/读编码 infile2.open(e:code.dat,ios:in|ios:binary); while(!infile2.eof() infile2.read(char*)tempcodenum,sizeo
17、f(tempcodenum); num+; infile2.close(); num-; cout从文件中读出的编码为endl; for(i=0;inum;i+) couttempcodei; coutendl; int m=2*n-2; i=0; coutendl; cout译码后为:endl; fstream outfile; outfile.open(e:textfile.txt,ios:out); if(!outfile) couttextfile.txt 文件不能打开!endl; abort(); while(inum)/ 小于字符串的长度 while(haffnodem.lchil
18、d!=-1haffnodem.rchild!=-1) if(tempcodei=0) m=haffnodem.lchild; i+; else if(tempcodei=1) m=haffnodem.rchild; i+; couthaffnodem.inf; outfilehaffnodem.inf; m=2*n-2; coutendl; outfile.close(); cout译码后的结果已经存入 textfile.txt 中!endl; delete haffnode; int main() int n; cout* 欢 迎 进 入 编 / 译 码 系 统 !*endl; int ch1; do cout 1.建树endl; cout 2:编码,并显示字符和对应的编码endl; cout 3:译码endl; cout 0:退出endl; cout*endl; cout请选择(03):; cinch1; while(!(ch1=3ch1=0) /输入不在 0 到 4 之间无效 cout数据输入错误,请重新选择(04):; cinch1; switch(ch1) case 1: coutttt请输入编码个数endl;/叶子结点个数 cinn; creat_haffmantree(n); break; case 2: haffcode(n); br
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 上海市浦东实验2025届高一化学第二学期期末检测试题含解析
- 上海市上戏附中2025届高一下化学期末教学质量检测模拟试题含解析
- 农机中心制度管理办法
- 合肥建设行业管理办法
- 殡葬服务租赁管理办法
- 村级代管资金管理办法
- 超高压挤包直流电缆绝缘系统技术难点及解决方案研究
- 华为薪资待遇管理办法
- 数据安全策略-第2篇-洞察及研究
- 脚手架施工方案:高空作业安全
- ASTM-D3359-(附著力测试标准)-中文版
- 石嘴山市直机关遴选公务员笔试真题2022
- 吉林省吉林市亚桥中学2023-2024学年七年级下学期期末考试数学试卷
- 贵州省贵阳市南明区2023-2024学年四年级下学期期末数学质量监测
- DL-T5706-2014火力发电工程施工组织设计导则
- 2024-2030年殷瓦钢行业市场现状供需分析及重点企业投资评估规划分析研究报告
- 第一目击者理论考试题题库110题
- 2024年县乡教师选调进城考试《教育学》题库附答案【综合卷】
- 2022智慧健康养老服务与管理专业人才培养调研报告
- 机动车驾驶员安全教育培训课件
- 三坐标检测报告样本
评论
0/150
提交评论