二、数据结构
1.单链表
头插法建立链表，删除一个数，在指定位置插入一个数
#include <iostream>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;
//idx，存储当前已经用到了哪个点。ne【i】表示节点的next指针是多少，
//e【i】表示结点i的值，head表示头结点的下标
void init()
{
//初始化链表
head=-1;
idx=0;
}
//将s插到头节点
void add_to_head(int x)
{
e[idx]=x;//先把x存下
ne[idx]=head;//红颜色指针指向head
head=idx;//head的值指向新增值
idx++;//结点已经被用过了移到下一个位置
}
//将x点插入下标为k的后面
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];//红颜色指针指向k
ne[k]=idx;//k指向下一步
idx++;
}
//单链表的删除,将k后面的删掉
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];
else remove(k-1);
}
else
{
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<' ';
cout<<endl;
return 0;
}
2.双链表
插入
看至数据结构01.01
3.栈、队列
栈先进后出，队列先进先出
//********栈
int stk[N],tt;
//插入
stk[++tt]=x;
//弹出
tt--;
//判断栈是否为空
if(tt>0) not empty
else empty
//栈顶
stk[tt];
//************队列
//在队尾插入元素，队尾弹出元素
int q[N],hh,tt=-1;
//弹出
hh++;
//插入
q[++tt]=x;
//判断是否为空
if(hh<=tt) not empty
else empty
//取元素
q(hh)
4.kmp：字符串查找算法
02:20
求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];//p[i]!=p[j+1]绿色和红色不匹配时
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}//i是起点
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;//如果它们匹配了就移动到下一个
if (j == m)
{
j = ne[j];
/ 匹配成功后的逻辑
}
}
5.trie
用来高效的存储和查找字符串集合的数据结构
例题
6.并查集（重要）集合，数据结构，寻找数用堆。
将两个集合合并，询问两个元素是否在一个集合当中。
基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，p【x】表示x的父节点。
int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}
例题
食物链
#include <iostream>
using namespace std;
const int N=50010;
int n,m;
int p[N],d[N];
int find(int x)//判断是不是树根
{
if(p[x]!=x)
{
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
p[i]=i;
}
int res=0;
while(m--)
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
if (x > n || y > n) res ++ ;//假话
else
{
int px = find(x), py = find(y);
if (t == 1)//同类时
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;//假话时
else if (px != py)//不在一个结合时
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n",res);
return 0;
}
7.堆
1.插入一个数.heap[++size]=x;up(size);
2.求集合中的最小值heap[1];
3.删除最小值heap[1]=heap[size];size--;down(1);
4.删除任意一个元素heap[k]=heap[size];size--;down(k);up(k);
5.修改任意一个元素heap[k]=x;down(k);up(k);
8.哈希表
哈希表的作用：把庞大复杂的数据映射到较小的范围。
可以把数据进行映射，成为哈希函数。
字符串哈希
字符串哈希主要用字符串前缀哈希法解决问题。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, P = 131;
unsigned long long h[N], p[N];
char str[N];
unsigned long long get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
cin >> str + 1;
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}
while (m--) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
STL
vector 变长数组，倍增的思想
queue队列，push(),front(),pop()