huffmandlg.cpp

哈夫曼的编码译码器

// huffmanDlg.cpp : implementation file
//

#include "stdafx.h"
#include "huffman.h"
#include "huffmanDlg.h"
#include <fstream.h>

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

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanDlg dialog

CHuffmanDlg::CHuffmanDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CHuffmanDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CHuffmanDlg)
	m_huffnew = _T("");
	m_huffold = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CHuffmanDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHuffmanDlg)
	DDX_Text(pDX, IDC_HUFFNEW_EDIT, m_huffnew);
	DDX_Text(pDX, IDC_HUFFOLD_EDIT, m_huffold);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CHuffmanDlg, CDialog)
	//{{AFX_MSG_MAP(CHuffmanDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_FILEIN_BUTTON, OnFileinButton)
	ON_BN_CLICKED(IDC_SAVE_BUTTON, OnSaveButton)
	ON_BN_CLICKED(IDC_CODE_BUTTON, OnCodeButton)
	ON_BN_CLICKED(IDC_DECODE_BUTTON, OnDecodeButton)
	ON_BN_CLICKED(IDC_PRESS_BUTTON, OnPressButton)
	ON_BN_CLICKED(IDC_UNPRESS_BUTTON, OnUnpressButton)
	ON_BN_CLICKED(IDC_CHN_BUTTON, OnChnButton)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanDlg message handlers

BOOL CHuffmanDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	num = 0 ;
	for (int i=0;i<200;i++)
		sta[i]=0;

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CHuffmanDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CHuffmanDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CHuffmanDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}


void CHuffmanDlg::haffman(int weight[],char ch[],int n,HafNode haffTree[])  //生成哈夫曼树的函数
{
	int i,j,m1,m2,x1,x2;
	for (i=0;i<2*n-1;i++)
	{
		if(i<n)
		{
			haffTree[i].weight=weight[i];
			haffTree[i].ch=ch[i];
		}
		else
		haffTree[i].weight=0;
		haffTree[i].parent=-1;
		haffTree[i].flag=0;
		haffTree[i].lchild=-1;
		haffTree[i].rchild=-1;
	}
	for (i=0;i<n-1;i++)
	{
		m1=m2=10000;
		x1=x2=0;
		for (j=0;j<n+i;j++)
		{
			if (haffTree[j].weight<m1&&haffTree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;
			}
			else if(haffTree[j].weight<m2 && haffTree[j].flag==0)
			{
				m2=haffTree[j].weight;
				x2=j;
			}
		}
		haffTree[x1].parent= n + i;
		haffTree[x2].parent = n + i;
		haffTree[x1].flag = 1;
		haffTree[x2].flag = 1;
		haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight;
		haffTree[n+i].lchild = x1;
		haffTree[n+i].rchild = x2;
	}

	FILE *fp;
    fp=fopen("huffman.hfm","w+");
	printf("%d\n",n);
	fprintf(fp,"%d\n",n);
	for (i=0;i<n;i++)	
		fprintf(fp,"%c %d %d %d\n",haffTree[i].ch,haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild);
    for (i=n;i<2*n-1;i++)
		fprintf(fp,"%d %d %d\n",haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild);	
    fclose(fp);

}

void CHuffmanDlg::HaffmanCode ( HafNode haffTree[], int n, Code haffCode[] )   //生成哈夫曼编码的函数
{
	Code *cd=( Code *) malloc (sizeof (Code));
	int i,j,child,parent;	
	for (i=0; i<n; i++)
	{
		cd->start=n-1;
		cd->weight=haffTree[i].weight;
		cd->ch=haffTree[i].ch;
		child=i;
		parent=haffTree[child].parent;
		while (parent !=-1)
		{
			if (haffTree[parent].lchild==child)
				cd->bit[cd->start]=0;
			else
				cd->bit[cd->start]=1;

			cd->start--;
			child =parent;
			parent=haffTree[child].parent;
		}
		for (j=cd->start+1; j<n; j++)
			haffCode[i].bit[j]=cd->bit[j];
		haffCode [i].start = cd->start+1;
		haffCode [i].weight=cd->weight;
		haffCode [i].ch=cd->ch;
	}
}






