版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验目的与规定运用C++编写程序,解决哈夫曼编码问题。实验内容哈夫曼树定义:设二叉树共有n个端点,从二叉树第k个端点到树的根结点的途径长度l(k)为该端结点(或叶子)的祖先数,即该叶子的层数减1。同时,每一种结点都带一种权(实数),第k个端点所带权为w(k)。定义各个端结点的途径长l(k)与该点的权w(k)的乘积之和为该二叉树的带权途径长。哈夫曼树:对n个权值w(1),w(2),…,w(n),构造出全部由n个分别带这些权值的叶结点构成的二叉树,其中带权途径长wpl最小的二叉树称为哈夫曼树。三.算法描述及实验环节哈夫曼算法哈夫曼给出一种贪心方略的算法,称为哈夫曼算法。1)根据给定的n个权值{w(1),w(2),…,w(n)}构成n棵二叉树的森林F=(T1,…,Tn)。其中每棵二叉树中只有一种带权为w(k)的根结点,其左右子树为空。2)在F中选用两棵结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上结点权值之和。3)在F中删除这两棵树,并把新得的二叉树加入F中。4)重复以上2),3),直到F只含一棵树为止。这棵树即为哈夫曼树。贪心算法设计(1)数据构造数组w:各字符频率或结点权值,操作中可变化;w(k)为第k个字符或结点的频率。数组u:各字符频率或结点权值,不参加操作。数组b:各字符或结点的次序号,如b[2]=4,即排序的第2位为第4位字符(结点)。数组lc:各字符或结点的左子号。数组rc:各字符或结点的右子号。数组p:各字符或结点的双亲号。数组q:计算各字符或结点的编码的十进制值。数组f:计算各字符或结点的的二进制位数。数组g:各字符或结点的编码十进制值转换的二进制数码。(2)构建哈夫曼树设立n-1次操作的k(1~n-1)循环。对每一种k,设立j(1或2)循环,比较产生须去掉的两个元素号b[2*k-2+j](每产生一种,该元素置非常大,以避免干扰背面比较)。产生一种新的结点:u[n+k]=u[b[2*k-1]]+u[b[2*k]];标注该结点的左右后继与双亲地址Lc[n+k]=b[2*k-1];rc[n+k]=b[2*k;P[b[2*k-1]]=n+k;p[b[2*k]]=n+k;至u[2*n-1]产生后结束构建哈夫曼树。(3)编码数值运算根据左边标注“0”右边标注“1”的规则,设立k(2n-1~n+1)循环逐级反推,前一级的数值须乘2,即q[lc[k]]=q[k]*2+0;q[rc[k]]=q[k]*2+1;f[rc[k]]=f[lc[k]]=f[k]+1;为了输出q[k](k=1,2,…,n)的哈夫曼编码,应用g数组存储分离q[k]的各个二进制数字g[i](i=1,2,…,j)输出时先输出f[k]-j个前置“0”,然后输出q[i](i=j,j-1,…,1)
四.程序设计#include<stdio.h>voidmain(){inta,k,i,j,n,w[100],u[100],b[100],lc[100],rc[100];intf[100],g[100],p[100],q[100];printf("请输入字符个数n:");scanf("%d",&n);for(k=1;k<=n;k++){printf("请输入第%d个字符频率:",k);scanf("%d",&w[k]);u[k]=w[k]; }for(k=1;k<=2*n;k++){p[k]=lc[k]=rc[k]=0;q[k]=0;}printf("原始频率为:");for(j=1;j<=n;j++)printf("%d",w[j]);for(k=1;k<=n-1;k++){for(j=1;j<=2;j++) {b[2*k-2+j]=1;for(i=2;i<=n+k-1;i++)if(w[i]<w[b[2*k-2+j]])b[2*k-2+j]=i;w[b[2*k-2+j]]=0+k+j;}u[n+k]=u[b[2*k-1]]+u[b[2*k]]; w[n+k]=u[n+k]; lc[n+k]=b[2*k-1];rc[n+k]=b[2*k]; p[b[2*k-1]]=n+k;p[b[2*k]]=n+k; }printf("\nkdaplcrc\n");for(k=1;k<=2*n-1;k++)printf("%4d%4d%4d%4d%4d\n",k,u[k],p[k],lc[k],rc[k]);q[2*n-1]=0;f[2*n-1]=0;for(k=2*n-1;k>n;k--){q[lc[k]]=q[k]*2+0;q[rc[k]]=q[k]*2+1;f[rc[k]]=f[lc[k]]=f[k]+1;}printf("kdabite\n");for(k=1;k<=n;k++){if(q[k]==0){j=1;g[1]=0;}else{a=q[k];j=0;while(a>0){j++;g[j]=a%2;a=a/2;}}printf("%c%2d",k+96,u[k]);for(i=1;i<=f[k]-j;i++)printf("0");for(i=j;i>=1;i--) printf("%d",g[i]);prin
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 成人夏季食品安全教育
- 企业宿舍管理培训
- 电视节目特邀嘉宾合同范本
- 城市绿化提升改造植树合同
- 跨国企业分公司负责人聘用合同
- 城市供热管道铺设顶管施工协议
- 体育综合楼租赁合同
- 房地产协会会员管理方法
- 消防安全廉洁自律承诺书
- 《Excel数据获取与处理实战》 课件 第2章 外部数据的获取
- 消防应急疏散预案培训
- 自然拼读法-图文.课件
- 创新创业实训智慧树知到期末考试答案章节答案2024年西安理工大学
- 2024届宜宾市九年级语文上学期期中考试卷附答案解析
- 大学生国家安全教育智慧树知到期末考试答案2024年
- 2024继续教育《医学科研诚信与医学了研究伦理》答案
- 硫磺安全技术说明书MSDS
- 国开电大《工程数学(本)》形成性考核作业5答案
- GB/T 28653-2012工业氟化铵
- GB/T 13914-2013冲压件尺寸公差
- 《舒适护理理论》PPT课件.ppt
评论
0/150
提交评论