第3章〓数据结构基础

本章介绍基础的数据结构和一个比较简单的高级数据结构——并查集。它们是蓝桥杯软件赛的必考知识点。



很多计算机教材提到: 程序=数据结构+算法本书作者曾写过一句赠言: “以数据结构为弓，以算法为箭”。。数据结构是计算机存储、组织数据的方法。在常见的数据结构教材中一般包含数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）、散列表（Hash Table)等内容。数据结构分为线性表和非线性表两大类。数组、栈、队列、链表是线性表，其他是非线性表。


1. 线性数据结构概述

线性表有数组、链表、队列、栈，它们有一个共同的特征: 把同类型的数据按顺序一个接一个地串在一起。与非线性数据结构相比，线性表的存储和使用显得很简单。由于简单，很多高级操作线性表无法完成。

下面对线性表做一个概述，并比较它们的优缺点。

（1） 数组。数组是最简单的数据结构，它的逻辑结构形式和数据在物理内存上的存储形式完全一样。例如在C语言中定义一个整型数组int a［5］，系统会分配一个20字节的存储空间，而且这20字节的存储地址是连续的。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 int a［5］;
5 for (int i=0;i<5;i++)
6cout<<&a［i］<<" ";//打印5个整数的存储地址
7 return 0;
8}





在作者的计算机上运行，输出5个整数的存储地址: 

0x6dfed8 0x6dfedc 0x6dfee0 0x6dfee4 0x6dfee8



数组的优点如下: 

① 简单，容易理解，容易编程。

② 访问快捷，如果要定位到某个数据，只需要使用下标即可。例如a［0］是第1个数据，a［i］是第i-1个数据。虽然a［0］在物理上是第1个数据，但是在编程时有时从a［1］开始更符合逻辑。

③ 与某些应用场景直接对应。例如数列是一维数组，可以在一维数组上进行排序操作; 矩阵是二维数组，表示平面的坐标; 二维数组还可以用来存储图。

数组的缺点: 由于数组是连续存储的，中间不能中断，这导致删除和增加数据非常麻烦和耗时。例如要删除数组int a［1000］的第5个数据，只能使用覆盖的方法，从第6个数据开始，每个往前挪一个位置，需要挪动近1000次。增加数据也麻烦，例如要在第5个位置插入一个数据，只能把原来从第5个开始的数据逐个往后挪一位，空出第5个位置给新数据，也需要挪动近1000次。

（2） 链表。链表能克服数组的缺点，链表的插入和删除操作不需要挪动数据。简单地说，链表是“用指针串起来的数组”，链表的数据不是连续存放的，而是用指针串起来的。例如，删除链表的第3个数据，只要把原来连接第3个数据的指针断开，然后连接它前后的数据即可，不用挪动任何数据的存储位置，如图3.1所示。



图3.1删除第3个数据



链表的优点: 增加和删除数据很便捷。这个优点弥补了数组的缺点。

链表的缺点: 定位某个数据比较麻烦。例如要输出第500个数据，需要从链表头开始，沿着指针一步一步走，直到第500个。

链表和数组的优缺点正好相反，它们的应用场合不同，数组适合静态数据，链表适合动态数据。

链表如何编程实现？在常见的数据结构教材中，链表的数据节点是动态分配的，各节点之间用指针来连接。但是在算法竞赛中，如果手写链表，一般不用动态分配，而是用静态数组来模拟各种场景的手写链表参考: 《算法竞赛》，清华大学出版社，罗勇军、郭卫斌著，第3页的“1.1.2 静态链表”。。当然，除非有必要，一般不手写链表，而是用系统提供的链表，例如C++STL的list。

（3） 队列。队列是线性数据的一种使用方式，模拟现实世界的排队操作。例如排队购物，只能从队头离开队伍，新来的人只能排到队尾，不能插队。队列有一个出口和一个入口，出口是队头，入口是队尾。队列的编程实现可以用数组，也可以用链表。

队列这种数据结构无所谓优缺点，只有适合不适合。例如宽度优先搜索（BFS）就是基于队列的，用其他数据结构都不合适。

（4） 栈。栈也是线性数据的一种使用方式，模拟现实世界的单出入口。例如一管泡腾片，先放进去的泡腾片位于最底层，最后才能拿出来。栈的编程比队列更简单，同样可以用数组或链表实现。

栈有它的使用场合，例如递归使用栈来处理函数的自我调用过程。

2. 非线性数据结构概述

（1） 二叉树。二叉树是一种高度组织性、高效率的数据结构。例如在一棵有n个节点的满二叉树上定位某个数据，只需要走O(log2n)步就能找到这个数据; 插入和删除某个数据也只需要O(log2n)次操作。不过，如果二叉树的形态没有组织好，可能退化为链表，所以维持二叉树的平衡是一个重要的问题。在二叉树的基础上发展出了很多高级数据结构和算法。大多数高级数据结构，例如树状数组、线段树、树链剖分、平衡树、动态树等，都是基于二叉树的本作者曾拟过一句赠言: “二叉树累并快乐着，她有一大堆孩子，都是高级数据结构”。，可以说“高级数据结构≈基于二叉树的数据结构”。

（2） 哈希表（Hash Table，又称为散列表）。哈希表是一种“以空间换时间”的数据结构，是一种重要的数据组织方法，用起来简单、方便，在算法竞赛中很常见。

在使用哈希表时，用一个哈希函数计算出它的哈希值，这个哈希值直接对应到空间的某个位置（在大多数情况下，这个哈希值就是存储地址），当后面需要访问这个数据时，只需要再次使用哈希函数计算出哈希值就能直接定位到它的存储位置，所以访问速度取决于哈希函数的计算量，差不多就是O(1)。

哈希表的主要缺点： 不同的数据，计算出的哈希值可能相同，从而导致冲突。所以在使用哈希表时一般需要使用一个修正方法，判断是否产生了冲突。当然，更关键的是设计一个好的哈希函数，从根源上减少冲突的产生。设计哈希函数，一个重要的思想是“雪崩效应”，如果两个数据有一点不同，它们的哈希值就会差别很大，从而不容易冲突。

哈希表的空间效率和时间效率是矛盾的，使用的空间越大，越容易设计哈希函数。如果空间很小，再好的哈希函数也会产生冲突。在使用哈希表时，需要在空间和时间效率上取得平衡。





3.1数组与高精度
数组是最简单的数据结构。数组的一个应用是高精度，高精度算法就是大数的计算方法。例如两个整数的计算，Java和Python能直接计算任意大的数，而C++的最大数据类型是64位的long long，更大的数不能直接计算，需要用数组来模拟。例如两个200位的十进制数相加，定义int a［205］和int b［205］，a［i］和b［i］代表整数的第i位，a［0］是个位，a［1］是十位，a［2］是百位，等等。

在竞赛中经常用到很大的数组。建议不要用malloc()动态分配，因为动态分配需要多写代码而且容易出错。大数组应该定义为全局静态数组，而且不需要初始化为0，因为全局变量在编译时会自动初始化为全0。



1#include <bits/stdc++.h>
2using namespace std;
3int a［10000000］;//定义一个很大的全局数组，一千万个。自动初始化为0
4int main(){
5 cout << a［0］; //输出0
6 return 0;
7}





大数组不能定义在函数内部，可能会导致栈溢出错误。因为大多数编译器的局部变量是在用到时才分配，大小不能超过栈，而栈一般不会很大。下面这样做很可能会报错: 



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 int a［10000000］={0};//这样写大多数编译器会报错
5 cout << a［0］;//出错
6 return 0;
7}





另外，注意全局变量和局部变量的初值。全局变量如果没有赋值，在编译时会被自动初始化为0。在函数内部定义的局部变量，若需要初值为0，一定要初始化为0，否则初值不可预测。



1#include <bits/stdc++.h>
2using namespace std;
3int a;//全局变量，如果不赋值，自动初始化为0
4int c = 999;//赋值为999
5int main(){
6 int b;
7 cout << a <<endl; //输出0
8 cout << c <<endl; //输出999
9 cout << b <<endl; //由于b没有初始化，这里输出莫名奇妙的值
10 return 0;
11}





除了C语言的静态数组，还可以用C++的vector定义大数组，见3.2节的介绍。


C++能表示的最大整数类型是64位的long long，如果需要计算更大的数，需要使用“高精度”。在C++STL中没有直接进行大数计算的库，遇到大数计算，需要自己写代码。

虽然在算法竞赛中高精度题目很罕见，但是用高精度来熟悉数组的应用是很好的练习。

基本的“加、减、乘、除”这4种高精度计算，做法是模拟每一位的计算，并处理进位或借位。

注意数字的读取和存储。设整数a有1000位，因为数值太大，无法直接赋值给变量，所以不能按数字读入，只能按字符读入。可以用字符串string读入大数sa，然后转换为int a［］，一个字符sa［］存为一位数字a［］。注意存储的顺序，在读入的时候，字符串sa［0］是最高位，sa［n-1］是最低位; 但是在计算时习惯用a［0］表示最低位，a［n-1］表示最高位，所以需要把输入的字符串sa倒过来存到a［］中。

1. 高精度加法







 
例3.1A+B problem（高精）https://www.luogu.com.cn/problem/P1601



问题描述: 高精度加法，相当于 a+b problem，不用考虑负数。

输入: 分两行输入，a,b≤10500。

输出: 输出一行，代表a+b的值。


输入样例: 

22222222222222222222222222222

333333333333333333333333333333
输出样例: 

355555555555555555555555555555



简单地模拟按位加即可，注意处理进位。

把输入的数字存到字符串中，然后用add()求和。先把字符转换成数字，做完加法后再转换回字符。



1#include <bits/stdc++.h>
2using namespace std;

3char a［1005］,b［1005］;//加数和被加数，或者定义为char

4string add(string sa,string sb){
5 int lena=sa.size(),lenb=sb.size();
6 for(int i=0;i<lena;i++)

7a［lena-1-i］ = sa［i］-'0'; //把字符转换成数字然后翻转，使a［0］是最低位

8 for(int i=0;i<lenb;i++)
9b［lenb-1-i］ = sb［i］-'0';
10 int lmax = lena>lenb ? lena : lenb;
11 for(int i=0;i<lmax;i++) {
12a［i］ += b［i］;

13a［i+1］ += a［i］/10; //处理进位
14a［i］%=10;
15 }
16 if(a［lmax］) lmax++;//若最高位相加后也有进位，数字长度加1
17 string ans;
18 for(int i=lmax-1;i>=0;i--)//把数字转换成字符，然后翻转
19ans += a［i］+'0';
20 return ans;
21}
22int main(){
23 string sa,sb;
24 cin >> sa >> sb; 
25 cout << add(sa,sb);
26 return 0;
27}





2. 高精度减法







 
例3.2高精度减法https://www.luogu.com.cn/problem/P2142 



问题描述: 给定两个整数a、b（第二个数可能比第一个数大），求它们的差。

输入: 分两行输入，0<a,b≤1010086。

输出: 输出一行，代表a-b的值。


输入样例: 

5

3
输出样例: 

2



简单地模拟按位减即可，注意处理借位。

下面是C/C++代码。



1#include <bits/stdc++.h>
2using namespace std;
3char a［11000］,b［11000］;//被减数和减数
4string sub(string sa,string sb){
5 if(sa == sb) return "0";//特判: 两数字相等
6 bool neg = 0;//标记是否为负数

7 if(sa.size() < sb.size() || sa.size() == sb.size() && sa < sb)

8swap(sa, sb), neg = 1;//让a大于b

9 int lena=sa.size(),lenb=sb.size();

10 for(int i=0;i<lena;i++)//把字符转换成数字然后翻转，使a［0］是最低位

11a［lena-1-i］=sa［i］-'0';
12 for(int i=0;i<lenb;i++)
13b［lenb-1-i］=sb［i］-'0';
14 int lmax = lena;
15 for(int i=0;i<lmax;i++){
16a［i］ -= b［i］;

17if(a［i］<0){//处理借位
18a［i］+=10;
19a［i+1］--;
20}
21 }

22 while(!a［--lmax］ && lmax>0) ; //找到首位为0的位置,什么都不做

23 lmax++;
24 string ans;

25 for(int i=lmax-1;i>=0;i--)//把数字转换成字符，然后翻转
26ans += a［i］+'0';
27 if(neg) ans = "-" + ans;//检查是否为负数
28 return ans;
29}
30int main(){
31 string sa,sb; cin>>sa>>sb;
32 cout<<sub(sa,sb);
33 return 0;
34}





3. 高精度乘法







 
例3.3A*B Problemhttps://www.luogu.com.cn/problem/P1303



问题描述: 给出两个非负整数，求它们的乘积。

输入: 输入共两行，每行一个非负整数，不超过102000。

输出: 输出一个非负整数，表示乘积。


输入样例: 

2

3
输出样例: 

6



乘法模拟小学的竖式乘法操作，按位做乘法最后相加。例如87×99，计算过程如下: 

87×99

6372_63_

+72_



8613

计算结果用int c［］存储，首先计算出c［0］=7×9=63，c［1］=8×9+7×9=72+63=135，c［2］=8×9=72，然后处理进位，得到乘积8613。

下面是C/C++代码。注意第3行int c［］不能定义为char c［］，例如上面例子中c［1］=135，超出了char的范围。



1#include <bits/stdc++.h>
2using namespace std;
3int a［2005］, b［2005］, c［4005］;//c = a*b
4string mul(string sa,string sb){
5 if(sa=="0"||sb=="0")return "0";
6 int lena=sa.size(),lenb=sb.size();
7 for(int i=0;i<lena;i++)a［lena-i］=sa［i］-'0'; 
8 for(int i=0;i<lenb;i++)b［lenb-i］=sb［i］-'0';
9 for(int i=1;i<=lena;i++)
10for(int j=1;j<=lenb;j++)
11c［i+j-1］ += a［i］*b［j］;
12 for(int i=1;i<=lena+lenb;i++) 
13c［i+1］+=c［i］/10,c［i］%=10;
14 string ans;
15 if(c［lena+lenb］)
16 ans += c［lena+lenb］+'0';
17 for(int i=lena+lenb-1;i>=1;i--) 
18 ans += c［i］+'0';//倒过来,把c的高位放在ans的前面
19 return ans;
20}
21int main(){
22 string sa,sb;
23 cin >> sa >> sb;
24 cout << mul(sa,sb);
25 return 0;
26}





4. 高精度除法







 
例3.4A/B Problemhttps://www.luogu.com.cn/problem/P1480



问题描述: 给出两个整数a和b，求它们的商。

输入: 输入共两行，第一行是被除数，第二行是除数。0<a≤105000，0<b≤109。

输出: 商的整数部分。


输入样例: 

5

3
输出样例: 

1



本题的被除数a是大数，除数b很小，情况比较简单。下面的代码模拟了除法的计算。

另外还有一种做法，即用减法求除法。a除以b，转化为a连续减去b，减了多少次就是商，最后不够减的是余数。



1#include <bits/stdc++.h>
2using namespace std;
3long long a［10001］,b,c［10001］;//被除数、除数、商
4int main(){
5 string sa;
6 cin >> sa >> b;//读被除数、除数
7 int len=sa.size();//被除数的位数
8 for (int i=1;i<=len;i++)
9 a［i］=sa［i-1］-'0';//将被除数一位一位放入a数组
10 long long d = 0;//余数

11 for (int i=1;i<=len;i++) {//被除数一位一位除以除数，若不够除，借位

12c［i］ = (d*10+a［i］)/b;
13d = (d*10+a［i］)%b;
14 }
15 int lenc = 1;//商的位数
16 while (c［lenc］==0 && lenc<len) lenc++;//删除前导0
17 for (int i=lenc;i<=len;i++) cout <<c［i］;//输出结果
18 return 0;
19}









3.2STL概述
刚参加算法竞赛学习的新同学常听说C++有一种特别神奇的工具——标准模板库（Standard Template Library,STL）。据说STL封装了算法竞赛用到的数据结构和算法，在做题时使用它就行了，不用管它具体如何实现，能大大降低编码的难度，在做竞赛题时无往不胜。

在很多场合下，这个说法是有道理的。例如在需要用队列时，虽然自己写代码实现队列也不难，但是如果直接用STL queue，不用自己编码和管理队列，代码既简短又可靠，节省的时间可以去做其他题目，从而占据先机。在有些情况下必须使用STL，例如优先队列，如果自己写代码非常麻烦，而直接使用STL priority_queue极为简单。所以参加C/C++组的算法竞赛一定要学STL，如果不用STL，竞赛成绩会大受影响。

