resultdlg1.cpp

这是一些Huffman编码的代码

/***************************************************
              Huffman编码设计辅助工具   
            杭州电子科技大学 胡峰令编写
***************************************************/


// ResultDlg1.cpp : implementation file
//

#include "stdafx.h"
#include "Huffman.h"
#include "ResultDlg1.h"
#include "math.h"

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

/////////////////////////////////////////////////////////////////////////////
// CResultDlg dialog


CResultDlg::CResultDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CResultDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CResultDlg)
	//}}AFX_DATA_INIT
}


void CResultDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CResultDlg)
	DDX_Control(pDX, IDC_LIST1, m_ListCtl);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CResultDlg, CDialog)
	//{{AFX_MSG_MAP(CResultDlg)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CResultDlg message handlers

BOOL CResultDlg::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	three=0;
	lea=1;
	be=new char*[num];
	LVCOLUMN column;
	column.mask=LVCF_FMT|LVCF_WIDTH|LVCF_TEXT|LVCF_SUBITEM;
	column.fmt=LVCFMT_LEFT;
	column.cx=50;
	column.iSubItem=0;
	column.pszText="编号";
	m_ListCtl.InsertColumn(0,&column);
	column.iSubItem=1;
	column.cx=80;
	column.pszText="频度";
	m_ListCtl.InsertColumn(1,&column);
	column.iSubItem=2;
	column.cx=170;
	column.pszText="Huffman编码";
	m_ListCtl.InsertColumn(2,&column);

	column.iSubItem=3;
	column.cx=96;
	column.pszText="信息冗余量";
	m_ListCtl.InsertColumn(3,&column);
	CString str,str1,str2;
	int i=0;

	item.mask=LVIF_TEXT;

	if(flag==0)
		Huffmancoding();
	if(flag==1)
		Extendcoding(num,0,flag);
	if(flag==2)
		Extendcoding2();
	if(flag==3)
	{
		Extendcoding(num,0,0);
		Extendcoding2();
		char s[256];
		for(i=0;i<num;i++)
		{
			item.iItem=i;
	        item.iSubItem=0;
	        str.Format("%d",i);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",wtemp[i]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(i,1,str1);
	        m_ListCtl.SetItemText(i,2,be[i]);
		}
		str1.Format("%f",lea);
		m_ListCtl.SetItemText(i-1,3,str1);
	}
/*	item.iItem=i;
	item.iSubItem=0;
	str.Format("%d",i);
	strcpy(s,str);
	item.pszText=s;
	str1.Format("%f",w[i]);
	m_ListCtl.InsertItem(&item);
	m_ListCtl.SetItemText(0,1,str1);
	m_ListCtl.SetItemText(0,2,HC[i]);
	for(i=1;i<num;i++)
	{
	item.iItem=i;
	item.iSubItem=0;
	str.Format("%d",i);
	strcpy(s,str);
	item.pszText=s;
	str1.Format("%f",w[i]);
	m_ListCtl.InsertItem(&item);
	m_ListCtl.SetItemText(i,1,str1);
	m_ListCtl.SetItemText(i,2,HC[i]);
	}*/


//	int a=1,b=1;
//	str.Format("%d\r\n%d",a,b);
//	m_Editr.SetWindowText("sdvasda\r\nasdadfa");
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}

void CResultDlg::Extendcoding(int num,int flag, int a)
{//进行二段扩展编码
	int k=1,l=0,k2,i,temp;
	CString str,str1;
	char s[256];
	two=0;
	
	while(k<=num)
	{
		k=k*2;
		l++;
	}
	for(k=1;k<l;k++)
	{
		temp=1;
		for(i=0;i<k;i++)
		{
			temp=temp*2;
		}
		temp--;
		k2=givenum(num-temp)+k;
		if(type)
		{
		if(flag==0)
		{
			item.iItem=two;
	        item.iSubItem=0;
	      //  str.Format("两段");
	       // strcpy(s,str);
	        item.pszText="";
	        str1.Format("%d",k);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(two,1,str1);
			str1.Format("%d",k2);
	        m_ListCtl.SetItemText(two,2,str1);
			two++;
		}
		else
		{
			item.iItem=three;
	        item.iSubItem=0;
	        str.Format("%d",a);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%d",k+a);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(three,1,str1);
			str1.Format("%d",k2+a);
	        m_ListCtl.SetItemText(three,2,str1);
			three++;
		}
		}
		if(flag==0)
			Output(k,k2);
		else
			Output2(a,k,k2-k,num);
	}

}

