sy9_1_1.c

数据结构实验与学习指导

/*  sy9_1_1.c  */
#include "stdio.h"
#include "alloc.h"
typedef int Status;
#define MAXLEN 100
typedef struct
  {int Num;
   char Name[8];
   float Score;
   }ElemType;
typedef struct
  {ElemType *data;
   int length;
  }SL;
SL *Create_Sq(int n) /*创建表，长度n*/
{SL *S=(SL *)malloc(sizeof(SL));
   S->data=(ElemType *)calloc(n+1,sizeof(ElemType));
   S->length=n;
   return S;
}
void Init_Sq(SL *S) /*初始化，赋值*/
{ int i;
   char ss[8];
   float fff;
   for(i=1;i<=S->length;i++)
    {printf("请输入一个学生的信息:num,name,score\n");
     scanf("%d",&S->data[i].Num);
     getchar();
     gets(ss);
     strcpy(S->data[i].Name,ss);
     scanf("%f",&fff);
     S->data[i].Score=fff;
    }
}
void Print(SL p)/*输出结果*/
{int i;/*循环控制变量*/
   for(i=1;i<=p.length;i++)
    {printf("%d\t",p.data[i].Num);
     printf("%s\t",p.data[i].Name);
     printf("%.1f\t\n",p.data[i].Score);
    }
}
void InsertSort(SL *p) /*直接插入排序*/
{int i,j;
   for(i=2;i<=p->length;i++)
    if(p->data[i].Num<p->data[i-1].Num)
    {p->data[0]=p->data[i];
     for(j=i-1;p->data[0].Num<p->data[j].Num;j--)
         p->data[j+1]=p->data[j];/*记录后移*/
     p->data[j+1]=p->data[0];
    }
}
void ShellInsert(SL *p,int dk)     /*一趟增量排序*/
{int i,j;
 for(i=dk+1;i<=p->length;i++)
   if(p->data[i].Num<p->data[i-dk].Num)
     {p->data[0]=p->data[i];
      for(j=i-dk;j>0&&p->data[0].Num<p->data[j].Num;j=j-dk)
        p->data[j+dk]=p->data[j];         /*记录后移*/
      p->data[j+dk]=p->data[0];
      }
 }
void ShellSort(SL*p,int dlta[],int t)
{/*按照增量序列dlta对顺序表作希尔排序*/
 int k;
 for(k=0;k<t;k++)
   ShellInsert(p,dlta[k]);
}
void SelectSort(SL *p) /*直接选择排序*/
{int i,j,k;
 for(i=1;i<p->length;i++)
  {k=i;
   for(j=i+1;j<=p->length;j++)
    if(p->data[k].Num>p->data[j].Num)
      k=j;
   if(i!=k)
    {p->data[0]=p->data[i];
     p->data[i]=p->data[k];
     p->data[k]=p->data[0];
    }
  }
}
void main()
{SL *p;
int i,k=0,j=-1,n,dlta[MAXLEN];
printf("请输入表的长度");
scanf("%d",&n);
  p= Create_Sq(n);/*创建长度为n的顺序表*/
  Init_Sq(p);
  for(i=2;i<=n;i=i+2)
    {dlta[k]=n/i;k++;}
while(j)
   {printf("请选择操作:\n");
printf("1  直接插入排序\n");
printf("2  快速排序\n");
printf("3  简单选择排序\n");
printf("0  退出程序\n");
scanf("%d",&j);
switch(j)
     { case 0:printf("程序退出!\n");
              exit(0);
       case 1:InsertSort(p);
              break;
       case 2:ShellSort(p,dlta,k);
              break;
       case 3:SelectSort(p);
             break;
     default: printf("输入无效，请重新输入!\n");
    }
   Print(*p);
  }
}