线性表
定义
一个最简单，最基本的数据结构。一个线性表由多个相同类型的元素穿在一次，并且每一个元素都一个前驱（前一个元素）和后继（后一个元素）。
线性表的类型
常见的类型：数组、栈、队列、链表
这些不同数据结构的特性可以解决不同种类的问题
P3156 【深基15.例1】询问学号
题面
题目描述
有 n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号（在 1 到 109 之间），按进教室的顺序给出。上课了，老师想知道第 i 个进入教室的同学的学号是什么（最先进入教室的同学 i=1），询问次数不超过 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的常用操作例如
vector<int> v;
v.push_back(a);
v.size();
v.resize(n,m);
等等，因此，这道题可以一个一个把学号读入然后pushback进这个可变长度数组。
代码
#include<iostream>
#include<vector>
using namespace std;
int n,m,tmp;
int main(){
vector<int> stu;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>tmp;
stu.push_back(tmp);
}
for(int i=0;i<m;i++){
cin>>tmp;
cout<<stu[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)。当 k=0 时说明清空该格子。 -
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复制文章来源：https://www.toymoban.com/news/detail-657582.html
6 4 6 0 2 3 5 1
输出 #1复制文章来源地址https://www.toymoban.com/news/detail-657582.html
1 4 2 6 5 3
题解
代码
到了这里，关于数据结构之线性表的类型运用Linear Lists: 数组，栈，队列，链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
