優先キュー解Huffman符号化c++

14181 ワード

  • 優先キュー小析
  • 優先キューのテンプレート:template,class Compare=less> 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=0, 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@163.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=0, 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() > 1)
        {
            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 += '0';
            PrintCode(t->lchild, str);
        }
    
        //    
        if (t->lchild == NULL && t->rchild == NULL)
        {
            cout<<t->c<<"'s code: "<<str<<endl;
        }
    
        str.erase(str.end()-1);        //        
    
        if (t->rchild)
        {
            str += '1';
            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() > 0)
        {
            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!
    "); return -1; } // fscanf(fp, "%d", &n); fscanf(fp, "%c", &tmp); // for (i=0; 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 0; }

    参照先:
    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