huffmantext.cpp

在VC环境下

// HuffmanText.cpp : implementation file
//

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanText.h"
#include "math.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//用hft[]来存放哈夫曼树结构
typedef struct
{
   unsigned long weight;
   int parant,lchirld,rchirld;
} note;

//用hcd[i]来存放ASCII为i字符的哈夫曼编码
typedef struct 
{
	int Bits[127];
	int start;
} code;
const int max_weight=32767;

/////////////////////////////////////////////////////////////////////////////
// CHuffmanText dialog


CHuffmanText::CHuffmanText(CWnd* pParent /*=NULL*/)
	: CDialog(CHuffmanText::IDD, pParent)                                                                                 
{
	//{{AFX_DATA_INIT(CHuffmanText)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void CHuffmanText::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHuffmanText)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CHuffmanText, CDialog)
	//{{AFX_MSG_MAP(CHuffmanText)
	ON_EN_CHANGE(IDC_EDIT_OriginalText, OnChangeEDITOriginalText)
	ON_BN_CLICKED(IDC_BUTTON_Scan1, OnBUTTONScan1)
	ON_BN_CLICKED(IDC_BUTTON_HuffmanTree, OnBUTTONHuffmanTree)
	ON_BN_CLICKED(IDC_BUTTON_Scan2, OnBUTTONScan2)
	ON_BN_CLICKED(IDC_RADIO_Compress, OnRADIOCompress)
	ON_BN_CLICKED(IDC_RADIO_DeCompress, OnRADIODeCompress)
	ON_BN_CLICKED(IDC_BUTTON_RUN, OnButtonRun)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanText message handlers



BOOL CHuffmanText::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	state=0;
	CButton *pButton=(CButton*)GetDlgItem(IDC_RADIO_Compress);
	pButton->SetCheck(1);
	CButton *pBtn;
	//设置原文本编辑框的内容
	this->SetDlgItemText(IDC_EDIT_OriginalText,"122333444455555");
    //屏蔽Huffman树按钮和单选解压按钮
	pBtn=(CButton*)GetDlgItem(IDC_RADIO_DeCompress);
	pBtn->EnableWindow(FALSE);

    pBtn=(CButton*)GetDlgItem(IDC_BUTTON_HuffmanTree);
	pBtn->EnableWindow(FALSE);
	
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}

//改变原编辑框内容时，各按钮的状态
void CHuffmanText::OnChangeEDITOriginalText() 
{
	// TODO: If this is a RICHEDIT control, the control will not
	// send this notification unless you override the CDialog::OnInitDialog()
	// function and call CRichEditCtrl().SetEventMask()
	// with the ENM_CHANGE flag ORed into the mask.
	
	// TODO: Add your control notification handler code here

	 CButton *pBtn;
	//激活单选压缩按钮
	pBtn=(CButton*)GetDlgItem(IDC_RADIO_Compress);
	pBtn->EnableWindow(TRUE);
	//屏蔽Huffman树按钮和单选解压按钮
	pBtn=(CButton*)GetDlgItem(IDC_RADIO_DeCompress);
	pBtn->EnableWindow(FALSE);

    pBtn=(CButton*)GetDlgItem(IDC_BUTTON_HuffmanTree);
	pBtn->EnableWindow(FALSE);
}
/**********************************************************************************
函数名：Text_Measure()
参数：unsigned long w[128]
功能：测试文本中各字符的权值	
说明：各字符的权值存放到w[i]中，文件字符的总数存人到p中,并把字符种类个数存人sum中
**********************************************************************************/

