用數組來模擬鏈表。這種實現鏈表的方式也叫靜態鏈表。
1.單鏈表
寫鄰接表：存儲圖和樹
我們定義：e[N]用來表示某個點的值是多少；ne[N]用來表示某個點的next指針是多少
e和ne是用下標關聯起來的
如：head->3->5->7->9->空(下標從0開始，3的下標是0，以此類推，空的下標為-1）
那么e[0]=3,ne[0]=1;e[1]=5,ne[1]=2;...e[3]=9,ne[3]=-1
?
//單鏈表模板//head指頭指針（頭指針指向頭結點），e[head]指的是頭結點的值
//idx指的是下一個可存儲的位置的索引，也可以說是插入的第幾個數的序號，即idx=0時表示插入的第一個數,其實就是存儲當前已經用到的點
int head,idx;int e[N],ne[N]; //e[N]存儲的是結點的值，ne[N]存儲的是結點的下一個結點的索引 //初始化
void init(){head = -1;//頭指針默認賦-1 idx = 0;
}//將x點插入頭結點
void insert_to_head(int x){e[idx] = x;
//將要插入的點的下一個指針指向head指向的點ne[idx] = head;
//將head指向新點，并idx指向下一個位置head = idx++;
}//將k后面的點刪除
void remove(int k){ne[k] = ne[ne[k]];
}//將x點插入下標為k的點后面
void insert(int k ,int x){e[idx] = x;
//將x點指向k指向的點ne[idx] = ne[k];
//將k指向x點，并idx向后走ne[k] = idx++;
}?
#include<iostream>using namespace std;const int N = 1e5+10;int head,idx;//head指頭指針（頭指針指向頭結點），e[head]指的是頭結點的值
//idx指的是下一個可存儲的位置的索引，也可以說是插入的第幾個數的序號，即idx=0時表示插入的第一個數int e[N],ne[N];//e[N]存儲的是結點的值，ne[N]存儲的是結點的下一個結點的索引 void init(){head = -1;//head的默認值賦-1 idx = 0;
}void insert_to_head(int x){e[idx] = x;ne[idx] = head;head = idx++;
}void remove(int k){ne[k] = ne[ne[k]];
}void insert(int k ,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}int main(){int m;cin>>m;init();while(m--){char op;int k,x;cin>>op;
//頭結點if(op == 'H'){cin>>x;insert_to_head(x);}else if(op == 'I'){//插入cin>>k>>x;insert(k-1,x);//第k個插入的數索引為k-1，因為idx是從0開始的，第一個插入的數索引為1；}else{//刪K后cin>>k;if(!k) head = ne[head];else remove(k-1);}}for(int i = head ; i != -1 ; i = ne[i]) cout<<e[i]<<" ";cout<<endl;return 0;
} 2.雙鏈表
我們定義：e[N]：當前結點的值是多少；l[N]：當前結點左邊是誰；r[N]：當前結點右邊是誰
并且令下標為0的點是head，下標為1的點是最后一個點
//雙鏈表模板 int l[N],r[N],e[N]; int idx; //初始化 void init(){//頭結點指向尾結點，尾結點指向頭節點，頭結點指針為0，尾結點指針為1，所以頭指針為1，尾指針為0r[0] = 1;l[1] = 0;idx = 2; //從2開始 } //插入，在k的右邊插入x void insert(int k, int x){e[idx] = x;//賦值 //先將k的兩邊分別指向原來鏈表l[idx] = k;r[idx] = r[k]; //改變原鏈表的指向l[r[k]] = idx;//必須這步在前面，否則r[k]的值會被修改 r[k] = idx++; }//在K的左邊插入，也可以直接調用，insert（l[k],x） //刪除第k個點，k右邊的左邊等于K的左邊，K的左邊的右邊等于k的右邊 void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k]; }
?
#include <iostream>
using namespace std;const int N=100010;
int idx,e[N],l[N],r[N];void init(){//0表示左端點//1表示右端點//虛擬頭和虛擬尾l[0]=-1,r[0]=1,l[1]=0,r[1]=-1;idx=2;
}
//最左端插入
void insertLeft(int x){e[idx]=x;r[idx]=r[0];l[idx]=0;l[r[0]]=idx;r[0]=idx;idx++;
}
//最右端插入
void insertRight(int x){e[idx]=x;r[idx]=1;l[idx]=l[1];r[l[1]]=idx;l[1]=idx;idx++;
}void insert_left_k(int k,int x){e[idx]=x;r[idx]=k;l[idx]=l[k];r[l[k]]=idx;l[k]=idx;idx++;
}void insert_right_k(int k,int x){e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}
//刪除第k個插入點
void remove(int k){l[r[k]]=l[k];r[l[k]]=r[k];
}int main(){int m;cin>>m;init();int k,x;string s;while(m--){cin>>s;if(s[0]=='L'){cin>>x;insertLeft(x);}else if(s[0]=='R'){cin>>x;insertRight(x);}else if(s[0]=='D'){cin>>k;remove(k+1);}else if(s[0]=='I' && s[1]=='L'){cin>>k>>x;insert_left_k(k+1,x);}else{cin>>k>>x;insert_right_k(k+1,x);}}for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";cout<<endl;return 0;
}
棧和隊列
棧：后進先出
隊列：先進先出
AcWing 828. 模擬棧
?//棧模板
// tt表示棧頂
int stk[N], tt;// 向棧頂插入一個數
stk[ ++ tt]?= x;// 從棧頂彈出一個數，刪除
tt?-- ;// 棧頂的值
stk[tt];// 判斷棧是否為空，如果 tt?>= 0，則表示不為空
if (tt?>= 0) not emptyelse empty
#include <iostream>
using namespace std;const int N=100010;
//tt是棧頂指針
int stk[N],tt;void push(int x){stk[tt]=x;tt++;
}void pop(){tt--;
}bool empty(){if(tt==0) return true;else return false;
}int query(){if(!empty()) return stk[tt-1];
}int main(){tt=0;int m;cin>>m;string s;int x;while(m--){cin>>s;if(s=="push"){cin>>x;push(x);}else if(s=="pop"){pop();}else if(s=="empty"){bool tmp=empty();if(tmp) cout<<"YES"<<endl;else cout<<"NO"<<endl;}else{cout<<query()<<endl;}}return 0;
}
AcWing 829. 模擬隊列?
//模擬普通隊列模板
// hh 表示隊頭，tt表示隊尾
int q[N], hh = 0, tt = -1;// 向隊尾插入一個數
q[ ++ tt] = x;// 從隊頭彈出一個數
hh ++ ;// 隊頭的值
q[hh];// 判斷隊列是否為空，如果 tt >= hh，則表示不為空
if (tt >= hh) not emptyelse empty
//模擬循環隊列模板
// 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];// 判斷隊列是否為空，如果hh != tt，則表示不為空(其實不能這樣簡單判斷是否為空)
if (hh != tt)
{}
?單調棧?
一般問題：給定一個序列，求序列中的每一個數左邊離它最近的且比它小的數在什么地方
//單調棧常見模型：找出每個數左邊離它最近的比它大/小的數
int top = -1;
while(n--)
{
? ? while (top >= 0 && check(stk[top], x)) top -- ;
? ? stk[ ++ top] = x;
}
?
//暴力做法，兩重循環
for(int i=0;i<n;i++){
?? ?for(int j=i-1;j>=0;j--){
?? ??? ?if(a[i]>a[j]){
?? ??? ??? ?cout<<a[j]<<endl;
?? ??? ??? ?break;
?? ??? ?}
?? ?}
}
?找性質：如果棧中兩個數,ai,aj存在：ai>=aj并且i<j，則ai可以刪除，這樣刪完后棧中嚴格單調。
這樣我們從單調棧的棧頂元素開始查找，如果棧頂元素大于等于a[i]，那么我們將其刪掉，直到棧頂元素小于a[i]，我們將其作為答案輸出，并把a[i]放進棧中。
#include <iostream>
using namespace std;
const int N = 100010;int stk[N];
int tt = -1;int main(){int n;cin>>n;while(n--){int x;cin>>x;while(tt >= 0 && stk[tt] >= x) tt--;//比x大的元素全彈出來 if(tt >= 0) cout<<stk[tt]<<" ";//彈完之后如果還有元素就輸出棧頂元素 else cout<<-1<<" ";//無就輸出-1 stk[++tt] = x;//最后要把x存入，因為x是有可能比之后的元素小的，并且x離之后的元素最近 }return 0;
}
單調隊列
常見用途：求滑動窗口里的最大值或最小值
//單調隊列常見模型：
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
? ? while (hh <= tt && check_out(q[hh])) hh ++ ; ?// 判斷隊頭是否滑出窗口
? ? while (hh <= tt && check(q[tt], i)) tt -- ;
? ? q[ ++ tt] = i;
}
?
隨著窗口的移動，每次在隊尾插入新元素，同時在隊頭彈出已經不在窗口里的元素，始終保證隊列的長度等于窗口里元素的個數。?
暴力做法：遍歷整個隊列，找到最小值/最大值。o(nk)
優化（最小值舉例）：
????????只要隊列里有前面一個數比后面一個數大，那前面的那個數就完全沒有用。我們把所有在前面的大的數刪掉后，整個序列就是一個單調遞增的序列。在單調遞增的序列里找最小值只需要找最左邊的端點，即隊頭。
最大值的做法和上面找最小值的做法類似
tips:隊列中存儲的是下標
#include <iostream>using namespace std;const int N = 1000010;int a[N],q[N];//q[N]存的是下標 int main(){int n,k;cin>>n>>k;for(int i = 0; i< n ; i++) cin>>a[i];//最小值 int hh = 0, tt = -1;for(int i = 0 ; i < n; i++){//滑出隊頭 if(hh <= tt && q[hh] < i-k+1) hh++;//i-k+1為窗口的最左端索引//去掉比當前要進入的數更大的數 while(hh <= tt && a[q[tt]] >= a[i]) tt--;//當前操作數的索引存入數組 q[++tt] = i;// i 等于 k - 1 時，窗口的大小剛好為 k。因此，當 i 大于或等于 k - 1 時，窗口就已經包含了至少 k 個元素。if(i >= k-1) cout<<a[q[hh]]<<" ";}cout<<endl;//最大值，除a[q[tt]] <= a[i]外無變化 hh = 0, tt = -1;for(int i = 0 ; i < n; i++){if(hh <= tt && q[hh] < i-k+1) hh++;while(hh <= tt && a[q[tt]] <= a[i]) tt--;q[++tt] = i;if(i >= k-1) cout<<a[q[hh]]<<" ";}cout<<endl;return 0;
}KMP
問題：需要在一個極長的字符串中匹配一個短字符串，比如各種文本編輯器里的查找功能。
即在母串中找到第一次出現完整子串時的起始位置。
我們將母串寫為S，模式串寫為P
暴力做法：
我們設置一個i指針指向母串和一個j指針指向模式串
當i指針和j指針指向的字符相等時，就同時后移一位；
當i指針和j指針指向的字符不相等時，就將i指針回溯到i-j+1的位置，j指針設置為0，重復匹配的過程，直到到達模式串的末尾，我們認為匹配成功
在最壞的情況下，這個算法的時間復雜度為O(mn)，m為母串的長度，n為模式串的長度
優化：利用已經部分匹配這個有效信息，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置
當匹配失敗時，我們將j指針移動到第k位，其中k的性質是：模式串P的第0位到第k-1位的串和母串T的i
指針前面的串盡可能地相等，即 T[i-k ~ i-1] == P[0 ~ k-1]
如果我們仔細觀察，又能發現 P[0 ~ k-1] == P[j-k ~ j-1]，也就是前綴和后綴相同。
為了能找到j指針回退的位置，我們預處理出來一個數組，稱為next數組，也被稱為部分匹配表。
next數組的值就表示：當主串與模式串的某一位字符不匹配時，模式串要回退的位置。
手動模擬求next數組：
對 p = “abcab”
? ? p?? ?a?? ?b?? ?c?? ?a?? ?b
下標?? ?1?? ?2?? ?3?? ?4?? ?5
next[]?? ?0?? ?0?? ?0?? ?1?? ?2
對next[ 1 ] ：前綴 = 空集—————后綴 = 空集—————next[ 1 ] = 0;
對next[ 2 ] ：前綴 = { a }—————后綴 = { b }—————next[ 2 ] = 0;
對next[ 3 ] ：前綴 = { a , ab }—————后綴 = { c , bc}—————next[ 3 ] = 0;
對next[ 4 ] ：前綴 = { a , ab , abc }—————后綴 = { a . ca , bca }—————next[ 4 ] = 1;
對next[ 5 ] ：前綴 = { a , ab , abc , abca }————后綴 = { b , ab , cab , bcab}————next[ 5 ] = 2;
?// s[]是長文本，p[]是模式串，m是s的長度，n是p的長度
//求模式串的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;
}// 匹配
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)
? ? {
? ? ? ? j = ne[j];
? ? ? ? // 匹配成功后的邏輯
? ? }
}
//KMP算法即字符串匹配算法
#include <iostream>using namespace std;const int N = 10010, M = 100010;//p，s，ne數組索引都是從1開始的
char p[N],s[M];
int ne[N];int main(){ int n,m;cin>>n>>p+1>>m>>s+1;// //輸出為空
// cout<<p<<endl;
// cout<<s<<endl;
// //輸出整個p和整個s
// cout<<p+1<<endl;
// cout<<s+1<<endl;//求ne數組的過程,ne[1]為0，所以從2開始，ne[i]表示從1到i之間，前綴和后綴最長相等元素的長度//next數組的求法是模板串自己與自己進行匹配 for(int i = 2, j = 0; i <= n; i++){//如果不等就回溯while(j && p[i] != p[j+1]) j = ne[j];//如果相等，模板串下標j的元素是提前和文本串對應j的下一個元素也就是下標為i的元素比較，所以j要+1if(p[i] == p[j+1]) j++;//現在j就已經是前綴和后綴最長相等元素的長度，所以要賦給ne[i]ne[i] = j;}//kmp匹配過程，模板串與文本串進行匹配 for(int i = 1, j = 0; i <= m; i++){//如果不等就回溯while(j && s[i] != p[j+1]) j = ne[j];//如果相等，模板串下標j的元素是提前和文本串對應j的下一個元素也就是下標為i的元素比較，所以j要+1（短的為模板串）if(s[i] == p[j+1]) j++;//j == n是找到了完整的相同的字符串if(j == n){cout<<i-n<<" ";//輸入匹配完全的字符串的頭下標，題目下標是從0開始的，所以不用加一 j = ne[j];//繼續回溯找下一個相同的字符串，不要從頭開始}}return 0;
}
?
)
)
