compressdlg.cpp

实现了一个相对简单的哈弗曼树的压缩算法

// compressDlg.cpp : implementation file
//

#include "stdafx.h"
#include "compress.h"
#include "compressDlg.h"
#include "fstream.h"
#include "HFMTree.h"
#include "cmath"
#include "HelpDlg.h"
//#include <map>

#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()

/////////////////////////////////////////////////////////////////////////////
// CCompressDlg dialog

CCompressDlg::CCompressDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CCompressDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CCompressDlg)
	m_ResourcePath = _T("");
	m_KeyPath = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	for(int i=0;i<=99999;i++)
		ResourceIn[i]=NULL;
}

void CCompressDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CCompressDlg)
	DDX_Text(pDX, IDC_EDIT1, m_ResourcePath);
	DDX_Text(pDX, IDC_EDIT2, m_KeyPath);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CCompressDlg, CDialog)
	//{{AFX_MSG_MAP(CCompressDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_COMPRESS, OnCompress)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	ON_BN_CLICKED(IDC_UNCOMPRESS, OnUncompress)
	ON_BN_CLICKED(IDC_HELP1, OnHelp1)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CCompressDlg message handlers

BOOL CCompressDlg::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
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CCompressDlg::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 CCompressDlg::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 CCompressDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CCompressDlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	for(int i=0;i<=99999;i++)
		ResourceIn[i]=NULL;
	CFileDialog Find(true,NULL,NULL,OFN_HIDEREADONLY,"文本文档(*.txt)|*.txt",NULL);
	//CFileDialog Find(true,NULL,NULL,OFN_HIDEREADONLY,NULL,NULL);
	if(IDOK==Find.DoModal())
	{
		m_ResourcePath=Find.GetPathName();
		UpdateData(FALSE);
		ifstream in(m_ResourcePath);
		for(int i=0;i<=99999;i++)
			in>>ResourceIn[i];
		GetDlgItem(IDC_COMPRESS)->EnableWindow();
		GetDlgItem(IDC_BUTTON2)->EnableWindow();
		//MessageBox(ResourceIn);
	}
}

