huffmandlg.cpp

HUFFMAN编码在信息论中的应用实例！

		currptr->probabality=pro;
	}
	else
	{		
		temp->sign=str;
		temp->probabality=pro;
		rear->next=temp;
		rear=rear->next;
	}
	CString str1;
	str1.Format("%f",temp->probabality);
	m_LISTIN.InsertItem(listinsize,temp->sign);
	m_LISTIN.SetItemText(listinsize,1,str1);
	listinsize++;

}


//从TXT文件读取信源符号和概率
void CHUFFMANDlg::OnButtonInfile() 
{
	// TODO: Add your control notification handler code here
	CFileDialog dlg(TRUE, "*.txt", NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,"Text Files(*.txt)|*.txt|All Files(*.*)|*.*||"); 
	if ( dlg.DoModal()!=IDOK ) return;
	//获取文件的绝对路径
	sFilePath=dlg.GetPathName();
	  CStdioFile   file1; 
	  CString   strfile; 
	  CString   strdouble;
	  double prob;
	  BOOL   bExist   = file1.Open(sFilePath,   CFile::modeRead   |   CFile::typeText   );
	  if(bExist)
	  {
		   while(NULL != file1.ReadString(strfile))
		   {
			   if (strfile!="") 
				{
				   if(file1.ReadString(strdouble)!=NULL)
				   {
					   while(strdouble=="")
					   {
						   file1.ReadString(strdouble);
					   }
						prob=atof(strdouble);//字符型转double
						CHUFFMANDlg::rearadd(strfile,prob);
				   }
				}
			   
		   }
			file1.Close();
	  }
	  else
	  {
		  MessageBox("打开文件失败,请确认文件存在!","错误",MB_OK);
	  }
	
}


//删除输入的所有信源符号及概率
void CHUFFMANDlg::OnButtonDelall() 
{
	// TODO: Add your control notification handler code here
	rear=currptr=prevptr=NULL;
	node *temp;
	//删除用以构造树的2个链表
	while(head!=NULL)
	{
		temp=head;
		head=head->next;
		delete temp;
	}
	while(head1!=NULL)
	{
		temp=head1;
		head1=head1->next;
		delete temp;
	}
	delete head;
	//清除列表框
	m_LISTIN.DeleteAllItems();
	m_LISTOUT.DeleteAllItems();
	listinsize=0;
	listoutsize=0;

}

void CHUFFMANDlg::OnButtonRedo() 
{
	// TODO: Add your control notification handler code here
	m_sign="";
	m_probablility=0;
	UpdateData(FALSE);
	
}

