＜数据结构＞ - 数据结构在算法比赛中的应用（上）
目录
单链表
双链表
单调栈
单调队列&滑动窗口
KMP字符串
单链表
思路：
工程链表：
typedef struct SListNode
{
int data; // val
struct SListNode* next; // 存储下一个节点的地址
}SLN;算法表示法：
head 表示头结点的下标，数组e[]表示链表 date值，ne[]表示存储下一个节点的地址的指针next，idx 存储当前已经用到了哪个点
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的指针
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点,工程链表中的新地址
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1; //-1表示指向空
idx = 0; //下标索引从0开始
}
// 将x插到头结点
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
// 将x插到下标是k的点后面
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]]; //让结点直接指向下一个结点的next，不用管内存泄漏
}
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]; //如果k为0，删除头结点，ne[head]必指向空
else remove(k - 1); //k-1对应从0开始的idx
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
双链表
思路：
与单链表类似，e[N]存值，l[N]、r[N]表示左右指针
双链表初始化：
0号店表示头结点，1号表示尾节点
r[0] = 1, l[1] = 0; idx = 2;删除节点a的remove（）函数
void remove(int a) { l[r[a]] = l[a]; r[l[a]] = r[a]; }在节点k的右边插入一个数x方法
第一步：开一个新节点，左右指针指向k，与k的下一个节点
第二步：先让k的下一个节点的左指针指向新点，再用k的右指针指向新点；顺序搞错会导致数据覆盖
void insert(int a, int x) { e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = 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;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1); //idx从2开始，插入节点夹在head与tail之间
}
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;
}
单调栈
cin，cout速度大幅提高方法：
cin.tie(0);
ios::sync_with_stdio(false);#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
//cin.tie(0);
// ios::sync_with_stdio(false);
int n;
cin >> n;
while (n -- )
{
int x;
cin>>x;
while (tt && stk[tt] >= x) tt -- ; //不符合，出栈
if (!tt) cout<<"-1"<<" ";
else cout<<stk[tt]<<" ";
stk[ ++ tt] = x; //当前值入栈，与下一个数比较
}
return 0;
}
单调队列&滑动窗口
思路：
- 利用双端队列思想
- 设 队列q[hh],q[tt]分别表示窗口左边界（队头）与右边界（队尾），存储下标
- 用 i 表示窗口进程，则窗口范围【i-k+1,i】
（先求最小值）根据滑动窗口性质，队头的数会先消失，如果队尾插入的值比前一个数小，则前数不是最小值，所以直到出窗口也不会被输出
核心操作：如果队尾插入的值比前一个数小，那么将前一个数移出队列，最终队列会形成单调递增，取最小值永远在q[hh]处取
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];
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 ++ ; //队首出窗口，hh++
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ; //队列不满足单调，tt--将元素移出
q[ ++ tt] = i; //将新元素下标入队尾
if (i >= k - 1) printf("%d ", a[q[hh]]); //满足遍历个数大于窗口k值，输出队头
}
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 n,m;
int ne[N];
char s[M],p[N];
int main()
{
cin>>n>>p+1>>m>>s+1;
for(int i=2,j=0;i<=n;i++) //构造next数组
{
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<=m;i++)
{
while(j&&s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n)
{
printf("%d ",i-n);
//j=ne[j]; 找到后直接跳过j段
}
}
return 0;
}