最小堆应用---用最小堆实现huffman树,huffman是形成huffman编码的基础.
#include"MinHeap.h"
template<class T> class HuffmanTree;
template<class T>
class TreeNode{
friend class HuffmanTree<T>;
private:
T data;
TreeNode<T> *left,*right;
public:
TreeNode(T value){
data = value;
left = right = NULL;
}
TreeNode(){
left = right = NULL;
}
bool operator > (const TreeNode &node){
return data > node.data;
}
bool operator < (const TreeNode &node){
return data < node.data;
}
bool operator == (const TreeNode &node){
return data == node.data;
}
bool operator >= (const TreeNode &node){
return data >= node.data;
}
};
template <class T>
class HuffmanTree{
public:
HuffmanTree();
HuffmanTree(T value[],int n);
protected:
TreeNode<T> *JoinTree(TreeNode<T> &node1,TreeNode<T> &node2);
TreeNode<T> *root;
};
template<class T>
HuffmanTree<T>::HuffmanTree():root(NULL){
}
template<class T>
HuffmanTree<T>::HuffmanTree(T value[],int n):root(NULL){
TreeNode<T> *nodes = new TreeNode<T>[n];
TreeNode<T> leftNode,rightNode;
int i = 0;
for(i = 0; i < n; i++){
nodes[i] = TreeNode<T>(value[i]);
}
MinHeap< TreeNode<T> > *m_heap = new MinHeap< TreeNode<T> >(nodes,n);
for(i = 0; i < n-1; i++){
m_heap->RemoveMin(leftNode);
m_heap->RemoveMin(rightNode);
root = JoinTree(leftNode,rightNode);
m_heap->Insert(*root);
}
}
template<class T>
TreeNode<T> *HuffmanTree<T>::JoinTree(TreeNode<T> &node1,TreeNode<T> &node2){
TreeNode<T> *r = new TreeNode<T>;
r->left = &node1;
r->right = &node2;
r->data = node1.data + node2.data;
return r;
}
分享到:
相关推荐
Huffman-Coding-Using-... 这是使用 JAVA 中实现的优先队列(使用最小堆)、二叉搜索树和链表等数据结构的霍夫曼编码的实现。 该项目可以对任何类型的文本文件进行无损数据压缩。 应用程序还可以解码以取回原始文件。
1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码
1、将信源发出的N个消息符号按其概率的递减次序依次排列。 2、取概率最小的两个符号分别配以0和1两个码元,并将这两个符号的概率相加作为一个新概率,与未分配码元的符号重新按...本程序可实现以上过程的Huffuman编码
具体要求如下:最小冗余码/哈夫曼码、ASCII码/定长码、哈夫曼码/不定长码、统计、构造Huffman树、在左分枝标0,右分枝标1、确定Huffman编码 3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个...
Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下: 1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi...
对BST树的方法进行扩充,实现如下功能: 1)给定一个节点,寻找并...对Huffman树的方法进行扩充,实现如下功能: 1)键盘输入一个字符串或者读入一个文本文件,统计每个字符出现的频率; 2)输出每个字符的Huffman编码
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 表达式树4.3 查找树ADT——二叉查找树4.3.1 MakeEmpty4.3.2 Find4.3.3 FindMin和FindMax4.3.4 Insert4.3.5 Delete4.3.6 平均情形分析...
八方向迷宫的实现 内附详细的程序说说明 还有树的相关程序 哈夫曼树(Huffman树)——设有n个权值{w1,w2,……wn},构造一棵有n个叶子结点的二叉树,每个叶子的权值为wi,则wpl最小的二叉树叫~,也称最优二叉树
最小堆的存储结构使用数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作,接下来是对堆的插入和删除操作,插入和删除都在建好的堆上操作。 输入一串小写字母组成的字符串(不超过1000000)。输出这个字符...
为了提高存储和处理文本的效率,在一些计算机应用场合,如数据通信,常采用不等长的编码,对常用的字符用较少的码位编码,不常出现的字符用较多的码位编码,从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等...
给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。本资源通过...
堆的初始化、堆的插入、删除算法 5.8 Huffman树;Huffman编码 6. 树的概念,树的周游,森林的周游;树、森林与二叉树之间的转换 7. 图的性质 1. 图的性质、图的存储、图的遍历(DFS,BFS) 2. 最小生成树概念,Prim...
1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码
红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程...
范例1-106 最小生成树 355 ∷相关函数:MiniSpanTree_PRIM函数 1.7.6 关节点和重连通分量 359 范例1-107 关节点和重连通分量 359 ∷相关函数:FindArticul函数 1.7.7 拓扑排序 366 范例1-108 拓扑排序 366 ∷相关...
红-黑树的实现 其他平衡树 小结 问题 实验 第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程...
数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,二斜堆,二项堆,二叉查找树,红黑树,AVL平衡树,Treap,Splay,静态二叉查找树,2-d树,...
数据结构算法实现(严蔚敏版配套实现程序) 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...
最小生成树 Minitree 关节点 FindArtgraph 图的应用 拓扑排序 TSort 关键路径 CritPath Dijkstra算法 DIJ Floyd算法 FLOYD 10 查找 静态查找 顺序查找、折半查找 SSearch 动态查找 二叉排序树 BSTSearch ...