feinuo.cpp

费诺编码的实现,通过C++来实现费诺编码的编码过程

#include<iostream>
#include<cmath>
using namespace std;
class DATA//数据类,采用双向表
{
public://初始化PXi=1是为了在排序迭代时方便
DATA(){next=NULL;qian=NULL;r=NULL;PXi=1;key[0]='\0';key[1]='\0';key[2]='\0';key[3]='\0';key[4]='\0';key[5]='\0';key[6]='\0';key[7]='\0';key[8]='\0';key[9]='\0';key[10]='\0';}
char Xi;//信源符号
double PXi;//信源概率
char key[11];//码字
DATA *next,*qian,*r;//地址
};
DATA *head=new DATA,*p=head;//mainini
int k=(-1);//编码函数用
void a(DATA* pp);//编码函数声明
DATA* sort(DATA* pp);//排序函数声明
DATA *HEAD=new DATA,*tt=HEAD,*T;//排序函数用
void shuru()
{//输入数据
double l,sum=0;
int n,i;
char L;
   cout<<"输入信源个数:";
	cin>>n;
    for(i=0;i<n;i++){
      cout<<"输入输入一个字符的信源符号:" <<endl;cin>>L;
	  cout<<"输入概率:" <<endl;cin>>l;
      p->Xi=L;
      p->PXi=l; 
	  sum=sum+p->PXi;
      p->next=new DATA;
      p->next->qian=p;//对新开类赋值
      p->r=p->next;
      p=p->next;  
	}
    if(sum!=1){
	   cout<<"所输入的概率之和是"<<sum<<"不为1，请重新输入"<<endl;
       shuru();}
     T=sort(head);//因为sort要改变tt，故需要一个中间变量
     tt->next=T;//由于迭代产生的链表格式不规范，以下句用来整理sort函数的返回结果
     tt->next->qian=tt;
     tt=tt->next;
     tt->next=new DATA;
     tt->next->qian=tt;//对新开类赋值
     tt=tt->next;
     HEAD->next->next->qian=NULL;
     HEAD=HEAD->next->next;
     cout<<"对输入信源排序结果如下："<<endl;
     for(p=HEAD;p->next!=NULL;p=p->next)//排序输出
        cout<<p->Xi<<":"<<p->PXi<<endl;
        cout<<"对输入信源编码结果如下："<<endl;
          a(HEAD);
}
//编码
void a(DATA* pp)//定义递归函数
{double y=1;//y定义为1是因为概率最多为1
k++;//递归自增值，用于字符数组定位
DATA *head1=pp,*head2;
int o=1;
 while(1)//分01组
 {
double l=0,z=0;
  for(int i=1;i<=o;i++)
  {
  if(pp->next==NULL) break;
  l=l+pp->PXi;
  pp=pp->next;
  }
 head2=pp->qian;//从这里分01段
  for(;pp->next!=NULL;pp=pp->next) z=z+pp->PXi;
  if(y>fabs(l-z))//判断两组值之差是否最小
  {
  y=fabs(l-z);
  pp=head1;
  o++;
  continue;
  }
  else if(z==0&&i<=2)//z=0i<1表示只有一个概率了
  {cout<<head1->Xi<<":"<<head1->key<<endl;break;}
  for(DATA* u=head1;u->next!=head2->next;u=u->next) u->key[k]='0';//为字符串赋值
  for(DATA* h=head2;h->next!=NULL;h=h->next) h->key[k]='1';
 head2->qian->next=new DATA;//分段：标记head2为上一段结束位置
 head2->qian->next->qian=head2->qian;//ini
 a(head1);//递归
 a(head2);
 break;
 }
k--;//迭代还原到上一个数组位置
}
DATA* sort(DATA* pp)//函数递归后头变到HEAD->next->next.返回值得到最后个head2没有与tt相连，需另设．得不到结尾为空的（next=MULL）地址
{
DATA *head1=pp,*head2=pp;
if(pp->next==NULL) return pp;//当pp是最后一个直时
 for(;pp->next!=NULL;pp=pp->next)
 {
 if(1-pp->PXi>=1-head2->PXi) //两个以上的值时,由于最后一个pxi为1，所以每次都会有个最小值
 head2=pp; 
 }
 if(head2->qian==NULL)//当pp是第一个直时
 {
 head2->next->qian=NULL;
 head1=head1->next;
 }
 else //当pp是最后一个值及中间的值时
 {head2->qian->next=head2->next;
 head2->next->qian=head2->qian;
 }
tt->next=sort(head1);//递归，先得第一个，再得下一个
tt->next->qian=tt;
tt=tt->next;
return head2;
}
void main()
{ shuru();
 cout<<endl;
}