数据结构之哈夫曼树 哈夫曼树编码

来源:西西图吧       编辑:书山居客
2020-07-07 06:56:27
点击:
6

本文章向大家介绍[C++] 数据结构之哈夫曼树(最优满二叉树) / 哈夫曼编码,主要包括[C++] 数据结构之哈夫曼树(最优满二叉树) / 哈夫曼编码使用实例、应用技巧、基本知识点总结和需要注意事项,具有一定的参考价值,需要的朋友可以参考一下。

1.1 基本概念

算法思想: 贪心算法(以局部最优,谋求全局最优)

定义

哈夫曼树 = 最优((满)二叉)树 = 带权路径最短的树

哈夫曼树所产生的哈夫曼编码 = (最优)前缀编码

1.2 算法描述/构造过程 1.3 算法实现 # define MAXNEGATIVE -9999 //最大负值
# define MAXPOSITIVE 9999 //最大正值
typedef struct HuffmanNode{ // 加 typedef : 避免发生编译错误 " variable or field 'functionName' declared void "
double weight;
int parent, lchild, rchild; //当前节点的双亲结点、左右孩子结点
}*HuffmanTree;

2> 确定最小的两个结点的选择策略(贪婪策略)【次核心】

/**
* 选择权值结点最小的两个结点 s1、s2
*/
void Select(HuffmanTree &HT,int k,int *s1,int *s2){
int min[2]={0, 0}; // 升序排名, 保留 HT中 权重值最小的两个结点的下标
cout<<"Select k:"<<k<<endl;
HT[0].weight = MAXPOSITIVE; // 初始化为最大正值,方便被 初始结点比最小而比下去
for(int i=1;i<=k;i++){
// cout<<"i:"<<i<<"tweight:"<<HT[i].weight<<"tparent:"<<HT[i].parent<<"tparent.weight:"<<HT[HT[i].parent].weight<<endl;
if( HT[i].parent==0 && (HT[i].weight<HT[min[1]].weight)){
if(HT[i].weight<HT[min[0]].weight){ // 小于 最小者
min[1] = min[0]; min[0] = i; cout<<i<<"小于最小者!"<<endl;
} else {
min[1] = i;cout<<i<<"小于次小者!"<<endl; //仅小于 次小者
}
}
}
*s1 = min[0]; // 最小者下标
*s2 = min[1]; // 次小者下标
// cout<<"s1:"<<*s1<<"ts2:"<<*s2<<endl;
}

3> 创建 Huffman 树【核心】

/**
* 创建 Huffman 树
* n : 初试结点(待编码结点)数
*/
void CreateHuffmanTree(HuffmanTree &HT, int n){
int m = 2*n-1;
HT = new HuffmanNode[m+1]; // 0 位空余
cout<<"Please input initiative node's weight : "<<endl; // 输入结点数据
for(int i=1;i<=n;i++){
cin>>HT[i].weight;
}
for(int k=1;k<=m;k++){ // 初始化所有结点
HT[k].lchild = 0;
HT[k].rchild = 0;
HT[k].parent = 0;
}
for(int j=n+1;j<=m;j++){
int s1,s2;
Select(HT, j-1, &s1, &s2); // 选择权值结点最小的两个结点s1、s2
HT[s1].parent = j; // 合并左右结点
HT[s2].parent = j;
HT[j].lchild = s1;
HT[j].rchild = s2;
HT[j].weight = HT[s1].weight + HT[s2].weight;
}
}

4> 输出哈夫曼树(输出 哈夫曼树 中 结点情况 )

void OutputHuffmanTree(HuffmanTree &HT, int n){ // 输出 哈夫曼树 中 结点情况
int m = 2*n-1;
for(int i=1;i<=m;i++){
cout<<"<"<<i<<"> weight: "<<HT[i].weight<<"t"<<"parent: "<<HT[i].parent<<"(weight:"<<HT[HT[i].parent].weight<<")t";
cout<<"parent.lchild:"<<HT[HT[i].parent].lchild<<"(weight:"<<HT[HT[HT[i].parent].lchild].weight<<")"<<"t";
cout<<"parent.rchild:"<<HT[HT[i].parent].rchild<<"(weight:"<<HT[HT[HT[i].parent].rchild].weight<<")"<<endl;
}
}
int main(){
HuffmanTree HT;
int n;
cout<<"Please input Huffman initiative Node Number:"; // 输入哈夫曼结点初始结点数目 n
int s1, s2;
cin>>n;
CreateHuffmanTree(HT, n);
OutputHuffmanTree(HT, n);
return 0;
}

