Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器 软件资源

软件开发、小程序制作、系统集成与运维、空间租用、硬件开发、视频监控、技术咨询与支持——联系电话：0311-88999002/88999003

首页 / 操作系统 / Linux / C++实现:霍夫曼编码

C++实现:霍夫曼编码：
  1. #ifndef CHUFFMANTREE_H_   
  2. #define CHUFFMANTREE_H_   
  3. #include <assert.h>   
  4. #include <iostream>   
  5. #include <string>   
  6. #include <deque>   
  7. using namespace std;  
  8. /***************************************************************************/  
  9. /*先谈谈霍夫曼编码的基本思想： 
  10. /*对于一个给定的概率数组，所有元素之和为1，为了便于算法实现，我们扩大100倍 
  11. /*选出序列中最小的两个元素，删除原序列中的这两个数，相加得到一个新的元素 
  12. /*再把新得到的数放入序列中，重复上述过程，直到序列中只有一个元素（100） 
  13. /*规定：1、左孩子必须不大于右孩子节点的值；2、左边编码为0，右边为1 
  14. /***************************************************************************/  
  15. typedef struct _ITEM  
  16. {  
  17.     int index;//元素在原来的数组中的索引值   
  18.     int data;//数据   
  19. }ITEM,*PITEM;  
  20. typedef struct _TREE  
  21. {  
  22.     _TREE* lChild;//指向左孩子   
  23.     _TREE* rChild;//指向右孩子   
  24.     _TREE* pParent;//指向父节点   
  25.     ITEM item;//当前节点的数据域   
  26. }TREE,*PTREE;  
  27. class CHuffmanTree  
  28. {  
  29. public:  
  30.     CHuffmanTree（int s[],const int len）;  
  31.     virtual~ CHuffmanTree（）;  
  32.     //初始化树   
  33.     void InitTree（）const;  
  34.     //打印输入的数据   
  35.     void ShowBuffer（）const;  
  36.     //打印树   
  37.     void ShowTree（）const;  
  38.     void ShowHuffmanCode（）;  
  39. protected:  
  40.     //对队列元素进行两次冒泡排序，以便选出最小的两个数   
  41.     void SortDeque（）;  
  42.     //选出队列中最小的两个元素构造新的树节点   
  43.     void Select（int& m,int& n）;  
  44.     //构造哈弗曼树   
  45.     void CreateHuffmanTree（）;  
  46. private:  
  47.     int* pBuffer;//把元素复制到自己的内存里，指向首地址   
  48.     int m_iLength;//数组元素个数   
  49.     PTREE pTree;  
  50.     deque<ITEM> que;//双向队列，在这里面进行筛选最小的两个   
  51. };  
  52. #endif;  
