xixibmdlg.cpp

香农编码

void CXixibmDlg::Onhelp() 
{
	// TODO: Add your control notification handler code here
	MessageBox("      在第一列输入消息概率！\n        :）\n点击自动分配可以自动填写信源概率！\n\n若手动填写请先点击清空或者编码按钮\n\n使信源符号按序排列！！");
}

void CXixibmDlg::OnOK() 
{
	// TODO: Add extra validation here
	
	CDialog::OnCancel();
	MessageBox("谢谢您的使用！愿你每天都有好的心情！:）");
}

/////////////////////////////////////////////////////////////////
void CXixibmDlg::paixu()////////////////******排序*********
{  
   for(int j=0;j<7;j++)
   {
	for(int i=0;i<7;i++)
   {
	   if (ay[i]<ay[i+1])
	   { 
		   ay[7]=ay[i];ay[i]=ay[i+1];ay[i+1]=ay[7];
           no[7]=no[i];no[i]=no[i+1];no[i+1]=no[7];//信源符号排序
	   }	  
   }
   }
   m1=no[0];m2=no[1];m3=no[2];m4=no[3];m5=no[4];m6=no[5];m7=no[6];
   a1=ay[0];a2=ay[1];a3=ay[2];a4=ay[3];a5=ay[4];a6=ay[5];a7=ay[6];
     UpdateData(false);
}

void CXixibmDlg::duishu()//求对数
{
  for(int i=0;i<=6;i++)
  {
   by[i]=-log(ay[i])/log(2);
  }

  b1=by[0];b2=by[1];b3=by[2];b4=by[3];b5=by[4];b6=by[5];b7=by[6];
    UpdateData(false);
}

void CXixibmDlg::Onaboutme() 
{
	// TODO: Add your control notification handler code here
	MessageBox("        作者：赵俭        \n\n      中国地质大学\n\n 信息工程学院通信四班\n\n 欢迎访问我的个人博客：\n\nHttp://hi.baidu.com/zjjs\n\n思想有多远，我们就能走多远！");
}

void CXixibmDlg::machang()   ///求各码长
{
  for(int i=0;i<=6;i++)
  {
	  double cc=by[i];
	  if (cc-int(by[i])==0) 
	  {
		  cy[i]=int(by[i]);
	  }
	  else
	  cy[i]=int(by[i])+1;
  }
  c1=cy[0];c2=cy[1];c3=cy[2];c4=cy[3];c5=cy[4];c6=cy[5];c7=cy[6];
    UpdateData(false);
}

void CXixibmDlg::ljgl()   //求香农编码的累加概率
{   dy[0]=0;
 	dy[1]=a1;
  dy[2]=dy[1]+a2;
  dy[3]=dy[2]+a3;
  dy[4]=dy[3]+a4;
  dy[5]=dy[4]+a5;
  dy[6]=dy[5]+a6;
  d1=dy[0];d2=dy[1];d3=dy[2];d4=dy[3];d5=dy[4];d6=dy[5];d7=dy[6];
    UpdateData(false);
}
///////////////////////////////////////////////////////////////////////
//////////////**************香农编码**************
void CXixibmDlg::bianma()
{   ////编码之前清空码字
	ey[0]=_T("");ey[1]=_T("");ey[2]=_T("");ey[3]=_T("");ey[4]=_T("");ey[5]=_T("");ey[6]=_T("");    
   double temp(0);
   for(int a=0;a<=6;a++)
   {
	   tbm[a]=dy[a];
   }
    for(int j=0;j<=6;j++)
	{
	for(int i=0;i<cy[j];i++)//cy[j]为码长
	{
		temp=tbm[j]*2.0;
		if (temp>=1.0)
		{//如果乘2的结果大于1，则编码为1
			ey[j]=ey[j]+"1";
			tbm[j]=temp-1.0;//去整取余
		}
		else
		{
			ey[j]=ey[j]+"0";
			tbm[j]=temp;
		}
	}
	}
	e1=ey[0];e2=ey[1];e3=ey[2];e4=ey[3];e5=ey[4];e6=ey[5];e7=ey[6];
	  UpdateData(false);
}