虽然STL在算法竞赛中必不可少，但是不要太夸大STL的作用，它并不是算法竞赛的全部，只是一小部分。在使用STL之前，也需要掌握有关知识点的原理并自己手写代码实现，以了解原理、掌握思路，这些原理和思路可以帮助大家提高算法思维，并应用到算法题目中。

在介绍C++STL之前，先说明C++的版本问题。C++在1985年诞生，ISO（国际标准化组织）发布过多个正式标准，常见的有C++98、C++11、C++14、C++20等。这些标准除了规定C++的语法、语言特性，还规定了C++内置库的实现规范，即C++标准库https://zh.cppreference.com/w/cpp/standard_library（C++ Standard Library）。标准库提供了可以在标准C++中使用的各种功能，例如输入/输出、基本数据结构、内存管理、诊断、通用工具库等。掌握标准库是成为C++程序员的基本功。

STL是C++标准库的一部分，包含了一些通用的数据结构和算法。STL有很多组件这个页面列出了STL的所有组件: https://en.cppreference.com/w/cpp，在竞赛中常用的有Strings library、迭代器（Iterators library）、容器（Containers library）、算法（Algorithms library)等。

STL功能强大，庞大复杂，全部学习很困难，这常让算法竞赛的初学者感到困惑。其实不用担心，算法竞赛只用到STL的一小部分，掌握这部分即可。具体来说，数据结构有vector、string、list、queue、stack、set、map、bitset等，算法函数有max、min、swap、sort、lower_bound、upper_bound、next_permutation、nth_element、unique、binary_search等。本书将在有关章节介绍它们，读者也可以在阅读代码遇到这些概念的时候自己总结。

在代码中引用C++的标准库时，用万能头文件即可，不用逐一列出每个头文件。

#include <bits/stdc++.h>//万能头文件



这个万能头文件包含了每个标准库，几乎所有编译器都支持。蓝桥杯使用的编译器也支持它，所以大家不用担心。

3.2.1String库

在算法竞赛中，字符串处理是极为常见的考点。虽然C语言也有字符串操作，但是只能通过定义字符串数组，自己编码实现字符串运算，相当麻烦。用STL的Strings libraryhttps://en.cppreference.com/w/cpp/string/basic_string提供的字符串处理函数，可以轻松、简便地处理字符串的计算。可以说，如果在竞赛时不用string，成绩会大受影响。

表3.1列出了常用的String函数。



表3.1常用的String函数





函数
功能
length()
返回字符串的长度
size()
返回字符串的长度
push_back()
在字符串尾部添加一个字符
append()
在字符串尾部添加一个字符串
find(str，pos)
查找str在pos（含）之后第一次出现的位置，若不写pos，默认为pos=0。如果找不到，返回 -1，注意需要强制转换为int型才能输出-1
substr(pos，len)
返回从pos位置开始截取最多len个字符组成的字符串，如果从pos开始的子串的长度不足len，则截取这个子串
insert(index,count,str)
在index处连续插入count次字符串str
insert(index,str)
在index处插入字符串str
erase(index,count)
将字符串从index位置开始（含）的count个字符删除，若不传参给count，则表示删去index位置及以后的所有字符
replace(pos,count,str)
把从pos位置开始count个字符的子串替换为str
replace(first,last,str)
把以first开始（含）、last结束（不含）的子串替换为str，其中first和last均为迭代器
empty()
判断字符串是否为空，如果为空返回1，不空返回0


下面给出例子。注意第18行和第52~56行，string重载了符号+、==、<、>，可以直接用于计算。

特别是字符串的比较，请特别注意。两个string变量，按它们的字典序进行比较。例如"bcd">"abc"。容易让人误解的是两个字符串长度不一样时的情况，例如“123”和“99”，按字符串比较，"123"<"99"，但按数字比较是123>99，两种比较的结果不同。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4//定义、初始化、赋值
5 string s1;//定义
6 string s2="bcd";//定义并赋值
7 s2="efg";//重新赋值
8 cout<<s2<<endl;//输出：efg
9 string s("abc");//定义并初始化
10 string s3(s);//复制
11//长度
12 cout<<s.length()<<endl;//或者：s.size()输出：3


13//遍历

14 for (int i=0; i<s.size(); i++) cout<<s［i］; cout<<endl; //输出：abc
15//添加，合并字符串

16 s.push_back('d');cout<<s<<endl; //在尾部添加字符。输出：abcd
17 s.append("efg"); cout<<s<<endl; //在尾部添加字符串。输出：abcdefg

18 s=s+'h'; s+='i'; cout<<s<<endl;
19//用重载的 + 在尾部添加字符。输出：abcdefghi
20 s=s+"jk"; s+="lmnabc"; s="xyz"+s; cout<<s<<endl;
21//输出：xyzabcdefghijklmnabc
22 string s4="uvw";
23 cout<<s+s4<<endl; //合并字符串。输出：xyzabcdefghijklmnabcuvw
24//查找字符和字符串
25 cout<<"pos of b=" <<s.find('b')<<endl;
26//查字符第一次出现的位置。输出：pos of b=4
27 cout<<"pos of ef="<<s.find('ef')<<endl;
28//查字符串第一次出现的位置。输出：pos of ef=8
29 cout<<"pos of ab="<<s.find('ab',5)<< endl;
30//从s［5］开始找字符串第一次出现的位置。输出：pos of ab=18
31 cout<<"pos of hello="<<(int)s.find('hello')<< endl;
32//没找到的返回值是-1，需要强制转换为int型。输出：pos of hello=-1
33//截取字符串
34 cout<<s.substr(3, 5)<<endl;
35//从s［3］开始截取5个字符构成的字符串。输出：abcde
36 cout<<s.insert(4,"opq")<<endl;


37//从s［4］开始插入字符串。输出：xyzaopqbcdefghijklmnabc
38//删除、替换
39 cout<<s.erase(10,2)<<endl;
40//从s［10］开始删除两个字符。输出：xyzaopqbcdghijklmnabc
41 cout<<s.erase(10)<<endl;
42//从s［10］开始删除后面的所有字符。输出：xyzaopqbcd
43 cout<<s.replace(2,3,"1234")<<endl;
44//把从s［2］开始的3个字符替换为"1234"。输出：xy1234pqbcd
45 cout<<s.replace(s.begin()+7,s.begin()+9,"5678")<<endl;
46//把s［7］~s［8］替换为"1234"。输出：xy1234p5678cd
47//清理、判断

48 cout<<s.empty()<<endl;//判断是否为空，不空返回0，空返回1。输出：0
49 s.clear();//清空
50 cout<<s.empty()<<endl;//输出：1
51//比较
52 string s5="abc";string s6="abc"; string s7="bc";
53 if(s5 == s6) cout << "=="<< endl;
54 if(s5 < s7)cout << "<" <<endl;
55 if(s5 > s7)cout << ">" <<endl;
56 if(s5 != s7) cout << "!=" <<endl;
57 return 0;
58}





下面是一道简单字符串题。






 
例3.5烬寂海之谜lanqiaoOJ 4050 



问题描述: 给定一个字符串S，以及若干个模式串P，统计每一个模式串在主串中出现的次数。

输入: 第一行一个字符串S，表示主串，只包含小写英文字母。第二行一个整数n，表示有n个模式串。接下来n行，每行一个字符串，表示一个模式串P，只包含小写英文字母。

输出: 输出n行，每行一个整数，表示对应模式串在主串中出现的次数。


输入样例: 

bluemooninthedarkmoon

3

moon

blue

dark
输出样例: 

2

1

1
评测用例规模与约定： 主串S的长度≤105，模式串的数量n≤100，模式串P的长度≤1000。


由于测试数据小，可以直接暴力比较。对每个P，逐一遍历S的字符，对比P是否出现，然后统计出现的次数。下面的代码用到string的length()和substr()函数。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 string s;
5 int n; 
6 cin >> s >> n;
7 while (n--){


8string p;
9cin >> p;
10int cnt = 0;
11for (int i = 0; i < s.length() - p.length() + 1; i++)//遍历S
12if (p == s.substr(i, p.length()))//查询P是否在S中出现
13cnt++;
14cout << cnt << endl;
15 }
16 return 0;
17}





【练习题】

简单的字符串入门题字符串入门题大多逻辑简单，用杂题的思路和模拟法实现即可，适合初学者练习string和提高编码能力。不过，作为知识点出现的字符串算法很难。字符串算法有进制哈希、Manacher、KMP、字典树、回文树、AC自动机、后缀树、后缀数组、后缀自动机等，都是中级和高级知识点。参考《算法竞赛》，清华大学出版社，罗勇军、郭卫斌著，第549页的“第9章字符串”。很多，大家请练习以下链接的题目。

洛谷的字符串入门题: https://www.luogu.com.cn/problem/list?tag=357

lanqiaoOJ的字符串题: https://www.lanqiao.cn/problems/?first_category_id=1&tags=字符串

NewOJ的字符串题: http://oj.ecustacm.cn/problemset.php?search=字符串

3.2.2迭代器

在使用STL容器时，需要通过迭代器（iteratorhttps://en.cppreference.com/w/cpp/iterator）来访问元素。迭代器变量可以看作一个指针，指向容器中某个元素所在的位置，然后做读取或写入数据的操作。

迭代器变量的定义，例如: 

vector<int>::iterator it;  //vector迭代器变量it，vector中的元素是int型

set<char>::iterator it;     //set迭代器变量it，vector中的元素是char型



迭代器主要支持两个运算符，其用法和C语言的指针差不多: 

（1） 自增，符号“++”，用来移动迭代器,有++it、it++两种写法,推荐使用++it，它的效率更高。注意不能把it加上一个偏移量，例如it=it+5，这样是错的，因为it和5的类型不同。

（2） 解引用，单目运算符“*”，用来获取指向的元素。例如*it是it指向的元素的值。

在后面介绍各种容器的时候将举例说明迭代器如何使用。下面先用vector容器说明迭代器的简单应用。

第5行定义了迭代器it，它指向vector<int>a的元素，第6行的*it是it当前指向元素的值。

由于迭代器的定义写起来有点麻烦，一般用auto关键字替代它。例如第8行，用auto替代vector<int>::iterator，非常简洁。数组也可以用更简单的方式遍历，例如第11、14行。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){



4 vector<int> a{5,7,3,64,23};//定义和初始化一个vector数组

5 for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)

6cout << *it << " ";//通过迭代器访问，输出：5 7 3 64 23
7 cout <<endl;

8 for (auto it = a.begin(); it != a.end(); ++it) //用auto取代迭代器

9cout << *it << " ";//输出：5 7 3 64 23
10 cout <<endl;
11 for (auto i : a)cout << i << " "; //直接遍历并输出：5 7 3 64 23
12 cout <<endl;
13 int b［］ = {5,7,3,64,23};//普通数组
14 for (auto i : b)cout << i << " "; //直接遍历并输出：5 7 3 64 23
15return 0;
16}





3.2.3容器概述

容器库（Containers library本节内容引用自https://en.cppreference.com/w/cpp/container）是一些通用的类模板与算法的汇集，允许程序员简单地实现如队列、链表、栈这样的常见数据结构。

在C++11之前有两类容器: 序列容器（Sequence containers）、关联容器（associative containers）。在C++11之后增加了无序关联容器（unordered associative containers）。

（1） 序列容器，实现能按顺序访问的数据结构。下面是一些序列容器。

array(C++11): 静态数组。

vector: 动态数组。蓝桥杯参赛必须掌握。

deque: 双端队列。蓝桥杯参赛常用。

forward_list(C++11): 单链表。

list: 双链表。蓝桥杯参赛必须掌握。

使用序列容器，可以实现容器适配器为帮助大家理解什么是适配器adapter，可以用电源插头适配器打比方。如果计算机上的电源线插头是两头的，但是插座是3头的，那么可以用一个适配器把两头转换成3头。也就是说，适配器只是一个接口转换头。。容器适配器封装了序列容器，提供了更多的功能。常见的容器适配器如下。

stack: 提供栈的功能，用deque实现。蓝桥杯参赛必须掌握。

queue: 提供队列的功能，用deque实现。蓝桥杯参赛必须掌握。

priority_queue: 提供优先级队列的功能，用vector容器存储数据，在vector上用堆进行计算。蓝桥杯参赛必须掌握。

（2） 关联容器，实现能快速查找的有序数据结构，计算复杂度为O(log2n)。下面是一些关联容器。

set: 键的集合，按照键排序，键是唯一的。蓝桥杯参赛必须掌握。

map: 键值对的集合，按照键排序，键是唯一的。蓝桥杯参赛必须掌握。

multiset: 键的集合，按照键排序，键不是唯一的，允许多个键有等价的值。

multimap: 键值对的集合，按照键排序，键不是唯一的，允许多个键有等价的值。

（3） 无序关联容器(从C++11起)，提供能快速查找的无序（散列）数据结构，计算复杂度平均为O(1)，最坏情况为O(n)。下面是一些无序关联容器。

unordered_set: 键的集合，按照键生成散列，键是唯一的。

unordered_map: 键值对的集合，按照键生成散列，键是唯一的。

unordered_multiset: 键的集合，按照键生成散列，键不是唯一的，允许多个键有等价的值。

unordered_multimap: 键值对的集合，按照键生成散列，键不是唯一的，允许多个键有等价的值。

本章后面几节将介绍vector、list、queue、priority_queue、stack、set、map，这是算法竞赛常用的容器。大家一定要掌握和应用它们，如果不用它们而自己实现相关功能，编码量很大，甚至无法编码，导致参赛失败。

3.2.4vector

在“3.1数组与高精度”中提到，算法竞赛中使用全局静态数组既简单又方便，和静态数组差不多简单、方便的是STL的vector容器，而且它还有一些高级功能。

vector是一个顺序容器（Sequence Container），可以简单地认为vector是一个能够存放任意类型的动态数组。和普通数组一样，在vector的末尾添加和删除元素很快，但是在中间插入和删除元素很慢。

vector的常见操作如表3.2所示。



表3.2vector的常见操作



操作
说明
push_back()
在末尾添加一个新元素，容器的大小加1
pop_back()
删除最后一个元素，容器的大小减1
insert()
在指定位置的元素前插入新元素
erase()
删除一个元素或一段元素
clear()
清空vector，容器的大小为0
front()
访问第一个元素
back()
访问最后一个元素
begin()
返回指向第一个元素的迭代器
end()
返回指向最后一个元素的迭代器
size()
返回vector中元素的数量
resize()
调整容器的大小


vector的迭代器可以使用auto关键字自动获取变量的类型。

下面是一些例子。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 vector<int> a;//初始化一个size为0的vector
5 a.insert(a.begin(), 4, 2);//在a开始位置处插入4个2
6 //下面的4个for是4种遍历方法
7 for (int i=0;i<a.size();i++)//通过下标访问，输出 2 2 2 2

8cout << a［i］<< ' '; cout <<"＼n";
9 for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)

10cout << *it << " "; cout <<"＼n";//通过迭代器访问
11 for (auto it = a.begin(); it != a.end(); ++it) //用auto获得迭代器
12cout << *it << " "; cout <<"＼n";



13 for (auto i : a)//直接访问
14cout << i << " ";  cout <<"＼n";
15 a.insert(a.begin()+1,9);//在a［1］处插入9， a = {2 9 2 2 2}
16 a.insert(a.begin()+2,2,5);//在a［2］处插入两个5，a = {2 9 5 5 2 2 2}
17 a.resize(3);//改变a的大小。a = {2 9 5}
18 vector<int> c(a);//复制a到c
19 vector<int> b;

20 b.insert(b.begin(), a.begin(), a.begin()+3); //将a的前3个数复制到b

21 //下面演示二维vector

22 vector<vector <char>> ch(2,vector<char>(3,'#'));//2行3列

23 for (int i=0;i<2;i++)//2行
24for (int j=0;j<3;j++)//3列
25cout << ch［i］［j］;
26 //下面演示用vector存结构体
27 struct point{ int x,y;};
28 vector <point> PP;
29 for (int i=0;i<3;i++){//赋值
30point t; t.x=i; t.y=i;
31PP.push_back(t);
32 }
33 for (int i=0;i<PP.size();i++) //输出