void CResultDlg::Output(int l1, int l2)
{//输出二段扩展编码
	int t=0;
	char **HC=new char*[num];
	float r;
	CString str,str1;
	char s[256];
	int i,s1=1,s2=1;
	for(i=0;i<l1;i++)
		s1=s1*2;
	for(i=0;i<s1-1;i++)
	{//第一段编码
		HC[i]=new char[l1+1];
		HC[i][l1]='\0';
		mychange(HC[i],i,l1);
		if(type)
		{
			item.iItem=two;
	        item.iSubItem=0;
	        str.Format("%d",t);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w2[t]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(two,1,str1);
	        m_ListCtl.SetItemText(two,2,HC[i]);
			t++;
			two++;
		}
	}

	for(i=s1-1;i<num;i++)
	{//第二段编码
		HC[i]=new char[l2+1];
		HC[i][l2]='\0';
		mychange(HC[i],s1-1,l1);
		mychange(HC[i]+l1,i-s1+1,l2-l1);
		if(type)
		{
			item.iItem=two;
	        item.iSubItem=0;
	        str.Format("%d",t);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w2[t]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(two,1,str1);
	        m_ListCtl.SetItemText(two,2,HC[i]);
			t++;
			two++;
		}
	}
    r=computer(w2,HC);
	if(r<lea)
	{
		for(i=0;i<num;i++)
		{
			be[i]=new char(strlen(HC[i])+1);
			be[i][strlen(HC[i])]='\0';
			for(int j=0;j<(signed)strlen(HC[i]);j++)
				be[i][j]=HC[i][j];
		}
		lea=r;
		wtemp=w2;
	}
	if(type)
	{
		str1.Format("%f",r);
		m_ListCtl.SetItemText(two-1,3,str1);
	}
//	cout<<"信息冗余量为:"<<r<<endl;

}

int CResultDlg::givenum(int n)
{//计算表示数n需要的位数
	int k=1,l=0;
	while(1)
	{
		k=k*2;
		l++;
		if(k>=n)
			break;
	}
	return l;

}

void CResultDlg::mychange(char *str, int n, int len)
{//将整数n以二进制形式存放在长度为str的字符串中，高位为补'0'
	int temp;
	len--;
	while(n)
	{
		temp=n%2+48;
		str[len]=temp;
		n=n/2;
		len--;
	}
	for(;len>=0;len--)
		str[len]='0';

}

float CResultDlg::computer(float *w, char **HC)
{
	float s1=0,s2=0;
	int i;
	for(i=0;i<num;i++)
		s1+=w[i]*strlen(HC[i]);
	for(i=0;i<num;i++)
		s2-=w[i]*(log10(w[i])/log10(2));
	return (s1-s2)/s1;

}

