脚本宝典收集整理的这篇文章主要介绍了算法基础课第二章数据结构，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

单链表

模板

#include<iostream>
using namespace std;
const int N = 100010;
int idx, a[N], ae[N]; 
int head;
// idx 表示当前还未填入的数，可以表示第几个插入的顺序，不过从0开始
// a[i]表示第 i + 1 次插入的数值,ae[i] 表示当前元素的下一个元素在 a 数组中的下标idx
void add_to_head(int x)
{
    a[idx] = x;
    ae[idx] = head; // 如果只插入1个节点，那么此节点指向-1，说明下一个j
    head = idx;
    idx++;
}

void add(int k, int x) // 在第k个插入的数后插入x
{
    a[idx] = x;
    ae[idx] = ae[k];
    ae[k] = idx;
    idx++;
}

void delt(int k) // 删除第k个插入的数
{
    ae[k] = ae[ae[k]]; // 指向把第k个数指向下下个下标位置
}


int main(){
    int n;
    idx = 0, head = -1; // 头结点刚开始没有
    cin >> n;

    while(n--)
    {
        char op;
        cin >> op;
        int k, x;
        if(op == 'H')
        {

            cin >> x;
            add_to_head(x);
        }
        if(op == 'D')
        {

            cin >> k;
            if(!k)  head = ae[head]; // k为0时删除头节点,head原来指向的第一个节点下标，那么head的值就是第一个节点的下标
            // 所以ne[head]是第二个节点的下标
             delt(k-1); // 第k个插入的数下标为 k - 1
        }
        else if(op == 'I'){
            int k, x;
            cin>>k>>x;
            add(k-1,x);
        }

    }
    for(int i=head;i!=-1;i=ae[i])
      cout<<a[i]<<" ";

    return 0;
}

双链表

题目： 双链表

• 双链表初始化时用0表示左端点、1表示右端点。无数据，真正的数据从e[2]开始。
• l、r数组表示某个端点左边和右边分别指向端点的索引idx

#include <iostream>

using namespace std;

const int N = 100010;

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

// 在节点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];
}

int main()
{
    cin >> m;

    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        // 在链表最左端插入x
        if (op == "L")
        {
            cin >> x;
            insert(0, x); // 在0端点右边插入
        }
        // 在链表最右端插入x
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x); // 在1端点左边的l[1]右边插入
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

模拟栈

题目： 模拟栈

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
// 让一个指针始终指向栈顶
int top = 0;

void push(int x) {
    a[++top] = x;
}

bool empty() {
    if(!top)   return true;
    else    return false;
}

void pop() {
    if(!empty())    top--;
}

