sy9_2.c

数据结构实验与学习指导

/*  sy9_2.c  */
#include "stdio.h"
#define MAXSIZE 10
typedef int KeyType;
typedef struct
  {KeyType Num;
   char Name[8];
   float Score;
  }ElemType;
typedef struct
 {ElemType data[MAXSIZE+1]; /*结点数组*/
  int length;
 }SL;
void InitHeap(SL *h) /*初始化，赋值*/
{ int i;
  float fff;
   for(i=1;i<=h->length;i++)
    {printf("请输入一个学生的信息:num,name,score\n");
     scanf("%d",&(h->data[i].Num));
     getchar();
     gets(h->data[i].Name);
     scanf("%f",&fff);
     h->data[i].Score=fff;
    }
}
void HeapSift(SL *p,int s,int m)/*建立堆*/
 {int j;
  ElemType rc;
  rc=p->data[s];
  j=2*s;
  while(j<=m)
    {if(j<m&&p->data[j].Num<p->data[j+1].Num)
      j++;
     if(rc.Num<p->data[j].Num)   /*建立堆完成*/
       {p->data[s]=p->data[j]; s=j;j=j*2;  }
     else
       j=m+1;
    }/*while*/
   p->data[s]=rc;     /*父结点等于根结点*/
}/*HeapSift*/
void HeapSort(SL *h)  /*堆排序*/
  {int i,j;
    ElemType rc;
   for(i=h->length/2;i>=1;i--)   /*将二叉树转换为堆排序*/
     HeapSift(h,i,h->length);
   for(j=h->length;j>=2;j--)  /*开始堆排序*/
     {rc=h->data[1];     /*根结点与最后一个结点交换*/
      h->data[1]=h->data[j];
      h->data[j]=rc;
      HeapSift(h,1,j-1);  /*其余结点重建堆*/
      }/*for*/
   }/*HeapSort*/
void PrintSort(SL *h)
 {int i=1;
  for(i=1;i<=h->length;i++)
    {printf("%d\t",h->data[i].Num);
     printf("%s\t",h->data[i].Name);
     printf("%.1f\n",h->data[i].Score);
    }
  }
void main()
  {SL *h;
   int node;
   int i,j;
   h=(SL *)malloc(sizeof(SL));
   printf("输入排序元素个数\n");
   scanf("%d",&node);
   h->length=node;
   InitHeap(h);
   printf("待排序列为:\n");  /*输出待排序列*/
   PrintSort(h);
   printf("\n");
   HeapSort(h);  /*进行堆排序*/
   printf("\n 排序结果是:\n"); /*输出排序结果*/
   PrintSort(h);
   printf("\n");
   getch();
  }