在存储和处理大批量数据时,一般会使用数组来实现,但是数组中的每一个数据的类型及含义必须一样。如果需要把不同类型、不同含义的数据当作一个整体来处理,比如1000个学生的姓名性别、年龄、体重、成绩等,怎么办呢?C++提供了结构体(struct)。本节课就来介绍C++结构体的定义和使用。
C++中的结构体是由一系列具有相同类型或不同类型的数据构成的数据集合,也叫结构。使用结构体,必须要先声明一个结构体类型,再定义和使用结构体变量。结构体类型的声明格式如下:
struct 类型名{
数据类型1 成员名1;
数据类型2 成员名2;
...
};
例如,声明一个记录学生信息的结构体:
struct student{ //声明一个结构体类型student
string name; //声明一个记录姓名的字符串成员name
char sex; //声明一个记录性别的字符型成员sex
int age; //声明一个记录年龄的整型成员age
double weight; //声明一个记录体重的双精度成员weight
}
其中,有4个成员:name、sex、age、weight。下面就可以定义结构体变量了格式如下:
struct 结构体类型名 变量名列表;//或 结构体类型名 变量名列表:
例如:
student stu;
student s[1000];
struct student st;
也可以把结构体类型声明和变量定义合在一起,格式如下:
struct 类型名(
数据类型1 成员名1;
数据类型2 成员名2;
...
}变量名;
结构体变量具有以下特点:
1)可以对结构体变量的整体进行操作。例如,swap(a[i],a[j])。
2)可以对结构体变量的成员进行操作。
引用结构体变量中成员的格式为:结构体变量名.成员名。例如:
cin >> s[i].name;
stu.age=16;
3)结构体变量的初始化方法与数组类似。例如:
student s = {"xiaoming",'f',16,169};
输入一个学生的信息,包括姓名、性别、年龄、体重,再输出这些信息。
【输入格式】
一行,依次是学生的姓名、性别、年龄、体重。
【输出格式】
一行、依次是姓名、性别、年龄、体重(体重保留一位小数)。
【输入样例】
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;
}
【问题描述】
输人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<<" "<<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≤109。
【输出格式】
一行一个正整数,代表猴王的编号。
【输入样例】
3 2
【输出样例】
3
【问题分析】
本题采用“模拟”法实现。定义一个一维组来模拟猴子在不在圈内,用a[i]代表第i只猴子的状态,0代表出圈,1代表在圈内。然后不断的扫描这个一维数组,如果猴子在圈内,则计数器加1;如果不在就不加,当计数器到达k时,就把当前这只猴子标志出圈,然后做出一些相关的处理;当还剩一只猴子时停止操作,输出剩下的圈内这猴子的编号。
以上算法的最大问题是,如果猴子数比较多,不断扫描一维数组的时候会很慢,特别是当大部分猴子都已经出圈,会扫描很多无猴子的“无效”操作。如果建立一个循环链表,那么在扫摄的时候就不会出现无猴子还扫描的情况,在猴子出圈的时候只需要在链表中删除一个元素,这样效率会提高很多。具体操作如下:定义一个结构体monkey,里面有两个参数,一个代表猴子编号,另一个记录这只猴子的下一只猴子的编号,注意一开始每只猴子的下一只猴子的编号是本身的编号加1,最后一只猴子的下一只猴子的编号是1号。
如果需要删除3号猴子,那么只需要把当前3号猴子前一只猴子2号的下一只猴子序号,指向当前猴子3号的下一只猴子序号。
#include
using namespace std;
struct monkey{ //声明monkey 结构体
int num; //代表编号
int next; //代表下一只猴子编号
};
#define MAXN 1010
monkey a[MAXN];
int main(){
int n,k,count = 0,remain,kk,cur,pre;
cin >> n >> k;
for(int i=1;i<n;i++){ //猴子建立循环链表
a[i].num=i;
a[i].next =i+1;
}
a[n].num=n;
a[n].next=1;
remain =n;
kk = k%remain; //所点个数取余
if(kk==0) kk=remain;
cur = 1; //当前猴子序号
pre=n; //当前猴子前面一只猴子序号
while(remain>1){
count++;
if(count==kk){ // 猴子出圈
a[pre].next=a[cur].next;
remain--;
count=0;
kk=k%remain;
if(kk==0) kk=remain;
}
else pre=cur;
cur=a[cur].next; //cur 指向后一只猴子
}
cout<<a[cur].num<<endl; //输出唯一在圈内的猴子
return 0;
}
【问题描述】
学校得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有语文、数学、英语3门课的成绩。先按总分从高到低排序,如果两个同学总分相同再按语文成绩从高到低排序;如果两个同学总分和语文成绩都相同,那么规定学号小的同学接在前面。这样,每个学生的排序是唯一确定的。
任务:先根据输人的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出!5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5 号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果前两名的输出数据是:
5 279
7 279
则按输出错误处理,不能得分。
【输人格式】
第1行为一个正整数n,表示该校参加评选的学生人数。
第2–n+1行,每行有3个用一个空格隔开的数字,每个数字都在 0–100之间。第 j 行的 3个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输人数据的行号减1)。
所给的数据都是正确的,不必检验。
【输出格式】
输出共有5行,每行是两个用一个空格隔开的正整数,依次表示前5名学生的学号和总分。
【输入样例】
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
【输出样例】
6 265
4 264
3 258
2 244
1 237
【数据规模】
对于50%的数据满足:各学生的总成绩各不相同。
对于100%的数据满足:6≤n≤300。
#include
using namespace std;
struct node{
int num,chi,mat,eng,tot;
};
node a[311];
bool cmp(node x,node y){
if (x.tot !=y.tot){
return x.tot>y.tot;
}else if (x.chi!=y.chi){
return x.chi>y.chi;
} else return x.num<y.num;
}
int main(){
int n;
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i].chi>>a[i].mat>>a[i].eng;
a[i].num=i;
a[i].tot=a[i].chi+a[i].eng+a[i].mat;
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<=5;i++){
cout<<a[i].num<<" "<<a[i].tot<<endl;
}
return 0;
}
【问题描述】
一个Windows桌面上的窗体用4个整数定义位置:左边坐标、右边坐标、上边坐标、下边坐标。
现在,请输入2个窗体的位置信息,判断它们的位置是否重叠。
【输入格式】
两行,每行1个窗体的位置信息,int 范围以内。
【输出格式】
输出2个窗体的重叠面积,不重叠就输出 0。
【输入样例】
10 100 20 60
60 160 50 200
【输出样例】
400
【参考代码】
#include
using namespace std;
struct twindow{
int left,right,top,bottom;
};
twindow wina,winb,tmp;
twindow indata(){
twindow tmp;
cin >> tmp.left >> tmp.right >> tmp.top >> tmp.bottom;
return tmp;
}
int main(){
// freopen("win.in","r",stdin);
// freopen("win.out","w",stdout);
wina = indata();
winb = indata();
tmp.left = max(wina.left,winb.left);
tmp.right = min(wina.right,winb.right);
tmp.top = max(wina.top,winb.top);
tmp.bottom = min(wina.bottom,winb.bottom);
int s = (tmp.right - tmp.left) * (tmp.bottom - tmp.top);
if((tmp.right <= tmp.left) || (tmp.bottom <= tmp.top)) s = 0;
cout << s << endl;
return 0;
}
学习目标:
1.理解运算符重载的含义及其使用。
2.理解成员函数的含义及其使用。
知识讲解
在C++中,由于类(class)技术的出现使结构体功能得到了很大的增强。本课简单介绍一些与信息学竞赛有关的运算符重载和成员函数知识,其他更详细、复杂的内容请参阅相关书籍和资料。
“运算符重载”常用于解决结构体或自定义数据类型的加法、减法等特殊含义的运算。运算符重载的一般格式为:
类型名 operator 运算符(const 类型名 变量)const{
...
}
【问题描述】
为了了解学生的课后作业负担情况,需要统计续若天完成作业所需的总时间。现在,输入某位学生n天完成作业的时间,格式为时、分、秒,最后输出这位学生n天完成作业的总时间(秒)。
【输入格式】
第1行一个正整数n,表示有n天;
第2~第n+1行,每行3个整数,分别代表时、分、秒。
【输出格式】
一行信息,表示这个学生完成作业的总时间,具体格式见输出样例。
【输人样例】
3
1 20 30
1 20 45
1 19 30
【输出样例】
4hour 0minute 45second
【问题分析】
本题需要把若干时间(时、分、秒)相加,但又不是普通的加法运算。所以,可以利用运算符重载,另外定义一个"+”运算,实现对两个结构体变量的加法。
#include
using namespace std;
struct worktime{ //声明一个结构体类型worktime 记录学生完成作业的时间
int h,m,s;//hr,minut,sec 分别代表时,分,秒
worktime operator +(const worktime x)const{//对+进行重新定义
worktime tmp;
tmp.s=(s+x.s)%60;
tmp.m=(m+x.m+(s+x.s)/60)%60;
tmp.h=h+x.h+( m+x.m+(s+x.s)/60 )/60;
return tmp;
}
};
int main(){
worktime stu,sum;
int n;
cin>>n;
sum.h=sum.m=sum.s=0;
for(int i=1;i<=n;i++){
cin>>stu.h>>stu.m>>stu.s;
sum=sum+stu;//两个结构体sum和stu通过重载+运算符进行加法运算
}
cout<<sum.h<<"hour "<<sum.m<<"minute "<<sum.s<<"second";
return 0;
}
在C++中,允许在结构中定义函数,该函数称为“成员函数”。描述形式如下:
struct 结构名{
数据成员
成员函数
};
【问题描述】输入n个学生的信息,每个学生信息包括姓名、身高、学号。编程输出身高最高的学生的信息。
【输入格式】
第1行一个正整数n,表示学生个数,n≤100。
以下n行,每一行依次输入学生的姓名、身高、学号。
【输出格式】
输出身高最高的学生信息,如果存在身高一样的,请输出学号小的那个同学。
【输人样例】
5
John 172 20160302
David 173 20160306
Jason 168 20160309
Jack 152 20160311
Kitty 147 20160319
【输出样例】
David 173 20160306
【问题分析】
#include
using namespace std;
struct stu{
string name;
int heigh;
int num;
void input(){
cin>>name>>heigh>>num;
}
void output(){
cout<<name<<" "<<heigh<<" "<<num<<endl;
}
};
stu a[110];
int main(){
int n;
stu maxn;
maxn.heigh=maxn.num=0;
cin>>n;
for(int i=1;i<=n;i++){
a[i].input();
if(a[i].heigh>maxn.heigh) maxn=a[i];
else if(a[i].heigh==maxn.heigh &&a[i].num<maxn.num) maxn=a[i];
}
maxn.output();
return 0;
}
【问题描述】
在一个有n个学生的大班级中,存在两个学生生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。
【输入格式】
第1行为正整数n,表示有n个学生,n≤180。
此后n行,每行包含一个字符串和两个正整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月m、生日d,1≤m≤12,1≤d≤31,名字、月、日之间用一个空格分隔。
【输出格式】
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如果没有生日相同的学生,输出“None”。
【输入样例】
6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 45
Lagrange 45
Bill 3 2
【输出样例】
3 2 Tim Bill Avril
45 Candy Sufia Lagrange
【参考代码】
#include
using namespace std;
struct node{
string name;
int mon,day;
};
node a[311];
bool cmp(node x,node y){
if (x.mon!=y.mon) return x.mon<y.mon;
else if (x.day!=y.day) x.day<x.day;
else if (x.name.size()!=y.name.size()) return x.name.size()<y.name.size();
else return x.name<y.name;
}
int main(){
int n;
freopen("birthday.in","r",stdin);
freopen("birthday.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i].name>>a[i].mon>>a[i].day;
}
sort(a+1,a+n+1,cmp);
int start=1,tot=1,flag=0;
for (int i=2;i<=n;i++){
if (a[i].mon==a[i-1].mon&&a[i].day==a[i].day) tot++;
else {
if (tot>1){
flag=1;
cout<<a[start].mon<<" "<<a[start].day<<" ";
for (int j=start;j<i-1;j++)
cout<<a[j].name<<" ";
cout<<a[i-1].name<<endl;
}
tot=1;
start=i;
}
}
if (tot>1){
flag=1;
cout<<a[start].mon<<" "<<a[start].day<<" ";
for (int j=start;j<n;j++)
cout<<a[j].name<<" ";
cout<<a[n].name<<endl;
}
if (flag==0) cout<<"None"<<endl;
return 0;
}
【问题描述】
在数学上,2个集合A和B之间的运算一般有并集、差集、交集,分别记作A+B、A-B、AxB。本题要求设计一款模拟集合运算的游戏程序,已知所有集合的元素都是小写字母,集合的输入、输出用字符串表示。例如,集合 A={a,b,d,e},输入输出用字符串“abde”表示。现在输人n个集合运算式,求运算结果。例如,运算式 abcd-bckg,那么结果为 ad。
【输入格式】
第一行一个正整数n,表示有多少运算式,1≤n≤100。
下面n行,每行一个运算式。运算符号一定是+、-、*之一,运算符号两边各有一个空格隔开。
【输出格式】
共n行,对应输入的运算结果。【输入样例】
2
abed + bcefg abed * beefg【输出样例】 abcdefg bc
#include
using namespace std;
struct tset{
bool set[26];//集合
void input()//输入集合成员函数
{
string s;
cin >> s;
memset(set,false,sizeof(set));
for(int i = 0; i < s.size(); i++)
set[s[i] - 'a'] = true;
}
void output()//输出集合成员函数
{
for(int i = 0; i < 26; i++)
if(set[i]) cout << char(i + 'a');
cout << endl;
}
tset operator + (const tset x) const//重载+
{
tset tmp;
for(int i = 0; i < 26; i++)
tmp.set[i] = set[i] || x.set[i];
return tmp;
}
tset operator - (const tset x) const//重载-
{
tset tmp;
for(int i = 0; i < 26; i++)
tmp.set[i] = set[i] && (!x.set[i]);
return tmp;
}
tset operator * (const tset x) const//重载*
{
tset tmp;
for(int i = 0; i < 26; i++)
tmp.set[i] = set[i] && x.set[i];
return tmp;
}
};
int n;
tset a,b,c;
char op;
int main(){
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
cin >> n;
for(int i = 0; i < n; i++){
a.input();
cin >> op;
b.input();
if(op == '+') c = a + b;
else if(op == '-') c = a - b;
else if(op == '*') c = a * b;
c.output();
}
return 0;
}
学习目标
1.理解共用体的概念和应用背景。
2.学会使用共用体解决一些实际问题。
知识讲解
在C++中,共用体也称联合(union),是一种数据格式,能存储不同类型数据。但同一时间只能存储其中的一种类型数据。例如,存放一个人的信息,如果是成年人,存放他的身份证号码;否则,存放他的学籍号。这里面就有2个成员,但是任何一个人只能使用其中的一个。
使用共用体前必须先声明一个共用体类型,才可以定义和使用共用体变量。例如,要声明一个记录个人信息的共用体,可以这样:
union person{ //声明一个共用体类型person
char id[18]; //声明一个字符数组,存储身份证号码
int num; //声明一个整数,存放学籍号
};
再例如,存放一种颜色的公用体类型如下:
union tcolor{
int rgb[3]; //rgb 和 cmyk 共用内存,不会同时使用
double cmyk[4];
};
共用体的最大用途是当数据项使用多种格式(但不会同时使用)时,可以节省空间。需要注意的是,union 中不能有空间不确定的数据结构类型,如 string。
【问题描述】
兴趣小组收集学员成绩信息,每个学员的成绩有两种表示方法,一种用best、good、poor三种等级来表示,有一种是直接用分数来表示(百分制)。请保存学员成绩信息,并且统计有多少人是用等级来表示成绩的,用分数来表示成绩的人的平均分是多少(取整就行)。
【输入格式】
第
1
1
1 行一个正整数n,表示学员人数,
n
≤
1000
n≤1000
n≤1000
第
2
n
+
1
2~n+1
2 n+1 行,每行一个字符和一个字符串,中间用一个空格隔开。第一个字符表示这个学生成绩类型,有C、N两种分别代表等级表示和分数表示,第二个字符申表示成绩信息。
【输出格式】
一行两个整数,分别表示用等级表示成绩的人数和用分数表示成绩人的平均分(取整),中间用一个空格隔开。
【输人样例】
5
C best
C good
N 90
C poor
N 98
【输出样例】
3 94
【问题分析】
#include
using namespace std;
int main(){
union res{ //声明一个共用体 res
char rank[5]; //用等级表示成绩
int x; //用分数表示成绩
};
struct stu{
char f; //代表学生用哪种方式记录成绩
res score; //定义 score 为共用体
};
stu a[1001];
int n,count =0, num=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].f;
switch(a[i].f){
case 'C':
for(int j=0;j<4;j++)
cin>>a[i].score.rank[j];
count++;
break;
case 'N':cin>>a[i].score.x;
num+=a[i].score.x;
}
}
cout<<count<<" "<<num/(n-count)<<endl;
return 0;
}
可以看出,共用体和结构体的使用方法基本差不多,两者的区别是结构体里所有成员都会分配内存空间,而共用体成员共享同一块大小的内存空间,一次只能供其中的一个成员使用。共用体中可以定义多个成员,其空间大小由最大的成员大小决定。对某一个成员赋值,会覆盖其他成员的值,因为它们共享一块内存。但前提是成员所占字节数相同,当成员所占字节数不同时,只会覆盖相应字节上的值。比如,对char成员赋值不会把整个int成员覆盖掉,因为char类型只占用1字节,而int类型占用4字节。
【问题描述】
在某网站收集了n个人的注册账号,账号类型有身份证号或者QQ号两种。请编程用恰当的数据结构保存信息,并统计身份证中男性和女性的人数,以及QQ账号的平均值(取整)。
提示:身份证号码中倒数第2位若为奇数则表示男性,若为偶数则表示女性。
【输入恪式】
第
1
1
1 行,一个正整数
n
n
n,
1
≤
n
≤
10000
1≤n≤10000
1≤n≤10000;
下面
n
n
n 行,每行一个字符和一个字符串。第一个字符表示账号类型,有i、q 两种,第二个字符串是账号信息。
【输出格式】
一行3个整数,分别代表男性人数、女性人数、QQ号平均值。
【输入样例】
6
i 522633200009118006
i 51170219990111195X
i 45102119800321935X
q 20081011
q 17254862
i 511702196505046283
【输出样例】
2 2 18667936
【参考代码】
#include
using namespace std;
struct tid{
char type; //账号类型,识别联合变量储存哪个类型
union //省略类型名,更方便存取联合的成员
{
char idc[18]; //存储身份证号
long long qq; //存储QQ号
};
}; //定义struct类型
tid a[10001];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].type;
switch (a[i].type) //判断类型
{ case 'i':
for (int j=0; j<18; j++) cin>>a[i].idc[j];
break;
case 'q':
cin>>a[i].qq;
}
}
long long sum=0; int c=0; //用于计算QQ号平均值
int men=0,women=0; //用于计算男性、女性人数
for(int i=1;i<=n;i++){
if (a[i].type=='i')
{ if((a[i].idc[16]-'0')%2) men++;
else women++;
}
if (a[i].type=='q') sum+=a[i].qq,c++;
}
cout<<men<<' '<<women<<' '<<sum/c;
return 0;
}
//注意:union里面不能有空间不确定的数据结构类型,比如string。