数据结构(1)acwing

（用数组模拟—>称为静态链表）

1.单链表和邻接表（存储树和图）

规范：

• -1表示空集，idx:指针(当前用到了哪个点)
• 第1个插入数的下标为0，因此第k个插入数的点下标为（k-1）

int e[n]:代表数组内部的值，ne[n]:代表指针，指向下一个节点

插入节点到链表中步骤：

（1）将x插到head结点

（2）将x插到k节点后面

（3）删除下标是k的后面的点

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

• 拓展题：反转链表（https://www.acwing.com/file_system/file/content/whole/index/content/2465788/）

  

2.双链表：优化某些问题

• 规范：

  • int e[n]、l[n]、r[n]，idx
  • 0：左端点，1：右端点

• 1.插入结点步骤：

  

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

ps: 想要在下标为k的左边，插入x—-》最easy方式：add(l[k],x)

• 2.删除节点

  // 删除第k个点 void delete(int k){     r[l[k]] = r[k];     l[r[k]] = l[k]; } 

3.栈

• 单调栈:（时间复杂度：o(n)—–>出栈及入栈分别为n）

  int n; int stk[n],tt; int main(){     cin >> n;     for(int i = 0; i <　n; i++){         int x;         cin >> x;         while(tt && stk[tt] >=x) t--;         if(tt) cout << stk[tt] << ' ';         else cout << -1 << ' ';                  stk[ ++ tt] = x;     }     return 0; } 

  

4.队列

• 单调队列：

  • 规范：hh = 0,tt = -1

• 实现代码（滑动窗口）——{没看懂}

  

  需要了解更多c/c++开发分享Acwing Arithmetic Learning：数据结构(1)，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!

5.kmp算法

• 思路：

1. 暴力算法怎么做？
2. 如何去优化？