資料結構(1)acwing
目錄- 資料結構(1)acwing
- 1.單鏈表和鄰接表（存盤樹和圖）
- （1）將x插到head結點
- （2）將x插到k節點后面
- （3）洗掉下標是k的后面的點
- 2.雙鏈表：優化某些問題
- 1.插入結點步驟：image-20210626104920749
- 2.洗掉節點
- 3.堆疊
- 4.佇列
- 5.KMP演算法
- 1.單鏈表和鄰接表（存盤樹和圖）
（用陣列模擬--->稱為靜態鏈表）
1.單鏈表和鄰接表（存盤樹和圖）
規范：
- -1表示空集，idx:指標(當前用到了哪個點)
- 第1個插入數的下標為0，因此第k個插入數的點下標為（k-1）
int e[N]:代表陣列內部的值，ne[N]:代表指標，指向下一個節點
插入節點到鏈表中步驟：
（1）將x插到head結點
（2）將x插到k節點后面
（3）洗掉下標是k的后面的點
void remove(int k){
ne[k] = ne[ne[k]];
}
2.雙鏈表：優化某些問題
-
規范：
- int e[N]、l[N]、r[N]，idx
- 0：左端點，1：右端點
-
1.插入結點步驟：
// 在下標為k的點的右邊，插入x
void add(int k,int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
}
ps: 想要在下標為k的左邊，插入x----》最easy方式：add(l[k],x)
-
2.洗掉節點
// 洗掉第k個點 void delete(int k){ r[l[k]] = r[k]; l[r[k]] = l[k]; }
3.堆疊
-
單調堆疊:（時間復雜度：O(n)----->出堆疊及入堆疊分別為n）
int n; int stk[N],tt; int main(){ cin >> n; for(int i = 0; i < n; i++){ int x; cin >> x; while(tt && stk[tt] >=x) t--; if(tt) cout << stk[tt] << ' '; else cout << -1 << ' '; stk[ ++ tt] = x; } return 0; }
4.佇列
-
單調佇列：
- 規范：hh = 0,tt = -1
-
實作代碼（滑動視窗）------{沒看懂}
5.KMP演算法
- 思路：
- 暴力演算法怎么做？
- 如何去優化？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288509.html
標籤：其他
上一篇：小程式學習紀實1
下一篇：RISC-V靠譜嗎？