在线问答5

这个屌丝很懒，什么也没留下！

热门标签

c++常用板子v1.6

作者：在线问答5 | 2024-08-01 10:50:09

踩

c++常用板子v1.6

v1.6
最近更新：2021/12/9

一、头文件

#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
const int INF = 0x3f3f3f3f;

注：math.h中，abs(x)求整数x绝对值，
fabs(x)求double型x绝对值,
ceil(x)取上整，floor(x)取下整，
pow(x,y) x的y次方，sqrt(x)开根
fabs、ceil、floor、pow、sqrt均返回double型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、排序与查找

1、快速排序

void quickSort(int a[],int l,int r){     //快速排序
    if(l < r){
        int pos = partition(a, l, r);
        quickSort(a, l, pos-1);
        quickSort(a, pos+1, r);
    }
}

int partition(int a[],int l,int r){      //快排的一趟
    int temp = a[l];
    while(l < r){
        while (l < r && temp <= a[r]) r--;
        a[l] = a[r];
        while(l < r && temp >= a[l]) l++;
        a[r] = a[l];
    }
    a[l] = temp;
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、归并排序

//非递归实现
void merge(int A[], int L1, int R1, int L2, int R2){    //将数组A的有序的[L1,R1]与[L2,R2]区间合并为一个有序区间。
    int i = L1, j = L2;
    int temp[maxn], index = 0;
    while(i <= R1 && j <= R2){
        if(A[i] <= A[j]){
            temp[index++] = A[i++];
        } else{
            temp[index++] = A[j++];
        }
    }
    while(i <= R1) temp[index++] = A[i++];
    while(j <= R2) temp[index++] = A[j++];
    for(i = 0; i < index; i++){
        A[L1 + i] = temp[i];
    }
}

void mergeSort(int A[]){        //主。额外注明：元素个数为n，数组下标从1开始。
    for(int step = 2; step / 2 <= n; step *= 2){	//step表示当前要合并的一对长度和的最大值
        for(int i = 1; i <= n; i += step){
            int mid = i + step / 2 - 1;
            if(mid + 1 <= n){
                merge(A, i, mid, mid+1, min(i + step - 1, n));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3、二分查找与快速幂

//假设不含重复元素，在递增序列A中进行二分查找，目标为x，找不到返回-1
int binarySearch(int A[], int left, int right, int x){
	int mid;
	while(left <= right){
		mid = (left + right) / 2;
		if(A[mid] == x) return mid;
		else if(A[mid] > x) right = mid - 1;
		else left = mid + 1;
	}
	return -1;
}

//假设可能含重复元素，lower_bound返回第一个值 >= x 的元素的位置 L，
//upper_bound返回第一个值 > x 的元素的位置 R
//如果A的最后一个元素是x，则x的个数是R-L+1。其余任何情况x的个数都是R-L。
int lower_bound(int A[], int left, int right, int x){
	int mid;
	while(left < right){
		mid = (left + right) / 2;
		if(A[mid] >= x) right = mid;
		else left = mid + 1;
	}
	return left;
}

int upper_bound(int A[], int left, int right, int x){
	int mid;
	while(left < right){
		mid = (left + right) / 2;
		if(A[mid] > x) right = mid;
		else left = mid + 1;
	}
	return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

typedef long long LL;
//快速幂的递归写法，计算a^b % m
LL binaryPow(LL a, LL b, LL m){
	if(b == 0) return 1;
	if(b & 1) return a * binaryPow(a, b - 1, m) % m;
	else{
		LL mul = binaryPow(a, b / 2, m);
		return mul * mul % m;
	}
}

//快速幂的迭代写法，计算a^b % m
LL binaryPow(LL a, LL b, LL m){
	LL ans = 1;
	while(b > 0){
		if(b & 1) ans = ans * a % m;
		a = a * a % m;
		b >>= 1;	//注：等价于b = b >> 1; 相当于b除以2
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、二分查找（二分使用该板子）
二分的本质不是单调性，能二分不一定要有单调性。二分的本质如下：假设有一整数序列，有一性质，使得某一个数右边（含该数）满足该性质，而该数左边（不含该数）不满足该性质。形象地表示，假设A是不满足该性质的数，B是满足该性质的数
AAAAAABBBBBBB
则二分可以寻找该性质的分界点，即既能寻找最右边的A，又能寻找最左边的B。

情况1：找最右边的A
mid = (l + r + 1) / 2; //注意加一！
if(检查mid是否满足A的性质)
如果true，答案在[mid, r]，令l=mid即可。
如果false，答案在[l, mid-1]，令r=mid - 1即可。

情况2：找最左边的B
mid = (l + r) / 2;
if(检查mid是否满足B的性质)
如果true，答案[l,mid]，令r = mid即可。
如果false，答案[mid+1,r]，令l=mid+1即可。

（以上循环条件l < r，注：循环结束时一定有 l = r）

现在解释为什么情况1里mid那要+1：当l=r-1时，mid = (l+r)/2 是等于l的，如果检查条件返回true，则死循环。因此补上+1。二分时，mid左右偏移一点完全不影响效率和正确性（只要不死循环）。

二分一定会停止，之后判断是否为题目中的无解情况，即判断序列[l]号元素是否满足要求。

以上情况对应的二分板子如下（推荐该板子，情况完备且有定式）：

4、二分查找（二分使用该板子）

// 情况1：找最右边的A时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid; // check()判断mid是否满足A的性质
        else r = mid - 1;
    }
    return l;
}

// 情况2：找最左边的B时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; // check()判断mid是否满足B的性质
        else l = mid + 1;
    }
    return l;
}
//注：check()判断 是否满足需要找的那个点所在分类的条件，满足为True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

记忆：
找最右 ~ mid多加1 ~ 左为mid（check条件后跟的是l=mid）
找最左 ~ mid不加1 ~ 右为mid

三、二叉树

1、存储结构与基本操作

struct node{
    int data;
    node* lchild;
    node* rchild;
};

node* newNode(int v){   //生成新结点，v为结点权值
    node* Node = new node;
    Node->data = v;
    Node-> lchild = Node->rchild = NULL;
    return Node;
}

void search(node* root,int x,int newdata){  //查找值为x的所有结点，并把它们的值修改为newdata
    if(root == NULL){
        return;
    }
    if(root->data == x){
        root->data = newdata;
    }
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}

void insert(node* &root,int x){ //插入值为x的新结点，查找失败的位置即插入位置，注意引用
    if(root == NULL){
        root = newNode(x);
        return;
    }
    if(x应该插在左子树){
        insert(root->lchild,x);
    }
    else{
        insert(root->rchild,x);
    }
}

node* Create(int data[],int n){ //创建二叉树，插入的数据在数组中
    node* root = NULL;
    for(int i = 0; i < n; i++){
        insert(root,data[i]);
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2、遍历

void preorder(node* root){  //先序遍历 根左右
    if(root == NULL){
        return;
    }
    visit(root);
    preorder(root->lchild);
    preorder(root->rchild);
}

void inorder(node* root){   //中序遍历 左根右
    if(root == NULL){
        return;
    }
    inorder(root->lchild);
    visit(root);
    inorder(root->rchild);
}

void postorder(node* root){ //后序遍历 左右根
    if(root == NULL){
        return;
    }
    postorder(root->lchild);
    postorder(root->rchild);
    visit(root);
}

void LayerOrder(node* root){    //层序遍历，为记录结点所在层数，在二叉树结构体中添加 int layer;
    queue<node*> q;
    root->layer = 1;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        q.pop();
        visit(now);
        if(now->lchild != NULL){
            now->lchild->layer = now->layer + 1;
            q.push(now->lchild);
        }
        if(now->rchild != NULL){
            now->rchild->layer = now->layer + 1;
            q.push(now->rchild);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

3、先序序列、中序序列构造二叉树

node* create(int preL,int preR,int inL,int inR){    //给定先序遍历序列pre[]、中序遍历序列in[]，重建二叉树。[preL,preR]为先序序列区间，[inL,inR]为中序序列区间。
    if(preL > preR){
        return NULL;
    }
    node* root = new node;
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == pre[preL]){
            break;
        }
    }
    int numLeft = k - inL;
    root->lchild = create(preL + 1,preL + numLeft,inL,k-1);
    root->rchild = create(preL + numLeft + 1,preR,k + 1,inR);
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4、二叉查找树的基本操作

//（1）二叉查找树的插入与建立
void insert(node* &root, int x){    //将x插入以root为根的二叉查找树中，递归地
    if(root == NULL){
        root = newNode(x);
        return;
    }
    if(x == root->data){
        return;
    }
    else if(x < root->data){
        insert(root->lchild, x);
    }
    else{
        insert(root->rchild, x);
    }
}

node* Create(int data[], int n){    //将data[]构造成一棵二叉查找树，返回根结点指针
    node* root = NULL;
    for(int i = 0; i < n; i++){
        insert(root, data[i]);
    }
    return root;
}

//（2）二叉查找树的查找
void search(node* root, int x){     //查找数据为x的结点
    if(root == NULL){
        printf("search failed\n");  //查找失败
        return;
    }
    if(x == root->data){
        //查找成功，在此处进行访问
    }
    else if(x < root->data){
        search(root->lchild, x);
    }
    else{
        search(root->rchild, x);
    }
}

//（3）二叉查找树的删除，复杂一些。思路：删结点a -> 用a的前驱（或后继）替代a，删除a的前驱（或后继）。边界：删除叶子。递归进行
node* findMax(node* root){      //辅助函数：寻找以root为根的二叉查找树中最大结点
    while(root->rchild != NULL){
        root = root->rchild;
    }
    return root;
}

node* findMin(node* root){      //辅助函数：寻找以root为根的二叉查找树中最小结点
    while(root->lchild != NULL){
        root = root->lchild;
    }
    return root;
}

void deleteNode(node* &root, int x){    //在以root为根的二叉查找树中删除值为x的结点。
    if(root == NULL){   //边界：不存在值为x的结点
        return;
    }
    if(root->data == x){    //找到了x，删除它
        if(root->lchild == NULL && root->rchild == NULL){   //边界：叶子结点，直接删除
            root = NULL;
        }
        else if(root->lchild != NULL){  //左结点不空，就找前驱递归
            node* pre = findMax(root->lchild);
            root->data = pre->data;
            deleteNode(root->lchild, pre->data);
        }
        else if(root->rchild != NULL){  //右结点不空，就找后继递归
            node* next = findMin(root->rchild);
            root->data = next->data;
            deleteNode(root->rchild, next->data);
        }
    }
    else if(x < root->data){    //往左查找
        deleteNode(root->lchild, x);
    }
    else if(x > root->data){    //往右查找
        deleteNode(root->rchild, x);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

5、平衡二叉树的建立

struct node{
	int v, height;
	node *lchild, *rchild;
};

node* newNode(int v){ //用于生成新结点
	node* Node = new node;
	Node->v = v;
	Node->height = 1;
	Node->lchild = Node->rchild = NULL;
	return Node;
}

int getHeight(node* root){ //获得以root结点为根的子树的高度
	if(!root) return 0;
	return root->height; 
}

int getBalanceFactor(node* root){ //获得root结点的平衡因子
	return getHeight(root->lchild) - getHeight(root->rchild);
}

void updateHeight(node* root){ //更新root的height值
	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

void L(node* &root){ //对root进行左旋操作。即root的右结点作新的根，root作为其左结点，其原来的左结点作为root的右结点
	node* temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}

void R(node* &root){//对root进行右旋操作。即root的左结点作新的根，root作为其右结点，其原来的右结点作为root的左结点
	node* temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}

void insert(node* &root, int v){ //插入权值为v的结点
	if(!root){
		root = newNode(v);
		return;
	}
	if(v < root->v){ //v比root小，则往左插
		insert(root->lchild, v); //往左递归插入
		updateHeight(root); //更新树高
		if(getBalanceFactor(root) == 2){ //如果失衡则进行相应调整
			if(getBalanceFactor(root->lchild) == 1){ //LL型
				R(root);
			}
			else if(getBalanceFactor(root->lchild) == -1){ //LR型
				L(root->lchild);
				R(root);
			}
		}
	}
	else{ //v比root大，以下同理。
		insert(root->rchild, v);
		updateHeight(root);
		if(getBalanceFactor(root) == -2){
			if(getBalanceFactor(root->rchild) == -1){ //RR型
				L(root);
			}
			else if(getBalanceFactor(root->rchild) == 1){ //RL型
				R(root->rchild);
				L(root);
			}
		}
	}
}

node* create(int data[], int n){ //建立AVL树
	node* root = NULL;
	for(int i = 0; i < n; i++){
		insert(root, data[i]);
	}
	return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

四、树

1、静态存储结构与基本操作

struct node{
    int data;
    vector<int> child;
} Node[maxn];

//新建一个结点
int index = 0;
int newNode(int v){
    Node[index].data = v;
    Node[index].child.clear();
    return index++;
}
1
2
3
4
5
6
7
8
9
10
11
12

2、遍历

void PreOrder(int root){    //树的先根遍历  根 子树，注：递归边界隐含在for循环的结束条件中，但是调用传入的root不能是空结点。
    visit(Node[root]);
    for(int i = 0; i < Node[root].child.size(); i++){
        PreOrder(Node[root].child[i]);
    }
}

void LayerOrder(int root){  //树的层序遍历，为记录结点所在层数，在树的结构体中添加 int layer;
    queue<int> Q;
    Q.push(root);
    Node[root].layer = 0;
    while(!Q.empty()){
        int front = Q.front;
        Q.pop();
        visit(Node[front]);
        for(int i = 0; i < Node[front].child.size(); i++){
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            Q.push(child);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、堆

//以大顶堆为例，堆是一棵完全二叉树，用数组存储，根节点在数组中下标为1，结点i的左子树下标为 i * 2，右子树下标为i * 2 + 1（如果存在）
//建堆：对于一棵乱序的完全二叉树，通过调整使其成为堆。由于用的是数组存储，是在一个乱序序列上建堆。
//设n为元素个数，heap[]是表示堆的数组
void createHeap(){  //时间复杂度：O(n)
    for(int i = n/2; i>= 1; i--){
        downAdjust(i,n);
    }
}

void downAdjust(int low, int high){ //向下调整，对heap在[low,high]范围内进行向下调整（high一般设置为n）。这一趟把low往下调整到正确位置。
    int i = low, j = i * 2;
    while(j <= high){
        if(j+1 <= high && heap[j+1] > heap[j]){
            j = j + 1;
        }
        if(heap[j] > heap[i]){
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        }
        else{
            break;
        }
    }
}

//删除堆顶元素：用最后一个元素覆盖堆顶元素，再对根节点向下调整。时间复杂度O(logn)
void deleteTop(){
    heap[1] = heap[n];
    n--;
    downAdjust(1, n);
}

//往堆中添加一个元素：把添加的元素放在最后，进行向上调整。
void insert(int x){
    n++;
    heap[n] = x;
    upAdjust(1, n);
}

void upAdjust(int low, int high){   //向上调整，对heap在[low,high]范围内进行向上调整（low一般设置为1）
    int i = high, j = i / 2;
    while(j >= low){
        if(heap[j] < heap[i]){
            swap(heap[j], heap[i]);
            i = j;
            j = i / 2;
        }
        else{
            break;
        }
    }
}

/*堆排序*/
//思路：（以大顶堆为例）建堆后，取出堆顶元素，将堆的最后一个元素移至堆顶，对堆顶向下调整，直到堆只有一个元素。
//给定一个初始乱序数组序列heap，调整后使其有序
void heapSort(){
    createHeap();
    for(int i = n; i > 1; i--){
        swap(heap[i], heap[1]);
        downAdjust(1, i - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

4、并查集

int father[maxn];   //father[i]表示i的父亲结点，若father[i] == i，则i是该集合的根结点。一个集合是一棵树（根有自环）

//初始化：father[i] = i;

int findfather(int x){  //(简单版)查找。返回元素x所在集合的根结点
    while(x != father[x]){
        x = father[x];
    }
    return x;
}

int findfather(int x){  //(路径压缩版)查找。均摊后时间复杂度降低为近似O(1)。
    int a = x;
    while(x != father[x]){
        x = father[x];
    }
    while(a != father[a]){
        int z = a;
        a = father[a];  //注意顺序
        father[z] = x;
    }
    return x;
}

void Union(int a, int b){   //合并。合并集合a、集合b。 注：Union中U必须大写，否则是关键字。
    int faA = findfather(a);
    int faB = findfather(b);
    if(faA != faB){
        father[faA] = faB;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

五、图

1、图的存储

//1邻接矩阵
int G[maxn][maxn];

//2邻接表，一个表存放一个顶点的所有出边
//第一种：邻接表只存边的终点编号，不存边权
vector<int> Adj[maxn];        //Adj有maxn个vector，vector元素为int，存放结点的出边终点。

//第二种：邻接表存边的终点编号、边权
struct Node{
    int v;  //出边的终点的编号
    int w;  //边权
    Node(int _v, int _w){   //构造函数
        v = _v;
        w = _w;
    }
};
vector<Node> Adj[maxn];    //Adj有maxn个vector，vector元素为Node，存放结点的出边终点以及对应边权。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、DFS遍历图

const int maxn = 1000;
const int INF = 0x3f3f3f3f;
//2.1邻接矩阵版
int n,G[maxn][maxn];    //n为顶点数
bool vis[maxn] = {false};

void DFS(int u, int depth){ //u为顶点编号，depth为深度，从1开始
    vis[u] = true;
    //在此进行对u顶点的操作
    for(int v = 0; v < n; v++){
        if(vis[v] == false && G[u][v] != INF){
            DFS(v, depth + 1);
        }
    }
}

void DFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            DFS(u, 1);
        }
    }
}

//2.2邻接表版（使用第二种邻接表，即邻接表存边的终点编号、边权）
vector<Node> Adj[maxn];
int n;  //n为顶点数
bool vis[maxn] = {false};

void DFS(int u, int depth){
    vis[u] = true;
    //在此进行对u顶点的操作
    for(int i = 0; i < Adj[u].size(); i++){
        int v = Adj[u][i].v;
        if(vis[v] == false){
            DFS(v, depth + 1);
        }
    }
}

void DFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            DFS(u, 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3、BFS遍历图

//3.1邻接矩阵版
int n,G[maxn][maxn];
bool vis[maxn] = {false};

void BFS(int u){
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        //在此对now顶点进行操作
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[now][v] != INF){
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

void BFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            BFS(u);
        }
    }
}

//3.2邻接表版
vector<Node> Adj[maxn];
int n;
bool vis[maxn] = {false};

void BFS(int u){
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        //在此对now顶点进行操作
        for(int i = 0; i < Adj[now].size(); i++){
            int v = Adj[now][i].v;
            if(vis[v] == false){
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

void BFSTrave(){
    for(int u = 0; u < n; u++){
        if(vis[u] == false){
            BFS(u);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

4、最短路径Dij + DFS

//4.1 输入图G后，使用Dijkstra 获得起点s到其他节点所有最短路长 + 前驱
//（邻接表版Dij）
vector<Node> Adj[maxn];
int d[maxn];                //记录起点到结点i的最短距离
vector<int> pre[maxn];      //pre[i]表示起点到结点i的最短路径里，结点i的前驱结点
bool vis[maxn] = {false};
void Dij(int s){             //s为起点
    fill(d, d + maxn, INF);	//memset(d, INF, sizeof(d)); 头文件cstring
    d[s] = 0;
    for(int i = 0; i < n; i++){
        int u = -1, MIN = INF;      //找出未访问的点里最小的
        for(int j = 0; j < n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1) return;     //剩下的结点不连通，结束
        vis[u] = true;
        for(int j = 0; j < Adj[u].size(); j++){
            int v = Adj[u][j].v;
            if(vis[v] == false){
                if(d[u] + Adj[u][j].w < d[v]){
                    d[v] = d[u] + Adj[u][j].w;
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if(d[u] + Adj[u][j].w == d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

//4.2 起点->终点有多条最短路，在其中找到使第二标尺最优的路径，使用DFS
//前提：在4.1的基础上，设st为路径起点。
int optvalue = 初值0或INF;   //第二标尺最优值
vector<int> path, temppath; //最优路径、临时路径，倒着存的
void DFS(int v){	//初始调用传入终点编号
    if(v == st){	//边界：到达起点
        temppath.push_back(v);
        int value;
        //此处计算temppath上的value值，涉及边权或者点权
        if(value优于optvalue){
            optvalue = value;
            path = temppath;
        }
        temppath.pop_back();
        return;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++){
        DFS(pre[v][i]);
    }
    temppath.pop_back();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

5、Floyd算法

//思想：若存在点k，使得k作中介能使i->j的最短路径缩短，则用k作中介。可以有负边权，但不能有负权回路。
//设n为结点数。时间复杂度O(n^3)，限制了n<=200
int dis[maxn][maxn];//dis[i][j]初始存i->j的边权，Floyd运算后dis[i][j]表示i->j的最短距离
void Floyd(){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dis[i][k] + dis[k][j] < dis[i][j] && dis[i][k] != INF && dis[k][j] != INF){
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

/*
附：dis[][]的初始化过程：1、全部赋INF 2、dis[i][i] = 0
此外，输入dis[i][j]的值为 w 时，若为无向图，记得dis[j][i] 也为 w
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6、拓扑排序

//邻接表实现。（1）拓扑序列：若图中存在边u->v，则序列中u在v前面。（2）拓扑排序可判断图是否为有向无环图。
vector<int> Adj[maxn];      //拓扑排序和权值没关系，此处以第一种邻接表为例
int n, m, inDegree[maxn];   //顶点数，边数，每个结点的入度
bool tppx(){    //返回true说明拓扑排序成功，图是有向无环图。否则图中有环。
    int num = 0;
    queue<int> q;
    for(int i = 0; i < n; i++){     //入度为0入队
        if(inDegree[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        //访问该结点，如printf("%d",u);
        for(int i = 0; i < Adj[u].size(); i++){
            int v = Adj[u][i];
            inDegree[v]--;
            if(inDegree[v] == 0){
                q.push(v);
            }
        }
        //可清空u的所有出边，也可不写。Adj[u].clear();
        num++;
    }
    if(num == n) return true;
    else return false;
}

//注：若题目要求有多个入度为0的点选择编号最小的，则把queue改成priority_queue，保证队首元素是最小的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

六、其他

1、大整数运算

struct bign{
    int d[1000]; //数的低位存在低下标，如235813存储为 d[0]~d[5] 分别为 318532
    int len;    //记录长度
    bign(){     //构造函数，方便初始化
        memset(d,0,sizeof(d));
        len = 0;
    }
};

bign change(char str[]){    //读入字符数组，转化为大整数bign
    bign a;
    a.len = strlen(str);
    for(int i = 0; i < a.len; i++){
        a.d[i] = str[a.len - 1 - i] - '0';
    }
    return a;
}

int compare(bign a, bign b){    //比较大整数a与b的大小。    a>b，a=b，a<b 分别返回 1,0，-1
    if(a.len > b.len) return 1;
    else if(a.len < b.len) return -1;
    else{
        for(int i = a.len - 1; i >= 0; i--){
            if(a.d[i] > b.d[i]) return 1;
            else if(a.d[i] < b.d[i]) return -1;
        }
        return 0;
    }
}

void print(bign a){     //输出大整数
    for(int i = a.len - 1; i >= 0; i--){
        printf("%d", a.d[i]);
    }
}

bign add(bign a, bign b){   //大整数加法
    bign c;
    int carry = 0;
    for(int i = 0; i < a.len || i < b.len; i++){
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    if(carry != 0){
        c.d[c.len++] = carry;
    }
    return c;
}

bign sub(bign a, bign b){   //大整数减法a-b
    bign c;
    for(int i = 0; i < a.len || i < b.len; i++){
        if(a.d[i] < b.d[i]){
            a.d[i + 1]--;
            a.d[i] += 10;
        }
        c.d[c.len ++] = a.d[i] - b.d[i];
    }
    while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
        c.len--;
    }
    return c;
}

bign multi(bign a, int b){  //大整数 乘以 普通整数
    bign c;
    int carry = 0;
    for(int i = 0; i < a.len; i++){
        int temp = a.d[i] * b + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    while(carry != 0){
        c.d[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

2、最大公约数与最小公倍数

int gcd(int a, int b){  //求a与b的最大公约数，a无须大于b
    if(b == 0) return a;
    else return gcd(b, a % b);
}

//a、b的最小公倍数 = a / 最大公约数 * b
1
2
3
4
5
6

3、分数运算

struct Fraction{    //用long long更好
    int up, down;   //规定1.分子up可以是负数，但分母down是非负数。2.若分数为0，规定up=0，down=1。3、分子分母互素（公约数只有1）
}

Fraction reduction(Fraction result){    //化简与约分，使一个分数满足上述三条规定
    if(result.down < 0){    //若分母是负数，则分母变成非负数
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0){     //若分数为0，则分母置1
        result.down = 1;
    }else{      //约分，分子分母除以它们的最大公约数即可
        int d = gcd(abs(result.up), result.down);   //d为分子分母的最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

void print(Fraction r){     //打印分数r
    r = reduction(r);
    if(r.down == 1){    //是整数（含0）
        printf("%lld", r.up);
    }
    else if(abs(r.up) > r.down){    //是假分数
        printf("%d %d/%d",r.up / r.down, abs(r.up) % r.down, r.down);
    }
    else{   //是真分数
        printf("%d/%d", r.up, r.down);
    }
}

Fraction add(Fraction f1, Fraction f2){     //分数相加，通分相加后再化简约分
    Fraction res;
    res.up = f1.up * f2.down + f2.up * f1.down;
    res.down = f1.down * f2.down;
    return reduction(res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

4、表达式计算

//题意：给定中缀表达式，计算值。
/*思路：1中缀转后缀：队列存后缀。顺序扫描中缀，若是操作数直接入队；
若是操作符op若优先级高则入栈，若优先级低或等于则弹栈至队列直到op优先级高于栈顶或栈空。扫描完后栈中剩余元素入队。
2计算后缀：队列顺序出队，若是操作数入栈，若是操作符弹栈两个数（后弹的是第一操作数），运算结果入栈。扫描完栈中只有一个数即是答案*/
struct node{
    double num;
    char op;
    bool flag;  //1表示是操作数，0表示是操作符
};

string str;     //输入的表达式
stack<node> s;  //操作符栈
queue<node> q;  //后缀表达式
map<char,int> op;
//0、初始化（使用时请放main函数里）
op['+'] = op['-'] = 1;  
op['*'] = op['/'] = 2;
for(string::iterator it = str.end(); it != str.begin(); it--){  //去掉str中所有空格
    if(*it == ' ') str.erase(it);
}

void Change(){  //1、中缀转后缀
    double num;
    node temp;
    for(int i = 0; i < str.size(); ){
        if(str[i] >= '0' && str[i] <= '9'){ //若是操作数
            temp.flag = true;
            temp.num = str[i] - '0';
            i++;
            while(i < str.size() && str[i] >= '0' && str[i] <= '9'){
                temp.num = temp.num * 10 + str[i] - '0';
                i++;
            }
            q.push(temp);
        }
        else{   //若是操作符
            temp.flag = false;
            while(!s.empty() && op[str[i]] <= sp[s.top().op]){
                q.push(s.top());
                s.pop();
            }
            temp.op = str[i];
            s.push(temp);
            i++;
        }
    }
    while(!s.empty()){      //剩余操作符入栈
        q.push(s.top());
        s.pop();
    }
}

double Cal(){   //2、计算后缀，返回答案
    double temp1, temp2;
    node cur, temp;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(cur.flag == true){   //若是操作数，直接入栈
            s.push(cur);
        }
        else{   //若是操作符
            temp2 = s.top().num;    //第二操作数
            s.pop();
            temp1 = s.top().num;    //第一操作数
            s.pop();
            temp.flag = true;
            if(cur.op == '+') temp.num = temp1 + temp2;
            else if(cur.op == '-') temp.num = temp1 - temp2;
            else if(cur.op == '*') temp.num = temp1 * temp2;
            else if(cur.op == '/') temp.num = temp1 / temp2;
            s.push(temp);
        }
    }
    return s.top().num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

5、KMP算法

文本串中匹配模式串 O（n+m）

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度，下标从1开始
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6、快速幂

//求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
    int res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

7、判断质数

//判断x是不是质数，时间复杂度O(根号n)
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

1
2
3
4
5
6
7
8
9
10

8、分解质因数

//形式：24 = 2 ^ 3 * 3 ^ 1，时间复杂度O(根号n)
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/913675

c++常用板子v1.6

目录

一、头文件

二、排序与查找

1、快速排序

2、归并排序

3、二分查找与快速幂

4、二分查找（二分使用该板子）

三、二叉树

1、存储结构与基本操作

2、遍历

3、先序序列、中序序列构造二叉树

4、二叉查找树的基本操作

5、平衡二叉树的建立

四、树

1、静态存储结构与基本操作

2、遍历

3、堆

4、并查集

五、图

1、图的存储

2、DFS遍历图

3、BFS遍历图

4、最短路径Dij + DFS

5、Floyd算法

6、拓扑排序

六、其他

1、大整数运算

2、最大公约数与最小公倍数

3、分数运算

4、表达式计算

5、KMP算法

6、快速幂

7、判断质数

8、分解质因数