| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1134 人关注过本帖, 1 人收藏
标题:刚写的Huffman树类模板.
只看楼主 加入收藏
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
结帖率:100%
收藏(1)
 问题点数:0 回复次数:0 
刚写的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]]
搜索更多相关主题的帖子: Huffman 模板 
2008-09-20 23:19
快速回复:刚写的Huffman树类模板.
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017088 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved