刚写的Huffman树类模板.
#ifndef HUFFTREE_H#define HUFFTREE_H
#include<iostream.h>
#include<stdlib.h>
#include"MinHeap.h"
#include"LinkedStack.h"
#define DefaultSize 20
////////////////////////////////////////////////////
//HuffmanNode结构 Huffman树的结点的定义
//T是关键码的类型,E是数据结点的类型
////////////////////////////////////////////////////
template<class T,class E>
struct HuffmanNode
{
E data; //结点数据
HuffmanNode<T,E>* leftChild; //左子树指针
HuffmanNode<T,E>* rightChild;//右子树指针
HuffmanNode<T,E>* parent; //父结点指针
//构造函数
HuffmanNode()
{leftChild=NULL;rightChild=NULL;parent=NULL;};
//带参数的构造函数
HuffmanNode(E elem,
HuffmanNode<T,E>* lc=NULL,
HuffmanNode<T,E>* rc=NULL,
HuffmanNode<T,E>* pr=NULL)
{
//初始化数据
data=elem;
//初始化三个指针域
leftChild=lc;
rightChild=rc;
parent=pr;
};
//对本结构中数据结点的关键码比较关系运算符重载
bool operator<(HuffmanNode<T,E>& HN);
bool operator>(HuffmanNode<T,E>& HN);
};
///////////////////////////Huffman结点结构的定义结束
////////////////////////////////////////////////////
//MinHeap类的成员关系运算符重载
//对HuffmanNode类型指针中数据结点的关键码重载
////////////////////////////////////////////////////
template<class T,class E>
bool HuffmanNode<T,E>::operator<(HuffmanNode<T,E>& HN)
{
return this->data<HN.data;
};
template<class T,class E>
bool HuffmanNode<T,E>::operator>(HuffmanNode<T,E>& HN)
{
return this->data>HN.data;
};
////////////////////////////////////////////重载结束
////////////////////////////////////////////////////
//HuffmanTree类的声明和定义
////////////////////////////////////////////////////
template<class T,class E>
class HuffmanTree
{
private:
//huffman树的根
HuffmanNode<T,E>* root;
//删除以t为根的子树
void deleteTree(HuffmanNode<T,E>* t);
//前序递归显示该Huffman树的内容
void pre(HuffmanNode<T,E>* p);
//显示Huffman树的编码的内容
void HuffmanCoding(HuffmanNode<T,E>* p);
public:
//构造函数,通过权值集合来构造一棵Huffman树
HuffmanTree(E w[],int n);
//析构函数
~HuffmanTree()
{/*deleteTree(root);*/};
//前序遍历这棵Huffman树的内容
void Dispaly()
{pre(root);};
//通过建立的Huffman树来进行无共同前缀编码
void HuffmanCoding()
{HuffmanCoding(root);};
};
///////////////////////////////////Huffman类声明结束
////////////////////////////////////////////////////
//构造函数
//通过数组中的带关键码的结点元素来构造Huffman树
//w[]是结点元素数组,n是数组中结点元素的个数
////////////////////////////////////////////////////
template<class T,class E>
HuffmanTree<T,E>::HuffmanTree(E w[],int n)
{
//定义HuffmanNode的指针数组
HuffmanNode<T,E>** HFN=new HuffmanNode<T,E>*[n];
//把w[]数组中的数取出来建立一个HuffmanNode的结点数组
for(int i=0;i<n;i++)
{
HFN[i]=new HuffmanNode<T,E>(w[i]);
}
//根据数组w中内容建立一个以HuffmanNode为结点的最小堆
MinHeap<T,HuffmanNode<T,E>* > MH(HFN,n);
//把MH调整成最小堆
MH.siftUp();
//存放从堆中取出的两个最小的结点的指针
HuffmanNode<T,E> *first,*second;
//存放父结点的指针
HuffmanNode<T,E> *parent;
while(1)
{
//从最小堆中取出两个最小元素
MH.RemoveMin(first);
MH.RemoveMin(second);
//新建一个父结点
parent=new HuffmanNode<T,E>(first->data+second->data);
//把子结点挂入堆中
parent->leftChild=first;
parent->rightChild=second;
//设置first和second的parent指针域
first->parent=parent;
second->parent=parent;
//如果堆已经空了就退出循环
if(MH.IsEmpty())
break;
//把父结点压入堆中
MH.Insert(parent);
}
//最终到了Huffman树的根结点指针
root=parent;
};
////////////////////////////////////////构造函数结束
////////////////////////////////////////////////////
//私有成员函数pre()
//前序遍历这棵Huffman树的内容
////////////////////////////////////////////////////
template<class T,class E>
void HuffmanTree<T,E>::pre(HuffmanNode<T,E>* p)
{
if(p!=NULL)
{
pre(p->leftChild);
pre(p->rightChild);
}
};
///////////////////////////////////Display()函数结束
////////////////////////////////////////////////////
//私有成员函数deleteTree()
//释放Huffman树的内存空间,删除以t为根的Huffman树
////////////////////////////////////////////////////
template<class T,class E>
void HuffmanTree<T,E>::deleteTree(HuffmanNode<T,E>* t)
{
if(t!=NULL)
{
deleteTree(t->leftChild);
deleteTree(t->rightChild);
deleteTree(t);
}
};
////////////////////////////////deleteTree()函数结束
////////////////////////////////////////////////////
//HuffmanCoding()私有成员函数
//对输入的权值对应的符号进行HUffman编码
////////////////////////////////////////////////////
template<class T,class E>
void HuffmanTree<T,E>::HuffmanCoding(HuffmanNode<T,E>* p)
{
if(p!=NULL)
{
//访问结点p,如果当前的结点是叶子结点
if( p->leftChild==NULL && p->rightChild==NULL)
{
LinkedStack<int> LS;
cout<<p->data<<":";
//游标指针
HuffmanNode<T,E>* ptr=p;
HuffmanNode<T,E>* next;
//从叶子结点往上到根结点,显示编码内容
while(ptr->parent!=NULL)
{
//得到ptr结点的父结点
next=ptr->parent;
//如果ptr是next的右子结点
if(next->leftChild==ptr)
LS.Push(1);
//如果ptr是next的左子结点
else if(next->rightChild==ptr)
LS.Push(0);
//沿父指针继续往上
ptr=ptr->parent;
};
//显示堆栈里的内容,即编码的结果
int code;
while(!LS.IsEmpty())
{
LS.Pop(code);
cout<<code;
};
cout<<endl;
};
//递归显示左右子树的编码内容
HuffmanCoding(p->leftChild);
HuffmanCoding(p->rightChild);
};
};
/////////////////////////////HuffmanCoding()函数结束
#endif
还缺一个月，正式学数据结构就已经满一年了，基本可以自己独立编写实现算法以及相应的抽象数据类型了，
可还是存在不少的问题，不过，觉得，实现数据结构还是用面向对象最好了,大家学数据结构的时候是不是
把所有的算法全部编写一遍？觉得这样实在是太累了...
不过觉得编成还是乐在其中的，虽然并不从事这个职业...
[[it] 本帖最后由 geninsf009 于 2008-9-20 23:21 编辑 [/it]]
