C++算法（数据结构）版

文章目录 隐藏

C++算法（数据结构）版

有些题目不是完整的题目，如需查看完整的题目请移步到acwing的算法基础课中

单链表

链表：

（单向）链表是由节点和指针构成的数据结构，每个节点存有一个值，和下一个指向下一个节点的指针，因此很多的链表问题可以用递归来处理。链表不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值

基本操作：

在链表头部插入 / 删除一个数

在链表尾部插入 / 删除一个数

在链表中间插入 / 删除一个数

单链表（邻接表）常用于存储图和树

题目：

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；
删除第 k 个插入的数后面的一个数；
在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

完整题目：（https://www.acwing.com/problem/content/description/828/）acwing算法基础课

思路：

插入操作：

当链表为空时，idx = 0
当插入第一个元素后(设第一个插入的元素为 a ) 则，e[0] = a , idx = 1
当插入第二个元素后(设第二个插入的元素为 b ) 则，e[1] = b , idx = 2
当插入第三个元素后(设第三个插入的元素为 c ) 则，e[2] = c , idx = 3
当插入第四个元素后(设第四个插入的元素为 d ) 则，e[3] = d , idx = 4

所以；第 K 个插入的数的索引值为 k – 1

删除加插入操作：

当链表为空时，idx = 0
插入第一个元素 a 后：e[0] = a, idx = 1，
插入第二个元素 b 后：e[1] = b, idx = 2,
删除第一个插入的元素 a：head 变为 1， idx 不变，= 2。
删除第二个插入的元素 b：head 变为 2， idx 不变，=2。
插入第三个元素 c 后：e[2] = c, idx = 3。

实现代码：

#include
#include

using namespace std;

const int N  = 100010;

int head,idx;
int ne[N],e[N];

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}


void add(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}