int query() {
    return a[top];
}
int main() {
    int n;
    cin >> n;
    while(n--) {
        string op;
        int x;
        cin >> op;
        if(op == "push") {
            cin >> x;
            push(x);
        }else if(op == "query") {
            cout << query() << endl;
        }else if(op == "pop") {
            pop();
        }else if(op == "empty") {
            if(empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

    return 0;
}

模拟队列

题目：模拟队列

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int hh = 1, tt = 0; // hh队头 tt队尾
void push(int x) {
    a[++tt] = x;
}

bool empty() {
    if(hh <= tt)   return false;
    return true;
}

void pop() {
    if(!empty())
        hh++; // 对头向右移动
}


int query() {
    return a[hh]; // i指向对头元素
}

int main() {
    int n;
    cin >> n;
    string op;
    int x;
    while(n--) {
        cin >> op;
        if(op == "push") {
            cin >> x;
            push(x);
        }
        else if(op == "pop")    pop();
        else if(op == "empty") {
            if(empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }else if(op == "query") cout << query() << endl;
    }
    return 0;
}

单调栈

题目：单调栈

#include<iostream>
#include<stack>
using namespace std;
const int N = 100010;
int a[N];
stack<int> s;
// 维护一个单调递增的栈,当栈顶元素大于(入栈元素)出栈，则入栈时，栈顶是第一个小于入栈元素的值
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)    {
        scanf("%d",&a[i]);
    }
    s.push(a[0]);
    cout << "-1 ";
    for(int i = 1;i < n;i++) {
        // while(a[i] <= s.top() && !s.empty()) {
        //     s.pop(); // 出栈
        // } 这是错误的写法
        while(!s.empty() && a[i] <= s.top())    s.pop();
        s.push(a[i]);
    }
    return 0;
}

单调队列

• 单调队列可以维护一定范围数量的单调序列,如滑动窗口。

题目：单调队列

#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N]; // q数组存放单调队列的下标

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int hh = 0, tt = -1; // 维护单调队列的下标
    for (int i = 0; i < n; i ++ )
    {
        // 如果队列中的数超过上限了，队头出队
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ; // 若加入的数小于队尾,我们要保证队首是最小的数
        q[ ++ tt] = i; // 下标入队尾

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}

KMP

题目：KMP字符串

#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
int ne[N];
char p[N], s[M]; // p是模式串、s是匹配串
int main() {
    int n,m;
    cin >> n >> p+1 >> m >> s+1;
    // 求next数组,模式串与自己匹配
    for(int i = 2, j = 0;i <= n;i++) {
        while(j && p[i] != p[j+1])  j = ne[j];
        if(p[i] == p[j+1])   j++;
        ne[i] = j;
    }

    // 利用next数组匹配需要匹配的串
    for(int i = 1,j = 0; i <= m;i++) {
        while(j && s[i] != p[j+1])  j = ne[j];
        if(s[i] == p[j+1])  j++;
        if(j == n) {
            cout << i - n << " "; // 本来是 i -n + 1,但我们初始时下标为1，本题是0
            j = ne[j]; // 匹配下一个,从j位置开始，当前j相当于从ne[j]的位置再次匹配
        }
    }

    return 0;
}

Trie树

题目： Trie字符统计

#include <iostream>
using namespace std;
const int N = 100010;
int children[N][26], cnt[N], idx;
char s[N];

void insert(char *s) {
    int p = 0; // idx从0开始遍历，根节点没有数据
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!children[p][u])
            children[p][u] = ++idx; // 增加 p->u 的边
        p = children[p][u]; // 从当前索引继续查找或插入
    }
    cnt[p]++; // 最后p代表最后字符节点的索引值
}

int query(char *s) {
    int p = 0; // 从根节点开始查找
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!children[p][u])
            return 0; // 中间值都匹配，就不用往下查找了
        p = children[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    char c;
    cin >> n;
    while (n--) {
        cin >> c;
        if (c == 'I') {
            cin >> s;
            insert(s);
        }

        else if (c == 'Q') {
            cin >> s;
            cout << query(s) << endl;
        }

    }

    return 0;
}

并查集

题目：连通块中点的个数

void init(int n)
{
    for (int i = 1; i <= n; i ++) fa[i] = i;
}

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

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

void merge(int x, int y)
{
    fa[find(x)] = find(y);
}

// 查询是否在同一集合
bool query(int i, int j) {
    if(find(i) == find(j))  return true;
    return false;
}

带权并查集

题目：食物链

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]]; // d[x]表示到合并后到根节点的距离
        p[x] = t;
    }
    return p[x];
}
// 合并函数视具体题目而定

模拟堆

• 下标从1开始

题目：模拟堆

#include<iostream>
#include<string>
using namespace std;
const int N = 100010;
int h[N], mysize, cnt; // cnt记录第k次插入
int ph[N], hp[N];
// ph[k]: 第k个插入 --> 下标
// hp[k]: 下标k -->第几个插入
// 交换堆中的两个数，那么下标和第几次插入的关系也要变化
void swap_heap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a],h[b]); // 交换数值
}

void down(int i) {
    int t = i;
    if(2 * i <= mysize && h[2 * i] < h[t])  t = 2 * i;
    if(2 * i + 1 <= mysize && h[2 * i + 1] < h[t])  t = 2 * i + 1;
    if(t != i) {
        swap_heap(t, i);
        down(t);
    }
}

