数据结构基础
第一部分
栈
栈的性质
栈是一种后入先出的数据结构，只能在一端进行插入和删除操作，这一端是栈顶，另外一端是栈底。
如图所示
栈的相关概念
栈顶：能插入和删除数据的一端。
栈底：最早加入的数据，栈顶的另一端。
入栈：将数据加入栈中，也叫压栈.
出栈：将数据从栈中删除，也叫弹栈。
栈的常用操作
使用数组简单暴力去模拟栈的常用操作
#include <iostream>
using namespace std;
struct stack {
int Nums[1005];
int TopIndex = 0;
void push(int Number) {
Nums[++TopIndex] = Number;
}
void pop() {
--TopIndex;
}
int top() {
return Nums[TopIndex];
}
int size() {
return TopIndex;
}
bool empty() {
return TopIndex == 0;
}
};
**使用标准库的栈需要引入头文件 **
///常用操作如下
#include <stack>
using namespace std;
stack <int> st;
//"< >" 中写栈中元素的数据类型
//创建了一个栈中元素是int类型的栈
st.empty(); // 判断栈是否为空，如果栈是空的，返回值是true, 否则返回值是false。
st.size(); // 查找栈中存在几个元素，返回值是栈中元素的个数。
st.pop(); // 出栈操作，从栈顶删除一个元素。
st.push(); // 括号中添加匹配的数据类型，入栈操作，向栈顶添加一个元素。
st.top(); // 查找栈顶的元素，栈只能查找栈顶的元素。
栈的应用场景
括号匹配
洛谷P1739
利用栈后入先出的特性完成工作，当查找到'('时，执行入栈操作，当查找到')'时，查找栈顶的元素是不是'('，若栈顶元素是'('，或者此时栈为空，则括号是不匹配的, 若栈顶元素是'('，则将匹配的括号出栈
#include <iostream>
#include <stack>
using namespace std;
stack <char> st;
string s;
bool check() {
for(char c : s) {
if(c == '(') st.push(c);
else if(c == ')') {
if(st.empty() || st.top() != '(') return false;
st.pop();
//将匹配的括号出栈，匹配其他括号
}
}
if(st.empty()) return true;
//最后如果栈不是空的，说明有没有被匹配的'(';
return false;
}
int main() {
cin >> s;
if(check()) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
第二部分
队列
队列的性质
和栈相反，队列是一种先入先出的数据结构，队列只允许在一端插入，在另外一端删除。 插入的一端叫队尾(rear)，进行删除的一端叫队头(front)。
如图所示：
队列的相关概念
队头：进行删除元素的一端
队尾：进行插入元素的一端
入队：向队列中插入元素
出队：从队列中删除元素
队列的常用操作
非常暴力的方式模拟队列的操作
#include <iostream>
using namespace std;
struct queue {
int Nums[1005];
int FrontIndex = 1, RearIndex = 0;
void push(int Number) {
Nums[++RearIndex] = Number;
}
void pop() {
++FrontIndex;
}
int front() {
return Nums[FrontIndex];
}
int Size() {
return RearIndex - FrontIndex + 1;
}
bool empty() {
return FrontIndex == RearIndex + 1;
}
};
使用标准库的队列要引入头文件
#include <queue>
using namespace std;
queue <int> q;
// < > 中写队列中元素的数据类型
q.push(); // 括号中写相匹配的数据类型，将这个数据从队尾入队。
q.pop(); // 出队操作，从队头删除一个元素。
q.size(); // 查找队列中有多少个元素，返回值是队列中的元素个数。
q.front(); // 查找队头元素，队列只能查找队头元素。
q.empty(); // 查找队列是否为空，如果队列为空，返回值是true，不为空，返回值是false。
双端队列
双端队列的性质
双端队列是一种具有队列和栈的性质的数据结构。双端队列中的两端都可以做到弹出元素和插入元素的操作。 双端队列的相关概念基本和队列相同。
双端队列的常用操作
使用标准库的双端队列要引入头文件
#include <deque>
using namespace std;
deque <int> q;
// < > 中写队列元素的数据类型
q.push_back(); // 括号中写一个元素，加入队列尾
q.push_front(); // 括号中写一个元素，加入队列头
q.pop_front(); // 从队头弹出一个元素
q.pop_back(); // 从队尾弹出一个元素
q.size(); // 返回值是队列中元素的个数
q.empty(); // 判断队列是否为空，若队列为空，返回值是true，否则返回值是false。
q.front(); // 返回队头元素
q.back(); // 返回队尾元素
双端队列的应用场景
滑动窗口求最值
以求滑动窗口的最小值为例
维护单调队列解决滑动窗口问题，维护一个单调递增的队列。
这个队列有以下两个性质：
1、队列中的元素单调递增
2、队列中元素在原数组中的下标也是单调递增
首先说采取的策略是什么。
当查找到当前数字时，从队头下标出窗口的数字出队列，从队尾查看数字，将队尾大于等于当前数字的数字出队，重复此过程，直到队列为空，或者队尾数字小于当前数字。然后加入当前数字，这样保证了队列中元素是单调递增的，保证了队列中元素在原数组中的下标也是单调递增的，检查队头的数字在原数组中的下标，将下标已经出滑动窗口的元素出队。每个窗口的最小值就是队头的元素。
策略如图所示：
8个数字， 窗口大小是3， 求最小值。
开始时对于3个数字操作
队列为空直接将1入队列，向后查找，查找到数字3，此时队尾的数字1小于3，将3入队列，向后查找到-1，此时队尾元素是3大于-1，将3出队列，再次查找队尾元素是1，大于-1，将1出队列，队列为空，-1入队列。入队操作同时也要记录下标。
此时队列中的元素有：
输出队头的元素的值，队头元素的值就是该窗口的最小值。
向后查找到数组中的第四个数字，数字的值是-3。
查看队列中队头元素的下标，下标是3，没有出窗口。
查看队列中队尾元素的值，元素的值是-1大于-3，将队尾元素出队列，此时队列为空，将-3加入队列。
此时队列中的元素有：
输出队头的元素的值，队头元素的值就是该窗口的最小值。
向后查找到数组中第五个数字，数字的值是5。
查看队列中队头元素的下标，下标是4，没有出窗口。
查看队列中队尾元素的值，元素的值是-3小于5，将5加入队列。
此时队列中的元素：
输出队头元素的值，队头元素的值就是该窗口的最小值。
向后查找到数组中第六个数字，数字的值是3。
查看队列中队头元素的下标，下标是4，没有出窗口。
查看队列中队尾元素的值，元素的值是5大于3，将队尾元素出队列，查看队列中队尾元素的值，元素的值是-3小于3，将3加入队列。
此时队列中的元素：
输出队头元素的值，队头元素的值就是该窗口的最小值。
向后查找到数组中第七个数字，数字的值是6.
查看队列中队头元素的下标，下标是4，出窗口，将队头元素出队列。
查看队列中队尾元素的值，元素的值是3小于6，将6加入队列。
此时队列中的元素：
输出队头元素的值，队头元素的值就是该窗口的最小值。
向后查找到数组中第八个数字，数字的值是7.
查看队列中队头元素的下标，下标是4，出窗口，将队头元素出队列。
查看队列中队尾元素的值，元素的值是3小于6，将6加入队列。
此时队列中的元素：
输出队头元素的值，队头元素的值就是该窗口的最小值。
为什么使用这样的策略？
当查找到的当前数字小的时候，当前数字一定在该窗口之内，然后直接将队尾所有大于当前数字的数字出队，出队的这些数字一定不会对答案有影响，对于当前窗口来说，最小值一定不是这些数字，对于后面的窗口，最小值也一定不是这些数字，因为当前查找到的数字更小，而且下标靠后。
代码部分：
#include <cstdio>
#include <deque>
using namespace std;
const int MAXN = 1e6 + 10;
int n, k, Nums[MAXN];
long long Min = 1e18;
long long Max = -Min;
deque <pair <int, int> > q;
// first 保存的是元素的值
// second 保存的是元素的下标
int main() {
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &Nums[i]);
for(int i = 1; i <= k; i++) {
while(!q.empty() && q.back().first >= Nums[i]) q.pop_back();
q.push_back(make_pair(Nums[i], i));
}
printf("%d", q.front().first);
for(int i = k + 1; i <= n; i++) {
if(!q.empty() && i - q.front().second + 1 > k) q.pop_front();
while(!q.empty() && q.back().first >= Nums[i]) q.pop_back();
q.push_back(make_pair(Nums[i], i));
printf(" %d", q.front().first);
}
putchar('\n');
while(!q.empty()) q.pop_front();
for(int i = 1; i <= k; i++) {
while(!q.empty() && q.back().first <= Nums[i]) q.pop_back();
q.push_back(make_pair(Nums[i], i));
}
printf("%d", q.front().first);
for(int i = k + 1; i <= n; i++) {
if(!q.empty() && i - q.front().second + 1 > k) q.pop_front();
while(!q.empty() && q.back().first <= Nums[i]) q.pop_back();
q.push_back(make_pair(Nums[i], i));
printf(" %d", q.front().first);
}
}
/*
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
*/
优先队列
优先队列的性质
优先队列一般用二叉堆来实现，二叉堆的实现不做讲解。
优先队列可以取出队列中优先值最大的元素，以及将队列中优先值最大的元素出队。
入队的元素会自动按照优先级排列。
优先队列的相关概念
队头：队列中优先级最大的元素。
出队：删除队列中优先级最大的元素。
入队：向优先队列中加入元素
优先队列的常用操作
使用标准库的优先度列有引入头文件
#include <queue>
using namespace std;
priority_queue <int> q;
// "< >" 中写优先队列总元素的数据类型
//
q.empty() // 判断优先队列是否为空，如果是空返回true，否则返回false。
q.push() // 向队列中加入元素，并按照元素的优先顺序排序。
q.pop() // 从队列中删除优先级最大的元素。
q.top() // 返回队列中优先级最大的元素
q.size() // 返回队列中的元素的个数
注意其中的 操作单次的时间复杂度是。
那么优先队列中的优先级是什么呢？
当我们不手动设置优先级的时候，认为数值大的优先级高。
看下面的代码：
#include <queue>
#include <iostream>
using namespace std;
priority_queue <int> q;
// "< >" 中写优先队列中数据的类型
// 创建了一队列中元素是int类型的优先队列
int nums[] = {1, 3, 6, 2, 45, 7, 8, 2, 4};
int main() {
for(int i = 0; i < 9; i++) q.push(nums[i]);
while(!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
/*
输出
45
8
7
6
4
3
2
2
1
*/
如果我们要使得数值小的优先级更高呢？
#include <queue>
#include <iostream>
using namespace std;
priority_queue <int, vector<int>, greater<int> > q;
// "< >" 中写优先队列中数据的类型
// 创建了一队列中元素是int类型的优先队列
int nums[] = {1, 3, 6, 2, 45, 7, 8, 2, 4};
int main() {
for(int i = 0; i < 9; i++) q.push(nums[i]);
while(!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
当然也可以自定义排序的规则：
例如为每一个元素含有三个int类型的优先队列设置优先级为：
第一个数字大的优先级高；
第一个数字相同时，第二个数字小的优先级高；
第二个数字相同时，第三个数字大的优先级高。
可以使用重载运算符的方法
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int x, y, z;
bool operator < (const Node & b) const {
if(x == b.x && y == b.y) return z < b.z;
if(x == b.x) return y > b.y;
return x < b.x;
}
};
priority_queue <Node> q;
int main() {
q.push(Node{1, 2, 3});
q.push(Node{1, 3, 2});
q.push(Node{1, 3, 3});
q.push(Node{2, 1, 1});
while(!q.empty()) {
cout << q.top().x << " " << q.top().y << " " << q.top().z << endl;
q.pop();
}
return 0;
}
优先队列的应用场景
合并果子
经典的优先队列问题.
贪心的策略是每次选取最小的两堆果子合并，用优先队列维护最小值即可。
#include <iostream>
#include <queue>
using namespace std;
priority_queue <int, vector<int>, greater<int> > q;
int main() {
int n, Sum = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
int Number;
cin >> Number;
q.push(Number);
}
while(q.size() != 1) {
int First = q.top();
q.pop();
int Second = q.top();
q.pop();
Sum += First;
Sum += Second;
q.push(First + Second);
}
cout << Sum << endl;
return 0;
}
第三部分
静态链表
算法竞赛中的链表使用时大都是静态链表，所以这里也仅介绍静态链表。
直接通过一道题目引入静态链表。
对于本题目使用静态链表可以O(1)完成使得队列的排布。
静态链表结点中的元素：
struct Node {
int FrontPos = 0, NextPos = 0;
} Queue[MAXN];
Queue[Index].FrontPos代表的是当前元素的左边的元素。
Queue[Index].NextPos代表的是当前元素的右边的元素。
Index 代表的是当前元素的编号。
假设我们现在有这样的队列:
3, 4, 5
3 右边是 3， 4 右边是 5。
数据结构图化 :
#include <cstdio>
using namespace std;
const int MAXN = 100010;
struct Node {
int NextPos = 0, FrontPos = 0;
};
bool vis[MAXN];
struct List {
Node Queue[MAXN];
List () {
Queue[0].NextPos = 1;
Queue[1].FrontPos = 0;
}
// 用 Queue[0] 作为头结点, 方便之后的操作
// 头结点的NextPos 是链表中的第一个结点。
inline void LeftInsert(int Index, int Pos) {
// 在Pos 左面插入Index
int LeftIndex = Queue[Pos].FrontPos;
Queue[LeftIndex].NextPos = Index;
Queue[Index].FrontPos = LeftIndex;
Queue[Pos].FrontPos = Index;
Queue[Index].NextPos = Pos;
}
inline void RightInsert(int Index, int Pos) {
// 在Pos 右面插入Index
int RightIndex = Queue[Pos].NextPos;
Queue[Pos].NextPos = Index;
Queue[Index].FrontPos = Pos;
Queue[Index].NextPos = RightIndex;
Queue[RightIndex].FrontPos = Index;
}
inline void Remove(int Pos) {
// 删除Pos元素
int RightIndex = Queue[Pos].NextPos;
int LeftIndex = Queue[Pos].FrontPos;
Queue[LeftIndex].NextPos = RightIndex;
Queue[RightIndex].FrontPos = LeftIndex;
}
void print() {
int Pos = 0;
while(Queue[Pos].NextPos) {
printf("%d ", Queue[Pos].NextPos);
Pos = Queue[Pos].NextPos;
}
}
} list;
int main() {
int n;
scanf("%d", &n);
for(int i = 2; i <= n; i++) {
int k, p;
scanf("%d %d", &k, &p);
if(p) list.RightInsert(i, k);
else list.LeftInsert(i, k);
}
int m;
scanf("%d", &m);
while(m--) {
int Pos;
scanf("%d", &Pos);
if(!vis[Pos]) list.Remove(Pos);
vis[Pos] = true;
}
list.print();
return 0;
}
第四部分
图
在计算机中图是一些顶点的集合，这些顶点是由边连接的，比如下面这样：
图的基本概念
有向图： 全部由有向边构成的图。
无向图： 全部由无向边构成的图。
环: 一点能通过边绕回自身，即一个环。
出度：有向图中以该点为起点的边的个数。
入度：有向图中以该店为终点的边的个数。
树的基本概念
简单来说， 树是个顶点条边构成的不成环的图。
树可以是有向图，也可以是无向图，注意有向图中一般箭头在图中向下。
根节点：树中深度最小的节点
树的深度：一棵树中节点的最大深度就是树的深度，也称为高度
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
子节点：一个节点含有的子树的根节点称为该节点的子节点
度：节点的子树数目就是节点的度
叶子节点：度为零的节点就是叶子节点
二叉树的基本概念
树中的节点最大是2的树
因为节点的度最大是2，所以将一个节点的子树分为左子树和右子树。
存图
邻接矩阵存图
用一个矩阵利用矩阵的行和列保存结合中两个节点之间的连边，就是邻接矩阵存图
用邻接矩阵存图表示 到 有一条有向边权值是。
int mp[100][100];
mp[i][j] = w;
/// 代表从i点到j点有一条权值为w的有向边
/// 如果是无向边呢？
mp[j][i] = w;
这是一种非常简单的存图方式，但是如果有以下的题目:
给出个点， 条边······
你就会发现 mp[100000][100000]大小的数组开不下。那么怎么办，可以使用下面的vector存图。
vector存图
存图能节省空间的原理是因为 是一种不定长度的容器，能根据需要开出需要的大小，还是上面的问题，面对 的数据范围vector存图采取的操作是：
//如果是没有权值的图
vector <int> mp[100000];
//mp[i] 是一个vector容器, 容器中包含了与i相连的点的集合
// 如果加入一条边，他是由3号节点指向4号节点的有向边
mp[3].push_back(4);
// 如果加入无向边呢？ 自己尝试
//如果加入的边有权值为w，那就让vector容器保存终点和边的权值
vector <pair <int, int> > mp[100000];
mp[3].push_back(make_pair(4, w));
链式前向星存图
vector 是 STL容器，使用起来会有一个常数的时间复杂度，而且vector内部虽然是动态申请内存的，但是也会提前申请一部分内存，所以虽然空间浪费没有邻接矩阵存图严重，但还是存在一定的空间浪费，所以有链式前向星存图，既没有vector的常数，而且不会申请不需要的空间。
链式前向星存图的代码很简短，先给出简短的代码。
/// 链式前向星把每一个点相连的边的信息保存为一个链表
const int MAXN = 100010;
int Head[MAXN], cnt = 0;
/// Head[i] 表示的是顶点i相连的边构成的链表的第一个结点编号
struct Edge {
int Next, to, cost;
} e[MAXN];
void add(int from, int to, int cost) {
e[++cnt].to = to;
e[cnt].cost = cost;
e[cnt].Next = Head[from];
Head[from] = cnt;
}
/// 函数的任务是加入一条from，指向to，权值为cost的边
接下来我们分析代码执行了什么工作？
比如我们向图中加入一条边一条边：
add(3, 4, w1);
那么这些变量的值会变成 :
Head[3] = 1;
cnt = 1;
e[1].cost = w1;
e[1].Next = 0;
e[1].to = 4;
画图表示为 ：
若再向图中加入一条边3 指向 5权值是的有向边呢?
Head[3] = 1;
cnt = 1;
e[1].cost = w1;
e[1].Next = 0;
e[1].to = 4;
画图表示为 :
京公网安备 11010502036488号