查找、排序的应用实验报告.doc

查找、排序的应用实验报告.doc查找、排序的应用实验报告
查找、排序的应用实验报告
1 / 131 / 13
查找、排序的应用实验报告
实验七 查找、排序的应用
一、 实验目的
1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。
2、学会比较各种排序与查找算法的优劣。
3、学会针对所给问题选用最适合的算法。
4、掌握利用常用的排序与选择算法的思想来解决一般问题的方
法和技巧。
二、实验内容
[ 问题描述 ]
对学生的基本信息进行管理。
[ 基本要求 ]
设计一个学生信息管理系统， 学生对象至少要包含： 学号、姓
名、性别、成绩 1、成绩 2、总成绩等信息。要求实现以下功能：
1．总成绩要求自动计算；
2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现） ；
3．排序：分别按学生的学号、成绩 1、成绩 2、总成绩进行排
序（要求至少用两种排序算法实现） 。
[ 测试数据 ]
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握哈希表的定义，哈希函数的构造方法。
2、掌握一些常用的查找方法。
1、掌握几种常用的排序方法。
2、掌握直接排序方法。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
五、算法设计
a、折半查找
设表长为 n， low 、 high 和 mid 分别指向待查元素所在区间的下界、上界和
查找、排序的应用实验报告
查找、排序的应用实验报告
2 / 132 / 13
查找、排序的应用实验报告
中点 ,key 为给定值。初始时，令 low=1,high=n,mid=
key 与 mid 指向的记录比较，
若 key==r[mid].key ，查找成功
若 key<r[mid].key ，则 high=mid-1
若 key>r[mid].key ，则 low=mid+1
重复上述操作，直至 low>high 时，查找失败

(low+high)/2

，让
查找、排序的应用实验报告
查找、排序的应用实验报告
13 / 1313 / 13
查找、排序的应用实验报告
b、顺序查找
从表的一端开始逐个进行记录的关键字和给定值的比较。 在这里从表尾开始并把下标为 0 的作为哨兵。
void chaxun(SqList &ST) // 查询信息
{ cout<<"\n************************"<<endl; cout<<"~ (1) 根据学号查询 ~"<<endl;
cout<<"~
(2)
根据姓名查询
~"<<endl;
cout<<"~
(3)
根据性别查询
~"<<endl;
cout<<"~
(4)
退出
~"<<endl;
cout<<"************************"<<endl; if(m==1)
折半查找算法 ：
for(int i=1;i<;i++)// 使学号变为有序
for(int j=i;j>=1;j--)
if([j].xuehao<[j-1].xuehao)
{
LI=[j];
[j]=[j-1];
[j-1]=LI;
查找、排序的应用实验报告
查找、排序的应用实验报告
13 / 1313 / 13
查找、排序的应用实验报告
}
int a=0;
cout<<" 输入要查找的学号 "<<endl;
cin>>n;
int low,high,mid;
low=0;high=-1; // 置区间初值 while (low<=high)
{
mid=(low+high)/2;
if(n==[mid].xuehao)
{
cout<<[mid].xuehao<<"
"<<[mid].xingming<<"
"<<[mid].xingbei<<"
"<<[mid].chengji1<<"
"<<[mid].chengji2<<"
"<<[mid].zong<<e