#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
typedef struct
{
    char a[15];
    float b;
}mynode1;

typedef struct
{   char a[15];
    
    float p;
    int geshu;
}mynode2;

void sort(mynode1 a[],int n)
{
    int i,j,flag=1;
    mynode1 temp;
  for(i=1;i<=n&&flag==1;i++)
  {
      flag=0;
  for(j=0;j<n-i;j++)
  {
      if(a[j].b<a[j+1].b)
      {
       flag=1;
      temp=a[j];
      a[j]=a[j+1];
      a[j+1]=temp;
      }
  }
  }
}


void main()
{
   int n,i;
   float sum=0,c,t;
   mynode1 *shanon;
   mynode2 *sorted;
   printf("请输入消息序列的个数:");
   scanf("%d",&n);

   if((shanon=new mynode1[n])==NULL) 
   {
      printf("申请堆内存失败!\n");
       exit(1);
   }
   if((sorted=new mynode2[n])==NULL) 
   {
      printf("申请堆内存失败!\n");
       exit(1);
   }
   printf("                                              名称       概率  \n");
   
   for(i=0;i<n;i++)
   {
       printf("请输入第%d个消息名称和概率\n",i+1);
    
   scanf("%s",shanon[i].a);
   scanf("%f",&shanon[i].b);
  printf("                                          %8s     %f\n",shanon[i].a,shanon[i].b);
   }
printf("\n\n\n");
//对消息序列进行排队
   printf("                                           概率按照从大到小的顺序排列后\n");
sort(shanon,n);
for(i=0;i<n;i++)
   {
      
   
  printf("                                          %8s     %f\n",shanon[i].a,shanon[i].b);
   }

for(i=0;i<n;i++)
{   sorted[i].p=sum;
    sorted[i].geshu=int(log10(1/(double)shanon[i].b)/log10((double)(2))+1);
    strcpy(sorted[i].a,shanon[i].a);
    sum=shanon[i].b+sum;
}

for(i=0;i<n;i++)
{
    printf("                    %s   %f  %d\n",sorted[i].a,sorted[i].p,sorted[i].geshu);

}

for(i=0;i<n;i++)
{ int j;
 c=sorted[i].p;
    printf("%s的香农编码：",sorted[i].a);
    for(j=0;j<sorted[i].geshu;j++)
    {
    c=c*2;
    t=c;
    printf("%d",(int)t);
    if(c>1)
    c=c-1;
    }
    printf("\n");
}
}