#include<iostream>
#include<cmath>
using namespace std;
class DATA//數(shù)據(jù)類,采用雙向表
{
public://初始化PXi=1是為了在排序迭代時(shí)方便
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;//信源符號(hào)
double PXi;//信源概率
char key[11];//碼字
DATA *next,*qian,*r;//地址
};
DATA *head=new DATA,*p=head;//mainini
int k=(-1);//編碼函數(shù)用
void a(DATA* pp);//編碼函數(shù)聲明
DATA* sort(DATA* pp);//排序函數(shù)聲明
DATA *HEAD=new DATA,*tt=HEAD,*T;//排序函數(shù)用
void shuru()
{//輸入數(shù)據(jù)
double l,sum=0;
int n,i;
char L;
   cout<<"輸入信源個(gè)數(shù):";
	cin>>n;
    for(i=0;i<n;i++){
      cout<<"輸入輸入一個(gè)字符的信源符號(hào):" <<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;//對(duì)新開類賦值
      p->r=p->next;
      p=p->next;  
	}
    if(sum!=1){
	   cout<<"所輸入的概率之和是"<<sum<<"不為1，請(qǐng)重新輸入"<<endl;
       shuru();}
     T=sort(head);//因?yàn)閟ort要改變tt，故需要一個(gè)中間變量
     tt->next=T;//由于迭代產(chǎn)生的鏈表格式不規(guī)范，以下句用來(lái)整理sort函數(shù)的返回結(jié)果
     tt->next->qian=tt;
     tt=tt->next;
     tt->next=new DATA;
     tt->next->qian=tt;//對(duì)新開類賦值
     tt=tt->next;
     HEAD->next->next->qian=NULL;
     HEAD=HEAD->next->next;
     cout<<"對(duì)輸入信源排序結(jié)果如下："<<endl;
     for(p=HEAD;p->next!=NULL;p=p->next)//排序輸出
        cout<<p->Xi<<":"<<p->PXi<<endl;
        cout<<"對(duì)輸入信源編碼結(jié)果如下："<<endl;
          a(HEAD);
}
//編碼
void a(DATA* pp)//定義遞歸函數(shù)
{double y=1;//y定義為1是因?yàn)楦怕首疃酁?
k++;//遞歸自增值，用于字符數(shù)組定位
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表示只有一個(gè)概率了
  {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;//分段：標(biāo)記head2為上一段結(jié)束位置
 head2->qian->next->qian=head2->qian;//ini
 a(head1);//遞歸
 a(head2);
 break;
 }
k--;//迭代還原到上一個(gè)數(shù)組位置
}
DATA* sort(DATA* pp)//函數(shù)遞歸后頭變到HEAD->next->next.返回值得到最后個(gè)head2沒有與tt相連，需另設(shè)．得不到結(jié)尾為空的（next=MULL）地址
{
DATA *head1=pp,*head2=pp;
if(pp->next==NULL) return pp;//當(dāng)pp是最后一個(gè)直時(shí)
 for(;pp->next!=NULL;pp=pp->next)
 {
 if(1-pp->PXi>=1-head2->PXi) //兩個(gè)以上的值時(shí),由于最后一個(gè)pxi為1，所以每次都會(huì)有個(gè)最小值
 head2=pp; 
 }
 if(head2->qian==NULL)//當(dāng)pp是第一個(gè)直時(shí)
 {
 head2->next->qian=NULL;
 head1=head1->next;
 }
 else //當(dāng)pp是最后一個(gè)值及中間的值時(shí)
 {head2->qian->next=head2->next;
 head2->next->qian=head2->qian;
 }
tt->next=sort(head1);//遞歸，先得第一個(gè)，再得下一個(gè)
tt->next->qian=tt;
tt=tt->next;
return head2;
}
void main()
{ shuru();
 cout<<endl;
}