手机版
你好,游客 登录 注册
背景:
阅读新闻

C++实现:霍夫曼编码

[日期:2012-05-22] 来源:Linux社区  作者:mfcing [字体: ]

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. }  


linux
相关资讯       C++  C++教程 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款