版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、PAGE 第7页 共7页数据结构 实验报告20112012学年 第 * 学期 *级 * 专业班级: * 学号: * 姓名: * 实验三 树的应用实验题目:树的应用哈夫曼编/译码实验内容:利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入字符及权值的基础上求哈夫曼编码。要求:从键盘输入字符集(字母az,空格)共27个字符,以及出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,并输出数组ht的初态和终态。对各个字符进行哈夫曼编码,打印输出字符及对应的哈夫曼编码。编码:从键盘输入字符串,利用已建好的哈夫曼编码,实现
2、该字符串的编码。(选作)译码:从键盘输入二进制串,利用已建好的哈夫曼编码,将二进制串还原为字符串。三、程序源代码:#include #include #include typedef structchar data;/结点值float weight;/权重int parent;/双亲结点int lchild;/左孩子结点int rchild;/右孩子节点HTNode;typedef structchar cd27;/各个字符的哈夫曼编码int start;/各个字符的哈夫曼编码的起始下标HCode;void CreateHT(HTNode ht,int n)/构建哈夫曼树int i,k,lno
3、de,rnode;char str27;float s27;cout请输入空格和26个字母:endl;gets(str);cout请分别输入这27个字符的权重:endl;for(i=0;isi;float min1,min2;for(i=0;in;i+)hti.data=stri;hti.weight=si;for(i=0;i2*n-1;i+)/所有结点的相关域置初值-1hti.parent=hti.lchild=hti.rchild=-1;cout哈夫曼树的初态:n序号 结点值 权重 双亲结点 左孩子结点 右孩子节点endl;for(i=0;in;i+)coutithti.datathti.
4、weightt;couthti.parentthti.lchildthti.rchildendl;for(i=n;i2*n-1;i+)/构造哈夫曼树min1=min2=32767;lnode=rnode=-1;for(k=0;k=i-1;k+)if(htk.parent=-1)if(htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if(htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlno
5、de.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;cout哈夫曼树的终态:n序号 结点值 权重 双亲结点 左孩子结点 右孩子节点endl;for(i=0;i2*n-1;i+)coutit;if(in)couthti.datat;elsecout t;couthti.weightthti.parentt;couthti.lchildthti.rchildendl;void CreateHCode(HTNode ht,HCode hcd,int n)/对哈夫曼树进行编码int i,f,c;HCode hc;for(i=0;in;i
6、+)hc.start=n-1;c=i;f=hti.parent;while(f!=-1)if(htf.lchild=c)hc.cdhc.start-=0;elsehc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)/输出各个字符的哈夫曼编码int i,k;cout输出哈夫曼编码:n字符t对应编码endl;for(i=0;in;i+)couthti.datat;for(k=hcdi.start;kn;k+)couthcdi.cdk;coutendl;void CreateStrHCode(HTNode ht,HCode hcd,int n)/对字符串进行编码char str50;int i,j,k;cout请输入要编码的字符串:endl;gets(str);int nLen=strlen(str);cout该字符串的编码为:endl;for(i=0;inLen;i+)for(j=0;jn;j+)if(stri=htj.data)for(k=hcdj.start;kn;k+)couthcdj.cdk;cout ;coutendl;void main()int n=27;HTN
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 黄山市博物馆租赁合同
- 测绘简单合同范本
- 电池的购销合同模板
- 起重机工业品买卖合同
- 安装给水管合同
- 海口外贸公司租赁合同
- 搅拌站施工合同范本
- 市政施工合同补充协议书格式
- 科室承包合同范本
- 全新建筑合同施工合同范本
- 洗衣房投标书
- 海底捞店经理培训教材
- 菩萨蛮书江西造口壁 省赛获奖 详细版课件
- 2022年苏州市昆山市事业单位招聘考试笔试题库及答案解析
- 上海初中信息科技学业考试考复习
- 国开 电大 1167 环境水利学 网上形考作业1-9参考答案 客观题全部排序后
- 蓝色科技风年会PPT模板
- 粉色童话六一儿童节亲子活动策划PPT模板
- 部编版六年级道德与法治下册知识要点归纳六年级上册道德与法治知识
- 博物馆精装修工程施工重点、难点分析及解决方案(27页)
- 单螺杆水产膨化机用户操作手册(38张幻灯片)课件
评论
0/150
提交评论