第二章 数据结构

​ 用数组模拟，不使用结构体的形式。

struct Node{
  int val;
    Node *next;
};

​ 这种操作在面试的时候常用，但在笔试题中用的不多，因为这种方式在创建新的链表的时候都会调用new函数，new Node();这种操作耗费的时间多，在十万或更多的级别会超时。

​ 多个单链表可以组合成邻接表——常用于用于存储图和树，head->空，head->⚪->⚪->⚪->空。链表不同于顺序表，逻辑上相邻的结点在物理上不一定相邻，只用靠指针链接就可以。

e[N];//表示某个点的值是多少。
ne[N];//表示某个点的next指针是多少。
//e[N]和ne[N]是用下标关联的。

int head,e[N],ne[N],idx;
// 初始化
void init(){
    head=-1;
    idx=0;
}

void add_to_head(int x){e[idx]=x,ne[idx]=head,head=idx++;}


void add(int k,int x){e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;}


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

826. 单链表 - AcWing题库

#include 
using namespace std;
const int N = 1e5+10;
int head=-1,e[N],ne[N],idx=0;
void add_to_head(int x){e[idx]=x,ne[idx]=head,head=idx++;}
void add(int k,int x){e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;}
void remove(int k){ne[k]=ne[ne[k]];}

int main(){
    int m;
    cin>>m;
    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;i=ne[i])cout< 
数组模拟双链表 
​ 常用于优化问题
 
e[N];//表示某个点的值是多少。
ne[N];//表示某个点的next指针是多少。
//e[N]和ne[N]是用下标关联的。

 
结点0
结点2
结点3
结点1
⚪
→
←
⚪
→
←
⚪
→
←
⚪
e[0]无意义
e[2]=5
e[3]=7
e[1]无意义
l[0]无意义
l[2]=0
l[3]=2
l[1]=3
r[0]=2
r[2]=3
r[3]=1
r[1]无意义
模板 
int e[N],l[N],r[N],idx;


void insert(int a,int x){
    e[idx]=x;
    l[idx]=a,r[idx]=r[a];
    l[r[a]]=idx,r[a]=idx++;
}


void remove(int a){
    l[r[a]]=l[a];
    r[l[a]]=r[a];
}
r[0]=1,l[1]=0,idx=2;
 
例题 
827. 双链表 - AcWing题库
 
#include 
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;

void insert(int a,int x){
    e[idx]=x;
    l[idx]=a,r[idx]=r[a];
    l[r[a]]=idx,r[a]=idx++;
}
void remove(int a){
    l[r[a]]=l[a];
    r[l[a]]=r[a];
}

int main(){
    r[0]=1,l[1]=0,idx=2;
    int n;
    cin>>n;
    while(n--){
        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);
        }
        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< 
栈与队列 
栈（先进后出） 
​ 栈的一个重要特性就是先进后出，
 
数组模拟栈 
模板 
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{

}
 
例题 
队列（先进先出） 
解析 
模板 
普通队列 
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}
 
循环队列 
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}
 
单调栈和单调队列 
单调栈 
​ 单调栈对应题型——给定一个序列，求序列中每一个数左（右）边，离它最近的且比它大（小）的数。
 
模板&例题 
830. 单调栈 - AcWing题库
 
​ 很容易能想到的暴力做法，使用两重循环，对每一个数向左进行查找，找到的第一个比当前数小的就输出找不到就“-1”然后进行下一个循环。当然这样就很容易超时。
 
​ 可以使用一个栈来保存经过的数字，每次查找的时候就向前出栈找，这样可以发现一个性质，要是存在一个数据段
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
      
      
       a_1,a_2,a_3
      
     
    a1​,a2​,a3​，其中
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1​大于
    
     
      
       
        
         a
        
        
         2
        
       
      
      
       a_2
      
     
    a2​，那么
    
     
      
       
        
         a
        
        
         2
        
       
      
      
       a_2
      
     
    a2​是不需要
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1​作为答案的而且
    
     
      
       
        
         a
        
        
         3
        
       
      
      
       a_3
      
     
    a3​或之后的数也不需要
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1​作为答案，因为要找也找比
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1​小的
    
     
      
       
        
         a
        
        
         2
        
       
      
      
       a_2
      
     
    a2​。这时候我们就可以确定
    
     
      
       
        
         a
        
        
         1
        
       
      
      
       a_1
      
     
    a1​是不会作为答案出现的，所以直接出栈就好。
 
​ 这个的时间复杂度看似有两重循环，但是一重循环内的入栈出栈操作每个数只会出现一次，所以实际时间复杂度是
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)级别的。
 
#include 
using namespace std;
const int N=100010;
int stk[N],tt;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        while(tt&&stk[tt]>=x)tt--;
        if(!tt)printf("-1 ");
        else printf("%d ",stk[tt]);
        stk[++tt]=x;
    }
    return 0;
}
 
单调队列 
解析 
模板&例题 
154. 滑动窗口 - AcWing题库
 
​ 可以使用一个队列来维护，每次一个数入队，要是当前队列长度超过窗口，就将队首元素弹出，以此保证窗口的稳定。
 
​ 从数据上来看，要是直接暴力跑时间复杂度将会是
    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        
         0
        
        
         6
        
       
       
        ∗
       
       
        1
       
       
        
         0
        
        
         6
        
       
       
        )
       
      
      
       O(10^6*10^6)
      
     
    O(106∗106)绝对超时，所以还要想办法优化。和单调栈一样找一个数据段
    
     
      
       
        
         a
        
        
         1
        
       
       
        ,
       
       
        
         a
        
        
         2
        
       
       
        ,
       
       
        
         a
        
        
         3
        
       
      
      
       a_1,a_2,a_3
      
     
    a1​,a2​,a3​，其中
    
     
      
       
        
         a
        
        
         1
        
       
       
        <
       
       
        
         a
        
        
         2
        
       
       
        <
       
       
        
         a
        
        
         3
        
       
      
      
       a_1a1​ 
#include 
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;iq[hh])hh++;

        while(hh<=tt&&a[q[tt]]>=a[i])tt--;
        q[++tt]=i;

        if(i>=k-1)printf("%d ",a[q[hh]]);
    }

    puts("");

    hh=0,tt=-1;
    for(int i=0;iq[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 
鸣谢 
文中出现的题目来自，主要思路和代码模板来自Acwing闫学灿大佬。
 题库 - AcWing