//哈夫曼树算法
#include<iostream>
using namespace std;
const int n=5;
const int m=2*n-1;
const int float_max=20;
typedef int datatype;
typedef struct
{
float weight; //定义权重
int parent; //定义双亲在向量中的下标
int lchild,rchild; //定义左右子树
} nodetype; //结点类型
typedef nodetype hftree[m]; //哈夫曼树类型,数组从0号单元开始使用
hftree T; //哈夫曼树向量
//哈夫曼树的构造
void huffman(hftree T)
{
int i,j,p1,p2;
float small1,small2;
for(i=0;i<n;i++) //初始化
{
T[i].parent=-1; //无双亲,即为根结点,尚未合并过
T[i].lchild=T[i].rchild=-1;//左右孩子指针置为-1
}
for(i=0;i<n;i++)
{
cin>>T[i].weight; //输入n个叶子的权
}
for(i=n;i<m;i++) //进行n-1次合并,产生n-1个新结点
{
p1=p2=-1;
small1=small2=float_max; //float_max为float类型的最大值
for(j=0;j<=i-1;j++)
{
if(T[j].parent!=-1) continue;//不考虑已合并过的点
if(T[j].weight<small1) //修改最小权和次小权及位置
{
small2=small1;
small1=T[j].weight;
p2=p1;
p1=j;
}
else if(T[j].weight<small2) //修改次小权及位置
{
small2=T[j].weight;
p2=j;
}
}
T[p1].parent=T[p2].parent=i; //新根
T[i].parent=-1;
T[i].lchild=p1;
T[i].rchild=p2;
T[i].weight=small1+small2; //新结点的权值为最小权与次小权之和
}
}
int main()
{
hftree T;
cout<<" 欢迎测试!!!! "<<endl;
cout<<"----------测试开始-----------"<<endl;
cout<<"首先调用哈夫曼树构造的函数:huffman"<<endl;
cout<<"按下标顺序输入叶子的权重:"<<endl;
cout<<" 0 1 2 3 4 5 6 7 8 "<<endl;
huffman(T);
cout<<"输出合并后的哈夫曼树的所有结点:"<<endl;
cout<<" 0 1 2 3 4 5 6 7 8 "<<endl;
for(int i=0;i<m;i++)
{
cout<<T[i].weight<<" ";
}
system("pause");
return 0;
}
分享到:
相关推荐
c++实现 哈夫曼树算法 数据结构作业 VS2005,2008,2010能直接打开
适合学习数据结构编程者,由于模仿,希望对大家有所帮助
数据结构的哈夫曼树,能输入任意字符串,并计算出现频率,同时统计编码长度,可编码,可解码,能计算压缩比,可执行程序包括实验报告
做数据结构课设的时候写的
改程序实现了经典的哈夫曼树算法,采用C++开发,对于认识数据结构有很大帮助
一、问题描述 运用哈夫曼算法构造哈夫曼树,并得到哈夫曼编码。 输入格式:10,5,21,18,8,13 ...1、构造哈夫曼树和哈夫曼编码的存储结构。 2、实现哈夫曼算法,实现哈夫曼树的存储并求出哈夫曼编码。
二、要求 通过这次设计,要求在数据结构析逻辑特性和物理表示,数据结构的选择的应用、 算法的设计及其实现等方面中深对课程基本内容的理解。同时,在程序设计方法以及上 机操作等基本技能和科学作风方面受到比较...
构造哈夫曼树的算法实现: 假设哈夫曼树采用双亲孩子表示法存储,并增加权值域,构造哈夫曼树的叶子结点(树木的权)有N个,合并次数为N—1次,则森林中总共有2N—1棵树,(包含合并后删除的)。
哈夫曼树的实现,哈夫曼编码解码,c++源码,数据结构与算法
通过自定义算法创建哈夫曼树和编码,对文件进行二进制操作实现压缩和解压。
本程序是c++语言利用数据结构中的树来实现二院哈夫曼编译码,支持任意字符串的编译码,直接用visual studio打开运行即可。
数据结构中哈夫曼树的实现,c++编写,很具有参考价值
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...
自己实现的哈夫曼树,代码不超过100行,用到了优先队列
任务 :建立建立最优二叉树函数 要求:可以建立函数输入...在上交资料中请写明:存储结构、 基本算法(可以使用程序流程图) 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法;
数据结构各种算法实现(C++模板) 数据结构各种算法实现(C++模板)暑假在家不能上网,把数据结构的一些算法实现了一遍,给大家分享一下,下面是程序的主要目录 1、顺序表 2、单链表 3、双向链表 4、循环链表 5、顺序栈 6、...
本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法。分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的...
哈夫曼树(Huffman Tree)是一种用于数据压缩的树形数据结构。它是由David A. Huffman在1952年提出的,被广泛应用于数据压缩算法中。 哈夫曼编码(Huffman Coding)是一种基于哈夫曼树的编码方法,它通过对数据中...
(1) 读入一个 ASCII 文件,统计文档中字符出现的频度,构造哈夫曼树; (2) 在构造好的哈夫曼树中对每个字符进行 Huffman 编码; (3) 要求打印出原始数据、每个字符对应的Huffman 编码和总编码长度。