《洛谷深入浅出进阶篇》简单数据结构

发布时间：2023年12月17日

本篇文章内容如下，请耐心观看，将持续更新。

简单数组
简单栈
简单队列
简单链表
简单二叉树
简单集合
图的基本概念
二叉堆
线段树
树状数组与字典树
线段树进阶

简单数组：

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();
}

简单二叉树：

文章来源:https://blog.csdn.net/louisdlee/article/details/134994199
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

《洛谷深入浅出进阶篇》简单数据结构

本篇文章内容如下，请耐心观看，将持续更新。

简单数组

简单栈

简单队列

简单链表

简单二叉树

简单集合

图的基本概念

二叉堆

线段树

树状数组与字典树

线段树进阶

简单数组：

STL可变数组 vector

简单栈：

简单队列：

简单链表 ：

简单二叉树：

简单链表：