C++实现:霍夫曼编码:
- #ifndef CHUFFMANTREE_H_
- #define CHUFFMANTREE_H_
- #include <assert.h>
- #include <iostream>
- #include <string>
- #include <deque>
- using namespace std;
- /***************************************************************************/
- /*先谈谈霍夫曼编码的基本思想:
- /*对于一个给定的概率数组,所有元素之和为1,为了便于算法实现,我们扩大100倍
- /*选出序列中最小的两个元素,删除原序列中的这两个数,相加得到一个新的元素
- /*再把新得到的数放入序列中,重复上述过程,直到序列中只有一个元素(100)
- /*规定:1、左孩子必须不大于右孩子节点的值;2、左边编码为0,右边为1
- /***************************************************************************/
- typedef struct _ITEM
- {
- int index;//元素在原来的数组中的索引值
- int data;//数据
- }ITEM,*PITEM;
- typedef struct _TREE
- {
- _TREE* lChild;//指向左孩子
- _TREE* rChild;//指向右孩子
- _TREE* pParent;//指向父节点
- ITEM item;//当前节点的数据域
- }TREE,*PTREE;
- class CHuffmanTree
- {
- public:
- CHuffmanTree(int s[],const int len);
- virtual~ CHuffmanTree();
- //初始化树
- void InitTree()const;
- //打印输入的数据
- void ShowBuffer()const;
- //打印树
- void ShowTree()const;
- void ShowHuffmanCode();
- protected:
- //对队列元素进行两次冒泡排序,以便选出最小的两个数
- void SortDeque();
- //选出队列中最小的两个元素构造新的树节点
- void Select(int& m,int& n);
- //构造哈弗曼树
- void CreateHuffmanTree();
- private:
- int* pBuffer;//把元素复制到自己的内存里,指向首地址
- int m_iLength;//数组元素个数
- PTREE pTree;
- deque<ITEM> que;//双向队列,在这里面进行筛选最小的两个
- };
- #endif;
- #include "stdafx.h"
- #include "HuffmanTree.h"
- CHuffmanTree::CHuffmanTree(int s[], const int len)
- :pBuffer(NULL)
- ,pTree(NULL)
- ,m_iLength(0)
- {
- assert(len>0);
- pBuffer=new int[len];
- int* p=pBuffer;
- for(int i=0;i<len;++i)
- {
- ITEM it;
- it.index=i;
- it.data=s[i];
- que.push_back(it);
- *(p+i)=s[i];
- }
- m_iLength=len;
- pTree=new TREE[2*len-1];
- InitTree();
- }
- CHuffmanTree::~CHuffmanTree()
- {//回收内存
- if(pTree)
- {
- delete[] pTree;
- pTree=NULL;
- }
- if(pBuffer)
- {
- delete[] pBuffer;
- pBuffer=NULL;
- }
- }
- void CHuffmanTree::InitTree() const
- {
- int* p=pBuffer;
- int i=0;
- for(;i<2*m_iLength-1;++i)
- {
- (pTree+i)->lChild=NULL;
- (pTree+i)->rChild=NULL;
- (pTree+i)->pParent=NULL;
- (pTree+i)->item.index=i;
- }
- for(i=0;i<m_iLength;++i)
- (pTree+i)->item.data=*(p+i);
- for(;i<2*m_iLength-1;++i)
- (pTree+i)->item.data=0;
- }
- void CHuffmanTree::ShowBuffer() const
- {
- for(int i=0;i<m_iLength;++i)
- cout<<*(pBuffer+i)<<" ";
- cout<<endl;
- }
- void CHuffmanTree::ShowTree() const
- {
- cout<<"index lChild rChild pParent data"<<endl;
- for(int i=0;i<2*m_iLength-1;++i)
- {
- cout<<(pTree+i)->item.index<<" ";
- if((pTree+i)->lChild)
- cout<<(pTree+i)->lChild->item.data<<" ";
- else
- cout<<"0 ";
- if((pTree+i)->rChild)
- cout<<(pTree+i)->rChild->item.data<<" ";
- else
- cout<<"0 ";
- if((pTree+i)->pParent)
- cout<<(pTree+i)->pParent->item.data<<" ";
- else
- cout<<"0 ";
- cout<<(pTree+i)->item.data<<endl;
- }
- }
- void CHuffmanTree::Select(int& m,int& n)
- {
- if(que.size()<2)
- return;
- SortDeque();
- //经过两次冒泡排序,最小的两个元素的索引当然是0和1了
- m=que.at(0).index;
- n=que.at(1).index;
- //出队列
- que.pop_front();
- que.pop_front();
- }
- void CHuffmanTree::SortDeque()
- {
- if(que.empty())
- return;
- //两次冒泡排序就可以筛选出最小的两个了
- for(int i=0;i<2;++i)
- {
- for(int j=que.size()-1;j>i;--j)
- {
- if(que.at(j).data<que.at(j-1).data)
- {
- ITEM temp=que.at(j);
- que.at(j)=que.at(j-1);
- que.at(j-1)=temp;
- }
- }
- }
- }
- void CHuffmanTree::CreateHuffmanTree()
- {
- for(int i=m_iLength;i<2*m_iLength-1;++i)
- {
- int m=0,n=0;
- Select(m,n);
- (pTree+m)->pParent=(pTree+i);
- (pTree+n)->pParent=(pTree+i);
- (pTree+i)->lChild=(pTree+m);
- (pTree+i)->rChild=(pTree+n);
- (pTree+i)->item.index=i;
- (pTree+i)->item.data=(pTree+m)->item.data+(pTree+n)->item.data;
- que.push_back((pTree+i)->item);//关键!产生的新节点一定要放入队列中
- }
- }
- void CHuffmanTree::ShowHuffmanCode()
- {
- CreateHuffmanTree();//生成霍夫曼树
- for(int i=0;i<m_iLength;++i)
- {
- TREE* p=(pTree+i);
- string s="";
- while(p->pParent)
- {//我们约定左0,右1
- if(p->pParent->lChild->item.index==p->item.index)
- s+="0";
- else
- s+="1";
- p=p->pParent;
- }
- s=string(s.rbegin(),s.rend());//逆置
- cout<<(pTree+i)->item.data<<"的编码为:"<<s<<endl;//打印每个元素的霍夫曼编码
- }
- }
代码有注释,在此不再啰嗦.
测试:
- #include "stdafx.h"
- #include <iostream>
- #include "huffmantree.h"
- using std::cout;
- using std::endl;
- int _tmain(int argc, _TCHAR* argv[])
- {
- int s[]={5,29,7,8,14,23,3,11};
- CHuffmanTree tree(s,8);
- tree.ShowBuffer();
- tree.ShowTree();
- tree.ShowHuffmanCode();
- tree.ShowTree();
- return 0;
- }