34cout << PP［i］.x << " " << PP［i］.y << "＼n";
35 auto it=PP.begin(); //等同于：vector<point>::iterator it=PP.begin();
36 for (;it!=PP.end();++it) cout << it->x <<" " << it->y<<"＼n";
37 return 0;
38}





3.2.5算法函数概述

STL算法库https://zh.cppreference.com/w/cpp/algorithm提供了大量的实用函数（例如查找、排序、计数等）。STL把算法函数分为以下几类：

（1） 不修改序列的操作，有批量操作、搜索操作、折叠操作。例如搜索函数find(first，last，value)，用于搜索［first，last)区间内是否有value。

（2） 修改序列的操作，有复制操作、交换操作、变换操作、生成操作、移除操作、顺序变更操作、采样操作。

（3） 排序和相关操作，有划分操作、排序操作、二分搜索操作（在已划分范围上）、集合操作（在已排序范围上）、归并操作（在已排序范围上）、堆操作、最大/最小操作、字典序比较操作、排列操作。

（4） 数值运算。

（5） 在未初始化内存上的操作。

下面简要介绍一些函数，它们在算法竞赛中很常用，如表3.3所示。



表3.3一些常用函数




函数
功能
find(a.begin(),a.end(),value)
顺序查找，value 为需要查找的值
reverse(a.begin(),a.end())
翻转数组、字符串
sort(a.begin(),a.end(),cmp)
排序，cmp 为自定义的比较函数
unique(first，last)
去除容器中相邻的重复元素，所以一般需要先排序，然后用unique去重。返回值为指向去重后最后一个不同元素的迭代器。注意原容器大小不变，末尾的重复元素可以用erase()删除
nth_element(a.begin(),
a.begin()+mid，a.end(),cmp)
按指定范围进行分类，找出序列中第 n 大的元素，使其左边均为小于它的数，右边均为大于它的数。该函数一般用于求第k小的数
binary_search(a.begin(),
a.end(),value)
在已经排好序的序列上做二分查找，需要先用sort()排序。value为需要查找的值，如果找到，返回true，否则返回false
lower_bound(a.begin(),
a.end(),x)
在一个有序序列中进行二分查找，返回指向第一个大于或等于x的元素的位置。如果不存在这样的元素，则返回尾迭代器
upper_bound(a.begin(),
a.end(),x)
在一个有序序列中进行二分查找，返回指向第一个大于x的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器
next_permutation(a.begin(),a.end())
将当前排列更改为全排列中的下一个排列。如果当前排列已经是全排列中的最后一个排列，该函数返回false，并将排列更改为全排列中的第一个排列 
prev_permutation()
将当前排列更改为全排列中的上一个排列，用法与 next_permutation（）相同
max()、min()
查找最大、最小值
swap()
交换两个元素的值


下面给出例子。为了方便读者理解，数列a［］分别用vector和数组定义，然后用各种函数操作它。

（1） 用vector定义数列a，函数用迭代器访问。



1#include <bits/stdc++.h>
2using namespace std;
3vector<int> a {23,5,36,4,8,7,5,23};
4void out(){
5 for(int i=0;i<a.size();i++)
6 cout << a［i］ << " ";
7 cout<<endl;
8}
9int main(){
10 auto it=find(a.begin(), a.end(), 5);
11 if(it != a.end()) cout<<"yes"<<endl;//找到了。输出：yes
12 else cout<<"no"<<endl;//没找到
13 nth_element(a.begin(),a.begin()+4,a.end()); 
14out();//输出：5 4 5 7 8 23 36 23


15 //下标为4，也就是第5个数放在正确的位置，即求的是第5小的数

16 cout <<"第5小："<< a［4］ << endl;//输出为第5小：8
17 unique(a.begin(),a.end()); out();//输出：5 4 5 7 8 23 36 23
18 sort(a.begin(),a.end()); out();//输出：4 5 5 7 8 23 23 36
19 auto last = unique(a.begin(),a.end());
20out();//输出：4 5 7 8 23 36 23 36
21 a.erase(last,a.end());//删除末尾的重复元素
22 out();//输出：4 5 7 8 23 36
23 it=lower_bound(a.begin(), a.end(),11);
24 if(it != a.end()) cout<<*it<<endl;//输出：23
25 it=upper_bound(a.begin(), a.end(),5);
26 if(it != a.end()) cout<<*it<<endl;//输出：7




27 if(binary_search(a.begin(), a.end(),23)) 
28cout <<"yes1"<<endl;//输出：yes1
29 else cout <<"no1"<<endl;
30 reverse(a.begin(), a.end()); 
31out();//输出：36 23 8 7 5 4
32 vector<int> b {2,5,7,4,5};
33 do {
34for(int i = 1; i < 4; i++) cout << b［i］ << " ";
35cout << endl;//输出：5 7 4 ;7 4 5 ;7 5 4 ;
36 } while (next_permutation(b.begin()+1, b.begin()+4));//从{5,7,4}开始的全排列
37 return 0;
38}




（2） 用数组定义数列a。



1#include <bits/stdc++.h>
2using namespace std;
3int a［］ = {23,5,36,4,8,7,5,23};
4int n = 8;
5void out(){
6 for(int i=0;i<n;i++)
7cout << a［i］ << " ";
8 cout<<endl;
9}
10int main(){
11 int k = find(a, a + n, 5) - a;

12 if(k !=n) cout<<"yes"<<endl; //找到了，输出：yes
13 else cout<<"no"<<endl;//没找到
14 nth_element(a, a + 4, a + n); out(); //输出：5 4 5 7 8 23 36 23

15 //下标为4，也就是第5个数放在正确的位置，即求的是第5小的数

16 cout <<"第5小："<< a［4］ << endl;//输出为第5小：8
17 sort(a, a + n); out();//输出：4 5 5 7 8 23 23 36
18 n = unique(a, a + n)-a;//n：更新去重后a的元素数量
19 out();//输出：4 5 7 8 23 36
20 k=lower_bound(a, a + n, 11) - a;
21 if(k !=n) cout<<a［k］<<endl;//输出：23
22 k=upper_bound(a, a + n, 5)-a;
23 if(k !=n) cout<<a［k］<<endl;//输出：7

24 if(binary_search(a, a + n, 23)) cout <<"yes1"<<endl;//输出：yes1

25 else cout <<"no1"<<endl;
26 reverse(a, a + n); out();//输出：36 23 8 7 5 4
27 int b［］ = {2,5,7,4,5};
28 do {

29for(int i = 1; i < 4; i++) cout << b［i］ << " ";

30cout << ";";//输出：5 7 4 ;7 4 5 ;7 5 4 ;

31 } while(next_permutation(b + 1, b + 4));//从{5,7,4}开始的全排列
32 return 0;
33}





3.2.6set和map

STL的顺序容器有vector、queue、list、string等，它们能够快速地顺序访问元素。关联容器有set、map等。

顺序容器和关联容器的区别如下: 

（1） 访问方式。关联容器中的元素按关键字来保存和访问; 顺序容器中的元素按它们在容器中的位置来顺序保存和访问。

（2） 操作。关联容器不支持顺序容器的与位置相关的操作，因为关联容器中的元素是根据关键字存储的，这些操作对关联容器没有意义。关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。

（3） 应用场景。关联容器支持高效的关键字查找和访问。map中的元素是键值（keyvalue）对，键起到索引的作用，值表示与索引相关联的数据。在set中每个元素只包含一个关键字，set 支持高效的关键字查询操作，检查一个关键字是否在set中。

1. set

set容器有4种: ①set，容器内只保存关键字; ②multiset，关键字可以重复出现的set; ③unordered_set，用哈希函数组织的set; ④unordered_multiset，用哈希函数组织的set，关键字可以重复出现。

下面是set的特点: 

（1） 每个元素的键值都唯一，不允许两个元素有相同的键值。这使得set有去重的功能: 在向set变量插入相同的数据时只会保留一个。

（2） 所有元素都会根据元素的键值自动排序，默认从小到大。如果要从大到小，需要加上greater，例如“set<int，greater<int>>s1;”。

（3） set中的元素不像map那样可以同时拥有实值(value)和键值(key)，只能存储键，是单纯的键的集合。

（4） set 中元素的值不能直接被改变。

（5） set支持大部分的map操作，但是set不支持下标操作。

sethttps://en.cppreference.com/w/cpp/container/set的常见操作如表3.4所示。



表3.4set的常见操作



操作说明

begin()
返回指向第一个元素的迭代器
end()
返回指向最后一个元素的后一个位置的迭代器
clear()
清除所有元素
count()
返回某个元素的个数，如果有这个元素，它的个数为1，否则为0
size()
返回集合中元素的数量
empty()
如果集合为空，返回true，否则返回false
insert()
在集合中插入元素
erase()
删除集合中的元素
find()
返回一个指向被查找到元素的迭代器，如果没有找到，返回end()
upper_bound()
返回大于某个值元素的迭代器
lower_bound()
返回指向大于（或等于）某值的第一个元素的迭代器
max_size()
返回集合能容纳的元素的最大限值


set在竞赛中常用于去重，把所有元素放进set，重复的会被去掉，保留在set中的都是唯一的，且按从小到大排序。

下面是set操作的例子，用count()判断set中是否有某个元素，见第20行和第21行。



1#include <bits/stdc++.h>
2using namespace std;
3set<int>st{5,9,2,3};//定义set，赋初值
4void out(){//输出set的所有元素

5 //set<int>::iterator it = st.begin();

6 auto it = st.begin();//与上一句的功能相同

7 for( ; it != st.end(); ++it) cout<<*it<<" ";
8 cout << endl;
9}
10int main() {

11 out();//set的元素从小到大排序。输出：2 3 5 9
12 st.insert(9);
13 out();//重复元素被去重，输出：2 3 5 9
14 auto it = st.lower_bound(6);//返回大于或等于6的第一个元素的迭代器
15 cout<<*it<<endl;//输出：9
16 it = st.find(7);

17 if(it==st.end()) cout<<"not find"<<endl; //输出：not find
18 else cout << *it<<endl;//无输出
19 st.erase(3);
20 if(st.count(5)) cout<<"find 5"<<endl;//输出：find 5
21 if(st.count(7)) cout<<"find 7"<<endl;//无输出
22 st.clear();//清空元素
23 if(st.empty()) cout << "empty"<<endl;//输出：empty
24 return 0;
25}





2. map

maphttps://en.cppreference.com/w/cpp/container/map是一种有序关联容器，它包含具有唯一键的键值对。键之间用比较函数Compare排序。map的搜索、移除和插入操作的复杂度是O(log2n)，效率非常高。map 通常实现为红黑树。

键值对的例子，例如学生的姓名和学号，把姓名看成键，学号看成值，键值对是{姓名,学号}。当需要查某个学生的学号时，通过姓名可以查到。如果用map存{姓名，学号}键值对，只需要计算O(1)次，就能通过姓名得到学号。map的效率非常高。

表3.5列出map的常见操作，和set的操作差不多。



表3.5map的常见操作



操作说明

begin()
返回指向第一个元素的迭代器
end()
返回指向最后一个元素的后一个位置的迭代器
clear()
清除所有元素
count()
返回某个元素的个数，如果有这个元素，它的个数为1，否则为0
size()
返回元素的数量
empty()
如果为空，返回true，否则返回false
insert()
插入元素
erase()
删除的元素
find()
返回一个指向被查找到元素的迭代器，如果没有找到，返回end()
upper_bound()
返回大于某个值元素的迭代器
lower_bound()
返回指向大于（或等于）某值的第一个元素的迭代器
max_size()
返回能容纳的元素的最大限值


下面是map操作的例子。往map中插入数据有两种方法，见第15行和第16行。

map有排序的功能，第7行遍历输出map的所有元素，是按键排序的。




1#include <bits/stdc++.h>
2using namespace std;
3map<int, string>mp{{7,"tom"},{2,"Joy"},{3,"Rose"}};//定义和赋初值

4void out(){//输出map的所有元素
5 //set<int>::iterator it = mp.begin();
6 auto it = mp.begin();//与上一句的功能相同
7 for( ; it != mp.end(); ++it)

8cout<<it->first<<" "<<it->second<<"; ";
9 cout << endl;
10}
11int main() {

12 out();//输出：2 Joy; 3 Rose; 7 tom;
13 cout<<"size = "<<mp.size()<<endl;//输出：size = 3

14 mp［3］ = "Luo";//修改了mp［3］的值。注意键是唯一的，不能改，值可以改
15 mp［5］ = "Wang";

16 mp.insert(pair<int, string>(9, "Hu"));//用pair定义键值对，然后插入

17 out();//输出：2 Joy; 3 Luo; 5 Wang; 7 tom; 9 Hu;
18 mp.erase(5);

19 out();//输出：2 Joy; 3 Luo; 7 tom; 9 Hu;
20 auto it = mp.find(3); //查询
21 if(it != mp.end())

22cout<<it->first<<" "<<it->second<<endl;//输出：3 Luo

23 else cout << "not find";//无输出
24 return 0;
25}





下面给出一道例题，分别用map和set实现。






 
例3.6眼红的Medusahttps://www.luogu.com.cn/problem/P1571



问题描述: Miss Medusa到北京领了科技创新奖。她发现很多人都和她一样获了科技创新奖，某些人还获得了另一个奖项——特殊贡献奖。Miss Medusa决定统计有哪些人获得了两个奖项。

输入: 第一行两个整数n、m，表示有n个人获得科技创新奖，m个人获得特殊贡献奖。第二行n个正整数，表示获得科技创新奖的人的编号。第三行m个正整数，表示获得特殊贡献奖的人的编号。

输出: 输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。


输入样例: 

4 3

2 15 6 8

8 9 2
输出样例: 

2 8
评测用例规模与约定： 对于60%的评测用例，0≤n,m≤1000，获得奖项的人的编号<2×109; 
对于100%的评测用例，0≤n,m≤105，获得奖项的人的编号<2×109。
输入数据保证第二行任意两个数不同，第三行任意两个数不同。


本题是查询n和m个数中哪些是重的。一种做法是检查m个数中的每一个数，如果它在n个数中出现过，就说明获得了两个奖。下面分别用map和set实现。

（1） 用map实现。把m个数放进map中，然后遍历map的每个数，如果在n个数中有，就输出。代码的计算复杂度是多少？map的每次操作是O(log2m)的，第9~11行的复杂度是O(mlog2m)，第13~15行的复杂度是O(nlog2m)，所以总计算复杂度是O(mlog2m+nlog2m)。



1#include<bits/stdc++.h>
2using namespace std;
3map<int,bool> mp;
4int a［101000］,b［101000］;
5int main(){
6 int n,m;
7 scanf("%d%d",&n,&m);
8for(int i=1;i<=n;i++) scanf("%d",&a［i］);
9for(int i=1;i<=m;i++) {
10scanf("%d",&b［i］);
11mp［b［i］］=true;
12 }
13for(int i=1;i<=n;i++)
14if(mp［a［i］］)
15printf("%d ",a［i］);//如果出现过,直接输出
16 return 0;
17}





（2） 用set实现。



1#include <bits/stdc++.h>
2using namespace std;
3set<int> st;
4int a［101000］, b［101000］;
5int main() {
6 int n, m; 
7scanf("%d%d", &n, &m);
8 for(int i = 1; i <= n; i++) scanf("%d", &a［i］);
9 for(int i = 1; i <= m; i++) {
10scanf("%d", &b［i］);
11st.insert(b［i］);
12 }
13 for(int i = 1; i <= n; i++) 
14if(st.count(a［i］)) 
15printf("%d ",a［i］);
16 return 0;
17}









3.3链表
数组的特点是使用连续的存储空间，访问每个数组元素非常快捷、简单。但是在某些情况下，数组的这些特点变成了缺点: 

（1） 需要占用连续的空间。若某个数组很大，可能没有这么大的连续空间给它用。不过这一般发生在较大的工程软件中，在竞赛中不用考虑占用的空间是否连续。例如一道题给定的存储空间是256MB，那么定义char a［100000000］，占用了连续的100MB空间，也是合法的。

（2） 删除和插入的效率很低。例如删除数组中间的一个数据，需要把后面所有的数据往前挪动，以填补这个空位，产生大量的复制开销，计算量为O(n)。中间插入数据，也同样需要挪动大量的数据。在算法竞赛中这是经常出现的考点，此时不能简单地使用数组。

