实验8-9查找和排序

实验八、九：查找、排序算法的应用

班级 B11521 学号 20114052103 姓名 王雅超 成绩

一、实验目的

1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。

3 掌握排序的不同方法，并能用高级语言实现排序算法。

4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。 二、实验内容

1 创建给定的顺序表。表中共包含八条学生信息，信息如下： 学号 姓名 班级 C 数据结构 1 王立 03511 85 76 2 张秋 03511 78 88 3 刘丽 03511 90 79 4 王通 03511 75 86 5 赵阳 03511 60 71 6 李艳 03511 58 68 7 钱娜 03511 95 89 8 孙胜 03511 45 60

2 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

3 使用二分查找方法，从查找表中查找学号为7和12的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。（注意：创建静态查找表时必须按学号的从小到大排列！）

4 使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。

5 使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。

6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。

7 编写一个主函数，将上面函数连在一起，构成一个完整程序。 8 将实验源程序调试并运行。 三、实验结果

#include #include #define M 100 typedef struct {

int classNum; char name; int studentNum;int C; int structure;

}Student; typedef struct { Student s[M]; int length; }s_t;

int creat(s_t *t,int Num) { int i; t->length=Num; for(i=1;i<=t->length;i++) { printf(\请输入学生的学号，姓名，班级，C语言成绩，数据结构成绩:\\n\ scanf(\>s[i].structure)); } return 0; }

int print(s_t *t) { int i; printf(\学生学号 姓名 班级 C语言成绩 数据结构成绩:\ for(i=1;i<=t->length;i++) {

printf(\ }

return 0; }

int S_Search(s_t *t,char kx) {

int i; t->s[0].name=kx; for(i=t->length;i>=0;i--) if(t->s[i].name==kx) return i; }

void InserSort(s_t *t) {

int i; for(i=2;i<=t->length;i++) if(t->s[i].names[i-1].name) {

t->s[0]=t->s[i]; for(int j=i-1;t->s[0].names[j].name;j--)

t->s[j+1]=t->s[j]; t->s[j+1]=t->s[0]; } }

int Select_Sort(s_t *t) { int i,j,k; for(i=0;ilength;i++) { k=i;

for(j=i+1;j<=t->length;j++) if(t->s[k].C>t->s[j].C) k=j; if(i!=k) {

t->s[0]=t->s[k]; t->s[k]=t->s[i]; t->s[i]=t->s[0]; } } return 0; }

int Half_Sort(s_t *t,int num) { int flag=0; int low,high,mid; low=1;

high=t->length; while(low<=high) { mid=(low+high)/2; if(t->s[mid].studentNum>num) high=mid-1;

else if(t->s[mid].studentNum

flag=mid; break; } } return flag; }

int Bu_Sort(s_t *t) { int i,j,swap;

for(i=1;ilength;i++) { swap=0;

for(j=1;j<=t->length-i;j++) if(t->s[j].structure>t->s[j+1].structure) { t->s[0]=t->s[j]; t->s[j]=t->s[j+1]; t->s[j+1]=t->s[0]; swap=1; } if(swap==0) break; } return 0; }

int Partition(s_t *t,int i,int j) {

t->s[0]=t->s[i]; while(i

while(is[j].studentNum>=t->s[0].studentNum) j--; if(is[i]=t->s[j]; i++; } while (is[i].studentNums[0].studentNum) i++; if(is[j]=t->s[i]; j--; } }

t->s[i]=t->s[0]; return i; }

void Quick_sort(s_t *t,int s,int p) { int i; if(s

i=Partition(t,s,p); Quick_sort(t,s,i-1);