void CCompressDlg::OnCompress() 
{
	// TODO: Add your control notification handler code here
	HFMTree hfmTree[90];
	for(int i=1;i<=26;i++)
		hfmTree[i].data=(char)(i+96);			//哈弗曼树的初始化
	for(i=0;i<100000&&ResourceIn[i]!=NULL;i++)
	{
		switch(ResourceIn[i])
		{
		case 'a':
			hfmTree[1].weight++;break;
		case 'b':
			hfmTree[2].weight++;break;
		case 'c':
			hfmTree[3].weight++;break;
		case 'd':
			hfmTree[4].weight++;break;
		case 'e':
			hfmTree[5].weight++;break;
		case 'f':
			hfmTree[6].weight++;break;					//权值的统计
		case 'g':
			hfmTree[7].weight++;break;
		case 'h':
			hfmTree[8].weight++;break;
		case 'i':
			hfmTree[9].weight++;break;
		case 'j':
			hfmTree[10].weight++;break;
		case 'k':
			hfmTree[11].weight++;break;
		case 'l':
			hfmTree[12].weight++;break;
		case 'm':
			hfmTree[13].weight++;break;
		case 'n':
			hfmTree[14].weight++;break;
		case 'o':
			hfmTree[15].weight++;break;
		case 'p':
			hfmTree[16].weight++;break;
		case 'q':
			hfmTree[17].weight++;break;
		case 'r':
			hfmTree[18].weight++;break;
		case 's':
			hfmTree[19].weight++;break;
		case 't':
			hfmTree[20].weight++;break;
		case 'u':
			hfmTree[21].weight++;break;
		case 'v':
			hfmTree[22].weight++;break;
		case 'w':
			hfmTree[23].weight++;break;
		case 'x':
			hfmTree[24].weight++;break;
		case 'y':
			hfmTree[25].weight++;break;
		case 'z':
			hfmTree[26].weight++;break;
		default :;

		}

	}

	ofstream outkeyfile("key.dat");
	for(i=1;i<=26;i++)
	outkeyfile<<hfmTree[i].weight<<'~';
	////////////////////////////////////////////////////生成哈弗曼树//////////////////////////////////////////////////
	int k1=1,k2=1;			//记录权值最小的节点
	for( i=27;i<=27+24;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			if(hfmTree[j].weight<=hfmTree[k1].weight)
				k1=j;
		}
		for(j=1;j<=i-1;j++)
			if(hfmTree[j].weight<=hfmTree[k2].weight&&j!=k1)
				k2=j;
			//CString str1;
			//str1.Format("%d,%d",k1,k2);
			//MessageBox(str1);
			hfmTree[i].lchild=k1;
			hfmTree[i].rchild=k2;
			hfmTree[k1].parent=i;
			hfmTree[k2].parent=i;
			hfmTree[i].weight=hfmTree[k1].weight+hfmTree[k2].weight;
			hfmTree[k1].weight=100000;
			hfmTree[k2].weight=100000;
	}
	////////////////////////////////////////////////////////哈弗曼编码的生成//////////////////////////////////////////
	CString str[27],formerStr[27];
	int pt;
	for(i=1;i<=26;i++)
	{
		pt=i;
		while(hfmTree[pt].parent!=0)
		{
			if(pt==hfmTree[hfmTree[pt].parent].lchild)
				formerStr[i]+='1';
			if(pt==hfmTree[hfmTree[pt].parent].rchild)
				formerStr[i]+='0';
			pt=hfmTree[pt].parent;
		}
		str[i]=convert(formerStr[i]);


	}
	//for(i=1;i<=26;i++)
	//MessageBox(str[1]);

CString outstr="";
	for(i=0;i<10000&&ResourceIn[i]!=NULL;i++)
	{
		switch(ResourceIn[i])
		{
		case 'a':
			outstr+=str[1];break;
		case 'b':
			outstr+=str[2];break;
		case 'c':
			outstr+=str[3];break;
		case 'd':
			outstr+=str[4];break;
		case 'e':
			outstr+=str[5];break;
		case 'f':
			outstr+=str[6];break;					//生成压缩文件
		case 'g':
			outstr+=str[7];break;
		case 'h':
			outstr+=str[8];break;
		case 'i':
			outstr+=str[9];break;
		case 'j':
			outstr+=str[10];break;
		case 'k':
			outstr+=str[11];break;
		case 'l':
			outstr+=str[12];break;
		case 'm':
			outstr+=str[13];break;
		case 'n':
			outstr+=str[14];break;
		case 'o':
			outstr+=str[15];break;
		case 'p':
			outstr+=str[16];break;
		case 'q':
			outstr+=str[17];break;
		case 'r':
			outstr+=str[18];break;
		case 's':
			outstr+=str[19];break;
		case 't':
			outstr+=str[20];break;
		case 'u':
			outstr+=str[21];break;
		case 'v':
			outstr+=str[22];break;
		case 'w':
			outstr+=str[23];break;
		case 'x':
			outstr+=str[24];break;
		case 'y':
			outstr+=str[25];break;
		case 'z':
			outstr+=str[26];break;
		default :
			outstr+=ResourceIn[i];break;
		}
	}
	///////////////////////////////////////////////////////////////
	//MessageBox(outstr);
	i=outstr.GetLength();
	int k=i%4;											//进行压缩
	for(i=1;i<=k;i++)
		outstr+='0';
	CString changeStr;
	changeStr.Format("%d",k);
	changeStr+=outstr;
	outstr=TwoT16(changeStr);
	