数据结构“链表”能解决上述问题，它不需要把数据存储在连续的空间上，而且删除和增加数据都很方便。链表把数据元素用指针串起来，这些数据元素的存储位置可以是连续的，也可以不连续。

链表有单向链表和双向链表两种。单向链表如图3.2所示，指针是单向的，只能从左向右单向遍历数据。链表的头和尾比较特殊，为了方便从任何一个位置出发能遍历到整个链表，让首尾相接，尾巴tail的next指针指向头部head的data。由于链表是循环的，所以任意位置都可以成为头或尾。有时应用场景比较简单，不需要循环，可以让第一个节点始终是头。



图3.2单向链表



双向链表是对单向链表的优化。每个数据节点有两个指针，pre指针指向前一个节点，next指针指向后一个节点。双向链表也可以是循环的，最后节点的next指针指向第一个节点，第一个节点的pre指针指向最后的节点，如图3.3所示。



图3.3双向链表


在需要频繁访问前后几个节点的场合可以使用双向链表。例如删除一个节点now的操作，前一个节点是pre，后一个节点是next，那么让pre指向next，now被跳过，相当于被删除。此时需要找到pre和next节点，如果是双向链表，很容易得到pre和next; 如果是单向链表，不方便找到pre。

链表的操作有初始化、遍历、插入、删除、查找、释放等。

和数组相比，链表的优点是删除和插入很快，例如删除功能，找到节点后，直接断开指向它的指针，再指向它后面的节点即可，不需要移动其他所有节点。

链表仍是一种简单的数据结构，和数组一样，它的缺点是查找慢。例如查找data等于某个值的节点时，需要遍历整个链表才能找到它，计算量是O(n)。

3.3.1手写链表

链表的编程实现有动态链表、静态链表、STL链表等多种方法。动态链表是用malloc()函数动态分配空间生成节点，静态链表是定义全局静态数组来模拟链表。在算法竞赛中为了加快编码速度，一般用静态链表或STL list。

1. 静态链表

静态链表用数组来模拟链表，即“逻辑上是链表，物理上是数组”。

下面先给出单向链表的实现。

（1） 链表节点的定义。用struct node定义链表节点: id，表示这个节点的编号，一般用不着，因为可以用nodes［i］的下标i来表示节点的编号; data，节点存储的数据; nextid，链表的指针，指向下一个节点的编号。



1const int N = 10000;//按需要定义静态链表的空间大小
2struct node{//单向链表
3 int id;//这个节点的id
4 int data;//数据
5 int nextid;//指向下一个节点的id
6}nodes［N］;//静态分配需要定义在全局
7//为链表的next指针赋初值，例如：
8 nodes［0］.nextid = 1;
9 for(int i = 1; i <= n; i++){
10nodes［i］.id = i;//把第i个节点的id赋值为i
11nodes［i］.nextid = i + 1; //next指针指向下一个节点
12 }
13//定义为循环链表：尾指向头
14 nodes［n］.nextid = 1;
15//遍历链表，沿着nextid访问节点即可

16//删除节点。设当前位于位置now，删除这个节点。需要找到前一个节点，即preid指针

17 nodes［preid］.nextid = nodes［now］.nextid; //跳过节点now，即删除now
18 now = nodes［preid］.nextid;//更新now
19//插入节点，略





（2） 链表的初始化。因为直接用i来赋值nodes［i］，第10行的id是不必要的，可以省去。重点是第11行的nextid和第14行的头尾相接，这样才能完成一个循环的链表结构。

（3） 遍历链表。沿着nextid指针访问所有节点。

（4） 删除节点。若当前节点是now，删除它，需要先找到前一个节点pre，然后nodes［pre］.nextid=nodes［now］.nextid。如何找到pre，是单向链表的麻烦。

（5） 插入节点。由于是用数组来模拟链表的，当需要插入一个节点时，只能把数组末尾还没用到的新nodes［］赋值给新节点。例如定义一个nodes［10000］的静态链表，已经用nodes［1］~nodes［100］构成了一个循环链表，现在需要在nodes［1］和nodes［2］之间插入一个新节点，那么新节点就使用nodes［101］，然后赋值nodes［1］.nextid=101，nodes［101］.nextid=2，这样就完成了插入。

用静态数组模拟链表的缺点是，若有频繁的删除和插入，会逐渐消耗数组空间。因为删除的节点不方便回收再使用。在插入节点时，不能使用已经被删除的节点，而是一直使用数组末尾的新nodes［］。所以需要定义一个足够大的nodes［N］，避免用完。 

双向静态链表的实现和单向链表差不多，只是多了指向前一个节点的指针preid。下面是部分代码。



1const int N = 10000;
2struct node{//双向链表
3 int id;//节点编号
4 int data;//数据
5 int preid;//前一个节点
6 int nextid;//后一个节点
7}nodes［N］;
8//为节点的指针赋初值
9 nodes［0］.nextid = 1;
10 nodes［1］.preid = 0;



11 for(int i = 1; i <= n; i++){//建立链表
12nodes［i］.id = i;
13nodes［i］.preid = i-1;//前节点
14nodes［i］.nextid = i+1;//后节点
15 }
16//定义为循环链表
17 nodes［n］.nextid = 1;//循环链表：尾指向头
18 nodes［1］.preid = n;//循环链表：头指向尾





用下面的简单题说明链表的应用。






 
例3.7小王子单链表lanqiaoOJ 1110



问题描述: 小王子有一天迷上了排队的游戏，桌子上有标号为1~10的10个玩具，现在小王子将它们排成一列，可小王子还是太小了，他不确定到底想把哪个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了M次，每次都是选取标号为X的放到最前面，求每次排完后玩具的编号序列。 

输入: 第一行是一个整数M，表示小王子排玩具的次数。随后M行，每行包含一个整数X，表示小王子要把编号为X的玩具放在最前面。

输出: 共M行，第i行输出小王子第i次排完序后玩具的编号序列。


输入样例: 

5

3

2

3

4

2
输出样例: 

3 1 2 4 5 6 7 8 9 10

2 3 1 4 5 6 7 8 9 10

3 2 1 4 5 6 7 8 9 10

4 3 2 1 5 6 7 8 9 10

2 4 3 1 5 6 7 8 9 10



本题是单链表的直接应用。

把1~10这10个数据存到10个节点上，即toy［1］~toy［10］这10个节点。代码有一个小技巧: toy［0］始终是链表的头，但是不用它存数据，真正的数据在它的后面。当需要遍历链表的时候，直接从toy［0］开始即可。



1#include <bits/stdc++.h>
2using namespace std;
3struct node{
4//int id;//没用到
5 int data;
6 int nextid;
7}toy［20］;
8void init(){//初始化链表
9 toy［0］.nextid = 1;//节点0是链表头，它指向下一个节点1
10 toy［10］.nextid = -1;//最后的节点10指向-1，表示没有后续节点

11 for (int i = 1; i <=10; i++) {

12toy［i］.data = i;//节点的值
13toy［i］.nextid = i + 1;//指针，指向下一个节点
14 }
15}
16void tohead(int x){//把x放到最前面
17 int p = 0;//p是x的前一个节点


18 while(toy［p］.nextid !=-1){ //遍历链表，查找x的前一个节点p

19if (toy［toy［p］.nextid］.data == x) break;

20p = toy［p］.nextid;
21 }
22 int now = toy［p］.nextid;//now是x所在的节点

23 toy［p］.nextid = toy［now］.nextid;//删除x节点

24 toy［now］.nextid = toy［0］.nextid;

25 toy［0］.nextid = now;//把x放到最前面
26}
27void out(){//输出链表，就是题目的编号序列
28 int head = toy［0］.nextid;//toy［0］始终是链表头，并且不用来存编号

29 for (int i = 1; i <=10; i++){
30cout << toy［head］.data << ' ';
31head = toy［head］.nextid;
32 }
33 cout << endl;
34}
35int main(){
36 init();
37 int m;
38 cin >> m;
39 while (m--) {
40int x;
41cin >> x;
42tohead(x);
43out();
44 }
45 return 0;
46}





本节后面用STL list重新写这一题的代码，非常简短。

2. 极简链表

这里介绍一种极为简单的链表，虽然应用场景很少，不过也有它的优势。

定义一维数组R［］，R［i］的i是链表上节点i的值，而R［i］的值是下一个节点，也就是说R［i］是指向下一个节点的指针。

图3.4构造了一个单向链表，只要定义R［1］=2，R［2］=3，R［3］=4，…，就完成了单向链表的构造。



图3.4构造一个单向链表



添加或删除节点很简单。例如删除节点2，只需要修改R［1］，从原来的R［1］=2改为R［1］=3，这样就跳过了节点2，如图3.5所示。




图3.5删除节点2



极简链表的使用场景有限，因为一个节点i只能存一个数据，这个数据就等于i。在特定场景下这种方法很有用，因为它有一个优点: 可以通过R［i］的下标i直接找到数据i，而不需要像普通链表那样需要遍历整个链表才能找到i。

下面的蓝桥杯真题巧妙地应用了极简链表的这个特点。






 
例3.82023年第十四届C/C++大学B组试题H: 整数删除lanqiaoOJ 3515



时间限制: 1s内存限制: 256MB本题总分: 20分

问题描述: 给定一个长度为N的整数数列A1，A2，…,AN，请重复以下操作K次。

每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除，并把与它相邻的整数加上被删除的数值。

输出K次操作后的序列。

输入: 第一行包含两个整数N和K。第二行包含N个整数A1,A2,A3,…,AN。

输出: 输出N-K个整数，中间用一个空格隔开，代表K次操作后的序列。


输入样例: 

5 3

1 4 2 8 7
输出样例: 

17 7

评测用例规模与约定: 对于20%的评测用例，1≤K<N≤10000; 对于100%的评测用例，1≤K<N≤5×105，0≤Ai≤108。


这道题在第2章用简单方法做过，能通过20%的测试。下面的方法能通过100%的测试。

本题的删除操作显然应该用链表。如果按第2章的简单方法，用数组来存数列，每次删除一个数，就需要把它后面所有的数往前挪一位，以填补它留下的空位，这样操作很耗时。如果用链表来处理数列，就不用挪动大量的数了。

另外，本题的每次操作要找到最小的数。如果遍历整个链表来找，每次查找是O(N)的计算量，那么K次操作的总计算量仍然是O(NK)，和第2章的简单方法的计算量差不多，仍不能通过100%的测试。解决方案是用优先队列来找最小的数，在N个数中找最小值，计算量只有O(log2N)。优先队列的讲解见本章“3.5 优先队列”。

如何把链表和优先队列结合起来？数列分别由链表和优先队列来处理: 

（1） 链表。把数列存到链表的节点上，在链表上删除最小值节点，并且更新它的邻居，也就是加上被删除的节点的值。最小值是通过优先队列找到的。

（2） 优先队列。把数列存到优先队列中，每次操作取出最小值。然后把更新后的数重新放进队列。

（3） 优先队列找到最小值后，如何在链表中定位？这是最关键的问题。如果是普通队列，那么就需要遍历链表，计算量是O(N)，还是一样耗时，优先队列白用了，还不如直接在链表中找最小值。这里如果用极简链表，非常巧妙: 用优先队列找最小值t，t对应的链表节点就是R［t］，无须遍历链表，计算量是O(1)。

总结以上思路，做一次操作的计算量是: 用优先队列找最小值t，计算量是O(log2N); 在链表上定位t的位置，计算量是O(1)，并用链表处理删除和更新邻接，计算量是O(1)。一次操作的计算量是O(log2N),K次操作是O(Klog2N)，顺利通过100%的测试。

第5行定义双向链表，L［］是左指针，R［］是右指针。

第7行删除节点x。R［L［x］］=R［x］表示x的左节点指向x的右节点，L［R［x］］=L［x］表示x的右节点指向x的左节点，这样x的左、右节点就跳过了x节点，相当于删除了x。

注意第27行优先队列的操作。优先队列的队头是最小值，但是这个最小值对应的节点数据可能被第31行的del()更新了，不再是最小值，所以需要重新放进队列，重新排序。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 5e5 + 10;
4long long v［N］;//数列的值相加后可能超过int，需要用long long
5int L［N］, R［N］;//双向链表
6void del(int x) {//双向链表：删除x节点

7 R［L［x］］ = R［x］, L［R［x］］ = L［x］;//删除第x个节点
8 v［L［x］］ += v［x］, v［R［x］］ += v［x］;//更新左、右邻居

9}
10int main() {
11 int n, k; cin >> n >> k;
12 //优先队列， 优先队列的元素是{权值，节点下标}
13 priority_queue<pair<long long, int>, vector<pair<long long, int>>,
14greater<pair<long long, int>>> Q;
15 //输入并构造双向链表

16 R［0］ = 1;//队头0，右指针R［0］指向节点1
17 L［n + 1］ = n;//队尾n+1，左指针L［N+1］指向节点n
18 for (int i = 1; i <=n; i ++) {

19cin >> v［i］;//读数列
20L［i］ = i - 1, R［i］ = i + 1;//构造双向链表，第i个节点表示V［i］
21Q.push({v［i］, i});//把数列放进优先队列，求最小值
22 }
23 while (k--) {//k次操作
24auto p = Q.top(); 

25//读优先队列的队头，队头是最小值。p.first是值，p.second是它的位置
26Q.pop();//弹走队头，优先队列会重新排序，新的队头仍是最小值 
27if (p.first != v［p.second］){//这个队头被del()改过了，不一定最小
28Q.push({v［p.second］, p.second}); //重新放进队列，重新排序

29k++;//撤销这次操作
30}
31else del(p.second);//删除节点并更新邻居
32 }
33 int t = R［0］;//队头0，R［0］指向第一个数
34 while (t != n + 1) {//遍历链表
35cout << v［t］ << " "; //输出链表元素
36t = R［t］;
37 }
38 return 0;
39}





3.3.2STL list

在大多数情况下不需要手写链表，而是直接使用C++的STL listhttps://zh.cppreference.com/w/cpp/container/list，代码更简单。

STL list的常用操作如表3.6所示。



表3.6STL list的常用操作




操作
说明
size()
链表的元素个数
empty()
链表是否为空
push_front()
在链表头添加元素
push_back()
在链表尾添加元素
unique()
将链表中相邻的重复元素去除，如果重复元素不相邻，则无效
sort()
升序排序
pop_back()
删除链表尾
pop_front()
删除链表头
front()
读队头
back()
读队尾
reverse()
反转链表
insert(it)
在it位置插入元素
erase(it)
在it位置删除元素


下面的代码演示了这些操作。



1#include <bits/stdc++.h>
2using namespace std;
3list<int> lis = {1,2,3};//定义链表，初值为{1,2,3}
4void out(){//输出链表

5 for (auto it = lis.begin(); it != lis.end(); ++it) //遍历链表

6cout << *it << " ";
7 cout << "＼n";
8}
9int main(){
10 list<int> list2(lis);//复制链表
11 cout << lis.size()<<"＼n"; //链表的元素个数，输出：3

12 if(!lis.empty()) cout<<"no empty"<<"＼n"; //输出：no empty

13 lis.push_front(9); out();//在链表头添加元素，输出：9 1 2 3
14 lis.push_back(9);  out();//末尾添加元素，输出：9 1 2 3 9
15 lis.unique(); out();//相邻重复元素去重，输出：9 1 2 3 9
16 lis.sort(); out();//升序排序，输出：1 2 3 9 9
17 lis.unique(); out();//去重，此时有效，输出：1 2 3 9
18 lis.pop_back(); out();//删除队尾，输出：1 2 3
19 lis.pop_front(); out();//删除队头，输出：2 3
20 cout<<lis.front()<<"＼n";//读队头，输出：2
21 cout<<lis.back() <<"＼n";//读队尾，输出：3
22 lis.reverse(); out();//反转，输出：3 2
23 auto it = lis.begin();

24 ++it;//注意，像it=it+5这样是错误的，因为it和5的类型不同

25 lis.insert(it, 5); out();//在it位置插入，输出：3 5 2
26 ++it;
27 if(it == lis.end()) cout << "end" << "＼n";//输出：end
28 --it;//如果it是end，不能erase
29 lis.erase(it); out();//删除it位置的元素，输出：3 5
30 return 0;
31}





