huffmandlg.cpp

对符号进行huffman编码和解码的程序

// HuffmanDlg.cpp : implementation file
//

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanDlg.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_sAdd = _T("");
	m_sYm = _T("");
	m_sDec = _T("");
	m_fGL = 0.0f;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	fGL=0.0;
}

void CHuffmanDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHuffmanDlg)
	DDX_Control(pDX, IDC_YMLIST, m_cYM);
	DDX_Control(pDX, IDC_BMLIST, m_cBM);
	DDX_Text(pDX, IDC_EDIT1, m_sAdd);
	DDX_Text(pDX, IDC_EDIT3, m_sYm);
	DDX_Text(pDX, IDC_EDIT4, m_sDec);
	DDX_Text(pDX, IDC_EDIT2, m_fGL);
	DDV_MinMaxFloat(pDX, m_fGL, 0.f, 1.f);
	//}}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_BUTTON4, OnAdd)
	ON_BN_CLICKED(IDOK2, OnDecode)
	ON_NOTIFY(LVN_ITEMCHANGED, IDC_BMLIST, OnItemchangedBmlist)
	ON_BN_CLICKED(IDC_BUTTON2, OnDelete)
	ON_BN_CLICKED(IDC_BUTTON3, OnClear)
	ON_COMMAND(IDCABORT, Onabort)
	ON_COMMAND(IDHELP, OnHelp)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanDlg message handlers
void CHuffmanDlg::Huffman()
{   
	CString name;   
	int   i=0;   
	M=m_cBM.GetItemCount();
	if(M>0)
	{   
		index=2*M-2;
		tree=new   node[2*M-1];   
		code=new   int[2*M];   
		nodes=new   elem[M];   
		for(i=0;i<M;i++)   
		{   
			nodes[i].name=m_cBM.GetItemText(i,1);
			str=m_cBM.GetItemText(i,2);
			nodes[i].weight=atof((LPTSTR)(LPCTSTR)str);
		}
	}   
	else   
	{   
		return;
	}

	//initialize   nodes[i].codes   
	for(i=0;i<M;i++)   
	{
		nodes[i].code=new   int[2*M];
	}
	//initialize   code     
	for   (i=0;i<2*M;i++)   code[i]=-1;   
	//sort   
	for(i=0;i<M-1;i++)   
	{   
		for(int   j=i+1;j<M;j++)   
		{   
			if(nodes[j-1].weight>nodes[j].weight)   
			{   
				nodes[j-1].weight=nodes[j-1].weight+nodes[j].weight;   
				nodes[j].weight=nodes[j-1].weight-nodes[j].weight;   
				nodes[j-1].weight=nodes[j-1].weight-nodes[j].weight;   
				name=nodes[j-1].name;   
				nodes[j-1].name=nodes[j].name;   
				nodes[j].name=name;   
			}   
		}   
	}   
	for(i=0;i<M;i++)   
	{   
		tree[i].elementary=nodes[i];   
		tree[i].weight=nodes[i].weight;   
		tree[i].leftson=NULL;   
		tree[i].rightson=NULL;   
	}   
}   

void CHuffmanDlg::FreeHuffman()   
{   
	//free   the   recource     
	delete   []tree;   
	delete   []code;   
	for(int   i=0;i<M;i++)   
	{   
		delete   []nodes[i].code;   
	}   
	delete   []nodes;   
} 

void CHuffmanDlg::MakeupTree()   
{
	node   node0,node1,node2;   

	if(index==2*M-2)flag=M;   
	if(index>0)   
	{   
		node0.weight=tree[0].weight+tree[1].weight;   
		node1=tree[0];   
		node2=tree[1];   
		tree[index]=node1;   
		node0.leftson=&tree[index--];   
		tree[index]=node2;   
		node0.rightson=&tree[index--];   
		for(int   i=0;i<flag-2;i++)   
		{   
			tree[i]=tree[i+2];   
		}   
		flag--;   
		for(i=0;i<flag-1;i++)   
		{   
			if(node0.weight<tree[i].weight)   
			break;   
		}   
		for(int   j=flag-1;i<j;j--)   
		{   
			tree[j]=tree[j-1];   
		}   
		tree[i]=node0;   
		MakeupTree();   
	}   
	return;   
}   