/////////////////////////////////////////////////////////////////


	//MessageBox(outstr);
	CFileDialog save(false,NULL,NULL,OFN_HIDEREADONLY,"文本文档(*.txt)|*.txt",NULL);
	if(IDOK==save.DoModal())
	{
	ofstream outfile(save.GetPathName()+=".txt");
			outfile<<outstr;
	outfile.close();
	for(int i=0;i<=99999;i++)
		ResourceIn[i]=NULL;
	}
	
}

void CCompressDlg::OnButton2() 
{
	// TODO: Add your control notification handler code here

	CFileDialog Find(true,NULL,NULL,OFN_HIDEREADONLY,"秘钥文件(*.dat)|*.dat",NULL);
	if(IDOK==Find.DoModal())
	{
		m_KeyPath=Find.GetPathName();
		UpdateData(FALSE);
		ifstream keyin(m_KeyPath);
		for(int i=0;i<=99;i++)
			keyin>>keyIn[i];
		keyin.close();
		GetDlgItem(IDC_UNCOMPRESS)->EnableWindow();
		GetDlgItem(IDC_COMPRESS)->EnableWindow(false);
		
	}
}

void CCompressDlg::OnUncompress() 
{
	// TODO: Add your control notification handler code here
	int keyWeight[27];
	int k=0;			//记录下面j的位置
	for(int i=1;i<=26;i++)
	{
		keyWeight[i]=0;

		for(int j=k;j<=99&&keyIn[j]!=NULL;j++)
		{
			if(keyIn[j]!='~')
				keyWeight[i]=keyWeight[i]*10+int(keyIn[j])-48;
			else 
			{
				k=j+1;
				break;
			}

			
		}
		//CString str;
		//str.Format("%d",keyWeight[i]);
		//MessageBox(str);

		
	}
	HFMTree keyTree[90];
	for( i=1;i<=26;i++)
	{
		keyTree[i].data=(char)(i+96);
		keyTree[i].weight=keyWeight[i];
		//MessageBox(&keyTree[i].data);
	}
	///////////////////////////////////////////////////////建立输出的哈弗曼树///////////////////////////////////////////////
	int k1=1,k2=1;			//记录权值最小的节点
	for( i=27;i<=27+24;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			if(keyTree[j].weight<=keyTree[k1].weight)
				k1=j;
		}
		for(j=1;j<=i-1;j++)
			if(keyTree[j].weight<=keyTree[k2].weight&&j!=k1)
				k2=j;
			//CString str1;
			//str1.Format("%d,%d",k1,k2);
			//MessageBox(str1);
			keyTree[i].lchild=k1;
			keyTree[i].rchild=k2;
			keyTree[k1].parent=i;
			keyTree[k2].parent=i;
			keyTree[i].weight=keyTree[k1].weight+keyTree[k2].weight;
			keyTree[k1].weight=100000;
			keyTree[k2].weight=100000;
	}
	////////////////////////////////////////////////////////解压缩的实现/////////////////////////////////////////////////////
	CString unCopressStr="",UnComstr="";
	for(i=0;i<100000&&ResourceIn[i]!=NULL;i++)
		UnComstr+=ResourceIn[i];
	UnComstr=UNCopmpress(UnComstr);
	int pt=51;
	for(i=0;i<UnComstr.GetLength();i++)
	{
		//pt=i+1;
		if(keyTree[pt].lchild==0&&keyTree[pt].rchild==0)
		{
			unCopressStr+=keyTree[pt].data;
			pt=51;
			i--;
		}
		else
		{
			switch(UnComstr[i])
			{
			case '1':			
				pt=keyTree[pt].lchild;
				break;
			case '0':
				
				pt=keyTree[pt].rchild;
				break;
			default :;
				
			}
		}
	}
	//MessageBox(unCopressStr);
	CFileDialog save(false,NULL,NULL,OFN_HIDEREADONLY,"文本文档(*.txt)|*.txt",NULL);
	if(IDOK==save.DoModal())
	{
	ofstream outfile(save.GetPathName()+=".txt");
	for(int j=0;j<unCopressStr.GetLength();j++)
			outfile<<unCopressStr[j];
	outfile.close();
	}
}

