[查找问题] 例5.2 查找学生信息

题目描述:

输入N个学生的信息，然后进行查询。

输入:

输入的第一行为N，即学生的个数(N<=1000)

接下来的N行包括N个学生的信息，信息格式如下：

01 李江 男 21

02 刘唐 男 23

03 张军 男 19

04 王娜 女 19

然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下：

02

03

01

04

输出:

输出M行，每行包括一个对应于查询的学生的信息。

如果没有对应的学生信息，则输出“No Answer!”

样例输入:

4

01 李江 男 21

02 刘唐 男 23

03 张军 男 19

04 王娜 女 19

5

02

03

01

04

03

样例输出:

02 刘唐 男 23

03 张军 男 19

01 李江 男 21

04 王娜 女 19

03 张军 男 19

来源:

清华大学计算机研究生机试真题

解题思路:先将输入的学生按学号排序重新存好, 然后采用二分查找法.

#include<bits/stdc++.h>using namespace std; struct Student{//用于表示学生的结构体char no[100];//学号 char name[100];//姓名int age; //年龄char sex[5];//性别bool operator < (const Student &A) const{//重载小于运算符使其能够使用sort函数排序 return strcmp(no, A.no) < 0; } }buf[1001];int main(){int n;while(scanf("%d", &n) != EOF){for(int i=0; i<n; i++){scanf("%s%s%s%d", &buf[i].no, &buf[i].name, &buf[i].sex, &buf[i].age); }sort(buf, buf+n);//对数组排序使其按照学号升序排列 int t;cin >> t;//有t组询问while(t--){int ans = -1; // 目标元素下标, 初始化为-1char x[30];scanf("%s", x);//带查找学号int top = n-1, base = 0; //初试时,开始下标0,结束下标n-1,查找子集为整个数组while(top>=base){//当查找子集不为空集时重复二分查找 int mid = (top + base) / 2; //计算中间点下标int tmp = strcmp(buf[mid].no, x); //比较中间点学号与目标学号if(tmp==0){ans = mid;break; // 若相等,则查找完成跳出二分查找 } else if(tmp>0) top = mid - 1;//若大于,则结束下标变为中间点前一个点下标else base= mid+1; //若小于,则开始点下标变为中间点后一个点坐标 } if(ans==-1){//若查找失败 cout << "No Answer!" << endl;}else printf("%s %s %s %d\n", buf[ans].no, buf[ans].name, buf[ans].sex, buf[ans].age);//若查找成功,则输出 } }return 0;}

本题在线测试入口

结束

如果觉得《[查找问题] 例5.2 查找学生信息》对你有帮助，请点赞、收藏，并留下你的观点哦！