第二章：数据结构
2-1-1 单链表
（因为传统链式存储需要大量使用New函数，会带来大量时间上的开销，所以我们用数组模拟）
（通常情况下，数据规模1e6）
#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;//指向空结点
idx=0;
}
//头插法：将x插到头结点
void add_to_head(int x){
e[idx]=x,ne[idx]=head,head=idx,idx++;
}
//将x插到下标是k的结点后面
void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++:
}
//将下标是k的点后面的点删掉
void remove(int k){
ne[k]=ne[ne[k]];
}
int main(){
}
/*双链表*/
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int m;
int e[N],l[N],r[N],idx;
//初始化
void init(){
//0表示左端点，1表示右端点
r[0]=1;l[1]=0;
idx=2;
}
//在下标是k的点的右边插入x
//如果是在下标为k的点的左边插入X，直接调用add(k-1,x)
void add(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]idx;
r[k]=idx;
}
//删除第k个点
void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main(){
}
const int N=100010;
//定义栈
int stk[N],tt;
//插入
stk[++tt] = x;
//弹出
tt--;
//判断栈是否为空
if (tt >0) not empty
else empty
//取栈顶元素
stk[tt];
//定义队列
int q[N],hh,tt=-1;
//在队尾插入元素，在队头弹出元素
//插入
q[++tt]=x;
//弹出
hh++;
//判断队列是否为空
if(hh<=tt) not empty
else empty
//取出队头元素
q[hh]
2-2-5 单调栈
常见题型：给出一个序列，找出每个数左边（或右边）满足某个性质最近的数
暴力做法：
for(int i=0;i<n;i++){
for(int j=i-1;j>=0;j--){
if(a[j]<a[i]){
cout<<j<<endl;
break;
}
}
}
#include<iostream>
using namespace std;
const int N=100010;
int n;
int stk[N],tt;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
while(tt && stk[tt]>=x) tt--;//一直出栈，直到找到第一个比栈顶小的元素
if(tt) cout<<stk[tt]<<" ";//栈不空，直接输出栈顶
else cout<<-1<<' ';//不存在
stk[++tt]=x;//该数入栈
}
return 0;
}
2-2-6 单调队列
求滑动窗口的最大值最小值
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,k;
int a[N],q[N];
int main(){
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--;//把队列里所有比a[i]大的数都踢掉，它们将永无出头之日
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
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
int n,m;//n是模式串，m是原串
char p[N],s[M];
int ne[N];
int main(){
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;
}
//kmp匹配过程
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);//不加1是因为下标要从0开始
//j已经走到头了，为了下一次匹配j走到ne[j]
j=ne[j];//为下一次匹配做准备
}
}
return 0;
}
2-2-8 Tire树
用来高效的存储和查找字符串集合的数据结构
题目一定会限制字符的种类
存储方法：如图所示。
最后需要在每一个单词的结尾加上一个标记
查询方法：
①在上图查询单词”abcf”
由根节点a–>b—>c，发现下面没有f，故不存在单词”abcf”
②在上图查询单词”abcd”
由根节点a—>b—>c—>d，虽然存在，但是d字母上没有标记，所以”abcd”也不存在
模板题：
维护一个字符串集合，支持两种操作：
“I x”向集合中插入一个字符串x；
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 1 e 5 1e51e5，字符串仅包含小写英文字母。
#include<iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;//son存储每个点的子结点，cnt存储当前点为结尾的单词个数,idx指示当前用到的下标
char str[N];
//下标是0的点，既是根结点，又是空结点
void insert(char str[]){
int p=0;//从根节点开始
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;//如果p点不存在u这个儿子，创建它
p=son[p][u];
}
//最后p点为该单词的结尾，对其加上标记，次数+1
cnt[p]++;
}
int query(char str[]){
int p=0;//从根结点开始
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}
int main(){
int n;
scanf("%d",&n);
while(n--){
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I') insert(str);
else printf("%d\n",query(str));
}
return 0;
}
应用：最大异或对
在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=32*N+5;
int son[N][2],idx;
int a[N];
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i &1;//取出整数的第i位
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x){
int p=0;
int t=0;
for(int i=30;i>=0;i--){
int u=x>>i &1;
if(son[p][!u]){
p=son[p][!u];
t=t*2+!u;
}else{
p=son[p][u];
t=t*2+u;
}
}
return t;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0;i<n;i++){
insert(a[i]);
int t=query(a[i]);
res=max(res,a[i]^t);
}
cout<<res<<endl;
return 0;
}
2-2-9 并查集
快速地处理以下问题：
1、将两个集合合并
2、询问两个元素是否在一个集合当中
对于暴力解法：
belong[x]=a;//x元素属于集合a
//查询是否在同一个集合操作
if(belong[x]==belong[y]) //O(1)
//合并两个集合
//需要一个一个修改每个元素的编号，时间复杂度太高
2-2-10 堆
如何手写一个堆？
手写堆主要解决以下问题：
1、插入一个数
heap[++size]=x;up(size);
1
2、求集合当中的最小值
heap[1];
1
3、删除最小值
heap[1]=heap[size];size–;down(1);
1
4、删除任意一个元素
heap[k]=heap[size];size–;down(k);up(k);//down和up只会执行一次
1
5、修改任意一个元素
heap[k]=x;down(k);up(k);
1
注：下标从1开始比较方便
核心函数：
down操作
int h[N],Size;
void down(int u){
int t=u;
if(u*2<=Size && h[u*2]<h[t]) t=u*2;
if(u*2+1<=Size && h[u*2+1] < h[t]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
up操作：
void up(int u){
while(u/2 &&h[u/2]>h[u]){
swap(h[u/2],h[u]);
u/=2;
}
}
例题：838. 堆排序
输入一个长度为n的整数数列，从小到大输出前m小的数。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int h[N],Size;
void down(int u){
int t=u;
if(u*2<=Size && h[u*2]<h[t]) t=u*2;
if(u*2+1<=Size && h[u*2+1] < h[t]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
Size=n;
for(int i=n/2;i;i--) down(i);
while(m--){
printf("%d ",h[1]);
h[1]=h[Size];
Size--;
down(1);
}
return 0;
}
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
“I x”，插入一个数x；
“PM”，输出当前集合中的最小值；
“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
“D k”，删除第k个插入的数；
“C k x”，修改第k个插入的数，将其变为x；
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010;
int n;
int h[N],ph[N],hp[N],Size;
/*ph[i]表示第i个插入的数的下标 hp[i]表示下标为i的数是第几个插入的*/
void heap_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u){
int t=u;
if(u*2<=Size && h[u*2]<h[t]) t=u*2;
if(u*2+1<=Size && h[u*2+1] < h[t]) t=u*2+1;
if(u!=t){
heap_swap(u,t);
down(t);
}
}
void up(int u){
while(u/2 &&h[u/2]>h[u]){
heap_swap(u/2,u);
u/=2;
}
}
int main(){
scanf("%d",&n);
int m=0;
while(n--){
char op[10];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I")){
scanf("%d",&x);
Size++;
m++;
ph[m]=Size;
hp[Size]=m;
h[Size]=x;
up(Size);
}else if(!strcmp(op,"PM")){
printf("%d\n",h[1]);
}else if(!strcmp(op,"DM")){
heap_swap(1,Size);
Size--;
down(1);
}else if(!strcmp(op,"D")){
scanf("%d",&k);
k=ph[k];
heap_swap(k,Size);
Size--;
down(k);up(k);
}else{
scanf("%d%d",&k,&x);
k=ph[k];
h[k]=x;
down(k),up(k);
}
}
return 0;
}
2-2-11 哈希表
哈希表存储结构：①开放寻址法 ②拉链法
字符串哈希方式
例如有哈希函数 h(x)，将区间[-1e9,1e9]的数字映射到[0,1e5]中
方法：直接将 x mod 1e5，但是这样会存在哈希冲突**（取模的数尽可能是质数）**
解决哈希冲突的方法：①开放寻址法 ②拉链法
模拟散列表
维护一个集合，支持如下几种操作：
“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。
拉链法：
#include<iostream>
#include<cstring>
using namespace std;
const int N=100003;//尽可能取成素数
int h[N],e[N],ne[N],idx;
void insert(int x){
int t=(x%N+N)%N;//防止出现负数
e[idx]=x;ne[idx]=h[t];h[t]=idx++;
}
bool find(int x){
int t=(x%N+N)%N;
for(int i=h[t];i!=-1;i=ne[i]){
int u=e[i];
if(u==x) return 1;
}
return 0;
}
int main(){
int n;
scanf("%d",&n);
memset(h,-1,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I'){
insert(x);
}else{
if(find(x)){
puts("Yes");
}else{
puts("No");
}
}
}
}
开放寻址法：
#include<iostream>
#include<cstring>
using namespace std;
const int N=100003,null=0x3f3f3f3f;
int h[3*N];
int find(int x){
int t=(x%N+N)%N;
while(h[t]!=null&&h[t]!=x){
t++;
if(t==N) t=0;
}
return t;
}
int main(){
int n;
scanf("%d",&n);
memset(h,0x3f,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
int k=find(x);
if(op[0]=='I'){
h[k]=x;
}else{
if(h[k]==null) puts("No");
else puts("Yes");
}
}
}