void CXixibmDlg::bmxl()    //求编码效率及平均码长
{
  double tem1(0.0),tem2(0.0);
  for(int i=0;i<=6;i++)
  {
	  tem1=tem1+ay[i]*by[i]; 
	  tem2=tem2+ay[i]*cy[i];
  }
  
  xl=tem1/tem2; 
  mc=tem2;
  xys=tem1;
  
    UpdateData(false);
}

void CXixibmDlg::feixiaolv()    //求费诺编码效率及平均码长
{double fnmc(0.0);double tem1(0.0);
 for(int i=0;i<=6;i++)
  {
	  tem1=tem1+ay[i]*by[i]; 
	  fnmc=fnmc+ay[i]*js[i];
  }
 mcfn=fnmc;
  xlfn=tem1/fnmc;
UpdateData(false);
}
//////////////////////////////////////////////////////////////////////////
//**************费诺编码********************
int CXixibmDlg::feinuobianma(int low,int high)
{
   int m=low,n=high;
   if(m==n)	return 1;
    else 
		if(m+1==n)
	{ //gy[m]为码字//// js[m]为码长
	   gy[m]=gy[m]+"0";js[m]=js[m]+1;
	   gy[n]=gy[n]+"1";js[n]=js[n]+1;
	   return 1;
    }
    else
	{/////////寻找分割点///////////
       double sum0=0,sum1=0,sum2=0;
       for(int i=m;i<=n;i++)  sum0+=ay[i];  
   do{
         sum1+=ay[m];
         sum2=sum1+ay[m+1];
         m++;
	 }while(pd(sum1/sum0-0.5)>pd(sum2/sum0-0.5));
     for(i=low;i<m;i++) 
	 {gy[i]=gy[i]+"0";js[i]=js[i]+1;}//m以上的赋0
     for(i=m;i<=n;i++)  
	 {gy[i]=gy[i]+"1";js[i]=js[i]+1;}//m以下的赋1
	}
	feinuobianma(low,m-1);/////
	feinuobianma(m,high);//////递归调用
	return 1;
}

double CXixibmDlg::pd(double f)
{return(f>=0?f:-f);}

void CXixibmDlg::diaoyong()////////调用费诺编码函数
{
	for (int m=0;m<=7;m++) gy[m]=_T("");
	for(int i=0;i<=6;i++) js[i]=0;
 feinuobianma(0,6);
g1=gy[0];g2=gy[1];g3=gy[2];g4=gy[3];g5=gy[4];g6=gy[5];g7=gy[6];
f1=js[0];f2=js[1];f3=js[2];f4=js[3];f5=js[4];f6=js[5];f7=js[6];
  UpdateData(false);
}

void CXixibmDlg::Onfeipei() //////////
/////**************产生随机数据**********
{
	// TODO: Add your control notification handler code here
    double ayy[7];int byy[7];double tem2(0.0),qi(0.0),qi1(0.0);
	srand((unsigned int)time((time_t *)NULL));//种子
	for(int i=0;i<=5;i++)
	{
	  byy[i]=10+rand()%90;//产生随机数
	}
	double sum8(0.0);///用来存储产生的6个随机数的总和
	for(int j=0;j<=5;j++)
	{	
		sum8=sum8+byy[j];
    	ayy[j]=byy[j];
	}
	for(int k=0;k<=5;k++)
	{	
		ayy[k]=int((ayy[k]/(sum8+150))*100);//总和加50，每位随机数除它们的总和
	    ayy[k]=ayy[k]/100;///////////////////保留两位有效数字
		tem2=tem2+ayy[k];
	}
	qi=1-tem2;qi1=int(qi*100);qi1=qi1/100;//处理第七位数
	if (qi-qi1>=0.005)///去尾巴
	{
		qi1=qi1+0.01;
	}
	else
	{	qi1=qi1;}
   a1=ayy[0];a2=ayy[1];a3=ayy[2];a4=ayy[3];a5=ayy[4];a6=ayy[5];//先产生六个随机数
   a7=qi1;/////////////////////////////////////////第七个通过计算而得，保证七个随机数总和为1
   m1=1;m2=2;m3=3;m4=4;m5=5;m6=6;m7=7;
	UpdateData(false);
}

