1、问题

参考我的博客：贪心算法之哈夫曼编码问题

2、优先队列知识复习

参考我的博客： C++之STL之priority_queue

3、代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //最大字符编码数组长度
     
    
   

    

     

    
    

     

      #define MAXCODELEN 100
     
    
   

    

     

    
    

     

      //最大哈夫曼节点结构体数组个数
     
    
   

    

     

    
    

     

      #define MAXHAFF 100
     
    
   

    

     

    
    

     

      //最大哈夫曼编码结构体数组的个数
     
    
   

    

     

    
    

     

      #define MAXCODE 100
     
    
   

    

     

    
    

     

      #define MAXWEIGHT  10000;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Haffman
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       //权重
     
    
   

    

     

    
    

     

       int weight;
     
    
   

    

     

    
    

     

       //字符
     
    
   

    

     

    
    

     

       char ch;
     
    
   

    

     

    
    

     

       //父节点
     
    
   

    

     

    
    

     

       int parent;
     
    
   

    

     

    
    

     

       //左儿子节点
     
    
   

    

     

    
    

     

       int leftChild;
     
    
   

    

     

    
    

     

       //右儿子节点
     
    
   

    

     

    
    

     

       int rightChild;
     
    
   

    

     

    
    

     

      	//下标
     
    
   

    

     

    
    

     

      	int index;
     
    
   

    

     

    
    

     

      }HaffmaNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct cmp 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	bool operator() (HaffmaNode haffman1, HaffmaNode haffman2)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		return haffman1.weight > haffman2.weight;
     
    
   

    

     

    
    

     

      	}	
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Code
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       //字符的哈夫曼编码的存储
     
    
   

    

     

    
    

     

       int code[MAXCODELEN];
     
    
   

    

     

    
    

     

       //从哪个位置开始
     
    
   

    

     

    
    

     

       int sta
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/79451943