用STL list写代码很简短。例如本节例题“小王子单链表 lanqiaoOJ 1110”，下面用STL list实现。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 list<int> toy{1,2,3,4,5,6,7,8,9,10};//定义链表



5 int m; cin >> m;
6 while (m--) {
7int x; cin >> x;
8toy.remove(x);//删除链表中的x
9toy.push_front(x);//把x插到链表头
10for(auto i:toy) cout<<i<<" ";//输出链表
11cout<<endl;
12 }
13 return 0;
14}





再看一道例题。






 
例3.9重新排队lanqiaoOJ 3255 



问题描述: 给定按从小到大的顺序排列的数字1到n，随后对它们进行m次操作，每次将一个数字x移动到数字y之前或之后。请输出完成这m次操作后它们的顺序。 

输入: 第一行为两个数字n、m,表示初始状态为1到n从小到大排列，后续有m次操作。第二行到第m+1行，每行3个数x、y、z。当z=0时，将x移动到y之后; 当z=1时，将x移动到y之前。

输出: 输出一行，包含n个数字，中间用空格隔开，表示m次操作完成后的排列顺序。


输入样例: 

5 3

3 1 0

5 2 1

2 1 1
输出样例: 

2 1 3 5 4





题目简单，下面是代码。



1#include <bits/stdc++.h>
2using namespace std;
3int main() {
4 int n, m;
5 cin >> n >> m;
6 list<int> lis;
7 for (int i = 1; i <=n; i++)
8lis.push_back(i); //链表赋值
9 while(m--){
10int x, y, z; 
11cin >> x >> y >> z;
12lis.remove(x);//删除x

13list<int>::iterator it = find(lis.begin(), lis.end(), y);//找到y

14//上一句可以把 list<int>::iterator it 改为 auto it

15if (z == 0) lis.insert(++it, x);//x放在y后面
16if (z == 1) lis.insert(it, x);//x放在y前面
17 }
18 for (int x : lis)
19cout << x << " ";
20 cout << endl;
21 return 0;
22}





【练习题】

lanqiaoOJ: 约瑟夫环1111、小王子双链表1112，以及种瓜得瓜，种豆得豆3150。

洛谷: 单向链表 B3631、队列安排P1160。






3.4队列
队列（queue）也是一种简单的数据结构。普通队列的数据存取方式是“先进先出”，只能往队尾插入数据、从队头移出数据。队列在生活中的原型就是排队，例如在网红店排队买奶茶，排在队头的人先买到奶茶然后离开，后来的人排到队尾。



图3.6队列




图3.6是队列的原理，队头head指向队列中的第一个元素a1，队尾tail指向队列中的最后一个元素an。元素只能从队头方向出去，并且只能从队尾进入队列。

3.4.1手写队列

队列的代码很容易实现。如果使用环境简单，最简单的手写队列代码用数组实现。



1const int N = 10005;//定义队列容量，确保够用
2int que［N］;//队列，用数组模拟
3int head = 0;//head始终指向队头。que［head］是队头
4//开始时队列为空，head = 0
5int tail = -1;//tail始终指向队尾。que［tail］是队尾
6//开始时队列为空，tail = -1
7//队列长度等于tail-head+1
8head++;//弹出队头元素，让head指向新队头
9//注意保持head <=tail
10que［head］;//读队头
11que［++tail］ = data;//入队：先tail加1，然后数据data入队
12//注意tail必须小于N





把它封装到结构体里更整洁一些: 



1const int N = 10005; //定义队列容量，确保够用
2struct myqueue{
3 int a［N］;//队列，用数组模拟
4 int head = 0; 

5//head始终指向队头。que［head］是队头。开始时队列为空，head = 0
6 int tail = -1;
7//tail始终指向队尾。que［tail］是队尾。开始时队列为空,tail = -1
8 int size(){return tail-head+1;}//队列长度等于tail-head+1
9 void push(int data){a［++tail］=data;}
10//入队：先tail加1，然后数据data入队
11 int front(){return a［head］;}//读队头
12 void pop(){head++;} 
13//弹出队头元素，让head指向新队头。注意保持head <=tail
14};





这个手写代码有一个缺陷: 如果进入队列的数据太多，使得tail超过了N，数组a［N］就会溢出，导致出错。

用下面的例子给出上述手写代码的应用。






 
例3.10约瑟夫问题https://www.luogu.com.cn/problem/P1996



问题描述: n个人，编号为1~n，按顺序围成一圈，从第一个人开始报数，数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，以此类推，直到所有的人都出圈，请依次输出出圈人的编号。

输入: 两个整数n和m，1≤n，m≤100。

输出: n个整数，按顺序输出每个出圈人的编号。


输入样例: 

10 3
输出样例: 

3 6 9 2 7 1 8 5 10 4


约瑟夫问题是一个经典问题，可以用队列、链表等数据结构实现。下面的代码用队列来模拟报数。方法是反复排队，从队头出去，然后重新排到队尾，每一轮数到m的人离开队伍。第22行把队头移到队尾，第23行让数到m的人离开。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 10005;
4struct myqueue{
5 int a［N］;
6 int head;
7 int tail;
8 void init(){head=0, tail=-1;} 
9 int size(){return tail-head+1;} 
10 void push(int data){a［++tail］=data;} 
11 int front(){return a［head］;}
12 void pop(){head++;}
13};
14myqueue que;
15int main(){
16 int n,m;
17 cin>>n>>m;
18 que.init();
19 for(int i=1;i<=n;i++) que.push(i);
20 while(que.size()!=0){
21for(int i=1;i<m;i++){
22que.push(que.front());
23que.pop();
24}
25cout << que.front() << " ";
26que.pop();
27 }
28 cout<<endl;
29 return 0;
30}





代码第3行定义了队列的容量N=10005。本题的n最大是100，每人出圈一次，所以队列长度一定不超过100×100。如果把N设置小了，例如N=2000，提交到OJ会返回RE，即Runtime Error，说明溢出了。

如果要防止溢出，可以使用循环队列手写循环队列的代码见《算法竞赛》,清华大学出版社，罗勇军、郭卫斌著，第8页的“1.2.2 手写循环队列”。。

队列是一种线性数据结构，线性数据结构的主要缺点是查找较慢。如果要在队列中查找某个元素，只能从头到尾一个一个查找。

3.4.2STL queue

在竞赛时一般不自己手写队列，而是用STL queueC++STL queue的官方文档: https://cplusplus.com/reference/queue/queue/，不用自己管理队列，也没有溢出的问题，大大加快了做题速度。STL queue的主要操作如表3.7所示。



表3.7STL queue的主要操作



操作
说明
queue<Type> q; 
定义队列，Type为数据类型，如int、float、char等
push()
在队列尾部插入一个元素
front()
返回队首元素，但不会删除
pop()
删除队首元素
back()
返回队尾元素
size()
返回元素的个数
empty()
检查队列是否为空


下面是“洛谷P1996”的STL queue实现，代码很简短。



1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 int n,m;
5 cin>>n>>m;
6 queue<int>q;
7 for(int i=1;i<=n;i++) q.push(i);
8 while(!q.empty()){
9for(int i=1;i<m;i++){
10q.push(q.front());//读队头，重新排到队尾
11q.pop();//弹走队头 
12}
13cout << q.front() << " ";
14q.pop();//第m个人离开队伍
15 }
16 cout<<endl;
17 return 0;
18}





下面用一道例题说明queue的应用。






 
例3.11机器翻译lanqiaoOJ 511



问题描述: 小晨的计算机上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。





这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译; 如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有M个单元，每个单元能存放一个单词和译义。在软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M-1，软件会将新单词存入一个未使用的内存单元; 若内存中已存入M个单词，软件会清空最早进入内存的单词，腾出单元来存放新单词。

假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前内存中没有任何单词。

输入: 输入共两行，每行中两个数之间用一个空格隔开。第一行为两个正整数M和N，代表内存容量和文章的长度。第二行为N个非负整数，按照文章的顺序，每个数(大小不超过1000)代表一个英文单词。文章中的两个单词是同一个单词，当且仅当它们对应的非负整数相同。其中，0<M≤100，0<N≤1000。

输出: 输出一行，包含一个整数，为软件需要查词典的次数。


输入样例: 

3 7

1 2 1 5 4 4 1
输出样例: 

5



用一个哈希表hashtable［］模拟内存，若hashtable［x］=true，表示x在内存中，否则表示不在内存中。用队列queue对输入的单词排队，当内存超过M时删除队头的单词。下面是代码。



1#include <bits/stdc++.h>
2using namespace std;
3bool hashtable［1003］;//全局数组，自动初始化为0
4int main(){
5 int m,n;
6 cin >> m >> n;
7 int ans=0;//函数内部变量，一定要初始化为0
8 queue<int> q;
9 for(int i=0;i<n;i++) {
10int x; cin >> x;
11if(hashtable［x］ == false) {
12hashtable［x］ = true;
13if(q.size() < m) q.push(x);
14else {

15hashtable［q.front()］ = false;
16q.pop();
17q.push(x);
18}

19ans++;//内存中没有这个单词，到外存中找，答案加1
20}
21 }
22 cout << ans << '＼n';
23 return 0;
24}





【练习题】

lanqiaoOJ: 餐厅排队 3745、小桥的神秘礼物盒3746、CLZ银行问题1113、繁忙的精神疗养院3747。






3.5优 先 队 列
前一节的普通队列，特征是只能从队头、队尾进出，不能在中间插队或出队。

本节的优先队列不是一种“正常”的队列。在优先队列中，所有元素有一个“优先级”，一般用元素的数值作为它的优先级，或者越小越优先，或者越大越优先。让队头始终是队列内所有元素的最值（最大值或最小值）。队头弹走之后，新的队头仍保持为队列中的最值。举个例子: 一个房间，有很多人进来; 规定每次出来一个人，要求这个人是房间中最高的那个; 如果某人刚进去，发现自己是房间里面最高的，就不用等待，能立刻出去。

优先队列的一个简单应用是排序: 以最大优先队列为例，先让所有元素进入队列，然后再一个一个弹出，弹出的顺序就是从大到小排序。优先队列更常见的应用是动态的，进出同时发生: 一边进队列，一边出队列。

如何实现优先队列？先试一下最简单的方法。以最大优先队列为例，如果简单地用数组存放这些元素，设数组中有n个元素，那么其中的最大值是队头，要找到它，需要逐一在数组中找，计算量是n次比较。这样是很慢的，例如有n=100万个元素，就得比较100万次。把这里的n次比较的计算量记为O(n)。

优先队列有没有更好的实现方法？常见的高效方法是使用二叉堆这种数据结构《算法竞赛》，清华大学出版社，罗勇军、郭卫斌著，第27页的“1.5 堆”。。它非常快，每次弹出最大值队头,只需要计算O(log2n)次。例如n=100万的优先队列，取出最大值只需要计算log2(100万)=20次。

在竞赛中，一般不用自己写二叉堆来实现优先队列，而是直接使用STL priority_queue，初学者只需要学会如何使用它即可。

STL优先队列priority_queuehttps://en.cppreference.com/w/cpp/container/priority_queue用堆来实现，堆是基于二叉树的一种数据结构。

定义: priority_queue<Type，Container，Functional>

Type是数据类型，Container是容器类型（默认是vector），Functional是比较的方式，当需要用自定义的数据类型时才需要传入这3个参数，在使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

priority_queue的常见操作如表3.8所示。



表3.8priority_queue的常见操作




操作
说明
priority_queue<Type，Container，Functional>
定义队列 
pq.push()
入队
pop()
出队
size()
返回当前队列中元素的个数
top()
返回队首元素
empty()
判断是否为空（空返回 1，非空返回 0）


下面是例子。第5行定义了一个队首是最大值的优先队列，第10行的输出如下: 

27-wuhan21-shanghai11-beijing 



第13行定义了一个队首是最小值的优先队列，第19行的输出如下: 

11-beijing21-shanghai27-wuhan





1#include <bits/stdc++.h>
2using namespace std;
3int main(){
4 priority_queue<pair<int, string>> pq;//队首是最大值
5 pair<int,string> a(11,"beijing"), b(21,"shanghai"), c(27,"wuhan");
6 pq.push(a);
7 pq.push(b);
8 pq.push(c);
9while (!pq.empty()){
10cout<<pq.top().first<<"-"<<pq.top().second<<"＼n";
11pq.pop();
12 }
13 priority_queue<pair<int,string>,vector<pair<int,string>>, ＼
14greater<pair<int,string>>> pq2;//队首是最小值
15 pq2.push(a);
16 pq2.push(b);
17 pq2.push(c);
18 while (!pq2.empty()) {
19cout<<pq2.top().first<<"-"<<pq2.top().second<<"＼n";
20pq2.pop();
21 }
22 return 0;
23}





用下面的例题介绍优先队列的应用。






 
例3.12丑数http://oj.ecustacm.cn/problem.php?id=1721



问题描述: 给定素数集合S={p1,p2,…，pk}，丑数是指一个正整数满足所有质因数都出现在S中，1默认是第1个丑数。例如S={2,3,5}时，此时前20个丑数为1、2、3、4、5、6、8、9、10、12、15、16、18、20、24、25、27、30、32、36。现在S={3,7,17,29,53}，求第20220个丑数是多少？


这是一道填空题，下面直接给出代码。



1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4int prime［］ = {3,7,17,29,53};
5int main(){
6 set<ll>s;//判重
7 s.insert(1);//第一个丑数是1



8 priority_queue<ll, vector <ll>, greater<ll>>q; //队列中是新生成的丑数

9 q.push(1);//第一个丑数是1，进入队列
10 int n = 20220;
11 ll ans;
12 for(int i = 1; i <=n; i++){ //从队列中由小到大取出20220个丑数
13ll now = q.top();

14q.pop();//把队列中最小的取出来，它也是已经取出的最大的

15ans = now;
16for(int i = 0; i < 5; i++){//5个素数
17ll tmp = now * prime［i］; //从已取出的最大值开始乘以5个素数
18if(!s.count(tmp)) {//tmp这个数没有出现过
19s.insert(tmp);//放到set里面
20q.push(tmp);//把tmp放进队列
21}
22}
23 }
24 cout<<ans<<endl;
25 return 0;
26}





再看一道例题。






 
例3.13分牌http://oj.ecustacm.cn/problem.php?id=1788



问题描述: 有n张牌，每张牌上有一个数字a［i］，现在需要将这n张牌尽可能地分给更多的人。每个人需要被分到k张牌，并且每个人被分到手的牌中不能有相同数字，同时需要保证可以尽可能地分给更多的人，输出任意的一种分法即可。 

输入: 输入第一行为正整数n和k，1≤k≤n≤1000000。第二行包含n个整数a［i］，1≤a［i］≤1000000。 

输出: 输出m行，m为可以分给的人数，数据保证m大于或等于1。第i行输出第i个人手中牌的数字。输出任意一个解即可。 


输入样例: 

样例1：

6 3

1 2 1 2 3 4



样例2：

14 3

3 4 1 1 1 2 3 1 2 1 1 5 6 7


输出样例: 

样例1: 

1 2 4

1 2 3



样例2: 

6 1 3

2 4 1

5 1 2

1 3 7


题意是有n个数字，其中有重复数字，把n个数字分成多份，每份k个数字，问最多能分成多少份。

很显然这道题用“隔板法”。用板子隔成m个空间，每个空间有k个位置。把n个数按数量排序，先把数量最多的数，每个隔板内放一个; 再把数量第2多的，每个隔板内放一个; 依次类推，直到放完所有的数。由于每个数在每个空间内只放一个，所以每个空间内不会有重复的数。

例如n=10，k=3，这10个数是{5，5，5，5，2，2，2，4，4，7}，按数量从多到少排好了序。用隔板隔出4个空间［］［］［］［］。

先放5: ［5］［5］［5］［5］

再放2: ［5,2］［5,2］［5,2］［5］

再放4: ［5,2,4］［5,2,4］［5,2］［5］

再放7: ［5,2,4］［5,2,4］［5,2,7］［5］

结束，答案是{5,2,4}、{5,2,4}、{5,2,7}。

如何编码？下面用优先队列编程。第7行用二元组pair<int，int>表示每个数的数量和数字。优先队列priority_queue会把每个数按数量从多到少拿出来，相当于按数量多少排序。