void CResultDlg::Huffmancoding()
{
	char** HC,s[256];
	int i,s1,s2,start,c,f,m,t=0;
	CString str,str1;
	float r;
	if(num<=1)
		return;
	m=2*num-1;
	HT=new HNode[m];
	HNode *p=HT;
	for(i=0;i<num;i++,p++)
	{
		p->weight=w[i];
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for(;i<m;i++,p++)
	{
		p->weight=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for(i=num;i<m;i++)
	{
		MySelect(s1,s2,i);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	HC=new char*[num];
//	char* HC;
	char *cd=new char[num];
	cd[num-1]='\0';
	for(i=0;i<num;i++)
	{
		start=num-1;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		{
			if(HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		}
		HC[i]=new char[num-start-1];
		strcpy(HC[i],&cd[start]);
		if(type)
		{
			item.iItem=t;
	        item.iSubItem=0;
	        str.Format("%d",t);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w[t]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(t,1,str1);
	        m_ListCtl.SetItemText(t,2,HC[i]);
			t++;
		}
	}
	r=computer(w,HC);
	if(type)
	{
		str1.Format("%f",r);
		m_ListCtl.SetItemText(t-1,3,str1);
	}
		
}

void CResultDlg::MySelect(int &s1, int &s2, int num)
{
	int i;
	float t=-1;
	for(i=0;i<num;i++)
	{
		if(HT[i].parent==0)
		{
		if(t==-1)
		{
			t=HT[i].weight;
			s1=i;
		}
		else
			if(HT[i].weight<t)
			{
			    t=HT[i].weight;
			    s1=i;
			}
		}
	}
	t=-1;
	for(i=0;i<num;i++)
	{
		if(HT[i].parent==0)
		{
		if(i!=s1)
		{
			if(t==-1)
			{
				t=HT[i].weight;
			    s2=i;
			}
		    else
				if(HT[i].weight<t)
				{
					t=HT[i].weight;
					s2=i;
				}
		}
		}
	}

}

void CResultDlg::Extendcoding2()
{//进行三段扩展编码
	int k=1,l=0,i,temp1;
	while(k<=num)
	{
		k=k*2;
		l++;
	}
	for(k=1;k<l;k++)
	{
		temp1=1;
		for(i=0;i<k;i++)
		{
			temp1=temp1*2;
		}
		temp1--;
		if(num-temp1>=2)
			Extendcoding(num-temp1,1,k);
	}

}

void CResultDlg::Output2(int l1, int l2, int l3, int num)
{//输出三段扩展编码
	float r;
	int i,s1=1,s2=1,temp=1;
	for(i=0;i<l1;i++)
		temp=temp*2;
	num+=temp-1;
	char **HC=new char*[num];
	CString str,str1;
	char s[256];
	for(i=0;i<l1;i++)
		s1=s1*2;
	for(i=0;i<s1-1;i++)
	{//第一段编码
		HC[i]=new char[l1+1];
		HC[i][l1]='\0';
		mychange(HC[i],i,l1);
		if(type)
		{
			item.iItem=three;
	        item.iSubItem=0;
	        str.Format("%d",i);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w2[i]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(three,1,str1);
	        m_ListCtl.SetItemText(three,2,HC[i]);
			three++;
		}
		//cout<<w2[i]<<"-----------"<<HC[i]<<endl;
	}

	for(i=0;i<l2;i++)
		s2=s2*2;
	for(i=s1-1;i<s1-1+s2-1;i++)
	{//第二段编码
		HC[i]=new char[l1+l2+1];
		HC[i][l1+l2]='\0';
		mychange(HC[i],s1-1,l1);
		mychange(HC[i]+l1,i-s1+1,l2);
		if(type)
		{
			item.iItem=three;
	        item.iSubItem=0;
	        str.Format("%d",i);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w2[i]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(three,1,str1);
	        m_ListCtl.SetItemText(three,2,HC[i]);
			three++;
		}
		//cout<<w2[i]<<"-----------"<<HC[i]<<endl;
	}

	for(i=s1-1+s2-1;i<num;i++)
	{//第三段编码
		HC[i]=new char[l1+l2+l3+1];
		HC[i][l1+l2+l3]='\0';
		mychange(HC[i],s1-1,l1);
		mychange(HC[i]+l1,s2-1,l2);
		mychange(HC[i]+l1+l2,i-s1-s2+2,l3);
		if(type)
		{
			item.iItem=three;
	        item.iSubItem=0;
	        str.Format("%d",i);
	        strcpy(s,str);
	        item.pszText=s;
	        str1.Format("%f",w2[i]);
	        m_ListCtl.InsertItem(&item);
	        m_ListCtl.SetItemText(three,1,str1);
	        m_ListCtl.SetItemText(three,2,HC[i]);
			three++;
		}
		//cout<<w2[i]<<"-----------"<<HC[i]<<endl;
	}

    r=computer(w2,HC);
	if(r<lea)
	{
		for(i=0;i<num;i++)
		{
			be[i]=new char(strlen(HC[i])+1);
			be[i][strlen(HC[i])]='\0';
			for(int j=0;j<strlen(HC[i]);j++)
				be[i][j]=HC[i][j];
		}
		lea=r;
		wtemp=w2;
	}
	if(type)
	{
		str1.Format("%f",r);
		m_ListCtl.SetItemText(three-1,3,str1);
	}
	//cout<<"信息冗余量为:"<<r<<endl;

}