void CXixibmDlg::clear()
{
    a1=a2=a3=a4=a5=a6=a7=0;
	b1=b2=b3=b4=b5=b6=b7=0;
	c1=c2=c3=c4=c5=c6=c7=0;
	d1=d2=d3=d4=d5=d6=d7=0;
	f1=f2=f3=f4=f5=f6=f7=0;
	h1=h2=h3=h4=h5=h6=h7=0;
	xys=0.0;mc=0.0;xl=0.0;
	xlfn=0.0;mcfn=0.0;
	xlhfm=0.0;mchfm=0.0;
	m1=1;m2=2;m3=3;m4=4;m5=5;m6=6;m7=7;
	e1=_T("");e2=_T("");e3=_T("");e4=_T("");e5=_T("");e6=_T("");e7=_T("");
    g1=_T("");g2=_T("");g3=_T("");g4=_T("");g5=_T("");g6=_T("");g7=_T("");
	i1=_T("");i2=_T("");i3=_T("");i4=_T("");i5=_T("");i6=_T("");i7=_T("");
	for(int i=0;i<=6;i++) js[i]=0;
	  UpdateData(false);
}

void CXixibmDlg::dyhuffman()//调用哈夫曼
{
  for (int m=0;m<7;m++) iy[m]=_T("");
  for(int i=0;i<=6;i++) hy[i]=0;
  huffman();//哈夫曼编码
  i1=iy[0];i2=iy[1];i3=iy[2];i4=iy[3];i5=iy[4];i6=iy[5];i7=iy[6];
  h1=hy[0];h2=hy[1];h3=hy[2];h4=hy[3];h5=hy[4];h6=hy[5];h7=hy[6];
  UpdateData(false);
}

