查找、排序实验
班级 学号 姓名
一、实验目的
1 掌握不同的查找和排序方法，并能用高级语言实现相应算法。
2 熟练掌握顺序查找和二分查找方法。
3 熟练掌握直接插入排序、选择排序、冒泡排序、快速排序。
二、实验内容
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 <iostream>
using namespace std;
#include <string>
#include <iomanip>
#define M 100
typedef string Keytype;
typedef struct
{
Keytype classNum;
Keytype 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++)
{
cout<<"请输入第"<<i<<"个学生的信息(学号，姓名，班级，C++，数据结构):"<<endl;
cin>>t->s[i].studentNum>>t->s[i].name>>t->s[i].classNum>>t->s[i].C>>t->s[i].structure;
}
return 0;
}
int print(s_t *t)
{
int i;
cout<<" "<<"学号"<<" "<<"姓名"<<" "<<"班级"<<" "<<"C++成绩"<<" "<<"数据结构"<<" "<<endl;
for(i=1;i<=t->length;i++)
{
cout<<" "<<t->s[i].studentNum<<" "<<t->s[i].name<<" "<<t->s[i].classNum<<" "<<t->s[i].C<<" "<<t->s[i].structure<<" "<<endl;
}
return 0;
}
int S_Search(s_t *t,Keytype 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].name<t->s[i-1].name)
{
t->s[0]=t->s[i];
for(int j=i-1;t->s[0].name<t->s[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;i<t->length;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<num)
low=mid+1;
else
{
flag=mid;
break;
}
}
return flag;
}
int Bu_Sort(s_t *t)
{
int i,j,swap;
for(i=1;i<t->length;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<j)
{
while(i<j&&t->s[j].studentNum>=t->s[0].studentNum)
j--;
if(i<j)
{
t->s[i]=t->s[j];
i++;
}
while (i<j&&t->s[i].studentNum<t->s[0].studentNum)
i++;
if(i<j)
{
t->s[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<p)
{
i=Partition(t,s,p);
Quick_sort(t,s,i-1);
Quick_sort(t,i+1,p);
}
}
void Quick(s_t *t,int n)
{
Quick_sort(t,1,n);
}
int main()
{
s_t *t;
int i,n,n1,Num;
int flag=1;
Keytype kx;
t=new s_t;
cout<<" *********欢迎进入学生管理系统************** "<<endl;
cout<<" 1 按姓名顺序查找 2 输出所有学生信息 3 直接插入排序"<<endl;
cout<<" 4 按C++选择排序 5 按学号二分查找 6 按数据结构冒泡排序 "<<endl;
cout<<" 7 按学号快速排序 8 建立学生的信息 0 退出程序 "<<endl;
cout<<" ******************************************** "<<endl;
while(flag)
{
cout<<"请选择要进行的操作:";
cin>>n;
switch(n)
{
case 1:
cout<<"请输入要查找的学生的姓名:"<<endl;
cin>>kx;
i=S_Search(t,kx);
if(i)
{
cout<<" "<<"学号"<<" "<<"姓名"<<" "<<"班级"<<" "<<"C++成绩"<<" "<<"数据结构"<<" "<<endl;
cout<<" "<<t->s[i].studentNum<<" "<<t->s[i].name<<" "<<t->s[i].classNum<<" "<<t->s[i].C<<" "<<t->s[i].structure<<" "<<endl;
cout<<endl;
}
else cout<<"没有此人！"<<endl;
break;
case 2:
cout<<"输出现在学生的全部信息:"<<endl;
print(t);
break;
case 3:cout<<"直接插入排序:"<<endl;
cout<<"排序前的学生信息"<<endl;
print(t);
cout<<"排序后的学生信息"<<endl;
InserSort(t);
print(t);
break;
case 4:cout<<"选择排序:"<<endl;
cout<<"排序前的学生信息"<<endl;
print(t);
Select_Sort(t);
cout<<"排序后的学生信息"<<endl;
print(t);
break;
case 5:Select_Sort(t);
cout<<"输入要查找的学号"<<endl;
cin>>n1;
i=Half_Sort(t,n1);
if(i)
{
cout<<" "<<"学号"<<" "<<"姓名"<<" "<<"班级"<<" "<<"C++成绩"<<" "<<"数据结构"<<" "<<endl;
cout<<" "<<t->s[i].studentNum<<" "<<t->s[i].name<<" "<<t->s[i].classNum<<" "<<t->s[i].C<<" "<<t->s[i].structure<<" "<<endl;
cout<<endl;
}
else cout<<"不存在此学号!"<<endl;
break;
case 6:cout<<"冒泡排序"<<endl;
cout<<"排序前的学生信息"<<endl;
print(t);
Bu_Sort(t);
cout<<"排序后的学生信息"<<endl;
print(t);
break;
case 7:
cout<<""<<endl;
print(t);
cout<<""<<endl;
Quick(t ,Num);
print(t);
break;
case 8:
cout<<"请输入学生的个数：";
cin>>Num;
creat(t,Num);
break;
case 0: return 0;
default:cout<<"没有此功能，请选择正确的操作！"<<endl;break;
}
}
return 0;
}
运行结果：
表1 输入学生信息
表2 顺序查找方法
表3 按姓名直接插入
表4 按C成绩选择排序
表5 按学号进行二分法查找
表6 按数据结构成绩进行冒泡法排序
四、实验总结
（1）直接插入排序时，要明确后移的结束条件，以便进行正确插入。
（2）选择排序时，选择最小或是最大的数据，放到最后。进行N-1趟排序，排序完成。
（3）二分法排序时，正确返回查找的下标。返回值flag要进行赋初值，以便返回时，正确输出查找结果。
（4）冒泡排序时，用swap进行排序的标志。节省排序的趟数。
北 华 航 天 工 业 学 院
《数据结构》
课程实验报告
实 验 题 目 ： 查找、排序实验
作者所在系部： 计算机科学与工程系
作者所在专业： 网络工程
作者所在班级：
作 者 学 号 ：
作 者 姓 名 ：
任课教师姓名：
完 成 时 间 ： 2010/12/28
北华航天工业学院教务处制