void CHuffmanDlg::coding(int   sign,node   *head)   
{   
	if(head!=NULL)   
	{   
		code[sign]=0;   
		coding(sign+1,head->leftson);   
		code[sign]=1;   
		coding(sign+1,head->rightson);   
	}   
	else   
	{   
		return;   
	}   
	if(head->rightson==NULL)   
	{
		for(int   i=0;i<=sign;i++)   
			head->elementary.code[i]=code[i];   
		head->elementary.code[sign]=-1;   
		code[sign]=-1;   
		for(int   j=0;head->elementary.name!=nodes[j].name;j++);   
		for(i=0;code[i]>=0;i++)   
		{   
			nodes[j].code[i]=code[i];   
		}   
		nodes[j].code[i]=-1;   
		// 添加到列表控件
		nCount=m_cYM.GetItemCount();
		str.Format("%d",nCount+1);
		m_cYM.InsertItem(nCount,str);
		str.Format("%s",head->elementary.name);
		m_cYM.SetItemText(nCount,1,str);
		str.Format("%f",head->elementary.weight);
		m_cYM.SetItemText(nCount,2,str);
		str.Empty();	
		for(i=0;head->elementary.code[i]!=-1;i++)
		{
			str2.Format("%d",head->elementary.code[i]);
			str+=str2;
		}
		m_cYM.SetItemText(nCount,3,str);
		str.Format("%d",i);
		m_cYM.SetItemText(nCount,4,str);
		return;   
	}   
}   

void CHuffmanDlg::doCode()   
{   
	MakeupTree();   
	coding(0,&tree[0]);
}

