哈夫曼树的建立及应用
更新时间:2024-03-03 04:50:01 阅读量: 综合文库 文档下载
哈夫曼树的建立及应用
1、 给定权值5,29,7,8,14,23,3,11,建立哈夫 曼树,输出哈夫曼编码。
2、对上述给定的哈夫曼树及得到的哈夫曼编码,试输入一串二 进制编码,输出它的哈夫曼译码。
三、算法描述
将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式,然后在主函数中调用它们。
建立哈夫曼树时,将哈夫曼树的结构定义为一个结构型的一维数组,每个元素含有四项:权值,双亲,左孩子,右孩子。给定的权值可以从键盘输入,要输出所建立的哈夫曼树,只要输出表示哈夫曼树的一维数组中的全部元素即可。
要实现哈夫曼编码,只要在所建立的哈夫曼树上进行二进制编码:往左走,编码为0,往右走,编码为1,然后将从根结点到树叶中的所有0、1排列起来,则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存,每个元素包含:编码、编码的开始位置、编码所对应的字符三项。
程序清单:
#include
constint m=2*n-1;
struct Tree //哈夫曼树的一个结点 {
intparent,lchild,rchild; //双亲,左孩子,右孩子 int weight; //权值 };
structcodetype //哈夫曼编码 {
int bits[n+1]; //编码存放的位置 int start; //编码开始存放的位置 char ch; //编码对应的字符 };
Tree huffTree[m+1]; codetype code[n+1];
void Select() //搜索权值最小的两个数并合并成哈夫曼树 {
intx,y;
int j,min1,min2;
for(int k=n+1;k<=m;k++) //合并成哈夫曼树 {
min1=min2=32767; x=y=0;
for(j=1;j<=k-1;j++) //找出权值最小的两个数 if(huffTree[j].parent ==0)
if(huffTree[j].weight min2=min1; min1=huffTree[j].weight ; y=x; x=j; } else if(huffTree[j].weight min2=huffTree[j].weight; y=j; } huffTree[x].parent=k; huffTree[y].parent=k; huffTree[k].lchild=x; huffTree[k].rchild=y; huffTree[k].weight=huffTree[x].weight+huffTree[y].weight; } } void HuffmanTree() //构造哈夫曼树 { for(inti=1;i<=m;i++) { huffTree[i].parent=0; huffTree[i].lchild=0; huffTree[i].rchild=0; huffTree[i].weight=0; } cout<<\请输入\个权值\ for(i=1;i<=n;i++) cin>>huffTree[i].weight; Select(); } void Huffcode() //哈夫曼编码 { codetype cd; intc,p; for (inti=1;i<=n;i++) { cd.start=n+1; cd.ch=96+i; //第一个字符为a,并依次排字符 c=i; p=huffTree[i].parent; while(p!=0) { cd.start--; if(huffTree[p].lchild==c) cd.bits[cd.start]=0; else cd.bits[cd.start]=1; c=p; p=huffTree[p].parent; } code[i]=cd; } for(i=1;i<=n;i++) { cout<<\字符\的权值为\编码是:\ for(int j=code[i].start;j<=n;j++) cout< void tranHuffcode() //哈夫曼译码 { inti=m;char b; cout<<\请输入一串二进制编码以(0和1以外的数结束)\ cin>>b; while((b=='0')||(b=='1')) { if(b=='0') i=huffTree[i].lchild; : else i=huffTree[i].rchild; if(huffTree[i].lchild==0) { cout< cin>>b; } } void main() { HuffmanTree(); //建立哈夫曼树 Huffcode(); //实现哈夫曼编码 tranHuffcode(); //实现哈夫曼译码 } 运行结果:
正在阅读:
哈夫曼树的建立及应用03-03
爱情攻略漫画02-12
海关监管笔记05-26
圆角在CSS2和CSS3里的创建方法06-03
spss中怎样进行fisher精确概率法统计 - 图文12-25
七年级数学下册 10.1 二元一次方程教案(新版)苏科版06-15
2015年春季八年级下册历史期末考试卷06-07
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 哈夫曼
- 建立
- 应用
- 2015年全国A类压力容器审核人取证考试试题
- 关于于正的25句名言
- 本科学士学位英语考试词汇重点
- 合理对待现代教育技术的利与弊
- 医疗废物管理制度
- 2008年4月自学考试刑事诉讼法学试题
- 互动式教学法在初中英语课堂教学中的有效应用
- 《少年维特的烦恼》读后感
- 体育康复复习资料
- 广东2012年会计从业资格考试会计基础模拟试卷
- 全面建设小康社会说课稿
- 银保产品产品说明会邀约话术
- 采购师职业资格认证考试模拟试题(判断题)
- 我国脑死亡立法和存在相关问题研究
- 电气四班安国栋(1)
- 八卦象数疗法配方大全
- 2016年上半年重庆省高级防水工程师模拟试题
- VF复习题 - 图文
- 既有居住建筑供热计量及节能改造项目工程施工组织设计大学论文
- 广东省自考混凝土及砌体结构 复习要点