void CXixibmDlg::hfmmc()///////计算哈夫曼平均码长和编码效率//////
{ 
	double temp(0.0),temp2(0.0);
  for(int i=0;i<=6;i++)
  {
	  temp=temp+ay[i]*by[i];
	  temp2=temp2+ay[i]*hy[i];
  }
   mchfm=temp2;//码长
   xlhfm=temp/temp2;//效率
   UpdateData(false);
}
////////////*********哈夫曼编码**********
void CXixibmDlg::huffman()
{
  class   Sarray   Array[7];         //这个数组保存了7个原始数据的输入     
  double   temp=0;                               
  double   total=0;                           //该变量用来记录每两个信号合成后，新节点（信号）的发生概率     
  int   i,j,k;                  //中间计数器     
  char ff=NULL;      //二叉树遍历函数     
  for(i=0;i<7;i++)                                                           
  {   
    temp=ay[i];    
    Array[i].symbol[0]='a';     //该信号命名为ai     
    Array[i].symbol[1]=(char)i;   
    Array[i].prb=temp;                                      //发生概率为刚才输入的数值     
    total+=temp;                                             //在这里total用来统计所有信号发生概率之和是否等于1     
    temp=0;                                           //为确保不影响后面的数据输入，这里temp置0                    
    }     
     char   t_symbol[2];   
    for(i=0;i<6;i++)                               //以下是冒泡排序过程     
    for(j=i+1;j<7;j++)   
  {   
      if(Array[i].prb<Array[j].prb)   
  {   
      temp=Array[i].prb;   
      t_symbol[0]=Array[i].symbol[0];   
      t_symbol[1]=Array[i].symbol[1];       
      Array[i].prb=Array[j].prb;   
      Array[i].symbol[0]=Array[j].symbol[0];   
      Array[i].symbol[1]=Array[j].symbol[1];   
      Array[j].symbol[0]=t_symbol[0];   
      Array[j].symbol[1]=t_symbol[1];   
      Array[j].prb=temp;   
      }   
    }   
    Node   *p;   
    for(i=0;i<7;i++)       //输出各个信号的概率，并为它们分配（在二叉树中的）存储空间     
  {         
     p=(Node   *)malloc(sizeof(Node));   
     Array[i].addr=p;   
     p->left=NULL;   
     p->right=NULL;   
     p->symbol[0]='a';   
     p->symbol[1]=(char)i;   	
  }
     temp=0.0;   
     int   time=0;       //该变量用来记录Huffman过程进行的次数     
     total=0.0;         //重置                     
     Node   *pleft,*pright;         
     while(total<1.0)             //当概率和小雨1时，Huffman就还可以继续     
     {   
        total=Array[6-time].prb+Array[6-time-1].prb;     //概率相加，新节点的概率等于它们的和                       
        pleft=Array[6-time-1].addr;           //新节点的左孩子为概率较大的节点     
        pright=Array[6-time].addr;             //新节点的右孩子为概率较小的节点     
        j=0;   
        Array[6-time].prb=0;                         //产生新节点前，先在Array[]中将相应信号的概率置0     
        Array[6-time-1].prb=0;   
        while(total<Array[j].prb)     { j++;}              //找出新节点在Array[]中的合适位置（排序）        
        if(j<(6-time-1))                       //如果合适的位置不在最后，则     
		{   
          for(k=6-time-2;k>=j;k--)       //从这里起，后面所有的信号都要依次后挪     
		  {                 
			  Array[k+1].symbol[0]=Array[k].symbol[0];   
			  Array[k+1].symbol[1]=Array[k].symbol[1];   
			  Array[k+1].prb=Array[k].prb;   
              Array[k+1].addr=Array[k].addr;   
		  }   
		}                               
             Array[j].symbol[1]=(char)time;           //新节点的标识为Q0,Q1,Q2...，下标也就是Huffman过程的次数     
             Array[j].symbol[0]='Q';   
             p=(Node   *)malloc(sizeof(Node));     //为新节点分配存储空间     
             Array[j].addr=p;         //把这个地址填充到Array[]当中     
             Array[j].prb=total;           //新节点的概率为两个信号概率之和     
             p->left=pleft;             //左指针，即左孩子的地址     
             p->right=pright;         //右指针     
             p->symbol[0]=Array[j].symbol[0];       //把新节点的标识填到二叉树当中     
             p->symbol[1]=Array[j].symbol[1];               
             time++;                 //Huffman过程的次数加一                                                            
    }       
       p=Array[0].addr;       //头指针（根节点的地址）置为数组第一个元素的指针     
       Traverse(p,-1);         //遍历二叉树   ，传入二叉树头节点的指针                             
       CString strtemp;
       for(i=0;i<7;i++)    //输出原始信号的Huffman编码码值    
      {   
         for(j=0;j<=result[i].length;j++)     
		{	
	    	strtemp=("%s",result[i].path[j]);
			iy[i] = iy[i] + strtemp;//结果输出
		}
			strtemp =_T("");
          hy[i]=result[i].length+1;//码长输出
      }   												
 }   

 void  CXixibmDlg:: Traverse(Node   *T,int   step)         //step记录了到达该节点时，该节点的深度（处于二叉树中的第几层）     
  {                                                                                   //这个层数也就是该节点Huffman编码码值的长度     
    static   char   dpath[7];                                 //该数组记录了从头节点一路走来碰到的所有"1"和"0"，也就是Huffman编码码值   
    static   int   value;                                         //value用来提取叶子节点标识当中的数字下标，如'a1'中的'1'     
    if(T->left!=NULL)                                         //如果左指针不为空，即下面还有孩子，则     
   {   
      step++;                         //步长递增     
      dpath[step]='1';                  //进入左孩子之前，左边置1     
      Traverse(T->left,step);           //搜寻左子树     
      dpath[step]='0';                    //此时已经从左子树返回了，将进入右子树，所以右边置0     
      Traverse(T->right,step);          //搜寻右子树     
	  step--;                           //此时可以从该节点返回了，所以步长递减     
   }   
     else   
	{                                           //如果它下面没有孩子了，即它是叶子节点，则     
      value=T->symbol[1];                       //提取下标，因为所有的原始信号都在叶子节点，且只有原始信号在叶子节点上     
      result[value].symbol[0]=T->symbol[0];       //按下标把该叶子节点的标识拷贝到输出表中     
      result[value].symbol[1]=T->symbol[1];   
      result[value].length=step;                             //信号的Huffman编码码值长度等于步长    
	  for(int   j=0;j<=step;j++)                                   //拷贝码值          
      result[value].path[j]=dpath[j];   	                                
     }              
 }