void CHUFFMANDlg::OnButtonCode() 
{
	node *temp1;
	while(head1!=NULL)
	{
		temp1=head1;
		head1=head1->next;
		delete temp1;
	}

	node *temp,*min[2];
	// TODO: Add your control notification handler code here
	//判断是否已输入数据
	currptr=head;
	if(currptr==NULL||head==rear)
	{
		m_LISTOUT.DeleteAllItems();
		MessageBox("当前无输入或输入信源个数少于二","错误",MB_ICONWARNING);		
		return;
	}
	//复制链表
	while(currptr!=NULL)
	{
	
		if(head1==NULL)
		{
			head1=new node;
			rear1=head1;
			head1->sign=currptr->sign;
			head1->probabality=currptr->probabality;
		}
		else
		{
			temp=new node;
			temp->sign=currptr->sign;
			temp->probabality=currptr->probabality;
			rear1->next=temp;
			rear1=rear1->next;
		}
		currptr=currptr->next;

	}


	//找出最小两值,并删除对应结点
	
	    while(head1->next!=rear1)
		{

			//找出链表中字母出现概率最小的三个结点,并用min[i](i=1,2,3)指向这三个结点,之后将这三个结点从链表中删除
			for(int i=0;i<2;i++)
			{
				min[i]=head1;
				currptr=head1;
				//找出最小结点
				while(currptr!=NULL)
				{
					if(currptr->probabality<min[i]->probabality)
					{
						min[i]=currptr;
					}
					currptr=currptr->next;
				}

				//从链表中删除结点									
				currptr=head1;
				while(currptr!=NULL)
				{
							if(head1==min[i])//当最小结点是链头时,删除链头结点,head指向删除前的第二结点
							{
								head1=head1->next;
							}
							else
							{
									if(currptr->next==min[i])
									{
										if(min[i]==rear1)//当最小结点在链尾时,直接删除
										{
											rear1=currptr;
											currptr->next=NULL;
										}
										else//当最小结点不在链的头或尾时,当前NEXT指针指向下下结点
										{
											currptr->next=currptr->next->next;
										}
										break;
									}										

							}
							prevptr=currptr;									
							currptr=currptr->next;//当前指针移动遍历链表
					}
					
				}
			//构建HUFFMAN树
			node *temp;
			temp=new node;
			temp->left=min[0];
			temp->right=min[1];
			temp->sign=min[0]->sign+min[1]->sign;
			temp->probabality=min[0]->probabality+min[1]->probabality;
			min[0]->parent=temp;
			min[1]->parent=temp;
			rear1->next=temp;
			rear1=rear1->next;
			rear1->next=NULL;			
		}
		//生成根结点
		root= new node;
		if(head1->probabality<rear1->probabality)
		{
			root->left=head1;
			root->right=rear1;
			head1->parent=root;
			rear1->parent=root;
			root->parent=NULL;
			root->sign="root";
			root->code="";
		}
		else
		{
			root->left=rear1;
			root->right=head1;
			head1->parent=root;
			rear1->parent=root;
			root->parent=NULL;
			root->sign="root";
			root->code="";
		}
		PreOrderto0(root);
		//编码
		PreOrder(root);

		//输出编码
		double HS=0;
		m_LISTOUT.DeleteAllItems();
		currptr=head;
		listoutsize=0;
		double counter=0,length1=0,p=0;
		while(currptr!=NULL)
		{
			//计算信源熵
			if(currptr->probabality!=0)
				HS+=-currptr->probabality*log(currptr->probabality)/log(2);

			//输出到列表
			findsign(currptr->sign,root);
			m_LISTOUT.InsertItem(listoutsize,currptr1->sign);
			m_LISTOUT.SetItemText(listoutsize,1,currptr1->code);
			length1+=currptr1->probabality*currptr1->code.GetLength();//计算平均码长
			p+=currptr1->probabality;//计算概率总和
			currptr=currptr->next;
			listoutsize++;
			counter+=1;
		}
		//输出信 源 熵
		CWnd *pWnd=GetDlgItem(IDC_STATIC_HS);
		CString strsta;
		strsta.Format("%f",HS);
		strsta.Insert(0,"信 源 熵: ");
		pWnd->SetWindowText(strsta);

		//输出平均码长
		strsta.Format("%f",length1);
		strsta.Insert(0,"平均码长: ");
		pWnd=GetDlgItem(IDC_STATIC_LEN);
		pWnd->SetWindowText(strsta);

		//输出编码效率
		strsta.Format("%f",HS/length1);
		strsta.Insert(0,"编码效率: ");
		pWnd=GetDlgItem(IDC_STATIC_N);
		pWnd->SetWindowText(strsta);

		if((1-p)>0.0005)
			MessageBox("信源符号出现概率之和小于1,可能输入不完整或输入错误","警告",MB_ICONWARNING);
		if((1-p)<-0.0005)
			MessageBox("信源符号出现概率之和大于1,可能输入有错误","警告",MB_ICONWARNING);


	
}

void PreOrder(node *t)//先序遍历二叉树进行编码
{
	if(t)
	{
		//处理
		if(t!=root)
		{			
			if(t->parent->left==t)
				t->code=t->parent->code+"1";
			else
				t->code=t->parent->code+"0";
		}


		if(t->left)
		{
		  PreOrder(t->left);
		  if(t->right)
			 PreOrder(t->right);
		}
		
	}


}



void PreOrderto0(node *t)//先序遍历二叉树
{
	if(t)
	{
        t->code="";
		
	}


}






//根据sign找对应结点(中根遍历法)
int findsign(CString str,node *t)
{

	if(t!=NULL)
	{
		findsign(str,t->left);
		//处理
		if(t->sign==str)
		{
			currptr1=t;return 1;
		}
		findsign(str,t->right);
	}
	
	
	
}