一言
那天,我听到了种子破土的声音,又细微又坚定。——子不语
数据结构基础模板题:数组模拟链表,栈,队列。

1链表

链表很简单,但是用数组模拟起来是真烦人,也可能我昨天脑子抽抽了。被各种没脑子的bug卡很久。。。

单链表

数组模拟链表:
所用的变量

//
struct node
{
    int val;
    int next;
} a[10000000];
int idx; // 当前数组用到的下标,可以理解成没有用的新地址。
int head;//头结点的地址

初始化:

 head = -1; // 让头结点指向空
 idx = 0;

头插:

void input_head(int num)
{
     这里是让新的节点作为头结点,而不是插到头结点的后边。
    a[idx].next = head;
    a[idx].val = num;
    head = idx;
    idx++;//这个地址用过了,所以要++。
}

因为链表本身的查找效率低,所以当要在某个点后边插入值或者在删除某个点,都要找到他再进行接下来的操作。但是当要求是,删除插入的第k个点后边的点,或者在插入的第k个点之后插入某个值的时候,这时候就比较简单,因为我们用的地址都是记录过的idx
idx从0开始,所以第k个数的下标为k-1。
在下标为k的节点后边插入num

void input_k(int k, int num)
{
    a[idx].val = num;
    a[idx].next = a[k].next;
    a[k].next = idx;
    idx++;
}

删除下标为k的后边那个节点

void dele(int k)
{
    a[k].next = a[a[k].next].next;
}

遍历
没什么好说的,让一个指针指向头结点,然后一直往后就ok

 int i = head;
    while (i != -1)
    {

        printf("%d ",a[i].val);
        i = a[i].next;
    }

题目:
实现一个单链表,链表初始为空,支持三种操作:

1 向链表头插入一个数;
2删除第 k个插入的数后面的数;
3在第k个插入的数后插入一个数。
现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k个数。操作过程中一共插入了 n个数,则按照插入的时间顺序,这 n个数依次为:第 1个插入的数,第 2个插入的数,…第 n个插入的数。
输入格式第一行包含整数 M,表示操作次数。接下来 M行,每行包含一个操作命令,操作命令可能为以下几种:
H x,表示向链表头插入一个数 x。
D k,表示删除第 k个插入的数后面的数(当 k为 0时,表示删除头结点)。
I k x,表示在第 k个插入的数后面插入一个数 x(此操作中 k均大于 0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5
AC代码:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val;
    int next;
} a[10000000];
int idx; // 当前数组用到的下标
int head;
void input_head(int num)
{
    a[idx].next = head;
    a[idx].val = num;
    head = idx;
    idx++;
}
void input_k(int k, int num)
{
    a[idx].val = num;
    a[idx].next = a[k].next;
    a[k].next = idx;
    idx++;
}
void dele(int k)
{
    a[k].next = a[a[k].next].next;
}
int main()
{
    // 初始化
    head = -1; // 让头结点指向空
    idx = 0;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char x;
        cin >> x;
        if (x == 'H')
        {
            int num;
            scanf("%d", &num);
            input_head(num);
        }
        if (x == 'I')
        {
            int num, k;
            cin >> k >> num;
            input_k(k - 1,num);
        }
        if (x == 'D')
        {
            int k;
            cin >> k;
            if (k == 0)
                head = a[head].next;
            else
                dele(k - 1);
        }
    }
    int i = head;
    while (i != -1)
    {
        // printf("%d %d %d\n", idx, a[i].val, a[i].next);
        printf("%d ",a[i].val);
        i = a[i].next;
    }

    return 0;
}

双链表

在单链表的基础上加了一指向前一个节点的指针,所以最开始要初始化两个端点,并且不存数据
题目:
实现一个双链表,双链表初始为空,支持 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个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。