代码的执行步骤: 把所有数放进队列; 每次拿出k个不同的数并输出，直到结束。

代码的计算复杂度： 进出一次队列是O(log2n)，共n个数，总复杂度为O(nlog2n)。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 1e6 + 10;
4int num［N］;
5int main(){
6 int n, k; cin >> n >> k;
7 priority_queue<pair<int, int>> q;
8 for (int i = 0; i < n; i++) {
9int x; cin >> x;

10num［x］++;//x这个数有num［x］个
11 }
12 for (int i = 0; i < N;  ++)
13if(num［i］ > 0)
14q.push({num［i］, i});//数i的个数，数i
15 while(q.size() >= k) {//队列中数量大于k，说明还够用

16vector<pair<int, int>> tmp(k);

17for (int i = 0; i < k; i++){ //拿k个数出来，且这k个数不同，这是一份
18tmp［i］ = q.top();//先出来的是num［］最大的
19q.pop();
20}
21for (int i = 0; i < k; i++) { //打印一份，共k个数

22cout << tmp［i］.second << " ＼n"［i == k - 1］;

23tmp［i］.first -= 1;//这个数用了一次，减1

24if(tmp［i］.first > 0) q.push(tmp［i］);//没用完，再次进队列
25}
26 }
27 return 0;
28}




【练习题】

lanqiaoOJ: 小蓝的神奇复印机3749、Windows的消息队列3886、小蓝的智慧拼图购物3744、餐厅就餐4348。





3.6栈
栈（stack）是比队列更简单的数据结构，它的特点是“先进后出”。

队列有两个口，一个入口和一个出口。栈只有唯一的一个口，既从这个口进入，又从这个口出来。栈像一个只有一个门的房子，而队列这个房子既有前门又有后门。所以如果自己写栈的代码，比写队列的代码更简单。

栈在编程中有基础的应用，例如常用的递归，在系统中是用栈来保存现场的。栈需要用空间存储，如果栈的深度太大，或者存进栈的数组太大，那么总数会超过系统为栈分配的空间，就会爆栈导致栈溢出。不过，算法竞赛一般不会出现这么大的栈。

栈的常见操作如下。

empty()： 返回栈是否为空。

size()： 返回栈的长度。

top()： 查看栈顶元素。

push()： 进栈，向栈顶添加元素。

pop()： 出栈，删除栈顶元素。

栈的这些操作的计算量都是O(1)，效率很高。

3.6.1手写栈

如果使用环境简单，最简单的手写栈代码用数组实现。



1const int N = 300008;//定义栈的大小
2struct mystack{
3int a［N］;//存放栈元素，从a［0］开始
4 int t = -1;//栈顶位置，初始栈为空，置初值为-1
5 void push(int data){a［++t］ = data;}//把元素data送入栈
6 int top() {return a［t］;}//读栈顶元素，不弹出
7 void pop() {if(t>-1) t--;}//弹出栈顶
8 int size() {return t+1;}//栈内元素的数量
9 int empty() {return t==-1 ? 1:0;}//若栈为空，返回1
10};





在使用栈时要注意不能超过栈的空间。上面第1行定义了栈的大小N，进栈的元素数量不要超过它。

用下面的例子给出上述手写代码的应用。






 
例3.14表达式括号匹配https://www.luogu.com.cn/problem/P1739



问题描述: 假设一个表达式由英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以@作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，输出YES，否则输出NO。表达式的长度小于255，左圆括号少于20个。

输入: 一行，表达式。

输出: 一行，YES或NO。


输入样例: 

2*(x+y)/(1-x)@
输出样例: 

YES


合法的括号串例如“(())”和“()()()”，像“)（（)”这样是非法的。合法括号组合的特点是左括号先出现，右括号后出现; 左括号和右括号一样多。

括号组合的合法检查是栈的经典应用。用一个栈存储所有的左括号。遍历字符串的每一个字符，处理流程如下。 

（1） 若字符是'('，进栈。

（2） 若字符是')'，有两种情况: 如果栈不空，说明有一个匹配的左括号，弹出这个左括号，然后继续读下一个字符; 如果栈空了，说明没有与右括号匹配的左括号，字符串非法，输出NO，程序退出。

（3） 在读完所有字符后，如果栈为空，说明每个左括号有匹配的右括号，输出YES，否则输出NO。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 300008;//定义栈的大小
4struct mystack{
5 int a［N］;//存放栈元素，从a［0］开始
6 int t = -1;//栈顶位置，初始栈为空，置初值为-1

7 void push(int data){a［++t］ = data;} //把元素data送入栈

8 int top() {return a［t］;}//读栈顶元素，不弹出
9 void pop() {if(t>-1) t--;}//弹出栈顶
10 int size() {return t+1;}//栈内元素的数量
11 int empty() {return t==-1 ? 1:0;}//若栈为空，返回1
12}st;
13int main(){
14 char x;
15 while(cin>>x){//循环输入
16if(x=='@') break;//输入为@停止
17if(x=='(') st.push(x);//左括号入栈
18if(x==')'){//遇到一个右括号
19if(st.empty()) {//栈空，没有左括号与右括号匹配
20cout<<"NO"; 
21return 0;
22} 
23else st.pop();//匹配到一个左括号，出栈
24}
25 }

26 if(st.empty())//栈为空，所有左括号已经匹配到右括号，输出YES
27cout<<"YES"; 
28 else cout<<"NO";
29 return 0;
30}





3.6.2STL stack

在竞赛时一般不自己手写栈,而是用STL stackhttps://www.cplusplus.com/reference/stack/stack/。

STL stack的主要操作如表3.9所示。



表3.9STL stack的主要操作




操作
说明
stack<Type>s; 
定义栈,Type为数据类型，如int、float、char等
push(item)
把item放到栈顶
top()
返回栈顶的元素，但不会删除
pop()
删除栈顶的元素，但不会返回
size()
返回栈中元素的个数
empty()
检查栈是否为空，如果为空返回true，否则返回false


用下面的例题说明STL stack的应用。






 
例3.15排列http://oj.ecustacm.cn/problem.php?id=1734



问题描述: 给定一个1~n的排列，每个<i，j>对的价值是j-i+1，计算所有满足以下条件的<i，j>对的总价值。（1）1≤i<j≤n; （2）a［i］~a［j］的数字均小于min(a［i］，a［j］); （3）a［i］~a［j］不存在其他数字则直接满足。

输入: 第一行包含正整数N(N≤300000)，第二行包含N个正整数，表示一个1~N的排列a。

输出: 一个正整数，表示答案。


输入样例: 

7

4 3 1 2 5 6 7
输出样例: 

24



把符合条件的一对<i，j>称为一个“凹”。首先模拟检查“凹”，了解执行的过程。以“3 1 2 5”为例，其中的“凹”有“312”和“3125”，以及相邻的“31”“12”“25”。一共有5个“凹”，总价值为13。

像“312”和“3125”这样的“凹”，需要检查连续3个以上的数字。

例如“312”，从“3”开始，下一个应该比“3”小，如“1”，再后面的数字比“1”大，才能形成“凹”。

再例如“3125”，前面的“312”已经是“凹”了，最后的“5”会形成新的“凹”，条件是这个“5”必须比中间的“12”大才行。

总结上述过程是先检查“3”; 再检查“1”符合“凹”; 再检查“2”，比前面的“1”大，符合“凹”; 再检查“5”，比前面的“2”大，符合“凹”。

以上是检查一个“凹”的两头，还有一种是“嵌套”。一旦遇到比前面小的数字，那么以这个数字为头，可能形成新的“凹”。例如“6 4 2 8”，其中的“6428”是“凹”，内部的“428”也是“凹”。如果大家学过递归、栈，就会发现这是嵌套，所以本题用栈来做很合适。

以“6 4 2 8”为例，用栈模拟找“凹”。当新的数比栈顶的数小，就进栈; 如果比栈顶的数大，就出栈，此时找到了一个“凹”并计算价值。图3.7中的圆圈数字是数在数组中的下标位置，用于计算题目要求的价值。





图3.7用栈统计凹



图(1): 6进栈。

图(2): 4准备进栈，发现比栈顶的6小，说明可以形成凹，4进栈。

图(3): 2准备进栈，发现比栈顶的4小，说明可以形成凹，2进栈。

图(4): 8准备进栈，发现比栈顶的2大，这是一个凹“428”，对应下标“②④”，弹出2，然后计算价值，j-i+1=④-②+1=3。

图(5): 8准备进栈，发现比栈顶的4大，这是一个凹“648”，对应下标“①④”，也就是原数列的“6428”。弹出4，然后计算价值，j-i+1=④-①+1=4。

图(6): 8终于进栈了，数字也处理完了，结束。

在上述过程中，只计算了长度大于或等于3的凹，没有计算题目中“（3）a［i］~a［j］不存在其他数字”的长度为2的凹，所以最后统一加上这种情况的价值(n-1)×2=6。

最后统计得“6 4 2 8”的总价值是3+4+6=13。

下面是代码。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 300008;
4int a［N］;//这里a［］是题目的数字排列
5int main(){
6 int n;cin>>n;
7 for(int i = 1;i <=n;i++)cin>>a［i］; //输入数列
8 stack <int> st;//定义栈
9 long long ans = 0;
10 for(int i = 1;i <=n;i++){
11while(!st.empty() && a［st.top()］ < a［i］){
12st.pop();
13if(!st.empty()){
14int last = st.top();
15ans += (i - last + 1);
16}
17}
18st.push(i);
19 }
20 ans += (n - 1) * 2;//(3)a［i］~a［j］不存在其他数字的情况
21 cout<<ans;
22}





【练习题】

lanqiaoOJ: 妮妮的神秘宝箱3743、直方图的最大建筑面积4515、小蓝的括号串2490、校邋遢的衣橱1229。

洛谷: 小鱼的数字游戏P1427、后缀表达式P1449、栈P1044、栈B3614、日志分析P1165。






3.7二叉树
在前几节介绍的数据结构中，数组、队列、栈和链表都是线性的，它们存储数据的方式是把相同类型的数据按顺序一个接一个地串在一起。线性表形态简单，难以实现高效率的操作。

二叉树是一种层次化的、高度组织性的数据结构。二叉树的形态使得它有天然的优势，在二叉树上做查询、插入、删除、修改、区间等操作极为高效，基于二叉树的算法也很容易实现高效率的计算。

3.7.1二叉树的概念

二叉树的每个节点最多有两个子节点，分别称为左孩子、右孩子，以它们为根的子树称为左子树、右子树。二叉树的每一层以2的倍数递增，所以二叉树的第k层最多有2k-1个节点。根据每一层的节点分布情况，有以下常见的二叉树。

（1） 满二叉树。其特征是每一层的节点数都是满的。第一层只有一个节点，编号为1; 第二层有两个节点，编号为2、3; 第三层有4个节点，编号为4、5、6、7; ……; 第k层有2k-1个节点，编号为2k-1,2k-1+1,…,2k-1。

一棵n层的满二叉树，一共有1+2+4+…+2n-1= 2n-1个节点。

图3.8演示了一棵满二叉树和一棵完全二叉树。





图3.8满二叉树和完全二叉树



（2） 完全二叉树。如果满二叉树只在最后一层有缺失，并且缺失的节点都在最后，称为完全二叉树。

（3） 平衡二叉树。任意左子树和右子树的高度差不大于1，称为平衡二叉树。若只有少部分子树的高度差超过1，则这是一棵接近平衡的二叉树。


图3.9演示了一棵平衡二叉树和一棵退化二叉树。



图3.9平衡二叉树和退化二叉树



（4） 退化二叉树本作者曾拟过一句赠言: “二叉树对链表说，我也会有老的一天，那时就变成了你”。。如果树上的每个节点都只有一个孩子，称为退化二叉树。退化二叉树实际上已经变成了一根链表。如果绝大部分节点只有一个孩子，少数有两个孩子，也看成退化二叉树。

二叉树之所以应用广泛，得益于它的形态。高级数据结构大部分和二叉树有关，下面列举二叉树的一些优势。

（1） 在二叉树上能进行极高效率的访问。一棵平衡的二叉树，例如满二叉树或完全二叉树，每一层的节点数量大约是上一层数量的两倍，也就是说，一棵有N个节点的满二叉树，树的高度是O(log2N)。从根节点到叶子节点，只需要走log2N步，例如N=100万，树的高度仅有log2N=20，只需要走20步就能到达100万个节点中的任意一个。但是，如果二叉树不是满的，而且很不平衡，甚至在极端情况下变成退化二叉树，访问效率会降低。维护二叉树的平衡是高级数据结构的主要任务之一。

（2） 二叉树很适合做从整体到局部、从局部到整体的操作。二叉树内的一棵子树可以看成整棵树的一个子区间，求区间最值、区间和，以及做区间翻转、区间合并、区间分裂等，用二叉树都很快捷。

（3） 基于二叉树的算法容易设计和实现。例如二叉树用BFS和DFS搜索处理都极为简便。二叉树可以一层一层地搜索，是BFS的典型应用场景。二叉树的任意一个子节点是以它为根的一棵二叉树，这是一种递归的结构，用DFS访问二叉树极容易编码。

3.7.2二叉树的存储和编码
1. 二叉树的存储方法

如果要使用二叉树，首先得定义和存储它的节点。

二叉树的一个节点包括3个值: 节点的值、指向左孩子的指针、指向右孩子的指针。需要用一个结构体来定义二叉树。

二叉树的节点有动态和静态两种存储方法，在竞赛中一般使用静态方法。

（1） 动态存储二叉树。例如写C代码，数据结构的教科书一般这样定义二叉树的节点: 



1struct Node{
2 int value;//节点的值，可以定义多个值
3 Node *lson, *rson; //指针，分别指向左右子节点
4};






其中,value是这个节点的值，lson和rson是指向两个孩子的指针。在动态创建一个Node时，用new运算符动态申请一个节点。在使用完毕后，需要用delete释放它，否则会内存泄漏。动态二叉树的优点是不浪费空间，缺点是需要管理，不小心会出错，在竞赛中一般不这样用。

（2） 用静态数组存储二叉树。在算法竞赛中，为了编码简单，加快速度，一般用静态数组来实现二叉树。下面定义一个大小为N的结构体数组。N的值根据题目要求设定，有时节点多，例如N=100万，那么tree［N］使用的内存是12MB，不算大。



1struct Node{//静态二叉树
2 int value;//可以把value简写为v
3 int lson, rson;//左右孩子，可以把lson、rson简写为ls、rs
4}tree［N］;//可以把tree简写为t





tree［i］表示这个节点存储在结构体数组的第i个位置，lson是它的左孩子在结构体数组的位置，rson是它的右孩子在结构体数组的位置。lson和rson指向孩子的位置，也可以称为指针。



图3.10二叉树的静态存储




图3.10演示了一棵二叉树的存储，圆圈内的字母是这个节点的value值。根节点存储在tree［5］上，它的左孩子lson=7，表示左孩子存储在tree［7］上; 右孩子rson=3，表示右孩子存储在tree［3］上。该图中把tree简写为t，lson简写为l，rson简写为r。

在编码时一般不用tree［0］，因为0常被用来表示空节点，例如叶子节点tree［2］没有孩子，就把它的左右孩子赋值为lson=rson=0。

2. 二叉树存储的编码实现


下面写代码演示图3.10中二叉树的建立，并输出二叉树。

第16~21行建立二叉树，然后用print_tree()输出二叉树。



1#include <bits/stdc++.h>
2using namespace std;
3const int N=100;//注意const不能少
4struct Node{//定义静态二叉树结构体
5 char v;//把value简写为v
6 int ls, rs;//左右孩子，把lson、rson简写为ls、rs
7}t［N］;//把tree简写为t
8void print_tree(int u){//打印二叉树
9 if(u){
10cout<<t［u］.v<<' ';//打印节点u的值
11print_tree(t［u］.ls); //继续搜左孩子
12print_tree(t［u］.rs); //继续搜右孩子
13 }
14}
15int main(){

16 t［5］.v='A'; t［5］.ls=7; t［5］.rs=3;
17 t［7］.v='B'; t［7］.ls=2; t［7］.rs=0;
18 t［3］.v='C'; t［3］.ls=9; t［3］.rs=6;

19 t［2］.v='D';//t［2］.ls=0;t［2］.rs=0;可以不写，t［］是全局变量，已初始化为0

20 t［9］.v='E';//t［9］.ls=0; t［9］.rs=0; 可以不写
21 t［6］.v='F';//t［6］.ls=0; t［6］.rs=0; 可以不写
22 int root = 5;//根是tree［5］
23 print_tree(5); //输出： A B D C E F
24 return 0;
25}





