![点击分享此内容可以赚币 分享](/master/images/share_but.png)
数据结构哈夫曼编码实验报告.doc
《数据结构哈夫曼编码实验报告.doc》由会员分享,可在线阅读,更多相关《数据结构哈夫曼编码实验报告.doc(15页珍藏版)》请在咨信网上搜索。
1、(完整word版)数据结构哈夫曼编码实验报告数据结构实验报告 实验五 简单哈夫曼编/译码的设计与实现本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验,阶段性实验时可以选择其中的几个功能来设计和实现。一、【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能:1、接收原始数据。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于
2、文件nodedata.dat中。2、编码。利用已建好的哈夫曼树(如不在内存,则从文件nodedata.dat中读入),对文件中的正文进行编码,然后将结果存入文件code.dat中。3、译码。利用已建好的哈夫曼树将文件code.dat中的代码进行译码,结果存入文件textfile.dat中。4、打印编码规则。即字符与编码的一一对应关系。二、【数据结构设计】1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,
3、描述结点的数据类型为:typedef struct int weight;/结点权值int parent;int lchild;int rchild;char inf;HNodeType;2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位码,所以设计如下数据
4、类型:#define MAXBIT 10typedef structint bitMAXBIT;int start;HcodeType;3、文件nodedata.dat、code.dat和textfile.dat。三、【功能(函数)设计】1、初始化功能模块。此功能模块的功能为从键盘接收字符集大小n,以及n个字符和n个权值。2、建立哈夫曼树的功能模块。此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树,即将HuffNode数组中的各个位置的各个域都添上相关的值,并将这个结构体数组存于文件hfmtree.dat中。3、建立哈夫曼编码的功能模块。此模块功能为从文件nodedat
5、a.dat中读入相关的字符信息进行哈夫曼编码,然后将结果存入code.dat中,同时将字符与0、1代码串的一一对应关系打印到屏幕上。4、译码的功能模块。此模块功能为接收需要译码的0、1代码串,按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件textfile.dat,同时将翻译的结果在屏幕上打印输出。四、【编码实现】 #include#include#include#include#define MaxBit 10#define Maxvalue 100/应该大于权重之和#define Maxleaf 100#define Maxnode Maxleaf*2-1typed
6、ef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxBit;int start;void Creat_Haffmantree(int &n)HNodeType *HaffNode=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=
7、-1;HaffNodei.inf=0;for(i=0;in;i+)cout请输入字符HaffNodei.inf;cout请输入该字符的权值HaffNodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)/选取最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=HaffNodej.weight
8、;x2=j;/将找出的最小和次小合并,创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+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 ;
9、coutHaffNodei.rchild ; coutHaffNodei.parent ; coutHaffNodei.infendl;/写入文件fstream outfile1;outfile1.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 哈夫曼 编码 实验 报告
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。