数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例:
8 7 7 3 2 9

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val;
    int l;
    int r;
} a[10000000];
int idx;                   // 当前数组用到的下标
void input(int k, int num) // 在索引为k右边的插入num,如果要实现向k的左边插入,那就是在索引为k-1的右边插入
{

    a[idx].val = num;
    a[idx].l = k;//新节点的左边指向k的地址
    a[idx].r = a[k].r;//新节点的右边指向k的下一个
    a[a[k].r].l=idx;//第k个节点的下一个左指针指向新节点
    a[k].r = idx;//第k个节点的右边指向新节点
    idx++;
}

void dele(int k)
{
    a[a[k].l].r = a[k].r;
    a[a[k].r].l = a[k].l;
}
int main()
{
    // 初始化
    // 这里的a[0]和a[1]就相当于两个端点,是不存数据的
    a[0].r = 1;
    a[1].l = 0;
    idx = 2;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string x;
        cin >> x;
        if (x == "L")
        {
            int num;
            cin >> num;
            input(0, num);
        }
        else if (x == "R")
        {

            int num;
            cin >> num;
            input(a[1].l, num);
        }
        else if (x == "D")
        {
            int k;
            cin >> k;

            dele(k + 1);
        }
        else if (x == "IL")
        {
            int k, x;
            cin >> k >> x;
            input(a[k + 1].l, x);
        }
        else if (x == "IR")
        {

            int k, x;
            cin >> k >> x;
            input(k + 1, x);
        }
    }
    int i = a[0].r;
    while (i != 1)
    {

        printf("%d ", a[i].val);
        i = a[i].r;
    }

    return 0;
}

很简单
模拟栈

int sk[1000000];
int top=-1;
void push(int x)//入栈
{
    sk[++top]=x;

}
void pop()//弹出
{
    top--;
}
bool empty()//判断是否为空
{
    if(top==-1)return true;
    return false;
}
int querey()//返回栈顶元素
{
    return sk[top];
}