初学者可能看不懂print_tree()是怎么工作的。它是一个递归函数，先打印这个节点的值t［u］.v，然后继续搜它的左右孩子。图3.10的打印结果是“A B D C E F”，步骤如下: 

（1） 打印根节点A。

（2） 搜左孩子，是B，打印出来。

（3） 继续搜B的左孩子，是D，打印出来。

（4） D没有孩子，回到B，发现B也没有右孩子，继续回到A。

（5） A有右孩子C，打印出来。

（6） 打印C的左右孩子E、F。

这个递归函数执行的步骤称为“先序遍历”，先输出父节点，再搜左右孩子并输出。

另外还有“中序遍历”和“后序遍历”，将在后面讲解。

3. 二叉树的极简存储方法

如果是满二叉树或者完全二叉树，有更简单的编码方法，连lson、rson都不需要定义，因为可以用数组的下标定位左右孩子。



图3.11一棵完全二叉树



一棵节点总数量为k的完全二叉树，设1号点为根节点（如图3.11所示），有以下性质: 

（1） p>1的节点，其父节点是p/2。例如p=4，父亲是4/2=2; p=5，父亲是5/2=2。

（2） 如果2×p>k，那么p没有孩子; 如果2×p+1>k，那么p没有右孩子。例如k=11，p=6的节点没有孩子; k=12，p=6的节点没有右孩子。

（3） 如果节点p有孩子，那么它的左孩子是2×p、右孩子是2×p+1。

在该图中圆圈内是节点的值，圆圈外的数字是节点的存储位置。

下面是代码。用ls(p)找p的左孩子，用rs(p)找p的右孩子。在ls(p)中把p*2写成p<<1，用了位运算。



1#include <bits/stdc++.h>
2using namespace std;
3const int N=100;//注意const不能少
4char t［N］;//简单地用一个数组定义二叉树
5int ls(int p){return p<<1;}//定位左孩子，也可以写成p*2
6int rs(int p){return p<<1 | 1;}//定位右孩子，也可以写成p*2+1
7int main(){

8 t［1］='A';t［2］='B';t［3］='C';
9 t［4］='D';t［5］='E';t［6］='F';t［7］='G';
10 t［8］='H';t［9］='I';t［10］='J'; t［11］='K';
11 cout<<t［1］<<":lson="<<t［ls(1)］<<" rson="<<t［rs(1)］; 

12//输出为A:lson=B rson=C
13 cout<<endl;

14 cout<<t［5］<<":lson="<<t［ls(5)］<<" rson="<<t［rs(5)］; 

15//输出为E:lson=J rson=K
16 return 0;
17}





其实，即使二叉树不是完全二叉树，而是普通二叉树，也可以用这种简单方法来存储。如果某个节点没有值，那么就空着这个节点不用，方法是把它赋值为一个不该出现的值，例如赋值为0或无穷大INF。这样虽然会浪费一些空间，但好处是编程非常简单。

3.7.3例题

二叉树是很基本的数据结构，大量算法、高级数据结构都是基于二叉树的。二叉树有很多操作，最基础的操作是搜索（遍历）二叉树的每个节点，有先序遍历、



图3.12二叉树例子



中序遍历、后序遍历。这3种遍历都用到了递归函数，二叉树的形态适合用递归来编程。图3.12所示为一个二叉树例子。

（1） 先（父）序遍历，父节点在最前面输出。先输出父节点，再访问左孩子，最后访问右孩子。该图的先序遍历结果是ABDCEF。为什么？把结果分解为ABDCEF。父亲是A，然后是左孩子B和它带领的子树BD，最后是右孩子C和它带领的子树CEF。这是一个递归的过程，每个子树也满足先序遍历，例如CEF，父亲是C，然后是左孩子E，最后是右孩子F。

（2） 中（父）序遍历，父节点在中间输出。先访问左孩子，然后输出父节点，最后访问右孩子。该图的中序遍历结果是DBAECF。为什么？把结果分解为DBAECF。DB是左子树，然后是父亲A，最后是右子树ECF。每个子树也满足中序遍历，例如ECF，先是左孩子E，然后是父亲C，最后是右孩子F。

（3） 后（父）序遍历，父节点在最后输出。先访问左孩子，然后访问右孩子，最后输出父节点。该图的后序遍历结果是DBEFCA。为什么？把结果分解为DBEFCA。DB是左子树，然后是右子树EFC，最后是父亲A。每个子树也满足后序遍历，例如EFC，先是左孩子E，然后是右孩子F，最后是父亲C。

这3种遍历，中序遍历是最有用的，它是二叉查找树的核心。






 
例3.16二叉树的遍历https://www.luogu.com.cn/problem/B3642



问题描述: 有一棵含n(n≤106)个节点的二叉树，给出每个节点的两个子节点的编号（均不超过n），建立一棵二叉树（根节点的编号为1），如果是叶子节点，则输入0 0。在建好这棵二叉树之后，依次求出它的先序、中序、后序遍历。

输入: 第一行一个整数n，表示节点数。之后n行，第i行两个整数l、r，分别表示节点i的左、右子节点编号。若l=0，表示无左子节点，r=0 同理。

输出: 输出3行，每行 n 个数字，用空格隔开。其中，
第一行是这个二叉树的先序遍历，
第二行是这个二叉树的中序遍历，
第三行是这个二叉树的后序遍历。


输入样例: 

7

2 7

4 0

0 0

0 3

0 0

0 5

6 0
输出样例: 

1 2 4 3 7 6 5

4 3 2 1 6 5 7

3 4 2 5 6 7 1


下面是代码。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 100005;
4struct Node{
5 int v; int ls, rs;
6}t［N］;//tree［0］不用，0表示空节点
7void preorder(int p){//求先序序列
8 if(p != 0){
9cout << t［p］.v <<" "; //先序输出
10preorder(t［p］.ls);
11preorder(t［p］.rs);
12 }
13}
14void midorder(int p){//求中序序列
15 if(p != 0){
16midorder(t［p］.ls);
17cout << t［p］.v <<" "; //中序输出
18midorder(t［p］.rs);
19 }
20}
21void postorder(int p){//求后序序列
22 if(p != 0){
23postorder(t［p］.ls);
24postorder(t［p］.rs);
25cout << t［p］.v <<" ";//后序输出
26 }
27}
28int main() {
29 int n; cin >> n;
30 for(int i = 1; i <= n; i++) {
31int a, b; cin >> a >> b;
32t［i］.v = i;
33t［i］.ls = a;
34t［i］.rs = b;
35 }
36 preorder(1); cout << endl;
37 midorder(1); cout << endl;
38 postorder(1); cout << endl;
39}





再看一道例题。






 
例3.172023年第十四届蓝桥杯省赛C/C++大学C组试题J: 子树的
大小lanqiaoOJ 3526




时间限制: 2s内存限制: 256MB本题总分: 25分

问题描述: 给定一棵包含n个节点的完全m叉树，节点按从根到叶、从左到右的顺序依次编号。例如图3.13是一棵拥有11个节点的完全3叉树。



图3.13一棵包含11个节点的完全3叉树







请求出第k个节点对应的子树拥有的节点数量。

输入: 输入包含多组询问。输入的第一行包含一个整数t，表示询问次数。接下来t行，每行包含3个整数n、m、k，表示一组询问。

输出: 一个正整数，表示答案。


输入样例: 

3

1 2 1

11 3 4

7 4 5 3

输出样例: 

1

2

24

评测用例规模与约定： 对于40%的评测用例，t≤50，n≤106，m≤16; 对于100%的评测用例，1≤t≤105，1≤k≤n≤109，2≤m≤109。


这一题可以帮助读者理解树的结构。

第u个节点的最左孩子的编号是多少？第u号节点前面有u-1个点，每个节点各有m个孩子，再加上1号节点，可得第u个节点的左孩子下标为(u-1)×m+2。例如该图中的3号节点，求它的最左孩子的编号。3号节点前面有两个点，即1号节点和2号节点，每个节点都有3个孩子，1号节点的孩子是2、3、4，2号节点的孩子是5、6、7，共6个孩子。那么3号节点的最左孩子的编号是1+2×3+1=8。

同理，第u个节点的孩子如果是满的，它的最右孩子的编号为u×m+1。

分析第u个节点的情况: 

① 节点u在最后一层。此时节点u的最左孩子的编号大于n，即(u-1)×m+2>n，说明这个孩子不存在，也就是说节点u在最后一层，那么以节点u为根的子树的节点数量是1，就是u自己。

② 节点u不是最后一层，且u的孩子是满的，即最右孩子的编号u×m+1≤n。此时可以继续分析u的孩子的情况。

③ 节点u不是最后一层，u有左孩子，但是孩子不满，此时u在倒数第2层，它的最右孩子的编号就是n。以u为根的子树的数量=右孩子编号-(左孩子编号-1)+u自己，即n-((u-1)×m+1)+1=n-u×m+m。

下面用两种方法求解。

（1） DFS，通过40%的测试。DFS在第6章讲解，请读者在学过第6章后回头看这个方法。

在情况2），用DFS继续搜u的所有孩子，下面的代码实现了上述思路。

代码的计算量是多少？每个点都要计算一次，共t组询问，所以总复杂度是O(nt)，只能通过40%的测试。



1#include <iostream>
2using namespace std;
3typedef long long ll;//注意要用long long，因为下面m*u可能超过int
4ll dfs(ll n, ll m, ll u) {

5 ll ans = 1;//u点自己算一个
6 if(m*u - (m-2) > n) return 1;//情况1)，u点在最后一层, ans=1
7 else if(m*u + 1 <=n) {//情况2)，u在倒数第2层且孩子满了

8for(ll c = m*u - (m-2); c <=m*u + 1; c++)//深搜u的每个孩子



9ans += dfs(n, m, c);//累加每个孩子的数量
10return ans;
11 }
12 else return n + m - m*u;//情况3)，u在倒数第2层且孩子不满
13}
14int main() {
15 int t; cin >> t;
16 while(t--) {
17ll n, m, k;cin >> n >> m >> k;
18cout << dfs(n,m,k) << endl;
19 }
20 return 0;
21}





（2） 模拟。

上面的DFS方法，对于情况2），把每个点的每个孩子都做了一次DFS，计算量很大。

其实每一层算一次就行了，在情况2）时每一层也只需要算一次。以题目的图为例，计算点1为根的节点数量。1号节点这一层有1个; 它的下一层是满的，有3个，左孩子是2，右孩子是4; 再下一层，2号节点的左孩子是5，4号节点的孩子是11，那么这一层有11-5+1=7个。累加得1+3+7=11。

计算量是多少？每一层只需要计算一次，共O(log2n)层，t组询问，总计算复杂度是O(tlog2n)，能通过100%的测试。



1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;//注意要用long long，因为下面m*u可能超过int
4int main(){
5 int t; cin >> t;
6 while(t--){
7ll n,m,k;
8cin >> n >> m >> k;

9ll ans = 1;//初值为1，即k点自己
10ll ls = k, rs = k;//从k点开始，分析它的最左和最右孩子

11while(1) {//从第k点开始一层一层往下计算直到最后一层

12ls =(ls-1)*m + 2; //这一层的最左孩子
13rs = rs*m + 1;//这一层的最右孩子
14if(ls > n) break; //情况1)，已经到最后一层，结束
15if(rs >=n){//情况3)，孩子不满 
16ans += n-ls+1;//加上孩子数量
17break;//结束
18}
19ans += rs-ls+1;//情况2)，这一层是满的，累加这一层的所有孩子
20}
21cout << ans <<endl;
22 }
23 return 0;
24}





再看一道例题。






 
例3.18FBI树lanqiaoOJ 571



问题描述: 可以把由“0”和“1”组成的字符串分为3类，全“0”串称为B串，全“1”串称





为I串，既含“0”又含“1”的串称为F串。FBI树是一种二叉树，它的节点类型也包括F节点、B节点和I节点3种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下: 

（1） T的根节点为R，其类型与串S的类型相同。

（2） 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2; 由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

输入: 第一行是一个整数N（0≤N≤10）。第二行是一个长度为 2N的 “01” 串。

输出: 输出一个字符串，即 FBI 树的后序遍历序列。


输入样例: 

3

10001011
输出样例: 

IBFBBBFIBFIIIFF

评测用例规模与约定： 对于40%的评测用例，N≤2; 对于100%的评测用例，N≤10。


首先确定用满二叉树来存题目的FBI树，满二叉树用静态数组实现。当题目中N=10时，串的长度是2N=1024，有1024个元素，需要建一棵大小为4096的二叉树tree［4096］。

题目要求建一棵满二叉树，从左到右的叶子节点就是给定的串S，并且把叶子节点按规则赋值为字符F、B、I，它们上一层的父节点上也按规则赋值为字符F、B、I。最后用后序遍历打印二叉树。

下面是代码。