int main()
{
    int m;
    cin>>m;
    
    init();
    
    while(m--)
    {
        int k,x;
        char op;
        cin>>op;
        
        if(op == 'H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin>>k;
            if(!k) head = ne[head];
            remove(k - 1);  //第k个元素对应的索引为k - 1
        }
        else
        {
            cin>>k>>x;
            add(k - 1,x);  //第k个元素对应的索引为k - 1
        }
    }
    
    for(int i = head;i != -1;i = ne[i])
    cout

总结模板：（acwing——Y总的）

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

题目：

实现一个双链表，双链表初始为空，支持 5 种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

思路：

和上面的单链表差不多

实现代码：

#include
#include

using namespace std;

const int N = 1e5 + 10;

int idx;
int l[N],r[N],e[N];

void init()
{
    //0表示左端点，1表示右端点
    l[1] = 0;
    r[0] = 1;
    idx = 2;
}

//在下标是k的点的右边，插入xl[idx] = 
void add(int k,int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    int m;
    cin>>m;
    
    init();
    
    while(m--)
    {
        int k,x;
        string op;
        cin>>op;
        
        if(op == "L")
        {
            cin>>x;
            add(0,x);
        }
        else if(op == "R")
        {
            cin>>x;
            add(l[1],x);
        }
        else if(op == "D")
        {
            cin>>k;
            remove(k + 1);
        }
        else if(op == "IL")
        {
            cin>>k>>x;
            add(l[k + 1],x);
        }
        else
        {
            cin>>k>>x;
            add(k + 1,x);
        }
    }
    
    for(int i = r[0]; i != 1;i = r[i])
    cout

总结模板：（acwing——Y总的）

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

栈

栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

问题：

实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果

完整题目：（https://www.acwing.com/problem/content/description/830/） acwing算法基础课

思路：

有数组来模拟栈：

用top表示栈顶所在的索引。初始时，top = -1。表示没有元素。
push x ：入栈，st[++top] = x。
pop : 出栈， top–。
empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”
query ：返回栈顶元素。st[top]

实现代码：

#include
#include

using namespace std;

const int N = 100010;
int st[N];
int top = -1;

int main()
{
    int m;
    cin>>m;
    
    while(m--)
    {
        string op;
        cin>>op;
        
        if(op == "push")
        {
            int x;
            cin>>x;
            
            st[++top] = x;
        }
        if(op == "pop")
        {
            top--;
        }
        if(op == "empty")
        {
            cout

总结模板：（acwing——Y总的）

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}

队列

队列：是一个特殊的数组。最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素。

题目;

实现一个队列，队列初始为空，支持四种操作：

push x – 向队尾插入一个数 x；
pop – 从队头弹出一个数；
empty – 判断队列是否为空；
query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

完整题目：（https://www.acwing.com/problem/content/description/831/）

思路：

用一个数组 q 保存数据。
用 hh 代表队头，q[hh] 就是队头元素，用 tt 代表队尾， q[tt] 就是队尾元素

实现代码：

#include
#include

using namespace std;

const int N = 100010;
int hh =0;
int tt = -1;
int q[N];

int m;
string s;

void push(int x)
{
    q[++tt] = x;
}

void pop()
{
    hh++;
}

void empty()
{
    if(tt >= hh)
    cout>m;
    
    while(m--)
    {
        cin>>s;
        
        if(s == "push")
        {
            int x;
            cin>>x;
            push(x);
        }
        if(s == "pop")
        {
            pop();
        }
        if(s == "empty")
        {
            empty();
        }
        if(s == "query")
        {
            query();
        }
    }
    
    return 0;
}

总结模板：（acwing——Y总的）

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh

这适用于普通队列，若是循环队列还需要加上

if (tt == N) tt = 0; 的判断条件

单调栈

单调栈是通过维持栈内值的单调递增（递减）性，在整体

o

(

n

)

o(n)

$o (n)$ 的时间内处理需要大小比较的问题。

题目：

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

思路：

用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素
我们只需要维护一个从栈顶到栈底单调递减的栈，每次不符合单调性就弹栈，最后输出栈顶即可，最后输出答案

实现代码：

#include
#include

using namespace std;

const int N = 100010;

int stk[N],tt;
int n;

int main()
{
    cin>>n;
    
    for(int i = 0;i >x;
        
        while(tt && stk[tt] >= x) tt--;
        if(tt) cout

核心部分：

while(tt && stk[tt] >= x) tt--;
if(tt) cout

总结模板：（acwing——Y总的）

//常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i

单调队列

题目：

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

思路：

实现代码：

#include
#include

using namespace std;

const int N = 1000010;

int n,k;
int hh = 0,tt = -1;
int q[N],a[N];

int main()
{
    scanf("%d%d",&n,&k);
 
    for(int i = 0;i  q[hh])  ++hh;  // 若队首出窗口，hh加1
        //维护队列单调性（保证队列递增）
        while(hh = k)
        printf("%d ",a[q[hh]]);   // 输出结果
    }
     printf("n");
    
    hh = 0,tt = -1;
    for (int i = 0; i  q[hh]) ++ hh;
        //维护队列单调性（保证队列递减）
        while (hh = a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    printf("n");
    
    return 0;
}

总结模板：（acwing——Y总的）

//常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i

KMP

KMP 算法常用于解决「模式串在文本串中是否存在匹配」的问题

题目：

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

思路：

求next数组 , 利用Next数组避免回溯 , 匹配字符串

实现代码：

#include
#include

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int Next[N];

int main() 
{
    cin >> n >> p + 1 >> m >> s + 1;
    
    for (int i = 2, j = 0; i

总结模板：（acwing——Y总的）

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的next数组：
for (int i = 2, j = 0; i

Trie

Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构

题目：

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

完整题目：（https://www.acwing.com/problem/content/837/）acwing 算法基础课

思路：

Trie 树中每个节点存储一个字符，从根节点到叶节点的一条路径存储一个字符串。

实现代码：

#include

using namespace std;

const int N = 100010;

char str[N];
int cnt[N],idx,son[N][26];

void insert(char str[])
{
    int p = 0;
    
    for(int i = 0;str[i];i++)
    {
        int u = str[i] - 'a';  //将字母转化为数字
        if(!son[p][u]) son[p][u] = ++idx;
        //该节点不存在，创建节点,其值为下一个节点位置
        p = son[p][u];   //使“p指针”指向下一个节点位置
    }
    
    cnt[p]++;  //结束时的标记，也是记录以此节点结束的字符串个数
}

int query(char str[])
{
    int p = 0;
    for(int i = 0;str[i];i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u];
    }
    
    return cnt[p];  //返回字符串出现的次数
}

int main()
{
    int n;
    cin>>n;
    
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(op[0] == 'I')
        insert(str);
        else
        printf("%dn",query(str));
    }

    return 0;
}

总结模板：（acwing——Y总的）

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

并查集可以动态的连通两个点，并且可以非常快速的判断两个点是否连通

题目：

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1 ≤ n,m ≤

10^5

$1 0^{5}$

思路：

基本原理：

每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示它的父节点

实现代码：

#include

using namespace std;

const int N = 100010;

int n,m;
int p[N];

int find(int x)
{
    if(x != p[x])
    p[x] =  find(p[x]);
    
    return p[x];
}

void merge(int a,int b)
{
    int pa = find(a);
    int pb = find(b);
    
    if(pa != pb)
    p[pa] = pb;
    
}


void query(int a,int b)
{
    int pa = find(a);
    int pb = find(b);
    
    if(pa == pb) cout>n>>m;
    
    for(int i = 1;i >op;
        
        int a,b;
        cin>>a>>b;
        
        if(op == 'M')
        {
            merge(a,b);
        }
        else
        {
            query(a,b);
        }
    }
    
    return 0 ;
}

朴素并查集–总结模板：（acwing——Y总的）

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
     return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i

堆

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为 $O (n l o g n)$ ，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，这种情况称为大顶堆。
每个结点的值都小于或等于其左右孩子结点的值，这种情况称为小顶堆。

题目：

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围

1 ≤ m ≤ n ≤

10^5

$1 0^{5}$

思路：

将序列构造成一个大顶堆，再将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

实现代码：

#include

using namespace std;

const int N = 100010;

int n,m;
int cnt;
int a[N];

void down(int u)
{
    //t记录最小点的编号
    int t = u;
    
    //有左儿子，并且左儿子比t节点的值小，更新t
    if(2 * u >n>>m;
    
    cnt = n;
    
    for(int i = 1;i >a[i];
        
    //从第一个非叶节点开始，从右到左，从下到上处理每个节点
    for(int i = n / 2;i >= 1;i--)
        down(i);
        
    while(m--)
    {
        cout

总结模板：（acwing——Y总的）

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 >= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希表

哈希表（hash table,hash map）,又称散列列表，使用O(n)空间复杂度存储数据，通过哈希函数映射位置，从而实现近似O(1)时间复杂度的插入，查找，删除等操作。哈希表可以用来统计频率，记录内容等等
如果元素有穷，并且范围不大，那么可以用一个固定大小的数组来存储或统计元素。

Hash表的主要基本操作：

计算Hash函数的值
定位到对应链表中依次遍历，比较

常用方法：

拉链法

开放寻址法

拉链法代码模板–总结模板：（acwing——Y总的）

int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

开放寻址法代码模板–总结模板：（acwing——Y总的）

int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
   int t = (x % N + N) % N;
   while (h[t] != null && h[t] != x)
   {
       t ++ ;
       if (t == N) t = 0;
    }
    return t;
}

文章来源于互联网:C++算法（数据结构）版

C++算法（数据结构）版

C++算法（数据结构）版

单链表

思路：

双链表

思路：

栈

思路：

队列

思路：

单调栈

思路：

单调队列

思路：

KMP

思路：

Trie

并查集

思路：

堆

思路：

哈希表

相关推荐

对比kimi、通义千问、文心一言的写代码能力

热门文章

AI大模型,我们的未来