void CHuffmanDlg::OnFileinButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE);

	CString m_path;
	CFileDialog dlg(true,NULL,NULL,NULL,"Txt files|*.txt|All files|*.*||");
	if(dlg.DoModal()==IDOK)
		m_path=dlg.GetPathName();
	CString str ;
	char ch;
	int i=0 ,j;
	ifstream fin;
	fin.open(m_path);
	m_huffold = "" ;
	while(fin.get(ch))
	{		
		for (i=0;i<num;i++)
			if (ch == fuhao[i])
				break;
		if (i==num){
			fuhao[num]=ch ; 
			sta[num]++ ;
			num++ ;
		}
		else sta[i]++;
		m_huffold += ch ;
	}



	UpdateData(FALSE) ;
}



void CHuffmanDlg::OnSaveButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	CString str;
	CString FilePathName;
	CFileDialog dlg(FALSE,NULL,"Code",NULL,"Txt files|*.txt|All files|*.*||");
	if(dlg.DoModal()==IDOK)
	{
		FilePathName=dlg.GetPathName()+".txt";
     	ofstream fout(FilePathName);//ios::out|ios::app
    	if(!(fout.is_open()))
		{
    		cerr<<"error";
    		exit(1);
		}

			fout<<m_huffnew;
	
	}

}

void CHuffmanDlg::OnCodeButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	m_huffnew="" ;


	int i,j;

	
	myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*num+1));
	myHaffCode =(Code *)malloc (sizeof (Code)*num);
	haffman(sta,fuhao,num,myHaffTree);
	HaffmanCode(myHaffTree,num,myHaffCode);
	FILE *fp ;

	fp=fopen("hfmtree.hfm","w+");		
	for (i=0;i<num;i++)
	{		
        for ( j=myHaffCode[i].start; j<num; j++)
		{	
			fprintf(fp,"%d",myHaffCode[i].bit[j]);
		}
        	fprintf(fp,"\n");
	}
	fclose(fp);
		

	
	fp=fopen("hfmtree.hfm","r");

	i=0;
	while (feof(fp)==0)
    {        	
			fscanf(fp,"%s",&myHaffCode[i].bit);
            i++;
	}
	fclose(fp);	


	DeleteFile("hfmtree.hfm") ;

	for (i=0;i<m_huffold.GetLength();i++){
		for (j=0;j<num;j++)
		if (m_huffold.GetAt(i) == myHaffCode[j].ch )
			m_huffnew += myHaffCode[j].bit ;
	}
	UpdateData(FALSE) ;
}