void up(int i) {
    while(i / 2 && h[i] < h[i / 2]) {
        swap_heap(i, i / 2);
        i /= 2; // 上升到父节点
    }
}
// 插入一个数,在最后插入
void insert(int x) {
    mysize++; // 记录下标
    cnt++; // 第几次插入
    ph[cnt] = mysize, hp[mysize] = cnt;
    h[mysize] = x;
    up(mysize);
}
// 删除第k个插入的数
void del(int k) {
    k = ph[k]; // 第k个插入的数对应的下标
    swap_heap(k, mysize);
    mysize--;
    down(k);
    up(k);
}
// 删除最小值，堆顶
void Del() {
    swap_heap(1, mysize);
    mysize--;
    down(1);
}

// 修改第k个插入的数
void change(int k, int x) {
    k = ph[k]; // 第k个插入的数对应的下标
    h[k] = x;
    down(k);
    up(k);
}
int main() {
    int n;
    cin >> n;
    string op;
    int x, y;
    while(n--) {
        cin >> op;
        if(op == "I") {
            cin >> x;
            insert(x);
        }else if(op == "PM") {
            cout << h[1] << endl;
        }else if(op == "D") {
            cin >> x;
            del(x);
        }else if(op == "DM") {
            Del();
        }else {
            cin >> x >> y;
            change(x, y);
        }
    }
    return 0;
}

模拟散列表

拉链法

实现代码：

#include<cstring>
#include<iostream>
using namespace std;

const int N = 100003; // 最好选质数
int h[N],e[N],ne[N],idx;

// 把某个数插入到槽内
void insert(int x)
{
    int k = (x%N+N) % N; // 求槽的下标
    e[idx] = x; // e数组是存取插入所有数的数据
    ne[idx] = h[k]; // 开始终点为-1，指向上一个结点,记录单链表
    // 的上一个结点
    h[k] = idx++; // 结点递增
    /h[k]表示在这个节点上的链表的最后一个节点的idx
}
// 散列表查询
bool find(int x)
{
    // 找到所在的槽
    int k = (x%N+N)%N;
    for(int = h[k];i != -1;i=ne[i])
    {
        if(e[i] == x)	return true;
    }
    return false;
}
int main()
{
    // 先把每个槽都置为-1，因为没有上个结点存在
    memset(h,-1,sizeof h);
    
}

---

开放寻址法

在一个数组中存数，如果当前位置没有人，则可以插入；否则一直向后查找，直到找到一个空位进行插入。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nul = 0x3f3f3f3f;
// N 应该为数据总数的整数倍数
int h[N];

int find(int x) // 查找和插入通用的函数
{
    int k = (x%N+N)%N;// 先锁定下标,再找空位
    while(h[k] != nul && h[k]!=x)
    {
        k++;
        if(k==N) k = 0; // 到尾了，返回头部进行插入
    }
    return k;
}
int main()
{
    memset(h,0x3f,sizeof h);
    int x;
    cin >> x;
    int k = find(x);
    // 插入
    h[k] = x; // 找到可以插入的空位
    
    // 查询
    if(h[k] != nul)	puts("存在该数字");
    // 如果当前的位置为空位，说明之前这个数字并没有进行插入，所以没有出现过
    
}

字符串哈希

将字符串映射为一个数字

前缀和公式 $h[i+1]=h[i]×P+s[i]h[i+1]=h[i]×P+s[i] i∈[0,n−1]i∈[0,n−1] $h为前缀和数组，s为字符串数组 区间和公式 (h[l,r]=h[r]−h[l−1]×P^{r−l+1})

#include<iostream>
#include<cstring>
typedef unsigned long long ull;
using namespace std;
const int N = 100010, P = 131;
ull h[N], p[N]; // h[N]是字符串哈希值得前缀和

ull query(int l, int r) {
    return  h[r] - h[l-1] * p[r-l+1];     
}

int main() {
    int n, m;
    cin >> n >> m;
    string x;
    cin >> x;
    h[0] = 0, p[0] = 1;
    for(int i = 0;i < n;i++) {
        p[i+1] = p[i] * P;
        h[i + 1] = h[i] * P + x[i];  // hash数组下标从1开始
    }
    while(m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(query(l1, r1) == query(l2, r2))  cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的算法基础课第二章数据结构全部内容，希望文章能够帮你解决算法基础课第二章数据结构所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。