CString CHuffmanDlg::DeCode(CString dec,node *head)
{   
	node *bl=head;
	int j=dec.GetLength();
	CString str="";
	for(int i=0;i<j;)
	{
		while (i<j)
		{
			if (dec.GetAt(i)=='0')
			{
				if (bl->leftson==NULL)
					break;
				bl=bl->leftson;
			}
			else if (dec.GetAt(i)=='1')
			{
				if (bl->rightson==NULL)
					break;
				bl=bl->rightson;
			}
			else
			{
				AfxMessageBox("待译码的数据中只能有'0'或'1'！");
				return "";
			}
			i++;
		}
		if (i<=j)
		{
			str+=bl->elementary.name;
			bl=head;
		}
	}
	return str;
}
//////////////////////////////////////////////////////////////////////////

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
	//设置列表控件风格
	m_cBM.SetExtendedStyle(LVS_EX_FULLROWSELECT | LVS_EX_GRIDLINES);
	m_cYM.SetExtendedStyle(LVS_EX_FULLROWSELECT | LVS_EX_GRIDLINES);
	//添加列表栏目
	m_cBM.InsertColumn(0,"序号",LVCFMT_CENTER,40);
	m_cBM.InsertColumn(1,"符号",LVCFMT_CENTER,100);
	m_cBM.InsertColumn(2,"概率",LVCFMT_CENTER,60);
	m_cYM.InsertColumn(0,"序号",LVCFMT_CENTER,40);
	m_cYM.InsertColumn(1,"符号",LVCFMT_CENTER,100);
	m_cYM.InsertColumn(2,"概率",LVCFMT_CENTER,80);
	m_cYM.InsertColumn(3,"哈夫曼码",LVCFMT_CENTER,100);
	m_cYM.InsertColumn(4,"码长",LVCFMT_CENTER,50);
	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::OnAdd() 
{
	UpdateData(TRUE);
	
	if (m_fGL<=0||m_fGL>=1)
	{
		AfxMessageBox("概率必需在(0,1)区间！");
		m_fGL=0;
		UpdateData(FALSE);
		return;
	}
	else if (m_sAdd.IsEmpty())
		{
			AfxMessageBox("请输入添加的数据(符号)！");
			return;
		}
	int num(m_cBM.GetItemCount());
	for (int i(0);i<num;i++)
	{
		TRACE(m_sAdd+" "+m_cBM.GetItemText(i,2));
		if(m_sAdd==m_cBM.GetItemText(i,1))
		{
			AfxMessageBox("符合重复，请重新输入！");
			GetDlgItem(IDC_EDIT1)->SetFocus();
			return;
		}
	}
	float fgl=m_fGL;
	CString str="概率(0-1之间)";
	//避免浮点数比较大小有误差
	if (fgl+fGL>1.000001)
	{
		AfxMessageBox("概率之和应不大于1。");
		return;
	}
	fGL+=fgl;
	str.Format("概率(%f)",fGL);
	GetDlgItem(IDC_STATICGL)->SetWindowText(str);
	m_cYM.DeleteAllItems();
	nCount=m_cBM.GetItemCount();
	str.Format("%d",nCount+1);
	m_cBM.InsertItem(nCount,str);
	m_cBM.SetItemText(nCount,1,m_sAdd);
	str.Format("%f",m_fGL);
	m_cBM.SetItemText(nCount,2,str);
	m_sAdd.Empty();
	m_fGL=0;
	UpdateData(FALSE);
}
//编码
void CHuffmanDlg::OnOK()
{
	UpdateData(TRUE);
	if (m_cBM.GetItemCount()<=0)
	{
		AfxMessageBox("请先添加数据！");
		return;
	}
	m_cYM.DeleteAllItems();
	Huffman();
	doCode();
	UpdateData(FALSE);
}   
//译码
void CHuffmanDlg::OnDecode() 
{
	UpdateData(TRUE);
	if (m_cYM.GetItemCount()<=0)
	{
		AfxMessageBox("请先添加数据,编码生成Huffman树！");
		return;
	}
	if (m_sYm.IsEmpty())
	{
		AfxMessageBox("请输入编码后的数据！");
		return;
	}
	m_sDec=DeCode(m_sYm,&tree[0]);
	UpdateData(FALSE);
}
//列表选择改变时触发事件
void CHuffmanDlg::OnItemchangedBmlist(NMHDR* pNMHDR, LRESULT* pResult) 
{
	NM_LISTVIEW* pNMListView = (NM_LISTVIEW*)pNMHDR;
	// TODO: Add your control notification handler code here
	m_sAdd=m_cBM.GetItemText(pNMListView->iItem,1);
	str=m_cBM.GetItemText(pNMListView->iItem,2);
	m_fGL=atof(str);
	UpdateData(FALSE);
	*pResult = 0;
}
//删除一条数据
void CHuffmanDlg::OnDelete() 
{
	// TODO: Add your control notification handler code here
	POSITION pos = m_cBM.GetFirstSelectedItemPosition();
	if (pos==NULL)
	{
		AfxMessageBox("请先选择要删除的数据！");
		return;
	}
	int item=m_cBM.GetNextSelectedItem(pos);
	m_cBM.DeleteItem(item);
	CString str;
	fGL=0.0;
	for (int i=0;i<m_cBM.GetItemCount();i++)
	{
		str.Format("%d",i+1);
		m_cBM.SetItemText(i,0,str);
		str=m_cBM.GetItemText(i,2);
		fGL+=atof(str);
	}
	str.Format("概率(%f)",fGL);
	GetDlgItem(IDC_STATICGL)->SetWindowText(str);
	m_cYM.DeleteAllItems();
}
//清除数据
void CHuffmanDlg::OnClear() 
{
	// TODO: Add your control notification handler code here
	m_cBM.DeleteAllItems();
	m_cYM.DeleteAllItems();
	fGL=0.0;
	GetDlgItem(IDC_STATICGL)->SetWindowText("概率(0-1之间)");
}
//关于对话框
void CHuffmanDlg::Onabort() 
{
	CAboutDlg dlg;
	dlg.DoModal();
	
}

void CHuffmanDlg::OnHelp() 
{
	ShellExecute(this->m_hWnd,"open","Huffman.chm","","",1);
	
}