[cpp] view plaincopyprint？
  1. #include "stdafx.h"   
  2. #include "HuffmanTree.h"   
  3. CHuffmanTree::CHuffmanTree（int s[], const int len）  
  4. :pBuffer（NULL）  
  5. ,pTree（NULL）  
  6. ,m_iLength（0）  
  7. {  
  8.     assert（len>0）;  
  9.     pBuffer=new int[len];  
  10.     int* p=pBuffer;  
  11.     for（int i=0;i<len;++i）  
  12.     {  
  13.         ITEM it;  
  14.         it.index=i;  
  15.         it.data=s[i];  
  16.         que.push_back（it）;  
  17.         *（p+i）=s[i];  
  18.     }  
  19.     m_iLength=len;  
  20.     pTree=new TREE[2*len-1];  
  21.     InitTree（）;  
  22. }  
  23. CHuffmanTree::~CHuffmanTree（）  
  24. {//回收内存   
  25.     if（pTree）  
  26.     {  
  27.         delete[] pTree;  
  28.         pTree=NULL;  
  29.     }  
  30.     if（pBuffer）  
  31.     {  
  32.         delete[] pBuffer;  
  33.         pBuffer=NULL;  
  34.     }  
  35. }  
  36. void CHuffmanTree::InitTree（） const  
  37. {  
  38.     int* p=pBuffer;  
  39.     int i=0;  
  40.     for（;i<2*m_iLength-1;++i）  
  41.     {  
  42.         （pTree+i）->lChild=NULL;  
  43.         （pTree+i）->rChild=NULL;  
  44.         （pTree+i）->pParent=NULL;  
  45.         （pTree+i）->item.index=i;  
  46.     }  
  47.     for（i=0;i<m_iLength;++i）  
  48.         （pTree+i）->item.data=*（p+i）;  
  49.     for（;i<2*m_iLength-1;++i）  
  50.         （pTree+i）->item.data=0;  
  51. }  
  52. void CHuffmanTree::ShowBuffer（） const  
  53. {  
  54.     for（int i=0;i<m_iLength;++i）  
  55.         cout<<*（pBuffer+i）<<"   ";  
  56.     cout<<endl;  
  57. }  
  58. void CHuffmanTree::ShowTree（） const  
  59. {  
  60.     cout<<"index         lChild        rChild        pParent       data"<<endl;  
  61.     for（int i=0;i<2*m_iLength-1;++i）  
  62.     {  
  63.         cout<<（pTree+i）->item.index<<"              ";  
  64.         if（（pTree+i）->lChild）  
  65.             cout<<（pTree+i）->lChild->item.data<<"             ";  
  66.         else  
  67.             cout<<"0             ";  
  68.         if（（pTree+i）->rChild）  
  69.             cout<<（pTree+i）->rChild->item.data<<"             ";  
  70.         else  
  71.             cout<<"0             ";  
  72.         if（（pTree+i）->pParent）  
  73.             cout<<（pTree+i）->pParent->item.data<<"             ";  
  74.         else  
  75.             cout<<"0             ";    
  76.         cout<<（pTree+i）->item.data<<endl;  
  77.     }  
  78.           
  79. }  
  80. void CHuffmanTree::Select（int& m,int& n）  
  81. {  
  82.     if（que.size（）<2）  
  83.         return;  
  84.     SortDeque（）;  
  85.     //经过两次冒泡排序，最小的两个元素的索引当然是0和1了   
  86.     m=que.at（0）.index;  
  87.     n=que.at（1）.index;  
  88.     //出队列   
  89.     que.pop_front（）;  
  90.     que.pop_front（）;  
  91. }  
  92. void CHuffmanTree::SortDeque（）  
  93. {  
  94.     if（que.empty（））  
  95.         return;  
  96.     //两次冒泡排序就可以筛选出最小的两个了   
  97.     for（int i=0;i<2;++i）  
  98.     {  
  99.         for（int j=que.size（）-1;j>i;--j）  
  100.         {  
  101.             if（que.at（j）.data<que.at（j-1）.data）  
  102.             {  
  103.                 ITEM temp=que.at（j）;  
  104.                 que.at（j）=que.at（j-1）;  
  105.                 que.at（j-1）=temp;  
  106.             }  
  107.         }  
  108.     }  
  109. }  
  110. void CHuffmanTree::CreateHuffmanTree（）  
  111. {  
  112.     for（int i=m_iLength;i<2*m_iLength-1;++i）  
  113.     {  
  114.         int m=0,n=0;  
  115.         Select（m,n）;  
  116.         （pTree+m）->pParent=（pTree+i）;  
  117.         （pTree+n）->pParent=（pTree+i）;  
  118.         （pTree+i）->lChild=（pTree+m）;  
  119.         （pTree+i）->rChild=（pTree+n）;  
  120.         （pTree+i）->item.index=i;  
  121.         （pTree+i）->item.data=（pTree+m）->item.data+（pTree+n）->item.data;  
  122.         que.push_back（（pTree+i）->item）;//关键！产生的新节点一定要放入队列中   
  123.     }  
  124. }  
  125. void CHuffmanTree::ShowHuffmanCode（）  
  126. {  
  127.     CreateHuffmanTree（）;//生成霍夫曼树   
  128.     for（int i=0;i<m_iLength;++i）  
  129.     {  
  130.         TREE* p=（pTree+i）;  
  131.         string s="";  
  132.         while（p->pParent）  
  133.         {//我们约定左0，右1   
  134.             if（p->pParent->lChild->item.index==p->item.index）  
  135.                 s+="0";  
  136.             else  
  137.                 s+="1";  
  138.             p=p->pParent;  
  139.         }  
  140.         s=string（s.rbegin（）,s.rend（））;//逆置   
  141.         cout<<（pTree+i）->item.data<<"的编码为:"<<s<<endl;//打印每个元素的霍夫曼编码   
  142.     }  
  143. }  
代码有注释，在此不再啰嗦.测试:
  1. #include "stdafx.h"   
  2. #include <iostream>   
  3. #include "huffmantree.h"   
  4. using std::cout;  
  5. using std::endl;  
  6.   
  7. int _tmain（int argc, _TCHAR* argv[]）  
  8. {  
  9.     int s[]={5,29,7,8,14,23,3,11};  
  10.     CHuffmanTree tree（s,8）;  
  11.     tree.ShowBuffer（）;  
  12.     tree.ShowTree（）;  
  13.     tree.ShowHuffmanCode（）;  
  14.     tree.ShowTree（）;  
  15.     return 0;  
  16. }  

版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图