6_9.txt

C语言数据结构知识原代码 C语言数据结构知识原代码C语言数据结构知识原代码

#include<stdio.h>
#define n 5
typedef struct huf{
 int parent,lchild,rchild;
 int low,high;                /*等级分数的上下限*/
 double w;
 char data;                   /*等级*/
 }huffman;
selectmin(huffman *p,int i,int *j,int *k)
 {
  int s,t;
  for(s=0;s<i;s++)
   if(p[s].parent==-1){
     *j=s;
     break;
     }
  for(t=s+1;t<i;t++)
    if(p[t].parent==-1){
    *k=t;
    break;
    }
  for(s=t+1;s<i;s++)
   {
    if(p[s].parent==-1)
    if(p[*j].w<p[*k].w){
        if(p[s].w<=p[*j].w){*k=*j,*j=s;}
         else
        if(p[s].w<p[*k].w)*k=s;
         }
     else
      if(p[*j].w>p[*k].w){
        if(p[s].w<=p[*k].w)*j=s;
         else
       if(p[s].w<p[*j].w){*j=*k;*k=s;}
        }
      else if(p[s].w<p[*j].w)*k=s; 
    }
 }
chuffman(double w[],char ch[],huffman *p)
 {
 int i,j,k;
 for(i=0;i<n;i++)
  {p[i].parent=-1;
   p[i].lchild=-1;
   p[i].rchild=-1;
   p[i].w=w[i];
   p[i].data=ch[i];
  }
 for(i=n;i<2*n-1;i++)
  {
   p[i].parent=-1;
   p[i].lchild=-1;
   p[i].rchild=-1;
   }
 for(i=n;i<2*n-1;i++)
  {
   selectmin(p,i,&j,&k);   /*从父结点为-1的结点中选择两个最小的结点*/
   p[i].w=p[j].w+p[k].w;
   p[i].lchild=j;
   p[i].rchild=k;
   p[j].parent=i;
   p[k].parent=i;
  }
 }
adjust(huffman *p)          /*调整后返回根结点的下标*/
 {
  int i,j;
  for(i=0;i<n;i++)
   {
    j=p[i].parent;
    if(p[j].lchild==i)
     switch(p[i].data){
     case 'E':p[j].low=0;p[j].high=59;
              break;
     case 'D':p[j].low=60;p[j].high=69;
              break;
     case 'C':p[j].low=70;p[j].high=79;
              break;
     case 'B':p[j].low=80;p[j].high=89;
              break;
     case 'A':p[j].low=90;p[j].high=100;
              break;
     }
    } 
   i=0;j=p[i].parent;
   while(p[j].parent!=-1)j=p[j].parent;
   return j;
 }
main()
{
 huffman p[2*n-1];int score,j;
 double w[]={0.05,0.15,0.40,0.30,0.10};
 char ch[]={'E','D','C','B','A'};
 chuffman(w,ch,p);
 j=adjust(p);                    /*调整内部结点,为了判别分数值属于的等级*/
 printf("input the score of a student:\n");
 scanf("%d",&score);
 while(p[j].lchild!=-1){
   if(score>=p[j].low && score<=p[j].high){ printf("%d is %c",score,p[p[j].lchild].data);
                                            break;}
   else j=p[j].rchild;
   if(p[j].lchild==-1){ printf("%d is %c",score,p[j].data);
                     break;}
   }
 }