优先队列求解Huffman编码 c++

优先队列小析

优先队列的模板： template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;

 可以看出priority_queue的模板声明带有三个参数，T为数据类型，Container为保存数据的容器，，Compare为元素比较方式，其中Container必须是用数组实现的容器，比如vector,deque，不能用list.STL里面容器默认用的是 vector. 比较方式默认用 operator< ,所以如果你把后面俩个参数 缺省的话，优先队列就是大顶堆。如果要用到小顶堆，则一般要把模板的三个参数都带进去。STL里面定义了一个仿函数 greater<Type>，对于基本类型可以用这个仿函数声明小顶堆。引用自(DanielWang_).
　　在求解Huffman编码里面,我们需要用到小顶堆性质,而且元素还是指针元素.因此我们使用如下的方式定义优先队列,把模板的三个参数都带进去,并且还自定义了仿函数.

typedef struct HTNode{

    char c;

    unsigned int freq;

    HTNode *lchild, *rchild;

    //构造函数

    HTNode(char key='\0', unsigned int fr=, HTNode *l=NULL, HTNode *r=NULL):

        c(key),freq(fr),lchild(l),rchild(r){};

}HTNode,*pNode;

//重载优先队列里的比较运算符

struct cmp{

    bool operator()(pNode node1, pNode node2){

        return node1->freq > node2->freq;

    }

};

//含有指针类型的优先队列

priority_queue<pNode, vector<pNode>, cmp> pq;

　　2. 具体实现代码

在打印Huffman 编码的时候,还用到了string的一个函数,erase,即删除某个字符.因为end()返回string的最后一个字符的下一个位置,那么就可以用如下的方法删除最后一个字符.
str.erase(str.end()-1);        //删除最后一个字符

*************************************************************************

    > File Name: Huffman_code_pg.cpp

    > Author: He Xingjie

    > Mail: gxmshxj@.com

    > Created Time: 2014年06月06日 星期五 08时57分01秒

    > Description:

 ************************************************************************/

#include<iostream>

#include<queue>

#include<vector>

#include<cstdio>

#include<stack>

using namespace std;

typedef struct HTNode{

    char c;

    unsigned int freq;

    HTNode *lchild, *rchild;

    //构造函数

    HTNode(char key='\0', unsigned int fr=, HTNode *l=NULL, HTNode *r=NULL):

        c(key),freq(fr),lchild(l),rchild(r){};

}HTNode,*pNode;

//重载优先队列里的比较运算符

struct cmp{

    bool operator()(pNode node1, pNode node2){

        return node1->freq > node2->freq;

    }

};

//含有指针类型的优先队列

priority_queue<pNode, vector<pNode>, cmp> pq;

void HuffmanCode(int n)

{

    pNode l, r;

    //从优先队列中找出优先级最小的两个元素,合并，并

    //把它加入到优先队列中

    while (pq.size() > )

    {

        pNode z = new HTNode;

        l = pq.top();

        pq.pop();

        r = pq.top();

        pq.pop();

        z->lchild = l;

        z->rchild = r;

        z->freq = l->freq + r->freq;

        pq.push(z);

    }

}

void PrintCode(pNode t, string str)

{

    //中序递归遍历HuffmanTree求解HuffmanCode

    if (t == NULL)

        return;

    if (t->lchild)

    {

        str += '';

        PrintCode(t->lchild, str);

    }

    //叶子节点

    if (t->lchild == NULL && t->rchild == NULL)

    {

        cout<<t->c<<"'s code: "<<str<<endl;

    }

    str.erase(str.end()-);        //删除最后一个字符

    if (t->rchild)

    {

        str += '';

        PrintCode(t->rchild, str);

    }

}

void DFS(HTNode *t)

{

    HTNode *node;

    stack<pNode, vector<pNode> > pstack;

    pstack.push(t);

    node = pstack.top();

    pstack.pop();

    while (pstack.size() > )

    {

        if (node->lchild)

        {

            pstack.push(node->lchild);

            node = node->lchild;

        }

        else if(node->rchild)

        {

            pstack.push(node->rchild);

            node = node->rchild;

        }

        else

        {

            printf("%d ", node->freq);

            node = pstack.top();

            pstack.pop();

        }

    }

}

int main()

{

    int n, i;

    FILE *fp;

    char tmp;

    string str;

    fp = fopen("in.txt", "r");

    if (fp ==NULL)

    {

        printf("fopen error!\n");

        return -;

    }

    //输入大小

    fscanf(fp, "%d", &n);

    fscanf(fp, "%c", &tmp);

    //输入数据

    for (i=; i<n; i++)

    {

        char c;

        int freq;

        pNode p = new HTNode;

        fscanf(fp, "%c%d", &c, &freq);

        p->c = c;

        p->freq = freq;

        fscanf(fp, "%c", &tmp);

        pq.push(p);

    }

    HuffmanCode(n);

    PrintCode(pq.top(), str);

    return ;

}

参考:

http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue

http://blog.csdn.net/liuzhanchen1987/article/details/7856893

http://blog.csdn.net/daniel_ustc/article/details/17613359

巴特西

优先队列求解Huffman编码 c++

最新文章

热门文章