void CHuffmanText::Text_Measure(unsigned long w[128])
{
	int i,ch;
	int C=0;
	char m_cOriginalText[32767];
	for(i=0;i<=127;i++)   //初始化w[i];
		w[i]=0;
	p=0;   //初始化p;
	strcpy(m_cOriginalText,(LPSTR)(LPCTSTR)sOriginalText);//将原文本编辑框的字符复制到m_cOriginal数组中
	ch=m_cOriginalText[C];
	while(ch!='\0')
	{
		p++;     //字符总数个数加1
		w[ch]++; //ch字符权值加1
		ch=m_cOriginalText[++C];//ch指向下一个字符
	}
	sum=0; //字符种类个数初始化
	for(i=0;i<=127;i++)
	{
		if(w[i]!=0)
			sum++;
	}
}

/************************************************************************
函数名：Select()
参数：int n,int *s1,int *s2
功能：选择权值最小的两个字符
说明：从hft[0]到hft[n]中选择parant为0，并且把它们的序号保存到s1和s2中
************************************************************************/

void CHuffmanText::Select(int n,int *s1,int *s2)
{
   int i;
   int min1=max_weight;
   int min2;
   for(i=0;i<=n;i++)    //找最小的结点序号
   {
	   if(hft[i].parant==0&&hft[i].weight!=0)
	   {
		   if(hft[i].weight<(unsigned long)min1)
		   {
               *s1=i;
			   min1=hft[i].weight;
		   }

	   }
   }
   min2=max_weight;
   for(i=0;i<=n;i++)   //找次小的结点序号
   {
	   if(hft[i].parant==0&&hft[i].weight!=0)
	   {
		   if(hft[i].weight<(unsigned long)min2&&(*s1!=i))
		   {
               *s2=i;
			   min2=hft[i].weight;
		   }

	   }
   }
}

/****************************************************************************
函数名：Creat_Tree()
参数：unsigned long w[128]
功能：创建Huffman树
说明：将创建的Huffman树保存到hft[]
*****************************************************************************/

void CHuffmanText::Creat_Tree(unsigned long w[128] )
{
	int i;
    int s1,s2;
	//初始化Huffman树的结点
	for(i=0;i<=254;i++)
	{
		hft[i].lchirld=0;
		hft[i].parant=0;
		hft[i].rchirld=0;
	}
	//将字符在文本出现的次数赋给结点的权值
	for(i=0;i<=127;i++)
	{
		hft[i].weight=w[i];
	}
	//创建huffman树
	for(i=128;i<=128+sum-2;i++)
	{
		Select(i-1,&s1,&s2);   //从hft[0]到hft[n]中选择权值最小的两个结点，并且把它们的序号保存到s1和s2中
        hft[s1].parant=i;    //hft[s1,s2]父结点指向i
		hft[s2].parant=i;
        hft[i].lchirld=s1;   //hft[i]左右孩子结点分别指向s1,s2
		hft[i].rchirld=s2;
		hft[i].weight=hft[s1].weight+hft[s2].weight;
	}
}

/********************************************************************
函数名：Huffman_Code
参数：code hcd[128]
功能：根据创建的Huffman树进行编码
说明：ASCII为i的字符保存在hcd[i]中
*********************************************************************/
void CHuffmanText::Huffman_Code(code hcd[128])
{
	int i,c,root;
	code cd;
	for(i=0;i<=127;i++)
	{
		cd.start=127;  //从Bits[]的127位向前填人编码
		c=i;
	    root=hft[c].parant;
		while(root!=0)    //为根结点时结束
		{
		    cd.start=cd.start-1;
			if(hft[root].lchirld==c)
				cd.Bits[cd.start]=0;  //左孩子赋为"0"
			else if(hft[root].rchirld==c)
				cd.Bits[cd.start]=1;  //右孩子赋为"1"
	       
			c=root;
			root=hft[root].parant; 
            
		}
		hcd[i]=cd;       //把cd的编码赋给hcd[i]
	}
}




