sy8_1.c

数据结构实验与学习指导

/*  sy8_1.c  8/
#include"stdio.h"
typedef int Status;
typedef struct std_info  /*定义数据元素类型*/
  { int Num;
    char Name[8];
    float Score;
  } ElemType;
typedef struct
  { ElemType *elem;
    int len;
  }ST;
ST *Init_Sq(int len) /*初始化,赋值*/
{  int i;
   ST *S=(ST *)malloc(sizeof(ST));
   float sco;
   char *n;
   S->len=len;
   for(i=1;i<=S->len;i++)
    { n=S->elem[i].Name;
      printf("请输入第%d个学生的信息\n",i); /*依次输入学生信息*/
      printf("请输入学号（整型）:");
      scanf("%d",&S->elem[i].Num);
      printf("请输入成绩（浮点型):");
      scanf("%f",&sco);
      S->elem[i].Score=sco;
      printf("请输入姓名:");
      scanf("%s",n);
    }
    return S;
}
void Order(ST *S)/*此函数的功能是排序*/
{int i,j;
   ElemType k;  /*k为中间临时变量*/
   for(i=1;i<S->len;i++)
   for(j=i;j<=S->len;j++)
     if(S->elem[j].Num<S->elem[i].Num) /* 交换*/
     { k=S->elem[i];
       S->elem[i]=S->elem[j];
       S->elem[j]=k;
      }/*从小到大排序完毕*/
}
Status Search_Seq(ST S,int key)       /*顺序查找*/
{  int i;
   S.elem[0].Num=key;/*哨兵*/
   for(i=S.len;S.elem[i].Num!=key;i--);  /*从后往前查找*/
   return i;/*返回找到的元素的下标*/
}
Status Search_Bin(ST S,int key)/*折半查找*/
{ int low,high,mid;
    low=1;/*指向第一个元素*/
    high=S.len;/*指向最后一个元素*/
    while(low<=high)
     { mid=(low+high)/2;
       if(S.elem[mid].Num==key) /*找到*/
         return mid;
       else if(key<S.elem[mid].Num)/*查找前半区*/
              high=mid-1;
           else low=mid+1;/*后半区*/
       }
     return 0;/*查找失败*/
   }
void Print(ST L)/*输出结果*/
 { int i;/*循环控制变量*/
    printf("学生序列为:\n");
    for(i=1;i<=L.len;i++)
    { printf("%d\t",L.elem[i].Num);
      printf("%s\t",L.elem[i].Name);
      printf("%.1f\t",L.elem[i].Score);
      printf("\n");
    }
}
void PrintOne(ST *L,int I) /*函数的功能是输出线性表L中第I个元素的内容*/
{ printf("%d\t",(L->elem[I]).Num);
  printf("%s\t",(L->elem[I]).Name);
  printf("%.1f\t\n",(L->elem[I]).Score);
}
void main()
   { int j=-1; /*菜单选择项*/
     int K;/*要查找的关键字,即学生的学号*/
     int suc;
     ST *st;
     st= Init_Sq(3); /*创建学生信息表，长度随意修改*/
     Print(*st);
     while(j) /*下面是功能菜单*/
     { printf("请选择操作:\n");
       printf("1: 顺序查找\n");
       printf("2: 二分查找\n");
       printf("0: 退出程序\n");
       scanf("%d",&j);
       switch(j)
       {    case 0: break;
             case 1: printf("请输入要查找的学生的学号:");
                      scanf("%d",&K);
                      suc=Search_Seq(*st,K);
                      if(suc) 
                      PrintOne(st,suc);
                 else printf("查找失败! \n ");
                 break;
        case 2: Order(st);       /*对学生信息表进行排序*/
                printf("请输入要查找的学生的学号:");
                scanf("%d",&K);
                suc= Search_Bin(*st,K);
                 if(suc) 
                     PrintOne(st,suc);
                 else printf("查找失败!\n ");
                break;
       default: printf("输入无效，请重新输入！\n");
               break;}
     }
   }