网站建设推广咨询平台,工厂做网站,灵犀科技 网站建设,制作网站推广线性表
定义
一个最简单#xff0c;最基本的数据结构。一个线性表由多个相同类型的元素穿在一次#xff0c;并且每一个元素都一个前驱#xff08;前一个元素#xff09;和后继#xff08;后一个元素#xff09;。
线性表的类型
常见的类型#xff1a;数组、栈、队列…线性表
定义
一个最简单最基本的数据结构。一个线性表由多个相同类型的元素穿在一次并且每一个元素都一个前驱前一个元素和后继后一个元素。
线性表的类型
常见的类型数组、栈、队列、链表
这些不同数据结构的特性可以解决不同种类的问题
P3156 【深基15.例1】询问学号
题面
题目描述
有 n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号在 1 到 109 之间按进教室的顺序给出。上课了老师想知道第 i 个进入教室的同学的学号是什么最先进入教室的同学 i1询问次数不超过 105 次。
输入格式
第一行 2 个整数 n 和 m表示学生个数和询问次数。
第二行 n 个整数表示按顺序进入教室的学号。
第三行 m 个整数表示询问第几个进入教室的同学。
输出格式
输出 m 个整数表示答案用换行隔开。
输入输出样例
输入 #1
10 3
1 9 2 60 8 17 11 4 5 14
1 5 9输出 #1
1
8
5
题解
可以直接设计一个数组记录每个学生的学号并查询那m个询问即可。还有一种做法是使STL中的容器Vector又称可变长度数组为了避免空间开的太大儿出现程序性错误。我在介绍STL的一篇博客写到过vector的常用操作例如 vectorint v;
v.push_back(a);
v.size();
v.resize(n,m);
等等因此这道题可以一个一个把学号读入然后pushback进这个可变长度数组。
代码
#includeiostream
#includevector
using namespace std;int n,m,tmp;
int main(){vectorint stu;cinnm;for(int i0;in;i){cintmp;stu.push_back(tmp);}for(int i0;im;i){cintmp;coutstu[tmp-1]endl;}return 0;
}
P3613 【深基15.例2】寄包柜
题面
题目描述
超市里有 n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一第 i 个寄包柜有 ai(1≤ai≤105) 个格子不过我们并不知道各个 ai 的值。对于每个寄包柜格子编号从 1 开始一直到 ai。现在有 q(1≤q≤105) 次操作
1 i j k在第 i 个柜子的第 j 个格子存入物品 k(0≤k≤109)。当 k0 时说明清空该格子。2 i j查询第 i 个柜子的第 j 个格子中的物品是什么保证查询的柜子有存过东西。
已知超市里共计不会超过 107 个寄包格子ai 是确定然而未知的但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
输入格式
第一行 2 个整数 n 和 q寄包柜个数和询问次数。
接下来 q 个整数表示一次操作。
输出格式
对于查询操作时输出答案以换行隔开。
输入输出样例
输入 #1
5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1
输出 #1
118014
1
题解 代码 B3630 排队顺序
题面
题目描述
有 n(2≤n≤106) 个小朋友他们的编号分别从 1 到 n。现在他们排成了一个队伍每个小朋友只知道他后面一位小朋友的编号。现在每个小朋友把他后面是谁告诉你了同时你还知道排在队首的是哪位小朋友请你从前到后输出队列中每个小朋友的编号。
输入格式
第一行一个整数 n表示小朋友的人数。
第二行 n 个整数其中第 i 个数表示编号为 i 的小朋友后面的人的编号。如果这个数是 0则说明这个小朋友排在最后一个。
第三行一个整数 ℎ表示排在第一个的小朋友的编号。
输出格式
一行 n 个整数表示这个队伍从前到后所有小朋友的编号用空格隔开。
输入输出样例
输入 #1复制
6
4 6 0 2 3 5
1
输出 #1复制
1 4 2 6 5 3
题解
代码