/********************************************************************
函数名：OnBUTTONScan1
返回值：void
说明：单击浏览按钮弹出对话框，从中选择要压缩的文件
********************************************************************/
void CHuffmanText::OnBUTTONScan1() 
{
	// TODO: Add your control notification handler code here
	CString fName;
	char Filter[]="所有文件(*.*)|*.*||文本文件(.txt)|*.htc|";
	CFileDialog dlg(TRUE,0,0,OFN_HIDEREADONLY|OFN_FILEMUSTEXIST,(LPCTSTR)Filter,NULL);
	if(dlg.DoModal()==IDOK)
		fName=dlg.GetPathName();    
	else
		return;
	CFile file;
	file.Open(fName,CFile::modeRead);   //打开所选的文件，并只读
	int length=file.GetLength();  //获取文件的长度
	char *temp;   
	temp=new char[length+1];   //开辟length+1长的空间，其中length位置用于存'\0'
	ZeroMemory(temp,length+1);  //将temp清空
	file.Read(temp,length);  //从打开的文件中读取到temp
	temp[length]='\0';     //在temp文件的末尾加入结束符
	file.Close();     //关闭文件
	sOriginalText=temp;   
	SetDlgItemText(IDC_EDIT_OriginalText,sOriginalText);  //在原编辑框中显示文件的内容
    CButton *pBtn;
	//激活单选压缩按钮
	pBtn=(CButton*)GetDlgItem(IDC_RADIO_Compress);
	pBtn->EnableWindow(TRUE);
	//屏蔽Huffman树按钮和单选解压按钮
	pBtn=(CButton*)GetDlgItem(IDC_RADIO_DeCompress);
	pBtn->EnableWindow(FALSE);

    pBtn=(CButton*)GetDlgItem(IDC_BUTTON_HuffmanTree);
	pBtn->EnableWindow(FALSE);

}


/***************************************************************
函数名：DeCompress
返回值：void
说明：根据压缩后得到的二进制流及Huffman树，还原成原来的字符
****************************************************************/
void CHuffmanText::DeCompress()
{

	char m_cCompress[32767];
	strcpy(m_cCompress,(LPSTR)(LPCTSTR)sCompressText);  //将二进制流复制给m_cCompress
	int C=0;
	CString str1;
	int num;
	num=p;   //把字符总数p赋给num
	char ch=m_cCompress[C];
    str.Format("");   //将str清空
    for(num;num>0;num--)
	{
  		int root=128+sum-2;   //找到根结点位置
		while(hft[root].lchirld!=0||hft[root].rchirld!=0)   //找对应的字符
		{
			if(ch=='0')        //是0就搜索Huffman树的左孩子
			   root=hft[root].lchirld;     
			else if(ch=='1')  //是1就搜索Huffman树的右孩子
			   root=hft[root].rchirld;     
		    ch=m_cCompress[++C];			
		}
        
		str1.Format("%c",root);  //存储现在解压的字符
		str=str+str1;      //存贮目前所接压的字符
		
	}
}




/************************************************************************
函数名：OnBUTTONHuffmanTree
返回值：void
说明：单击Huffman树按钮，在Huffman树结构编辑框中显示所创建的Huffman树
************************************************************************/
void CHuffmanText::OnBUTTONHuffmanTree() 
{
	// TODO: Add your control notification handler code here

	int i=0,j=0,k,flag=0;
	int a[127];
    int ch,temp;
    CString HuffmanTree;  //存储Huffman树结构图
	CString HuffmanTree1;
	int column[255];    //记录各结点的显示列数
	for(k=0;k<127;k++)
		column[k]=0;
	column[128+sum-2]=1; //根结点的列数为1
	a[j]=128+sum-2;  //根结点赋给a[0]
	
	ch=64;
	HuffmanTree.Format("");
	HuffmanTree1.Format("%c(%3d)",ch,hft[a[j]].weight); //把 结点的权值和字符写入HuffmanTree
    HuffmanTree=HuffmanTree+HuffmanTree1;
	while(j>=0)
	{
		while(hft[a[j]].lchirld!=0)
		{
			a[j+1]=hft[a[j]].lchirld; //左孩子存入a[j+1]中
			column[a[j+1]]=column[a[j]]+1; //左孩子的列数等于父结点的列数加1