《洛谷深入浅出进阶篇》简单数据结构
本篇文章内容如下，请耐心观看，将持续更新。
-
简单数组
-
简单栈
-
简单队列
-
简单链表
-
简单二叉树
-
简单集合
-
图的基本概念
-
二叉堆
-
线段树
-
树状数组与字典树
-
线段树进阶
简单数组：
-
STL可变数组 vector
" 我们首先要知道这个容器有什么特性，然后它是咋创建的、然后要知道这个东西最常见的功能，访问，查找，删除，修改，添加……是如何实现的。再接着，我们尽可能了解一些这个容器的常见函数的使用，还要知道它的时间复杂度。那么这个容器，你就算大概了解了。"
vector 是一个“ 可变长度 ” 数组。 一般是数组，定义的时候需要同时定义长度。
有些时候，我们不知道应该定义多长，或者定义过长会出现浪费的情况
那么我们就希望 有一个弹性的数组，需要用多少就有多长。
vector 就是一个这样的东西
?“ 建立一个可变长度数组v，内部元素类型是int ， 该可变数组最开始有 n 个元素， 每个元素被初始化为 m 。如果省略m，那么这个可变数组有n个元素，每个元素初始化为0.”
vector<int>? v(n,m)"我们也可以省略上面的 （n，m），此时的 v 长度就是0。 “
vector<int > v“并且，v容器内的元素还可以是其他的数据类型。”?
vector<string>? v;vector<char> v;对于vector 数组的 访问 或 编辑 ，我们可以像普通数组一样使用方括号进行索引（也就是说下标这个概念是存在于vector中的），比如 v [1 0 ] ,就是访问下标为10的元素。
不过需要注意的是: 如果使用下标进行访问，那么需要注意vector 的长度是不是足够，否则就会造成越界。
其实，因为vector 是可变长的，所以如果空间可能会不够的话，我们可以实时地给它增长长度。
就可以用 push_back ( )? , 或者? resize ( ) 函数，进行增长。
然后要想知道这个数组的长度的话，我们就可以用 size（）函数。
vector <int > v ;
1、v.push_back(a);
2、v.resize(n,m);
3、v.size();1、v.push_back(a) 指的是 向容器里添入一个元素，添入成功后，自然v的长度也就变长了? 。
2、v.resize（n，m）指的是? “重新调整数组长度为n”? ，如果当前vector 的长度小于n ，那么他的长度在原来的基础上就会增加到n，而新增加的元素，就会被初始化为m。
倘若vector 的长度 大于n ，那么就会删除多余的部分。
3、v.size() 指的是 " 返回v数组的长度"。
来一道简单的例题，上手实践一下这个新容器吧?
P3156 【深基15.例1】询问学号 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P3156
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> arr;
int n,m;
cin >> n>>m;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
arr.push_back(temp);
}
for (int i = 0; i < m; i++)
{
int temp;
cin >> temp;
cout << arr[temp-1];
if(i!=m-1)cout<<endl;
}
}看到这里，我们想想还有什么没讲？
- 上面说了增删改查的第一种形式，就是使用数组下标，那么还有没有另一种方式呢？
- 上面介绍了一维vector ， 我们都知道数组也有二维，那么vector 有没有二维呢?
- vector 还有其他有用的函数吗？ 这些函数对比常规的静态数组有什么优势呢?
接下来的内容我们就围绕这些问题来讲述：
增删改查的第二种形式： 迭代器。
vector <int > v;
vector <int > :: iterator it;
vector <char > :: iterator ii; 定义一个迭代器 i t，这个迭代器只能指向 vector<int >。
定义一个迭代器 i i ，这个迭代器只能指向 vector<char >。
由上面的代码，我们足以看出一些东西了。
首先 迭代器一定是有对象的（悲，我没有 ），并且这个迭代器 是为一类容器服务的，不是为了某一个具体的容器。所以我们后续可能会有一些方法，使得这个迭代器变成某个具体容器的专门迭代器。
其次，迭代器的定义也太特么长了吧！！ （说不定存在某些东西可以让我们简写）
最后，迭代器肯定和一般的int，char 这种数据类型不一样，它肯定是一种特殊的数据类型，比如指针这种。所以使用它的时候，我们不能以看待常见的数据类型的眼光去看它……。
相信，再给一段代码，这段代码代表，遍历容器内所有的元素，你一定能解决上面的问题吧！喵
vector<int > v;
vector<int > :: iterator it;
for( it = v.begin() ; it != v.end() ; it++ ){
cout << *it<<' ' ;
}” 如果你是第一次看见， 你可能会说， 卧槽，这一坨东西是啥，为什么我每个字母都看得懂，连起来我就不知道是啥了 啊 呜呜呜 “ 。
别急别急，我们细细分析， 在上面我们说到，it 迭代器是为一类容器服务的（比如容器内部是int的元素算一类 ）? ?但是为啥? it 能用来遍历 v容器（一个具体的容器）啊？? ?噢！
因为我们让 it 等于了? v.begin() 这个东西。 所以it 就暂时为 v容器服务了。
我们还能知道，因为it是迭代器类型， 一个东西能直接给它赋值， 那么这俩玩意，一定是互通的，或者说，这俩是同一种类型 。??
哎哟卧槽，这岂不是说
v.begin( ) 应该就是 专属于 v的东西（因为它开头已经被打上了标记v
并且，v.begin( ) （我们可以看出他应该是个函数） 这个函数的返回值必然是 一个 迭代器类型的东西！！！。
bingo ！！恭喜你少年，你猜对了！！。
那么 v.end () 肯定跟 v.begin ( ) 是差不多的东西辣。
结合他俩的英文单词，再加上我说这串代码是遍历容器v，所以所以所以！！！
v.begin ( )? 返回的是一个指向 v容器开头的迭代器，
v.end( ) 返回的是指向v容器末尾的迭代器。
我们的临时工 it ，从v容器的开头，遍历到v容器的结尾， 这特么可不就是遍历吗！！！！
但是，你可能还有一个疑问，这和我们常规的数组遍历不一样啊，咋回事啊？
for ( int i=0 ;i< v.size() ;i ++ ) {
cout << v[i]<<' ';
}
vector<int > :: iterator it;
for ( it = v.begin() ;it!= v.end(); it++ )
cout<< *it<<' ';
}(为啥一个 是 i<v.size()? , 一个是 it != v.end(?) )
(为啥一个是 cout<< i? , 一个是cout<< *it? )
等等，华生，你发现了盲点！！！cout后面的内容，居然是输出 *it ， 那么岂不是说明，这个迭代器，在某些层面上和指针是一样的！！！
嗷嗷嗷嗷嗷，你彻底懂了， 所以 it 不能写成? it< v.end(） ，为啥，这特么是地址啊，只有等于或不等于的情况，没有大于小于的情况。
那么也就明白了， it ++ 是什么意思， 也就是指向下一个元素 地址。总之，这一方面，就是指针的内容。
好好好 ， 你已经彻底懂了迭代器是啥，也知道begin,end 这俩函数是啥，你已经掌握一大半了。
你也许会问，为啥，it ！= v.end() , end 难道不是最后一个元素吗？??
其实。。? end不是指最后一个元素，它指的是最后一个元素的再后面一个位置，这个位置是未知的，所以千万要小心，不能输出 *end。
然后，就剩最后一个问题了，二维的vector是咋样的呢？
首先，我先不告诉你二维的vector 是啥样的。我们不妨来想象一下吧！
对于一个这样的数组：
int a[10][10] ;?
我们都知道它可以表示成：
{ ………………} ，
{………………}，
…………
{………………}，
一共有是10 层，每一层都有 10个元素。
也就是说，如果这个数组是二维的，那么它的一维下标代表有多少层，二维下标代表这一层有多少个数字。（等等，我们为啥说是数字呢？因为，这个数组的数据类型是 int ）
好，那么我们参照二维普通数组的概念。
那么可变二维vector 我们可以猜测： 它的第一维表示有多少层，这个层数是不定长的，二维表示每一层有多少元素，这个元素也是不定个数的。
不等层数，每一层不定元素的初始化：?
vector< vector<int > > v;定层数，但是每一层元素不固定的初始化：（最常用）
vector< vector<int > > v（5）;定层数，定元素的初始化：
vector< vector<int > > v (5，vector<int>(4,0) );那么我们由彼及此，由于二维vector 的 第二维也是一个vector ，那么 v是一个vector ， v[i] 自然也是一个vector咯。
v[ 1 ].push_back(b), 就代表在第一层，添加一个元素；
看到这里你可能会想：那第一种不定层数，不定元素的 二维vector 应该怎么加入层数呢？
我们观察它的初始化，不难发现，最外层的vector 的元素的数据类型 也是 vector，所以要想增加层数，则我们只要push_back( )? vector类型就行了。
现在你已经知道 了二维vector ， 那么就来做一道题巩固一下吧！！！
传送门：P3613 【深基15.例2】寄包柜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3613
题解:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<cctype> #include<map> #include<set> #include<queue> #include<numeric> #include<iomanip> using namespace std; int n, q, i, j, k, ops; int main() { cin >> n >> q; vector< vector<int> > v(n+10); while (q--) { cin >> ops; if (ops == 1) { cin >> i >> j>>k; if (v[i].size() <= j) { v[i].resize(j + 1); } v[i][j]=k; } else { cin >> i >> j; cout << v[i][j] << endl; } } }
现在你已经大致了解了 简单vector 的用法。下面我们来介绍一些好用的vector 函数，这些函数可以给我们解题带来极大的遍历。（待更新中……）
简单栈：
“ 啥是栈啊？ ”
你可以把它想象成一个深坑。? 嗯。。没了，这就是栈。
你任意在这个坑里面放一些元素（元素不能融合！）
你能想到的任何对这些元素的操作，都是栈操作。（不要杠我
栈的最常见的操作就是，压入，取出。
你可以想象，我们将一些物品用1~n标号，逐个放入这个坑中。我们想将1取出，那么必然要将1上面的物品取出，要想取出1上面的物品，那就要取出1上面的上面的物品…………
直到这个物品上方为空（即没有任何物体）
我们可以发现，这样的坑，有个明显的特点” 后进先出，先进后出 “，”只能从一端进行增删的操作“。
于是，聪明的数学家们，将满足上面性质的东西，称作栈结构。
所以啊，我们便不必局限于是不是一个坑了。任何满足这些性质的东西，我们都可以将它抽象成一个栈结构。
对于一个栈结构，我们一般会对其进行以下的操作：
stack < int > s;
s. push（a）? 将a压入栈中
s.pop? （） 弹出栈顶元素
s.top? ? （）查询栈顶元素
s.size? ?（）查询栈内元素个数
s.empty （）查询栈是否为空我们再用一个例子来描述一下栈的简单操作流程：
假设现在有 1，2，3 三个数 ， 我们依次将其压入栈，然后压入之后，再一个一个取出来。
stack <int > s;
s.push(1);
s.push(2);
s.push(3);
cout<<s.top()<<endl;
s.pop();
cout<<s.top()<<endl;
s.pop();
cout<<s.top()<<endl;
s.pop()
输出结果： 3 2 1 在我们初步了解了栈的基本操作之后，我们就应该试图手写一个栈。
ps：（栈虽然直接用stl方便，但是如果我们不打开 O2优化的话，就会有一点慢。
在一些非常需要追求运行速度的情况下，往往需要自己手写栈。）
手写栈：
#include<iostream>
using namespace std;
const int MAXN = 1e5;
int stack[MAXN];
int p = 0; //栈顶指针
void push(int x) {
if (p >= MAXN) {
cout << "Stack overflow" << endl;
return;
}
p++;
stack[p] = x;
return;
}
void pop() {
if (p == 0) {
cout << "Stack is empty";
return;
}
p--;
}
int top() {
if (p == 0) {
cout << "Stack is empty";
return 0;
}
return stack[p];
}
int size() {
if (p == 0) {
cout << "Stack is empty";
return 0;
}
return p;
}
bool empty() {
if (p == 0)return true;
else return false;
}
好啦，现在你已经大概知道了栈是如何工作的。
那么我们就做几道题来巩固一下吧。
例题1、
Parentheses Balance - UVA 673 - Virtual Judgehttps://vjudge.net/problem/UVA-673
输入一个包含“()”和“[]”的括号序列，判断是否合法。 具体规则：
- 空串合法；
- 如果A和B合法，那么AB合法；
- 如果A合法(A)和[A]都合法
输入输出样例：
输入 #1复制3 ([]) (([()]))) ([()[]()])()输出 #1复制
Yes No Yes
#include<bits/stdc++.h>
using namespace std;
char reverse(char ch){
if(ch==')')return '(';
if(ch==']')return'[';
else return ' ';
}
int main(){
stack<char> s;
int sum;
cin>>sum;
cin.ignore();
string t;
while(sum--){
while(!s.empty())s.pop();
getline(cin,t);
for(int i=0;i<t.size();i++){
if(s.empty()){s.push(t[i]);continue;}
if(reverse(t[i])==s.top())s.pop();
else s.push(t[i]);
}
if(s.empty())cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}例题2、后缀表达式 - 洛谷1449??????https://www.luogu.com.cn/problem/P1449
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
using namespace std;
stack<int > S;
void todo(char ch,int first,int second) {
if (ch == '*')S.push(first * second);
else if (ch == '+')S.push(first + second);
else if (ch == '-')S.push(second - first);
else if (ch == '/')S.push(second / first);
return;
}
int main() {
string s;
getline(cin, s);
int first, second;
int t = 0;
for (int i = 0; i < s.size(); i++) {
while (isdigit(s[i])) {
t = t * 10 + s[i] - '0';
i++;
}
if (s[i] == '.') {
S.push(t);
t = 0;
continue;
}
else if (s[i] == '@')break;
else {
first = S.top();
S.pop();
second = S.top();
S.pop();
todo(s[i], first, second);
}
}
cout << S.top();
}
简单队列：
这玩意，我们需要解释吗？啥是队列，超市买东西排队这就是队列。一端付完钱直接走人，叫队头。
一端挑完东西，加入队列，叫队尾。
所以，一端进入一端出去，先进先出就是队列。
如果我们看到一道题目满足这样的性质，我们就可以用队列来模拟。
那么，对于这样的队列，我们有啥操作呢？其实和栈是差不多了。
- queue< int > q ;
- 入队 （加入队尾） q.push()
- 出队? ?(从队首出队）q.pop（）
- 查询队首 q. front()
- 查询队尾? q.back()
- 查询元素个数? q. size()
- 是否为空? q.empty ()?
这样光说，肯定是枯燥的，那么我们就列举一个生活中常见的例子吧。
超市排队：（编写一个程序模拟收银过程）
超市排队模拟器：
int queue[MAXN]; // 用数组模拟队列,MAXN 表示队伍一次性能加入的人数
int head=0; // 队头指针
int tail=0; // 队尾指针
有人挑完东西，加入正在付款的队伍：
void push(int x){
if( tail>MAXN ) cout<<" Queue overflow "<<endl;
else {
queue[tail]=x;
tail++;
}
}
队伍最前面的人已经买完了东西，现在要走人
void pop(){
if(head==tail){
cout<<"Queue is empty"<<endl;
}
else{
head++;
}
}
查询队伍最前面的人是谁
int front(){
if(head==tail){
cout<<"Queue is empty"<<endl;
}
else{
return queue[head];
}
查询队伍最后面的人是谁
int back(){
if(head=tail){
cout<<"Queue is empty"<<endl;
}
else{
return queue[tail-1];
}
查询队伍人数：
int size(){
return tail-head;
}
查询队伍是否为空：
bool empty(){
if(head==tail)return 1;
else return 0;
}
现在，你应该对队列的操作熟悉了吧？那下面来写一道经典的习题吧！！
P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1996ps(这道题可以优化成一个队列的写法，就是每次数到的数字整除m，先输出，再删除，，否则，先将数字加入队尾，然后再删除。
退出循环的条件就是这个队列为空
#include<bits/stdc++.h>
using namespace std;
queue<int > id;
queue<int > temp;
queue<int > out;
//先将所有的人加入到id队列
// 将id队列的人一个一个出队，出到 temp临时队列
// 每次当数到的数字能够整除m，此时的人出队，进入到out队列。
// 然后循环完了一遍，将temp队列重新赋值到id队列，再将temp队列清空
// 结束条件就是out队列的数量大于等于 n
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)id.push(i);
int count = 1;
while (out.size()<=n) {
if (out.size() >= n)break;
int len = id.size()+count-1;
for (; count <= len; count++) {
if (count % m == 0)out.push(id.front());
else temp.push(id.front());
id.pop();
}
while (!temp.empty()) {
id.push(temp.front());
temp.pop();
}
}
while (!out.empty()) {
cout << out.front() << ' ';
out.pop();
}
}简单链表 ：
啥是链表？链表是一种和上面我们讲过的栈，队列，数组 相似的线性的，储存元素排列顺序的表。
让我们再接触链表之前，先和之前一样从生活实际开始模拟。
假设n名同学排成一排，解散后，现在要求每个人重新排成原来的样子，但是没有人知道原来是怎么排的，好在每个同学都记得自己后面的第一个人是谁。利用这些信息，你能还原出初始的队列吗？
假如有4名同学编号从1~4，他们后面的同学分别是：4，3，0，2 (0代表后面无人）
(已经知道1号同学站在第一位）
不难写出代码：
int Next[MAXN];
for(int i=1;i<=MAXN;i++){
cin>>Next[i];
}
for(int i=1;i!=0;i=Next[i]){
cout<<i<<' ' ;
}从这个问题，我们不难知道链表具有怎样的性质：
如果你知道每个元素的前面后面是谁，那么你就可以恢复整个表的顺序。
也就是说，链表，其实就是一种储存了每个元素前驱和后继的表。
如此，我们就得到了链表的重要特性，利用这个特性，我们可以做什么呢？
下面通过另一个问题来回答这个问题。
有n名同学正在排队，但是来了一位恶霸（y号）插队到了x号的后面，其余的同学顺序不变，求，插队之后，队伍是什么样的顺序？
int Next[MAXN];
void insert(int x,int y) {
int temp = Next[x]; // 先储存x的后继
Next[x] = y; // x的后继为y
Next[y] = temp; // y的后继是原来x 的后继
}通过这样的方式，我们就可以快速地实现插入这一步骤了，即时数据量再大也不怕捏。
那么再来思考一下这个：
假如，x同学的后面一个同学忍不住，先离开了，那么现在的队列应该是什么顺序呢？
void restore(int x) {
Next[x] = Next[Next[x]];
}通过以上的两种方法，我们可以只要耗费O（1）的时间复杂度就完成一次维护。
这是单链表的使用方法，但其实上，我们有很多类型的链表需要学习：（目前只了解单双链表即可）
- 单链表（每一个结点记录自己的后继，只能单向移动）
- 双链表（每一个结点记录自己的前驱和后继，可以双向移动）
- 循环单链表（尾部的后继是头部）
- 循环双链表
- 块状链表
- 跳表
老规矩下面进行一个排队的模拟(假设队伍里最开始只有编号1这一个人）：
这是排队的程序应该有的功能
- ins_back(x,y); 将元素y插入到x的后面
- ins_bcak(x,y); 将元素y插入到x的前面
- ask_back(x)； 询问x的后继是谁
- ask_front(x);? 询问x的前驱是谁
- del(x)； 从列表中删除元素，不改变其他元素的先后顺序。
这题，我们就可以用双向链表来维护：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
using namespace std;
const int MAXN = 1e6 + 7;
struct node {
int pre,nex,val; // 前驱，后继，值
}a[MAXN] = {0};
int n, pls;//相对位置
int flag[MAXN]; //标记数组，标记是否存在
int index1[MAXN];//用来记录每个结点编号
void ins_pre(int x, int y) {
//首先找到x的结点编号
int now =
pls++; //新增一个编号给y用
a[pls].nex = now; // y的后缀等于 x的结点编号now
a[pls].val = y; // y的值等于y。
a[pls].pre = a[now].pre; // y的前驱是x原来的前驱
a[a[now].pre].nex = pls; // x原来的前驱的后继变成y的编号 pls
a[now].pre = pls; // x的前驱是pls。
index1[y] = pls;
}
//将y元素插在x 的后面
void ins_back(int x, int y) {
int now = index1[x];
pls++;
a[pls].pre = now; // 先把y的前驱改成x
a[pls].nex = a[now].nex;//再把y的后继改成x的后继
a[pls].val = y;//再把y的值附上
a[a[now].nex].pre = pls;//然后改变x的后继的前驱
a[now].nex = pls;//最后改变x的后继
index1[y] = pls;
}
//询问x的后继的值
int ask_back(int x) {
return a[a[index1[x]].nex].val;
// 先查询x的结点编号，然后返回x的后继的val，这里跳步了直接return
}
//查询x 的前驱的值
int ask_pre(int x) {
return a[a[index1[x]].pre].val;
}
//从链表中删除元素
void del(int x) {
int now = index1[x]; // 找到x的结点编号
a[a[now].pre].nex = a[now].nex;// 将x前驱的后继改成x的后继
a[a[now].nex].pre = a[now].pre;// 将x后继的前驱改成x的前驱
}
int main() {
a[0].val = 0;
a[0].pre = 0;
a[0].nex = 0;
index1[0] = 0;
ins_back(0,1);
}(如果数据过大，index1可能存不下那么多，那么可以用hash或map来优化）
相信看完前面，你对链表也已经有了一些理解，下面来几道简单的例题练练手吧！
例题1：
P1160 队列安排 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1160
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
struct node {
int pre,nex,val; // 前驱，后继，值
}a[MAXN] = {0};
int n, pls;//相对位置
int flag[MAXN]; //标记数组，标记是否存在
int index1[MAXN];//用来记录每个结点编号
void ins_left(int x, int y) {//把y插入到x的左边
int now =index1[x];
pls++;
a[pls].val = y;
a[pls].nex = now;
a[pls].pre = a[now].pre;
a[a[now].pre].nex=pls;
a[now].pre = pls;
index1[y] = pls;
}
void ins_right(int x, int y) {
int now = index1[x];
pls++;
a[pls].val = y;
a[pls].pre = now;
a[pls].nex = a[now].nex;
a[a[now].nex].pre = pls;
a[now].nex = pls;
index1[y] = pls;
}
void del(int x) {
int now = index1[x];
int Nex = a[now].nex;
int Pre = a[now].pre;
a[Nex].pre = Pre;
a[Pre].nex = Nex;
index1[x] = 0;
}
int main() {
cin >> n;
a[0].val = 0;
a[0].pre = 0;
a[0].nex = 0;
ins_right(0, 1);
for (int i = 2; i <= n; i++) {
int k, p;
cin >> k >> p;
if (p == 0) {
ins_left(k, i);
}
else ins_right(k, i);
}
int m;
cin >> m;
while (m--) {
int temp;
cin >> temp;
if (index1[temp])del(temp);
}
int now = a[0].nex;
while (now) {
cout << a[now].val<<' ';
now = a[now].nex;
}
}ps(虽然我没写注释，但是这道题和我们上面的模拟排队是几乎一样的，所以看懂一个就行 了。）
例题2：
P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1996
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
using namespace std;
const int MAXN = 1e6 + 7;
struct node {
int pre,nex,val; // 前驱，后继，值
node(int _pre=0, int _nex=0 , int _val=0 ) {
pre = _pre, nex = _nex, val = _val;
}
}a[MAXN] ;
int n, pls;//相对位置
int flag[MAXN]; //标记数组，标记是否存在
int index1[MAXN];//用来记录每个结点编号
void ins_pre(int x, int y) {
//首先找到x的结点编号
int now = index1[x];
pls++; //新增一个编号给y用
a[pls] = node(a[now].pre, now, y);
a[a[now].pre].nex = pls; // x原来的前驱的后继变成y的编号 pls
a[now].pre = pls; // x的前驱是pls。
index1[y] = pls;
}
//将y元素插在x 的后面
void ins_back(int x, int y) {
int now = index1[x];
pls++;
a[pls] = node(a[now].nex, now, y);
a[a[now].nex].pre = pls;//然后改变x的后继的前驱
a[now].nex = pls;//最后改变x的后继
index1[y] = pls;
}
//询问x的后继的值
int ask_back(int x) {
return a[a[index1[x]].nex].val;
// 先查询x的结点编号，然后返回x的后继的val，这里跳步了直接return
}
//查询x 的前驱的值
int ask_pre(int x) {
return a[a[index1[x]].pre].val;
}
//从链表中删除元素
void del(int x) {
int now = index1[x]; // 找到x的结点编号
int Nex = a[now].nex;
int Pre = a[now].pre;
a[Nex].pre = Pre;
a[Pre].nex = Nex;
index1[x] = 0;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
index1[i] = i;
a[i] = node(i - 1, i + 1, i);
}
//搞一个循环双链表。然后循环的次数大一点，一定是可以删除干净的。
//其实循环单链表好像也可以。
a[1] = node(n, 2, 1);
a[n] = node(n - 1, 1, n);
int m;
cin >> m;
int now = index1[1];
while (n--) {
for (int i = 1; i <= m; i++) {
if (i == m) {
cout << now << ' ';
del(now);
}
now = a[now].nex;
}
}
}好啦，上面是手写链表的过程，那么接下来我就介绍一下链表（stl）：list
下面给出链表的常用函数：
定义一个int类型的链表
list<int > a;?
我们可以用这样的方式来给链表初始化。
int arr[5] = {1,2,3} ; list<int > a(arr.arr+3 ) ；
返回链表的节点数量：
a.size();
定义一个迭代器：
list<int >:: iterator it ;
链表的开头，和末尾( 返回的是迭代器）
a.begin() ,? a.end() ；
在链表的开头或者末尾插入元素x
a.push_front (x)?
a.push_back(x) ;
在链表某一位置的前面插入元素x：
a.insert( it,x ) ;? it 表示这个位置的迭代器
在链表开头或结尾删除元素
a.pop_front () ,? a.pop_bcak();
删除链表某一位置的元素
a.erase(it)? it表示这一位置的迭代器
遍历整个链表
for( it=a.begin() ; it!=a.end() ; it++)?
有了上面的那些函数，我们就可以实现如下功能
- ins_back(x,y); 将元素y插入到x的后面
- ins_bcak(x,y); 将元素y插入到x的前面
- ask_back(x)； 询问x的后继是谁
- ask_front(x);? 询问x的前驱是谁
- del(x)； 从列表中删除元素，不改变其他元素的先后顺序。
const int MAXN = 1e6 + 7; list<int > a; list<int >::iterator index1[MAXN]; // 迭代器数组，用来代替find void ins_front(int x, int y) { //y插入x的前面 auto it = index1[x]; a.insert(it, y); index1[y] = --it; // y的迭代器就是it的前一个位置 } void ins_back(int x, int y) { //yc插入 x的后面 auto it = index1[x]; it++; a.insert(it, y); index1[y] = --it; } void del(int x) { //删除x if (index1[x] == a.end())return; auto it = index1[x]; a.erase(it); index1[x] = a.end(); } int ask_front(int x){ auto it=index1[x]; return *(--it); } int ask_back(int x){ auto it=index1[x]; return *(++it); } void print() { for (auto it = a.begin(); it != a.end(); it++) { cout << *it<<' '; } }
P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1996
#include<bit/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
list<int > a;
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a.push_back(i);
}
list<int >::iterator it, now;
it = a.begin();
int count = 0;
while (!a.empty()) {
count++;
now=it;
if (++it == a.end())it = a.begin();
if (count % m == 0) {
cout << *now << ' ';
a.erase(now);
}
}
}?P1160 队列安排 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1160
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
#include<list>
using namespace std;
const int MAXN = 1e6 + 7;
list<int > a;
list<int >::iterator index1[MAXN];
void ins_front(int x, int y) {
auto it = index1[x];
a.insert(it, y);
index1[y] = --it; // y的迭代器就是it的前一个位置
}
void ins_back(int x, int y) {
auto it = index1[x];
it++;
a.insert(it, y);
index1[y] = --it;
}
void del(int x) {
if (index1[x] == a.end())return;
auto it = index1[x];
a.erase(it);
index1[x] = a.end();
}
void print() {
for (auto it = a.begin(); it != a.end(); it++) {
cout << *it<<' ';
}
}
int main() {
int n;
cin >> n;
a.push_back(1);
index1[1] = a.begin();
for (int i = 2; i <= n; i++) {
int k, p;
cin >> k >> p;
if (p == 0)ins_front(k, i);
else ins_back(k,i);
}
int m;
cin >> m;
while (m--) {
int temp;
cin >> temp;
del(temp);
}
print();
}简单二叉树：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！