void CHuffmanDlg::OnDecodeButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	FILE *fp ;
	fp=fopen("huffman.hfm","r");
    int i,n;
	fscanf(fp,"%d",&n);
	fgetc(fp) ;
	HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1));
	for (i=0;i<n;i++){
		myHaffTree[i].ch=fgetc(fp) ;
        fscanf(fp,"%d %d %d",&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
		fgetc(fp) ;
	}
	for (i=n;i<2*n-1;i++)
		fscanf(fp,"%d %d %d\n",&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
    fclose(fp);
	int j ;
	i=2*n-2;
	m_huffnew = "" ;
	for ( j = 0 ; j < m_huffold.GetLength() ; j ++ )
    {		
		if (m_huffold.GetAt(j)=='0')                    //若编码为０，则找此结点的左孩子；
			i=myHaffTree[i].lchild;
		if (m_huffold.GetAt(j)=='1')                    //若编码为１，则找此结点的右孩子；　
			i=myHaffTree[i].rchild;   
		if (i<n)
		{
			if (myHaffTree[i].ch==' ')	m_huffnew += " " ;
			else
			m_huffnew += myHaffTree[i].ch;            
			i=2*n-2;
		}
	}
	UpdateData(FALSE) ;		
}

void CHuffmanDlg::OnPressButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	int i , sum = m_huffnew.GetLength() , tem , n ;
	CString str , str1 ;
	tem = sum;
	str = "" ;
	str.Format("%d", sum % 6 ) ;
	
	sum = tem ;

	tem %= 6 ;
	tem = 6 - tem  ;
	m_huffold = m_huffnew ;
	for ( i = 0 ; i < tem ; i ++ )
		m_huffnew += "0" ;
	if (tem == 0)	tem = sum / 6 ;
	else	tem = sum / 6 + 1 ;

	for ( i = 0 ; i < tem ; i ++ ){
		n = 0 ;

		n += ( m_huffnew.GetAt( i * 6 + 0 ) - '0' ) * 32 ;
		n += ( m_huffnew.GetAt( i * 6 + 1 ) - '0' ) * 16 ;
		n += ( m_huffnew.GetAt( i * 6 + 2 ) - '0' ) * 8 ;
		n += ( m_huffnew.GetAt( i * 6 + 3 ) - '0' ) * 4 ;
		n += ( m_huffnew.GetAt( i * 6 + 4 ) - '0' ) * 2 ;
		n += ( m_huffnew.GetAt( i * 6 + 5 ) - '0' ) ;
		
		str1.Format("%c",n+50) ;
		str += str1 ; 
	}
	m_huffnew = str ;

	
	CString FilePathName;
	CFileDialog dlg(FALSE,NULL,"press",NULL,"Txt files|*.txt|All files|*.*||");
	if(dlg.DoModal()==IDOK)
	{
		FilePathName=dlg.GetPathName() + ".txt";
     	ofstream fout(FilePathName);//ios::out|ios::app
    	if(!(fout.is_open()))
		{
    		cerr<<"error";
    		exit(1);
		}
			fout<<m_huffnew;	
	}
	UpdateData(FALSE) ;
}

void CHuffmanDlg::OnUnpressButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	int len = m_huffold.GetLength() ;
	int n , i , j ; 
	CString str="" ;
	n = m_huffold.GetAt(0) -'0' ;
//	m_huffnew.Format("%d", n ) ;
	if ( n == 0 )	len ++ ;
	for ( i = 1 ; i < len - 1 ; i ++ ){
		n = m_huffold.GetAt(i) ;
		n -= 50 ;

		if ( n / 32 )	str += "1" ;
		else	str += "0" ;
		n %= 32 ;
		if ( n / 16 )	str += "1" ;
		else	str += "0" ;
		n %= 16 ;
		if ( n / 8 )	str += "1" ;
		else	str += "0" ;
		n %= 8 ;
		if ( n / 4 )	str += "1" ;
		else	str += "0" ;
		n %= 4 ;
		if ( n / 2 )	str += "1" ;
		else	str += "0" ;
		n %= 2 ;
		if ( n )	str += "1" ;
		else	str += "0" ;
	}
	
	n = m_huffold.GetAt(i) - 50 ;
	if ( n >= 1 ){
		if ( n / 32 )	str += "1" ;
		else	str += "0" ;
	}
	n %= 32 ;
	if ( n >= 2){
		if ( n / 16 )	str += "1" ;
		else	str += "0" ;
	}
	n %= 16 ; 
	if ( n >= 3 ){
		if ( n / 8 )	str += "1" ;
		else	str += "0" ;
	}
	n %= 8 ;
	if ( n >= 4 ){
		if ( n / 4 )	str += "1" ;
		else	str += "0" ;
	}
	n %= 4 ;
	if ( n >= 5 ){
		if ( n / 2 )	str += "1" ;
		else	str += "0" ;
	}
	n %= 2;
	if ( n )	str += "1" ;
	else	str += "0" ;

//	m_huffold = m_huffnew ;
	m_huffnew = str ;
	UpdateData(FALSE) ;
}

void CHuffmanDlg::OnChnButton() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE) ;
	m_huffold = m_huffnew ;
	m_huffnew = "" ;
	UpdateData(FALSE) ;
}