2020-2021学年信息学奥赛资料 第十八课 基本数据结构（适用于高中）课件（13张PPT）

第十八课 基本数据结构

目 标
01、理解结构体的概念和应用背景。
02、 学会使用结构体解决一些实际问题。
结构体
在存储和处理大批量数据时，一般会使用数组来实现，但是每一个数据的类型及含义必须一样。如果需要把不同类型、不同含义的数据当作一个整体来处理，如 1000 个学生的姓名、性别、年龄、体重、成绩等，怎么处理呢？
C++ 提供了结构体（struct）来解决这类问题。
1. 结构体的定义
C++ 中的结构体是由一系列具有相同类型或不同类型的数据构成的数据集合，也叫结构。
使用结构体，必须要先声明一个结构体类型，再定义和使用结构体变量。结构体类型的声明格式如下：
struct 类型名{
数据类型1 成员名1;
数据类型2 成员名2;
…};
定义结构体变量
定义结构体变量格式如下：
struct 结构体类型名 变量名列表;
也可以把结构体类型声明和变量定义合在一起，格式如下：
struct 类型名{
数据类型1 成员名1;
数据类型2 成员名2;
…
} 变量名;
2. 结构体的使用
结构体变量具有以下特点：
（1）可以对结构体变量的整体进行操作。
例如：swap(a[i],a[j])
（2）可以对结构体变量的成员进行操作。
引用结构体变量中成员的格式为：
结构体变量名. 成员名
（3）结构体变量的初始化方法与数组类似。
例1、学生信息
【问题描述】
输入一个学生的信息，包括姓名、性别、年龄、体重，再输出这些信息。
【输入格式】
一行，依次是学生的姓名、性别、年龄、体重。
【输出格式】
一行，依次是姓名、性别、年龄、体重（体重保留一位小数）。
【输入样例】
zhangsan m 20 90.5
【输出样例】
zhangsan m 20 90.5
#include
using namespace std;
struct student{
string name;
char sex;
int age;
double weight;
};
int main(){
student stu;
cin >> stu.name >> stu.sex >> stu.age >> stu.weight;
cout << stu.name << “ “ << stu.sex << “ “ << stu.age << “ “ ;
cout << fixed << setprecision(1) << stu.weight << endl;
return 0;
}
例2、年龄排序
【问题描述】
输入 n 个学生的信息，包括姓名、性别、出生年月。要求按年龄从小到大依次输出这些学生的信息。数据保证没有学生同年同月出生。
【输入格式】
第一行一个整数 n，表示学生人数，n≤100。
接下来 n 行，每一行依次输入学生的姓名、性别、出生年份、出生月份。
【输出格式】
按年龄从小到大，一行输出一个学生的原始信息。
【输入样例】
5
John male 1999 12
David female 1999 8
Jason male 1998 11
Jack female 1998 8
Kitty female 2000 7
【输出样例】
Kitty female 2000 7
John male 1999 12
David female 1999 8
Jason male 1998 11
Jack female 1998 8
#include
using namespace std;
struct stu{
string name;
string sex;
int year,month;};
const int MAXN = 110;
stu a[MAXN];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i].name >> a[i].sex >> a[i].year >> a[i].month;
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
if(a[i].year < a[j].year || a[i].year == a[j].year && a[i].month < a[j].month)
swap(a[i],a[j]);
for(int i = 1; i <= n; i++){
cout<< a[i].name << ” ” << a[i].sex << ” ” ;
cout<< a[i].year << ” ” << a[i].month << endl; }
return 0;}
作业、猴子选大王
【问题描述】
有 n 只猴子围成一圈，从 1~n 编号，大家决定从中选出一个大王。经过协商，决定选大王的规则为：从编号为1的猴子开始报数，报到k的猴子出圈，然后再从下一只开始继续报1到k……最后剩下来的那一只就是大王。要求编程从键盘输入 n、k，输出成为大王的猴子编号。
【输入格式】
一行两个正整数 n 和 k，2≤n≤1000，2≤k≤10^9 。
【输出格式】
一行一个正整数，代表猴王的编号。
【输入样例】
3 2
【输出样例】
3
【问题分析】
本题采用“模拟”法实现。可以定义一个一维数组来模拟猴子在不在圈内，用 a[i] 代表第 i 只猴子的状态，0 代表出圈，1 代表在圈内。然后不断的扫描这个一维数组，如果猴子在圈内，则计数器加 1；如果不在就不加，当计数器到达 k 时，就把当前这只猴子标志出圈，然后作出一些相关的处理；当还剩一只猴子的时候就停止操作，输出剩下的圈内这只猴子的编号。
以上算法的最大问题是，如果猴子数比较多，不断扫描一维数组的时候会很慢，特别是当大部分猴子都已经出圈，会扫描很多无猴子的“无效”操作。如果建立一个循环链表，那么在扫描的时候就不会出现无猴子还扫描的情况，在猴子出圈的时候只需要在链表中删除一个元素，这样效率会提高很多。
具体操作如下：定义一个结构体 monkey，里面有两个参数，一个代表猴子编号，另一个记录这只猴子的下一只猴子的编号，注意一开始每只猴子的下一只猴子的编号是本身的编号加 1，最后一只猴子的下一只猴子的编号是 1 号。
如果需要删除 3 号猴子，那么只需要把当前 3 号猴子前一只猴子 2 号的下一只猴子序号，指向当前猴子 3号的下一只猴子序号 4。