CString CCompressDlg::convert(CString str)
{
	CString s;
	for(int i=str.GetLength()-1;i>=0;i--)
		s+=str[i];
	return s;

}

double CCompressDlg::TwoTTen(CString str)
{
	double dou=0;
	for(int i=0;i<str.GetLength();i++)
	{
		if(str[i]=='1')
		{
			dou+=pow(2,str.GetLength()-1-i);
		}
	}
	return dou;
}

CString CCompressDlg::TwoT16(CString str)
{
	CString returnstr;
	CString chstr[9000];
	returnstr+=str[0];
	int j=0;
	for(int i=1;i<str.GetLength();i++)
	{
		if(i%4==0)
			chstr[j++]+=str[i];
		else
			chstr[j]+=str[i];
	}
	//for(i=0;i<j;i++)
	//MessageBox(chstr[i]);
	for(i=0;i<j;i++)
	{
		if(chstr[i]=="0000")
			returnstr+='0';
		else if(chstr[i]=="0001")
			returnstr+='1';
		else if(chstr[i]=="0010")
			returnstr+='2';
		else if(chstr[i]=="0011")
			returnstr+='3';
		else if(chstr[i]=="0100")
			returnstr+='4';
		else if(chstr[i]=="0101")
			returnstr+='5';
		else if(chstr[i]=="0110")
			returnstr+='6';
		else if(chstr[i]=="0111")
			returnstr+='7';
		else if(chstr[i]=="1000")
			returnstr+='8';
		else if(chstr[i]=="1001")
			returnstr+='9';
		else if(chstr[i]=="1010")
			returnstr+='A';
		else if(chstr[i]=="1011")
			returnstr+='B';
		else if(chstr[i]=="1100")
			returnstr+='C';
		else if(chstr[i]=="1101")
			returnstr+='D';
		else if(chstr[i]=="1110")
			returnstr+='E';
		else if(chstr[i]=="1111")
			returnstr+='F';
		
	}
	//(returnstr);
	return returnstr;
}

CString CCompressDlg::UNCopmpress(CString chstr)
{
	
	CString returnstr="";
	int kj=int(chstr[0])-48;
	for(int i=1;i<chstr.GetLength();i++)
	{
		if(chstr[i]=='0')
			returnstr+="0000";
		else if(chstr[i]=='1')
			returnstr+="0001";
		else if(chstr[i]=='2')
			returnstr+="0010";
		else if(chstr[i]=='3')
			returnstr+="0011";
		else if(chstr[i]=='4')
			returnstr+="0100";
		else if(chstr[i]=='5')
			returnstr+="0101";
		else if(chstr[i]=='6')
			returnstr+="0110";
		else if(chstr[i]=='7')
			returnstr+="0111";
		else if(chstr[i]=='8')
			returnstr+="1000";
		else if(chstr[i]=='9')
			returnstr+="1001";
		else if(chstr[i]=='A')
			returnstr+="1010";
		else if(chstr[i]=='B')
			returnstr+="1011";
		else if(chstr[i]=='C')
			returnstr+="1100";
		else if(chstr[i]=='D')
			returnstr+="1101";
		else if(chstr[i]=='E')
			returnstr+="1110";
		else if(chstr[i]=='F')
			returnstr+="1111";
	}
	//MessageBox(returnstr);
	return returnstr;
}

//DEL void CCompressDlg::OnHelp() 
//DEL {
//DEL 	// TODO: Add your control notification handler code here
//DEL 	HelpDlg dlg;
//DEL 	dlg.DoModal();
//DEL }

void CCompressDlg::OnHelp1() 
{
	// TODO: Add your control notification handler code here
	HelpDlg dlg;
	dlg.DoModal();
}