huffmancode.cpp

哈夫曼编码解码演示程序

// HuffmanCode.cpp: implementation of the CHuffmanCode class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanCode.h"
#include "HuffmanDlg.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


#define XINTERVAL 30
#define YINTERVAL 80
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHuffmanCode::CHuffmanCode()
{
	m_PasStepNum[0]=0;
	for(int i=1;i<19;i++)
	{
		m_PasStepNum[i]=m_PasStepNum[i-1]+1;
		if((i==1)||(i==5))
			m_PasStepNum[i]++;
	}
	m_bEnCode=FALSE;
	m_Length=0;
}

CHuffmanCode::~CHuffmanCode()
{
	Clear();
}
void CHuffmanCode::CreateCode(int weight[],int n)
{
	m_Length=n;
	if(!Resume(0))
		return;
	if(n<=1)return;
	int m=2*n-1;
	
	int i;
	for(i=0;i<m;i++)
	{
		CHuffNode *pTree=new CHuffNode;
		if(i<n)
		{
			pTree->Set(weight[i],-1,-1,-1);
			pTree->Use();
			SetItem(i,weight[i],-1,-1,-1);
            if(i==0)
			{
				if(!Resume(1,FALSE))
					return;
			}
		}
		else
		{
			if(i==n)
			{
				if(!Resume(2))
					return;
			}
			pTree->Set(-1,-1,-1,-1);
			SetItem(i,-1,-1,-1,-1);
		}
        m_arHuffman.Add(pTree);
	}		

	for(i=n;i<m;i++)
	{	
		if(!Resume(3,FALSE))
			return;
		int s1,s2;
		if(!Resume(4,FALSE))
			return;	
		SelectMin(i-1,s1,s2);	    	
        CHuffNode*ps1=m_arHuffman.GetAt(s1);
        CHuffNode*ps2=m_arHuffman.GetAt(s2);
		ps1->SetFocus();
		ps2->SetFocus();

		if(!Resume(5))
			return;
		ps1->SetParent(i);//[s1].SetParent(i);
		SetItem(s1,-2,i,-2,-2);
        
		ps2->SetParent(i);//m_arHuffman[s2].SetParent(i);
		SetItem(s2,-2,i,-2,-2);

		CHuffNode*p=m_arHuffman.GetAt(i);
		p->SetlChild(s1);//m_arHuffman[i].SetlChild(s1);
		SetItem(i,-2,-2,s1,-2);
		p->SetrChild(s2);//m_arHuffman[i].SetrChild(s2);	    
		SetItem(i,-2,-2,-2,s2);
		p->Use();
		
		if(!Resume(6))
			return;
		p->SetWeight(ps1->weight+ps2->weight);//[s1].weight+
		SetItem(i,ps1->weight+ps2->weight,-2,-2,-2);
			//m_arHuffman[s2].weight);
		ps1->SetFocus(FALSE);
		ps2->SetFocus(FALSE);
		if(!Resume(7))
			return;
	} 

    m_bEnCode=TRUE;
	for(i=0;i<n;i++)
	{		
		m_Bits.Clear();
		CBits *pbits=new CBits;
		if(!Resume(8))
			return;
		if(!Resume(9))
		{
			delete pbits;
			return;
		}
		int start=n-1;
		CHuffNode*pp=m_arHuffman.GetAt(i);
		pp->SetFocus();
		pp->bIsTrace=TRUE;
        if(!Resume(10))
		{
			delete pbits;
			return;
		}
	    int c=i;
		int f=m_arHuffman.GetAt(c)->parent;//m_arHuffman[c].parent;
        
		while(f!=-1)
		{
			CHuffNode*pr=m_arHuffman.GetAt(f);
			pr->SetFocus();
			pr->bIsTrace=TRUE;
			if(!Resume(11))
			{
				delete pbits;
				return;
			}
			if(m_arHuffman.GetAt(f)->lChild==c)//[f].lChild==c)
			{
				if(!Resume(12))
				{
					delete pbits;
					return;
				}				
				m_Bits.Add('0');
				pbits->Add('0');
			}
			else 
			{
				if(!Resume(13))
				{
					delete pbits;
					return;
				}
				m_Bits.Add('1');
				pbits->Add('1');
			}
			if(!Resume(14))
			{
				delete pbits;
				return;
			}
			c=f;
			pr->SetFocus(FALSE);
			f=m_arHuffman.GetAt(f)->parent;//[f].parent;
			if(!Resume(15))
			{
				delete pbits;
				return;
			}
		}
		if(!Resume(16))
		{
			delete pbits;
			return;
		}
		m_HTCode.Add(pbits);
		pp->SetFocus(FALSE);
		if(!Resume(17))
		{
			delete pbits;
			return;
		}
	}//*/	
	if(!Resume(18))
		return;
}	
void CHuffmanCode::Decode(CString Code,CString &decode)
{
	if(!m_bEnCode)
	{
		AfxMessageBox("编码还没有完成!");
		return;
	}
	int root=(2*m_Length-1)-1;
	CString str=Code;
	decode.Empty();
	int index=0;
	CHuffNode *p;
	while(index<str.GetLength())
	{		
		p=m_arHuffman.GetAt(root);				
		p->SetFocus();
		Resume(-1);
		p->SetFocus(FALSE);
		BOOL err=FALSE;
		CString bits='(';
		while((index<str.GetLength())&&(p->lChild!=-1)
			&&(p->rChild!=-1))
		{
			CString tmp=str.GetAt(index++);
			if(tmp=='0')
			{
				p=m_arHuffman.GetAt(p->lChild);
                p->SetFocus();
				Resume(-1);
				bits+='0';
			}
			else if(tmp=='1') 
			{
				p=m_arHuffman.GetAt(p->rChild);
				p->SetFocus();
				Resume(-1);
				bits+='1';
			}
			else 
			{
				err=TRUE;
				break;
			}
			p->SetFocus(FALSE);
		}
		bits+=") ";
		if((!err)&&(p->lChild==-1)
			&&(p->rChild==-1))
		{
			CString w;
		    w.Format("%d",p->weight);
			w+=bits;
			decode+=w;		
		}
		p->SetFocus(FALSE);
		bits.Empty();
//		Resume(-1);
	}
}
BOOL CHuffmanCode::SelectMin(int range,int &s1,int &s2)
{
	int min1=32768-1;
	int min2=32768;
	for(int i=0;i<=range;i++)
	{
		if(m_arHuffman.GetAt(i)->parent==-1)
		{
			if((m_arHuffman.GetAt(i)->weight<min1))				
			{
				s1=i;
				min1=m_arHuffman.GetAt(i)->weight;
			}
		}
	}
	for(i=0;i<=range;i++)
	{
	    if(m_arHuffman.GetAt(i)->parent==-1)
		{			
			if((m_arHuffman.GetAt(i)->weight<min2)&&(i!=s1))
			{
				s2=i;
				min2=m_arHuffman.GetAt(i)->weight;
			}
		}
	}
	return TRUE;
}
//设置信息
/*void CHuffmanCode::SetInfo(CHuffmanDlg*pDlg)
{
	ASSERT(pDlg);
	m_pDlg=pDlg;
}*/
BOOL CHuffmanCode::Resume(int index,BOOL bDemoRedraw)
{
	CHuffmanDlg *m_pDlg=(CHuffmanDlg*)AfxGetApp()->m_pMainWnd;
	ASSERT(m_pDlg);	
    
	if(m_pDlg->m_bIsStart==FALSE)
		return FALSE;

	if(index!=-1)
		m_pDlg->m_SrcList.SetCurSel(m_PasStepNum[index]);
	if(bDemoRedraw)
		m_pDlg->m_Demo.Invalidate();
	if(m_pDlg->m_Mode==0)
	{
		while((!m_pDlg->m_bStep)&&(m_pDlg->m_Mode==0)&&
			m_pDlg->m_bIsStart)
			Sleep(50);
		m_pDlg->m_bStep=FALSE;
	}
	else if(m_pDlg->m_Mode==1)
	{
		if(m_pDlg->m_bIsStart)
			Sleep(m_pDlg->m_Wait);
	}
	else if(m_pDlg->m_Mode==2)
	{
	}
    while(m_pDlg->m_Pause&&m_pDlg->m_bIsStart)
		Sleep(500);
	return TRUE;	
}
//w,p,l,r值为-2时忽略该项
void CHuffmanCode::SetItem(int num,int w,int p,int l,int r)
{
	static int total=0;
	CHuffmanDlg *pDlg=(CHuffmanDlg *)AfxGetApp()->GetMainWnd();
	CString str;
	str.Format("%d",num+1);
	if(total<=num)
	{
		
		pDlg->m_StateList.InsertItem(total++,str);
	}
	pDlg->m_StateList.SetItemText(num,0,str);
	if(w!=-2)
	{
		if(w==-1)
			str="-";
		else 
			str.Format("%d",w);
		pDlg->m_StateList.SetItemText(num,1,str);
	}
	if(p!=-2)
	{
		str.Format("%d",p+1);
		pDlg->m_StateList.SetItemText(num,2,str);
	}
	if(l!=-2)
	{
		str.Format("%d",l+1);
		pDlg->m_StateList.SetItemText(num,3,str);
	}
	if(r!=-2)
	{
		str.Format("%d",r+1);
		pDlg->m_StateList.SetItemText(num,4,str);
	}
}
void CHuffmanCode::Clear()
{
	m_arHuffman.Clear();
	m_HTCode.Clear();
	m_bEnCode=FALSE;
}