1#include <bits/stdc++.h>
2using namespace std;
3char s［1100］,tree［4400］;//tree［］存满二叉树
4int ls(int p){return p<<1;}//定位左儿子：p*2
5int rs(int p){return p<<1|1;}//定位右儿子：p*2+1
6void build_FBI(int p,int left,int right){
7if(left==right){//到达叶子节点
8if(s［right］=='1') tree［p］='I';
9else tree［p］='B';
10return;
11 }
12 int mid=(left+right)/2;//分成两半
13build_FBI(ls(p),left,mid);//递归左半
14build_FBI(rs(p),mid+1,right);//递归右半
15 if(tree［ls(p)］=='B' && tree［rs(p)］=='B')//左右儿子是B，自己也是B
16tree［p］='B';

17 else if(tree［ls(p)］=='I'&&tree［rs(p)］=='I'）//左右儿子是I，自己也是I


18tree［p］='I';
19else tree［p］='F';
20}
21void postorder(int p){//后序遍历
22 if(tree［ls(p)］) postorder(ls(p));
23 if(tree［rs(p)］) postorder(rs(p));
24printf("%c",tree［p］);
25}
26int main(){
27 int n;cin >>n;
28 cin >>s+1;
29build_FBI(1,1,strlen(s+1));
30 postorder(1);
31}





【练习题】

lanqiaoOJ: 完全二叉树的权值183。

洛谷: American Heritage P1827，求先序排列P1030。






3.8并查集
并查集通常被认为是一种“高级数据结构”，可能是因为用到了集合这种“高级”方法。不过，并查集的编码很简单，数据存储方式也仅用到了最简单的一维数组，可以说并查集是“并不高级的高级数据结构”。

并查集，英文为Disjoint Set，直译是“不相交集合”。意译为“并查集”非常好，因为它概括了并查集的3个要点: 并、查、集。并查集是“不相交集合上的合并、查询”。

并查集精巧、实用，在算法竞赛中很常见，原因有三点: 简单且高效、应用很直观、容易和其他数据结构与算法结合。并查集的经典应用有判断连通性、最小生成树Kruskal算法并查集是Kruskal算法的绝配，如果不用并查集，Kruskal算法很难实现。本作者曾拟过一句赠言: “Kruskal对并查集说，咱们一辈子是兄弟！”、最近公共祖先（Least Common Ancestors，LCA）等。

通常用“帮派”的例子来说明并查集的应用背景。在一个城市中有n个人，他们分成不同的帮派; 给出一些人的关系，例如1号、2号是朋友，1号、3号也是朋友，那么他们都属于一个帮派; 在分析完所有的朋友关系之后，问有多少个帮派，每个人属于哪个帮派。给出的n可能大于106。如果用并查集实现，不仅代码很简单，而且计算复杂度几乎是O(1)，效率极高。

并查集效率高，是因为用到了“路径压缩本作者曾拟过一句赠言: “路径压缩担任总经理之后，并查集公司的管理效能实现了跨越式发展。””这一技术。

3.8.1并查集的基本操作

用“帮派”的例子说明并查集的3个基本操作: 初始化、合并、查找。

（1） 初始化。在开始的时候，帮派的每个人是独立的，相互之间没有关系。把每个人抽象成一个点，每个点有独立的集，n个点就有n个集。也就是说，每个人的帮主就是自己，共有n个帮派。

如何表示集？非常简单，用一维数组int s［］来表示，s［i］的值就是点i所属的并查集。初始化s［i］=i，也就是说，点i的集就是s［i］=i，例如点1的集s［1］=1，点2的集s［2］=2，等等。

用图3.14说明并查集的初始化。左边的图给出了点i与集s［i］的值，下画线数字表示集。右边的图表示点和集的逻辑关系，用圆圈表示集，方块表示点。初始时，每个点属于独立的集，5个点有5个集。




图3.14并查集的初始化



（2） 合并。把两个点合并到一个集，就是把两个人所属的帮派合并成一个帮派。

如何合并？如果s［i］=s［j］，就说明i和j属于同一个集。操作很简单，把它们的集改成一样即可。下面举例说明。

例如点1和点2是朋友，把它们合并到一个集。具体操作是把点1的集1改成点2的集2，s［1］=s［2］=2。当然，把点2的集改成点1的集也行。经过这个合并，1和2合并成一个帮，帮主是2。

图3.15演示了合并的结果，此时有5个点，有4个集，其中s［2］包括两个点。




图3.15合并(1，2)



下面继续合并，合并点1和点3。合并的结果是让s［1］=s［3］。

首先查找点1的集，发现s［1］=2。再继续查找点2的集，s［2］=2，点2的集是自己，无法继续，查找结束。这个操作是查找1的帮主。

再查找点3的集，s［3］=3。由于s［2］不等于s［3］，说明2和3属于不同的帮派。下面把点2的集2合并到点3的集3。具体操作是修改s［2］=3，也就是让2的帮主成为3。此时，点1、2、3都属于一个集: s［1］=2、s［2］=3、s［3］=3。1的上级是2，2的上级是3，这3个人的帮主是3，形成了一个多级关系。

图3.16演示了合并的结果。为了简化图示，把点2和集2画在了一起。




图3.16合并(1，3)



继续合并，合并点2和点4。结果如图3.17所示，合并过程请读者自己分析。合并的结果是s［1］=2、s［2］=3、s［3］=4、s［4］=4。4是1、2、3、4的帮主。另外还有一个独立的集s［5］=5。




图3.17合并(2，4)



（3） 查找某个点属于哪个集。从上面的图示可知，这是一个递归的过程，例如找点1的集，递归步骤是s［1］=2、s［2］=3、s［3］=4、s［4］=4，最后点的值和它的集相等，递归停止，就找到了集。

（4） 统计有几个集。只要检查有多少个点的集等于自己（自己是自己的帮主），就有几个集。如果s［i］=i，这是这个集的根节点，是它所在的集的代表（帮主）; 统计根节点的数量，就是集的数量。在上面的图示中，只有s［4］=4、s［5］=5，有两个集。

从上面的图中可以看到，并查集是“树的森林”，一个集是一棵树，有多少棵树就有多少个集。有些树的高度可能很大（帮会中每个人都只有一个下属），递归步骤是O(n)的。此时这个集变成了一个链表，出现了并查集的“退化”现象，使得递归查询十分耗时。这个问题可以用“路径压缩”来彻底解决。经过路径压缩后的并查集，查询效率极高，是O(1)的。

用下面的例题给出并查集的基本操作的编码。






 
例3.19亲戚https://www.luogu.com.cn/problem/P1551



问题描述: 若某个家族人员过多，要判断两个人是否为亲戚，确实很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定: x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x和y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 

输入: 第一行有3个整数n、m、p,n、m、p≤5000，分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行，每行两个数Mi、Mj、1≤Mi，Mj≤n，表示Mi和Mj有亲戚关系。接下来p行，每行两个数Pi、Pj，询问Pi，Pj是否为一个亲戚关系。

输出: 输出p行，每行一个Yes或No，表示第i个询问的答案为“具有”或“不具有”亲戚关系。



输入样例: 

6 5 3

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6
输出样例: 

Yes

Yes

No


下面是并查集的代码。

（1） 初始化init_set()。

（2） 查找find_set()。这是一个递归函数，若x==s［x］，则这是一个集的根节点，结束。若x!=s［x］，继续递归查找根节点。

（3） 合并merge_set(x，y)。合并x和y的集，先递归找到x的集，再递归找到y的集，然后把x合并到y的集上。如图3.18所示，x递归到根b，y递归到根d，最后合并为set［b］=d。合并后，这棵树变长了，查询效率变低。




图3.18合并






1#include <bits/stdc++.h>
2using namespace std;
3const int N = 5010;
4int s［N］;
5void init_set(){//初始化
6 for(int i=1; i<=N; i++) s［i］ = i;
7}
8int find_set(int x){//查找
9 //if(x==s［x］) return x;
10 //else return find_set(s［x］);//这两行合并为下面的一行
11 return x==s［x］? x:find_set(s［x］);
12}
13void merge_set(int x, int y){//合并
14 x = find_set(x);
15 y = find_set(y);
16 if(x != y) s［x］ = s［y］;//y成为x的上级，x的集改成是y的集
17}
18int main(){
19 init_set();
20 int n,m,p; cin>>n>>m>>p;
21 while(m--){//合并
22int x,y; cin>>x>>y;
23merge_set(x, y);
24 }
25 while(p--){//查询
26int x,y; cin>>x>>y;

27if(find_set(x)==find_set(y)) cout << "Yes"<<endl;
28else cout << "No"<<endl;
29 }
30 return 0;
31}





下面用路径压缩来优化并查集的退化问题。

3.8.2路径压缩

在做并查集题目时，一定需要用到“路径压缩”这个优化技术。路径压缩是并查集真正的核心，不过它的原理和代码极为简单。

在上面的查询函数find_set()中，查询元素i所属的集，需要递归搜索整个路径直到根节点，返回值是根节点。这条搜索路径可能很长，导致超时。

如何优化？如果在递归返回的时候，顺便把这条路径上所有的点所属的集改成根节点（所有人都只有帮主一个上级，不再有其他上级），那么下次再查这条路径上的点属于哪个集，就能在O(1)的时间内得到结果。如图3.19的左图所示，在第一次查询点1的集时，需要递归路径查3次，在递归返回时，把路径上的1、2、3所属的集都改成4，使得所有点的集都是4，如右图所示。下次再查询1、2、3、4所属的集，只需递归一次，就查到了根。




图3.19路径压缩



路径压缩的代码非常简单。把上面代码中的find_set()改成以下路径压缩的代码。



1int find_set(int x){
2 if(x != s［x］) s［x］ = find_set(s［x］); //路径压缩
3 return s［x］;
4}






以上介绍了查询时的路径压缩，那么合并时也需要做路径压缩吗？一般不需要，因为合并需要先查询，查询用到了路径压缩，间接地优化了合并。

在路径压缩之前，查询和合并都是O(n)的。经过路径压缩之后，查询和合并都是O(1)的，并查集显示出了巨大的威力。

3.8.3例题







 
例3.20修复公路https://www.luogu.com.cn/problem/P1111



问题描述: A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路，给出A地区的村庄数N和公路数M，公路是双向的，告知每条公路连着哪两个村庄，并告知什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两个村庄都至少存在一条修复完成的道路（可以由多条公路连成一条道路）。

输入: 第一行两个正整数N、M。下面M行，每行3个正整数x、y、t，告知这条公路连着x和y两个村庄，在时间t时能修复完成这条公路。

输出: 如果全部公路修复完毕仍然存在两个村庄无法通车，输出-1，否则输出最早什么时候任意两个村庄能够通车。 


输入样例: 

4 4

1 2 6

1 3 4

1 4 5

4 2 3
输出样例: 

5
评测用例规模与约定： 1≤x，y≤N≤103，1≤M，t≤105。


题目看起来像图论的最小生成树，不过用并查集可以简单地解决。

本题实际上是连通性问题，连通性也是并查集的一个应用场景。

先按时间t把所有道路排序，然后按时间t从小到大逐个加入道路，合并村庄。如果在某个时间所有村庄已经通车，这就是最小通车时间，输出并结束。如果所有道路都已经加入，但是还有村庄没有合并，就输出-1。

用并查集处理村庄合并，在合并时统计通车村庄的数量。

下面的代码没有写合并函数merge_set()，而是把合并功能写在第19~21行，做了灵活处理。第20行，如果村庄x、y已经连通，那么连通的村庄数量不用增加; 第21行，如果x、y没有连通，则合并并查集。



1#include <bits/stdc++.h>
2using namespace std;
3struct node{int x,y,t;} e［100010］;
4bool cmp(node a, node b){return a.t<b.t;}//sort函数的比较
5int s［100010］;
6int find_set(int x){//用"路径压缩"优化的查询
7 if(x != s［x］) s［x］ = find_set(s［x］);//路径压缩
8 return s［x］;
9}
10int main(){
11 int n,m; scanf("%d%d",&n,&m);
12 for(int i=1;i<=m;i++) s［i］=i;//并查集的初始化
13 for(int i=1;i<=m;i++) 
14scanf("%d%d%d",&e［i］.x,&e［i］.y,&e［i］.t);
15 sort(e+1,e+1+m,cmp);//按时间t排序
16 int ans=0;//答案，最早通车时间
17 int num=0;//已经连通的村庄数量
18 for(int i=1;i<=m;i++){

19int x=find_set(e［i］.x), y=find_set(e［i］.y);

20if(x==y) continue;//x、y已经连通，num不用增加
21s［x］=y;//合并并查集，即把村庄x合并到y上

22num++;//连通的村庄加1
23ans = max(ans,e［i］.t);//当前最大通车时间
24 }
25 if(num!=n-1) printf("-1＼n");
26 else printf("%d＼n",ans);
27 return 0;
28}





再看一道比较难的例题。






 
例3.212019年第十届蓝桥杯省赛C/C++大学A组试题H: 修改数组
lanqiaoOJ 185




时间限制: 1s内存限制: 256MB本题总分: 20分

问题描述: 给定一个长度为N的数组A=［A1，A2,…，AN］，数组中可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2、A3、…、AN。当修改Ai时，小明会检查Ai是否在A1~ Ai-1中出现过。如果出现过，则小明会给Ai加上1; 如果新的Ai仍在之前出现过，小明会持续给Ai加1，直到Ai没有在A1~Ai-1中出现过。当AN也经过上述修改之后，显然A数组中就没有重复的整数





了。给定初始的A数组，请计算出最终的A数组。

输入: 第一行包含一个整数N，第二行包含N个整数A1，A2，…，AN。

输出: 输出N个整数，依次是最终的A1，A2，…，AN。


输入样例: 

5

2 1 1 3 4
输出样例: 

2 1 3 4 5

评测用例规模与约定： 对于80%的评测用例，1≤N≤10000; 对于所有评测用例，1≤N≤100000，1≤Ai≤1000000。


这是一道好题，很难想到可以用并查集来做。

先尝试暴力的方法: 每读入一个新的数，就检查前面是否出现过，每一次需要检查前面所有的数。共有n个数，每个数检查O(n)次，所以总复杂度是O(n2)，写代码提交可能通过30%的测试。

大家容易想到一个改进的方法: 用hash。定义vis［］数组，vis［i］表示数字i是否已经出现过。这样就不用检查前面所有的数了，基本上可以在O(1)的时间内定位到。

然而，本题有一个特殊的要求: “如果新的Ai仍在之前出现过，小明会持续给Ai加1，直到Ai没有在A1~Ai-1中出现过。”这导致在某些情况下仍然需要大量的检查。以5个6为例: A［］={6，6，6，6，6}。

第一次读A［1］=6，设置vis［6］=1。

第二次读A［2］=6，先查到vis［6］=1，则把A［2］加1，变为A［2］=7; 再查vis［7］=0，设置vis［7］=1。检查了两次。

第三次读A［3］=6，先查到vis［6］=1，则把A［3］加1得A［3］=7; 再查到vis［7］=1，再把A［3］加1得A［3］=8，设置vis［8］=1; 最后查vis［8］=0，设置vis［8］=1。检查了3次。

……

每次读一个数，仍需检查O(n)次，总复杂度仍然是O(n2)。

下面给出hash代码，提交后能通过80%的测试。



1#include <bits/stdc++.h>
2using namespace std;
3const int N=1000002;//A的hash，1≤Ai≤1000000
4int vis［N］;//hash: vis［i］=1表示数字i已经存在
5int main(){
6 int n; 
7 scanf("%d",&n);
8 for(int i=0;i<n;i++){
9int a; 
10scanf("%d",&a);//读一个数字

11while(vis［a］==1)//若a已经出现过，加1。若a加1后再出现，则继续加1

12a++;
13vis［a］=1;//标记该数字
14printf("%d ",a);//打印
15 }
16}





这道题用并查集非常巧妙。

前面提到，本题用hash方法，在特殊情况下仍然需要大量的检查。问题出在“持续给Ai加1，直到Ai没有在A1~Ai-1中出现过”。也就是说，问题出在那些相同的数字上。当处理一个新的A［i］时，需要检查所有与它相同的数字。

如果把这些相同的数字看成一个集合，就能用并查集处理。

用并查集s［i］表示访问到i这个数时应该将它换成的数字。以A［］={6，6，6，6，6}为例。初始化时set［i］=i，处理过程如图3.20所示。





图3.20用并查集处理数组A



图3.20(a)读第一个数A［0］=6。6的集set［6］=6。紧接着更新set［6］=set［7］=7，作用是后面再读到某个A［k］=6时，可以直接赋值A［k］=set［6］=7。

图3.20(b)读第二个数A［1］=6。6的集set［6］=7，更新A［1］=7。紧接着更新set［7］=set［8］=8。如果后面再读到A［k］=6或7时，可以直接赋值A［k］=set［6］=8或者A［k］=set［7］=8。

图3.20(c)读第三个数A［2］=6。请读者自己分析。

下面是C++代码，只用到并查集的查询，没用到合并，必须用“路径压缩”优化才能加快查询速度，通过100%的测试。没有路径压缩，仍然超时。



1#include <bits/stdc++.h>
2using namespace std;
3const int N = 1000002;
4int A［N］;
5int s［N］;//并查集
6int find_set(int x){//用“路径压缩”优化的查询
7 if(x != s［x］) s［x］ = find_set(s［x］);//路径压缩
8 return s［x］;
9}
10int main(){
11 for(int i=1;i<N;i++) s［i］=i;//并查集的初始化
12 int n; 
13 scanf("%d",&n);
14 for(int i=1;i<=n;i++){
15scanf("%d",&A［i］);
16int root = find_set(A［i］);//查询到并查集的根
17A［i］ = root;
18s［root］ = find_set(root+1); //加1

19 }
20 for(int i=1;i<=n;i++) printf("%d ",A［i］);
21 return 0;
22}





【练习题】

lanqiaoOJ: 蓝桥幼儿园1135、简单的集合合并3959、合根植物110。

洛谷: 一中校运会之百米跑P2256、村村通P1536、家谱P2814、选择题P6691。





3.9扩 展 学 习
数据结构是算法大厦的砖石，它们渗透在所有问题的代码实现中。数据结构和算法密不可分。

本章介绍了一些基础数据结构: 数组、链表、队列、栈、二叉树。在竞赛中这些数据结构可以用STL实现，也可以手写代码实现。STL应该重点掌握，大多数题目能直接用STL实现，编码简单、快捷，不容易出错。如果需要手写数据结构，一般都使用静态数组来模拟，这样做编码快且不容易出错。

对于基础数据结构，程序员应该不假思索地、条件反射般地写出来，使得它们成为大脑的“思想钢印”。

在学习基础数据结构的基础上可以继续学习高级数据结构。大部分高级数据结构很难，是算法竞赛中的难题。在蓝桥杯这种短时个人赛中，高级数据结构并不多见，近年来考过并查集、线段树。读者可以多练习线段树，线段树是标志性的中级知识点，是从初级水平进入中级水平的里程碑。

学习计划可以按以下知识点展开。

中级: 树上问题、替罪羊树、树状数组、线段树、分块、莫队算法、块状链表、LCA、树上分治、Treap树、笛卡儿树、KD树。

高级: Splay树、可持久化线段树、树链剖分、FHQ Treap树、动态树、LCT。

在计算机科学中，各种数据结构的设计、实现、应用非常精彩，它们对数据的访问方式、访问的效率、空间利用各有侧重。通过合理选择和设计数据结构，可以优化算法的执行时间和空间复杂度，从而提高程序的性能。