数据结构（1）

单链表

#include <iostream> 
using namespace std;
const int N = 1e6+10; 
int shuzhi[N], next_position[N]; 
int head, idx ; //头结点下标、当前的下标 

void init()
{
    head = -1; 
    idx = 0 ; 
}

void add_to_head(int x)
{
    shuzhi[idx] = x ; 
    next_position[idx] = head ;  //这个值指向当前head的值 
    head = idx ; // head指向这个值 
    idx++ ;     //当前idx的值被使用过了 
}

void insert(int k, int x)
{
    shuzhi[idx] = x ; 
    next_position[idx] = next_position[k] ; 
    next_position[k] = idx ;     
    idx++ ;  
} 

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

int main(){
    init() ; 
    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 = next_position[head] ; 
            remove(k-1) ; 
        }
        else {
            cin>>k>>x ; insert(k-1,x) ; 
        }
    }
    
    for(int i=head  ; i != - 1; i = next_position[i] )
        cout<<shuzhi[i]<<' ' ;
    
    return 0;
} 

双链表

#include <iostream> 
using namespace std;
const int N = 1e6+10; 
int e[N], idx ; 
//不带头结点
int l[N],r[N] ; //左、右指针 

void init()
{
    // 0为左端点、1为右端点 
    r[0] = 1 ; l[1] = 0 ;
    idx = 2 ;   
}

void add( int k, int x) //在k的右边插入 
{
    e[idx] = x ; 
    l[idx] = k ; 
    r[idx] = r[k] ; 
    l[r[k]] = idx ;  //
    r[k] = idx ;      // 这两个顺序不能反 
    idx ++ ;         
}
 
void remove(int k)
{
    r[l[k]] = r[k] ; 
    l[r[k]] = l[k] ;    
} 

int main(){
    init() ; 
    int m ; cin>>m ;
    while(m--)
    {
        int k,x ; 
        string op ; cin>>op ; 
        if(op=="IR") {
            cin>>k>>x ; add(k+1,x) ; 
        } 
        else if(op=="D"){
            cin>>k; remove(k+1) ; 
        }
        else if(op=="IL"){
            cin>>k>>x; add(l[k+1],x); 
        }
        else if(op=="L"){
            cin>>x ; add(0,x) ;
        }
        else{
            cin>>x; add(l[1],x) ; 
        }
 
    }
    for(int i=r[0]; i!=1  ; i = r[i])
        cout<<e[i]<<' ' ; 
    
    return 0;
} 

栈

#include <iostream> 
using namespace std;
const int N = 1e6+10; 

int  s[N], tail=0 ; 

void push(int x){
    tail ++ ; 
    s[tail] = x ;
}

void pop(){
    tail-- ;
}

bool empty()
{
    return tail>0 ; 
}

void query(){
    cout<<s[tail]<<endl ; 
} 

int main(){

    int m; cin>> m ; 
    while(m--){
        string op; 
        int x ; 
        cin>>op;
        if(op=="push") {
            cin>>x ; push(x)  ;
        }
        else if(op=="pop")  pop(); 
        else if(op=="query") query() ; 
        else{
            if(empty()) cout<<"No"<<endl; 
            else cout<<"YES"<<endl; 
        }       
    }
    return 0;
} 

队列

#include <iostream>
using namespace std ;
const int N = 1e6 ; 

int m,q[N],head=0,tail=-1 ; 

void push(int x){
    q[++tail] = x ; 
}

void query(){
    cout<<q[head]<<endl ; 
}

bool empty(){
    if( head <= tail ) cout<<"NO\n"  ; 
    else cout<<"YES\n" ;
}

void pop(){
    head++ ; 
}

int main(){
    cin>> m ; 
    while(m--){
        string s ;
        int x ; 
        cin>>s ;
        if(s == "push") cin>>x , push(x) ; 
        else if(s == "pop") pop() ; 
        else if(s == "query") query() ; 
        else empty() ;
    }
    return 0; 
}

单调栈

给定一个长度为 <span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mi">N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 <span id="MathJax-Span-5" class="mrow"><span id="MathJax-Span-6" class="mo">−<span id="MathJax-Span-7" class="mn">1。

#include <iostream> 
using namespace std ; 
const int N = 1e6 ; 
int s[N] , tail =0 ; 

int main(){
    int n ; cin>>n ; 
    while(n--){
        int x; cin>>x ; 
        while( tail > 0 && s[tail] >= x ) tail-- ; 
        if(tail == 0) cout<<"-1 "; 
        else {
            cout<<s[tail]<<' '; 
        }
        s[++tail] = x ; 
    }
    
    return 0; 
}

 单调队列

依次输出给定窗口中的最大值与最小值 

#include <iostream> 
using namespace std;
const int N = 1e6+10; 
int a[N], q[N] ; 
int head=0, tail = -1 ; 
// 单调队列 实现 滑动窗口
// 1 3 -1 -3 5 3 6 7  
int main(){
    int n,k ; 
    cin>>n>>k ; 
    for( int i=0;  i<n ; i++) cin>>a[i] ; //读取序列 
    
    for( int i = 0 ; i<n ; i++ )
    {
        if(head<= tail&& q[head]<i-k+1) head++ ; // 判断窗口是否应该滑动 
        while( head<=tail  && a[q[tail]] >= a[i] ) tail-- ; // 单增去掉更大值
        q[++tail] = i ;  //入队 ，入队的是数值的下标
        if( i>=k-1 ) cout<<a[q[head]] << ' ';  //大于3开始，输出此时队头(即最小) 
    } 
    cout<<endl ; 
    
    head = 0 ; tail =-1 ; 
    for( int i = 0; i<n ; i++)
    {
        if(head<= tail && q[head]<i+1-k ) head++ ; 
        while(head<=tail && a[q[tail]] <= a[i] ) tail-- ;
        q[++tail] = i ; 
        if( i>= k-1 ) cout<<a[q[head]]<<' ';
     } 

    return 0;
} 

KMP

学习过原理，具体实现还是第一次，感觉有点问题

#include <iostream> 
using namespace std;
const int N = 1e6+10; 
int ne[N] ; // next数组 
char p[N],s[N] ; //模式串和主串 
int n,m; 

int main(){
     
    cin>>n>>p+1>>m>>s+1 ; 
    // 求解next数组, ababa -> 01123 
    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 ; 
    }
    
    
    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)
        {
            cout<<i-n<<' ' ; 
            j = ne[j] ; 
        }
    }
    return 0;
}