《数据结构(C语言版):严蔚敏/吴伟民》

社会
相关阅读
商业银行的负债管理与结构分析 商业银行负债结构分析

商业银行的负债管理与结构分析 商业银行负债结构分析

商业银行的负债管理与结构分析目录:第一节、存款的种类和构成第二节、存款的定价第三节、非存款性的资金来源第四节、商业银行负债成本的管理第五节、我国商业银行的负债结构分析,商业银行的负债管理与结构分析内容

07-07
胡适《我的母亲》教案 胡适我的母亲结构图

胡适《我的母亲》教案 胡适我的母亲结构图

教学目标,1.熟读全文,理解并掌握本课生字新词;,2.理解文意,概括、提炼文中的母亲形象,,3.从文章所写的具体事件中概括出母亲的品性、特点。,4.了解胡适及其母亲身上代表的文化意义。,教学时数:课

07-07
汽车大学堂之避震器三种结构说明介绍 汽车减震器结构图

汽车大学堂之避震器三种结构说明介绍 汽车减震器结构图

单筒还是双筒?气压还是油压?避震器的三种结构避震器结构一共有三种(见附图), 分别为单筒高气压(Mono Tube High Pressure Gas), 双筒低气压(Twin Tube Low

07-07
关于明朝住宅的室内结构 中国明朝建筑风格

关于明朝住宅的室内结构 中国明朝建筑风格

1框架结构住宅是指以钢筋混凝土浇捣成承重梁柱,再用预制的加气混凝土、膨胀珍珠岩、浮石、陶粒等轻质板材隔墙分户装配而成的住宅。框架结构住宅是指以钢筋混凝土浇捣成承重梁柱,再用预制的加气混凝土、膨胀珍珠岩

05-29
下表是美、德两国第二次工业革命时期就业结构表 第二次工业革命表格

下表是美、德两国第二次工业革命时期就业结构表 第二次工业革命表格

【推荐1】某校研究性学习课题组就“第二次工业革命与世界市场最终形成”展开研究,最后得出如下结论,正确的是,①确立于19世纪末20世纪初②第二次工业革命对市场形成有重要作用,③有利于世界经济的增长和世界

05-27
想修改PSP游戏的存档 psp解密存档数据

想修改PSP游戏的存档 psp解密存档数据

最近在手机上用模拟器ppsspp玩《战神》,存档前没发现血几乎快没了,又没有血,前面就是BOSS,没有退路,没有宝箱开。真的打不过呀!而且也不想从前面的存档开始了,一是,前一个存档距离有些远,隔好几个

05-26
iphone6移动数据网络怎么设置 移动数据怎么设置

iphone6移动数据网络怎么设置 移动数据怎么设置

都在设置里面,分别是设置-无线局域网和设置-蜂窝移动网络两个地方,实在不行还可以在设置-通用-还原-还原网络设置里复原。回复:都在设置里面,分别是设置-无线局域网和设置-蜂窝移动网络两个地方,实在

05-26
背景数据块与共享数据块中实际值的理解 共享数据问题

背景数据块与共享数据块中实际值的理解 共享数据问题

(1)首先我们看一下OB1中的程序 调用FB1,FB1的背景数据块是DB1;FB1有三个输入的形参,二个输出的形参。可以看到actualspeed 这里没有输入实参。这种情况下就会用db1中的实际

05-26
五台山我国仅存的唐代木结构建筑 唐朝建筑内部结构

五台山我国仅存的唐代木结构建筑 唐朝建筑内部结构

时至今日,五台山已经成为中国古代建筑的稀世宝库。, 我国保存下来的寺庙木结构古建筑,最早的是唐代遗物。五台山南禅寺大殿与佛光寺东大殿,则是唐代木结构建筑的鼻祖与典范。唐代

05-13
经济数据亮红灯准备重启经济 美国确诊超120万

经济数据亮红灯准备重启经济 美国确诊超120万

美国确诊人数已经超过120万,这个触目惊心的数字让很多人心里不平静,这是生命的数字,美国这个确诊数字已经占据全球确诊病例的1/3。美国的疫情从1月21日报告首例确诊病例开始,

05-11