实验五 查找与排序
实验课程名:数据结构与算法
专业班级: 12级软件工程1班 学号: 201240450149 姓名: 刘浩
实验时间: 6.14 6.21 34节 实验地点: K4-201 指导教师: 邓丹君
实验七 查找、排序的应用
一、 实验目的
1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。
2、学会比较各种排序与查找算法的优劣。
3、学会针对所给问题选用最适合的算法。
4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。
二、实验内容
[问题描述]
对学生的基本信息进行管理。
[基本要求]
设计一个学生信息管理系统,学生对象至少要包含:学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能:
1.总成绩要求自动计算;
2.查询:分别给定学生学号、姓名、性别,能够查找到学生的基本信息(要求至少用两种查找算法实现);
3.排序:分别按学生的学号、成绩1、成绩2、总成绩进行排序(要求至少用两种排序算法实现)。
[测试数据]
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握哈希表的定义,哈希函数的构造方法。
2、掌握一些常用的查找方法。
1、掌握几种常用的排序方法。
2、掌握直接排序方法。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果,对程序进行分析。
五、算法设计
a、折半查找
设表长为n,low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时,令low=1,high=n,mid=?(low+high)/2,让key与mid指向的记录比较,
若key==r[mid].key,查找成功
若key<r[mid].key,则high=mid-1
若key>r[mid].key,则low=mid+1
重复上述操作,直至low>high时,查找失败
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<ST.length;i++)//使学号变为有序
for(int j=i;j>=1;j--)
if(ST.r[j].xuehao<ST.r[j-1].xuehao)
{
LI=ST.r[j];
ST.r[j]=ST.r[j-1];
ST.r[j-1]=LI;
}
int a=0;
cout<<"输入要查找的学号"<<endl;
cin>>n;
int low,high,mid;
low=0;high=ST.length-1; // 置区间初值
while (low<=high)
{
mid=(low+high)/2;
if(n==ST.r[mid].xuehao)
{
cout<<ST.r[mid].xuehao<<" "<<ST.r[mid].xingming<<" "<<ST.r[mid].xingbei<<" "<<ST.r[mid].chengji1<<" "<<ST.r[mid].chengji2<<" "<<ST.r[mid].zong<<endl;
a=1;
break;
}
else if(n<ST.r[mid].xuehao )
high=mid-1; // 继续在前半区间进行查找
else
low=mid+1; // 继续在后半区间进行查找
顺序查找算法:
cout<<"输入要查找的姓名"<<endl;
cin>>name;
for(int i=0;i<ST.length;i++)
{
if(name==ST.r[i].xingming)
{
cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" "<<ST.r[i].zong<<endl;
a=1;
}
1、 插入排序
每步将一个待排序的记录,按其关键码大小,插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。
//按学号排序,使用插入排序
RecordType LI; //定义存储学号向量
for(int i=1;i<ST.length;i++)
for(int j=i;j>=1;j--)
if(ST.r[j].xuehao<ST.r[j-1].xuehao)
{
LI=ST.r[j];
ST.r[j]=ST.r[j-1];
ST.r[j-1]=LI;}
2、选择排序
首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换
再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换
重复上述操作,共进行n-1趟排序后,排序结束。
//按成绩1排序,用选择排序
RecordType LI;
for(int i=0; i<ST.length;i++)
for (int j=i+1;j<ST.length;j++)
{if(ST.r[i].chengji1>ST.r[j].chengji1)
{LI=ST.r[j];
ST.r[j]=ST.r[i];
ST.r[i]=LI;
六、运行测试结果
输入学生信息
以多种方式进行查找
按总成绩进行排序
六、实验总结
通过本次实验我对查找排序的应用有了一定得了解,知道了各种查找排序的基本知识。 同时,通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点,比如这次的界面是复制过来的,其中很多语句经过同学的讲解都理解了。但这次实验也有很多不尽人意的地方,我将在以后多学习同学优秀的地方.也会在以后的学习过程中要尽量考虑周全,使程序更有实用价值,提高编程能力。
七、源代码
#include <iostream>
using namespace std;
#include <string>
#define MAXSIZE 100 //设记录不超过20个
typedef struct //定义每个记录(数据元素)的结构
{
string xingming; //姓名
string xingbei; //性别
float xuehao; //学号
float chengji1,chengji2; //成绩1,成绩2
float zong; //总分
}RecordType;
typedef struct //定义顺序表的结构
{
RecordType r[ MAXSIZE +1 ]; //存储顺序表的向量
int length; //顺序表的长度
}SqList;
void caidan(SqList &ST);
void CreatList(SqList &ST)//创建学生的相关信息
{
cout<<"输入学生个数"<<endl;
cin>>ST.length;
for(int i=0;i<ST.length;i++)
{
cout<<"输入第"<<i+1<<"学生的信息"<<endl;
cout<<"学号"<<endl;
cin>>ST.r[i].xuehao;
cout<<"姓名"<<endl;
cin>>ST.r[i].xingming;
cout<<"性别"<<endl;
cin>>ST.r[i].xingbei;
cout<<"成绩1"<<endl;
cin>>ST.r[i].chengji1;
cout<<"成绩2"<<endl;
cin>>ST.r[i].chengji2;
}
cout<<"输入完毕"<<endl;
}
void zong(SqList &ST) //计算总分
{
for(int i=0;i<ST.length;i++)
{
ST.r[i].zong=ST.r[i].chengji1+ST.r[i].chengji2;
}
}
void shuchu(SqList &ST)//输出
{
cout<<"学生的信息如下"<<endl;
cout<<"学号 姓名 性别 成绩1 成绩2 总分 "<<endl;
for(int i=0;i<ST.length;i++)
{
cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" " <<ST.r[i].zong<<" "<<endl;
}
}
void chaxun(SqList &ST) //查询信息
{
l1: cout<<endl;
cout<<"(1)根据学号查询"<<endl;
cout<<"(2)根据姓名查询"<<endl;
cout<<"(3)根据性别查询"<<endl;
cout<<"(4)退出"<<endl;
int n,m;
string name;
string xb;
cin>>m;
if(m==1) //折半查找
{
RecordType LI; //使学号变为有序
for(int i=1;i<ST.length;i++)
for(int j=i;j>=1;j--)
if(ST.r[j].xuehao<ST.r[j-1].xuehao)
{
LI=ST.r[j];
ST.r[j]=ST.r[j-1];
ST.r[j-1]=LI;
}
l2: int a=0;
cout<<"输入要查找的学号"<<endl;
cin>>n;
int low,high,mid;
low=0;high=ST.length-1; // 置区间初值
while (low<=high)
{
mid=(low+high)/2;
if(n==ST.r[mid].xuehao)
{
cout<<ST.r[mid].xuehao<<" "<<ST.r[mid].xingming<<" "<<ST.r[mid].xingbei<<" "<<ST.r[mid].chengji1<<" "<<ST.r[mid].chengji2<<" "<<ST.r[mid].zong<<endl;
a=1;
break;
}
else if(n<ST.r[mid].xuehao )
high=mid-1; // 继续在前半区间进行查找
else
low=mid+1; // 继续在后半区间进行查找
}
if(!a)
{
cout<<"所查信息不存在!"<<endl;
cout<<"请重新输入"<<endl;
goto l2;
}
goto l1;
}
if(m==2) //顺序查找
{
l3: int a=0;
cout<<"输入要查找的姓名"<<endl;
cin>>name;
for(int i=0;i<ST.length;i++)
{
if(name==ST.r[i].xingming)
{
cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" "<<ST.r[i].zong<<endl;
a=1;
}
}
if(!a)
{
cout<<"所查信息不存在!"<<endl;
cout<<"请重新输入"<<endl;
goto l3;
}
goto l1;
}
if(m==3) //顺序查找
{
l4: int a=0;
cout<<"输入要查找性别"<<endl;
cin>>xb;
for(int i=0;i<ST.length;i++)
{
if(xb==ST.r[i].xingbei)
{
cout<<ST.r[i].xuehao<<" "<<ST.r[i].xingming<<" "<<ST.r[i].xingbei<<" "<<ST.r[i].chengji1<<" "<<ST.r[i].chengji2<<" "<<ST.r[i].zong<<endl;
a=1;
}
}
if(!a)
{
cout<<"所查信息不存在!"<<endl;
cout<<"请重新输入"<<endl;
goto l4;
}
goto l1;
}
if(m==4)
{
caidan(ST);
}
}
void paixu(SqList &ST) //排序
{
l1: int n;
cout<<endl;
cout<<"(1)根据学号排序"<<endl;
cout<<"(2)根据成绩1排序"<<endl;
cout<<"(3)根据成绩2排序"<<endl;
cout<<"(4)根据总成绩排序"<<endl;
cout<<"(5)退出";
cout<<endl;
cin>>n;
if(n==1) //按学号排序,使用插入排序
{
RecordType LI; //定义存储学号向量
for(int i=1;i<ST.length;i++)
for(int j=i;j>=1;j--)
if(ST.r[j].xuehao<ST.r[j-1].xuehao)
{
LI=ST.r[j];
ST.r[j]=ST.r[j-1];
ST.r[j-1]=LI;
}
shuchu(ST);
cout<<"排序完毕"<<endl;
goto l1;
}
if(n==2) //按成绩1排序,用选择排序
{
RecordType LI;
for(int i=0; i<ST.length;i++)
for (int j=i+1;j<ST.length;j++)
{
if(ST.r[i].chengji1>ST.r[j].chengji1)
{
LI=ST.r[j];
ST.r[j]=ST.r[i];
ST.r[i]=LI;
}
}
shuchu(ST);
cout<<"排序完毕"<<endl;
goto l1;
}
if(n==3) // 根据成绩2排序,使用选择法排序
{
RecordType LI;
for(int i=0; i<ST.length;i++)
for (int j=i+1;j<ST.length;j++)
{
if(ST.r[i].chengji2>ST.r[j].chengji2)
{
LI=ST.r[j];
ST.r[j]=ST.r[i];
ST.r[i]=LI;
}
}
shuchu(ST);
cout<<"排序完毕"<<endl;
goto l1;
}
if(n==4) //根据总成绩排序,使用选择法排序
{
RecordType LI;
for(int i=0; i<ST.length;i++)
for (int j=i+1;j<ST.length;j++)
{
if(ST.r[i].zong>ST.r[j].zong)
{
LI=ST.r[j];
ST.r[j]=ST.r[i];
ST.r[i]=LI;
}
}
shuchu(ST);
cout<<"排序完毕"<<endl;
goto l1;
}
if(n==5) //退出
{
caidan(ST);
}
}
void caidan(SqList &ST)//选择菜单
{
cout<<"请选择要进入的模块"<<endl;
cout<<"(1)查询"<<endl;
cout<<"(2)排序"<<endl;
cout<<"(3)退出"<<endl;
int c;
cin>>c;
if(c==1)
{
chaxun(ST);
}
if(c==2)
{
paixu(ST);
}
if(c==3)
{
exit(0);
}
}
void main()
{
SqList ST;
CreatList(ST);
zong(ST);
shuchu(ST);
caidan(ST);
}
实验十查找排序计算机学院12级2班1211020xx李龙实验目的1掌握折半查找算法的思想2实现折半查找的算法3掌握常见的排序算法插…
实验五查找与排序实验课程名数据结构与算法专业班级12级软件工程1班学号20xx40450149姓名刘浩实验时间61462134节实…
电子科技大学信息与软件工程学院实验报告电子科技大学实验报告课程名称学生姓名学号点名序号指导教师实验地点实验时间20xx20xx2学…
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
信息检索课程结业报告姓学信息检索与web搜索应用背景及概念信息检索InformationRetrieval是指信息按一定的方式组织…
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
学生成绩查询系统一实习任务2二系统分析3三系统设计4四调试排错测试试运行过程7五源程序完整或主要代码10六总结与体会17七参考文献…
附件2天津商业大学学生实验报告开课实验室403机房开课时间20xx年10月17日实验报告20xx年10月17日注1每个实验项目一份…