例题
给定一个表达式,其中运算符仅包含 +,-,,/(加 减 乘 除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)
(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 231−1。
题目中的整除是指向 0取整,也就是说对于大于 0的结果向下取整,例如 5/3=1对于小于 0的结果向上取整,例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。
输出格式
共一行,为表达式的结果。
数据范围
表达式的长度不超过 105

输入样例:
(2+2)*(1+1)
输出样例:
8
还没写。留个坑。

我是坑 

单调栈

单调栈就是让栈内元素满足单调性
单调递减栈:检查一下新入栈的元素,如果比栈顶元素大,就弹出这个栈顶元素,一直弹到栈顶元素比新入栈的元素大或者栈为空,然后将这个元素入栈。
反之亦然。
例题
给定一个长度为 N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1

输入格式第一行包含整数 N,表示数列长度。

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

输出格式共一行,包含 N个整数,其中第 i个数表示第 i个数的左边第一个比它小的数,如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
首先想一下暴力做法。

for(int i=0;i<n;i++)
{
    for(int j=i-1;j>=0;j--)
    {
        if(a[j]<a[i])
        {
         minans=a[j];
         break;
        }

    }
    if(minans<a[j])cout<<manans
    else cout<<"-1";
    }

浪费在哪里了呢?
当没有比a[j]小的数字时,就会白白遍历一遍。
这其实是可以避免的。
例如:
1,6,5,7,9
如果比如当遍历的6时,6比5大,所以,再往后,不可能有一个数字左边第一个比他小的数字是6了,因为有5,所以6就可以抹掉(出栈)
这时候需要用到单调栈,一个单调递增栈,
每次判断新入栈的元素是否比栈顶元素小,如果新入栈的元素比栈顶元素小,就弹出栈顶元素。
while(!empty()&&a[top]>=newnum)top--;
然后 栈顶元素就是当前元素左侧的第一个比当前元素小的元素
如果栈为空,那就不存在,就输出-1。
然后再将当前元素入栈
AC代码

#include<bits/stdc++.h>
using namespace std;
int sk[1000000];
int top=-1;
void push(int x)
{
    sk[++top]=x;

}
void pop()
{

    top--;
}
bool empty()
{
    if(top<0)return true;
    return false;
}
int main()
{
    int n;
    cin>>n;
   for(int i=0;i<n;i++)
   {
       int x;
       scanf("%d", &x);
        while(sk[top]>=x&&!empty())pop();
        if(empty())printf("-1 ");
        else {
            printf("%d ",sk[top]);

        }
        push(x);

}
return 0;
}

队列

模拟队列
手写队列的好处就是可以访问队尾元素,比如滑动窗口这道题就需要用到直接访问队尾元素

int sk[1000000];
int front=0,rear=-1;
void push(int x)//入队
{
    sk[++rear]=x;

}
void pop()//队头出队
{
    front++;
}
void pop_rear//队尾出队
{
    rear--;
}
bool empty()//判断是否为空
{
    if(rear<front)return true;
    return false;
}
int querey()//队头元素
{
    return sk[front];
}
int querey_tail()//队尾元素
{
    return sk[rear];
}

单调队列

单调队列,也是维护一个满足单调性的队列。
从头到尾单调递增:
每次入队前,判断入队元素与队尾元素的大小。如果入队元素小于队尾元素,就将这个队尾元素抹去。直到队尾元素大于入队元素或者队列为空。这样的话从头到尾就是单调增的
例题:
给定一个大小为 n≤106的数组。
有一个大小为 k的滑动窗口,它从数组的最左边移动到最右边。
你只能在窗口中看到 k个数字。每次滑动窗口向右移动一个位置。
以下是一个例子:该数组为 [1 3 -1 -3 5 3 6 7],k为3。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 7-36
1 3 -1 -3 5 [3 6 7]-37

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

输入格式
输入包含两行。

第一行包含两个整数 n和 k,分别代表数组长度和滑动窗口的长度。
第二行有 n个整数,代表数组的具体数值。同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
思路就是 维护一个长度为K的队列,
暴力做法的话

for(int i=front;i<=rear;i++)
{
 if(maxans<a[i])maxans=a[i];
}

就是每次遍历这个队列,找到最小的或者最大的。那就是O(n*k)的复杂度。
单调队列的做法呢?
例如求最小值。我们需要一个单调递增的队列,这样队头就是最小的元素。
维护的时候。
例如给定数组
1,4,6,3,4,5
该数组对与队列中的两个元素,到3要入队时,3比队尾元素6小,则对于往后只要6在窗口中,3一定在。这样的话,6就永远不可能是窗口中最小的值,所以6就可以从队尾剔除了,之后队尾是4,还比3大,继续剔除,然后将3入队,队尾就成了3。输出队头,1是最大的

while(!q.empty()&&newnum<q.rear())
{
q.pop_rear();
}

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[10000000];
int q[10000000];
int front=0,rear=-1;
void push(int x)//入队
{
    q[++rear]=x;

}
void pop()//队头出队
{
    front++;
}
void pop_rear()//队尾出队
{
    rear--;
}
bool empty()//判断是否为空
{
    if(rear<front)return true;
    return false;
}
void clear()
{
     front=0,rear=-1;
}
int main()
{

    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        while(!empty()&&a[i]<q[rear])
        {
           pop_rear();
        }
        push(a[i]);
        if(i-k>=1&&a[i-k]==q[front])pop();//当i-k>=1时,说明队列已经维持在k以上个了,
                                         //当a[i-k]==q[front],则下一步,队头就不在这个滑动窗口内了
                                         //因为这里是一次走一步,所以可以if判断,换成while也可以
        if(i-k>=0)cout<<q[front]<<" ";//判断队列元素够不够k个,够的话就是输出队头,就是最小值。

    }
     puts("");
     clear();//清空一下队列
       //反之亦然
       for(int i=1;i<=n;i++)
       {
         while(!empty()&&a[i]>q[rear])//这里改一下就行
        {
           pop_rear();
        }
        push(a[i]);
        if(i-k>=1&&a[i-k]==q[front])pop();

        if(i-k>=0)cout<<q[front]<<" ";
       }

}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