文章目錄

• 鏈表和鄰接鏈表
• • 單鏈表
  • • 826 單鏈表
  • 雙鏈表
  • • 827 雙鏈表
• 棧與隊(duì)列
• • 830 單調(diào)棧
• kmp
• • 831 kmp字符串

鏈表和鄰接鏈表

數(shù)據(jù)模擬的速度會(huì)快很多，每次 new 一個(gè)新的節(jié)點(diǎn)，速度非常慢。

單鏈表

其中的領(lǐng)接表用的最多，主要是用來存儲(chǔ)圖和數(shù)。

每個(gè)點(diǎn)都存儲(chǔ)了 value 和 next
e[N], ne[N] 當(dāng)前的數(shù)值和next指針空節(jié)點(diǎn)的位置是-1

826 單鏈表

實(shí)現(xiàn)一個(gè)單鏈表，鏈表初始為空，支持三種操作：

向鏈表頭插入一個(gè)數(shù)；
刪除第 k 個(gè)插入的數(shù)后面的數(shù)；
在第 k 個(gè)插入的數(shù)后插入一個(gè)數(shù)。
現(xiàn)在要對(duì)該鏈表進(jìn)行 M 次操作，進(jìn)行完所有操作后，從頭到尾輸出整個(gè)鏈表。

注意:題目中第 k 個(gè)插入的數(shù)并不是指當(dāng)前鏈表的第 k 個(gè)數(shù)。例如操作過程中一共插入了 n 個(gè)數(shù)，則按照插入的時(shí)間順序，這 n 個(gè)數(shù)依次為：第 1 個(gè)插入的數(shù)，第 2 個(gè)插入的數(shù)，…第 n 個(gè)插入的數(shù)。

輸入格式
第一行包含整數(shù) M，表示操作次數(shù)。

接下來 M 行，每行包含一個(gè)操作命令，操作命令可能為以下幾種：

H x，表示向鏈表頭插入一個(gè)數(shù) x。
D k，表示刪除第 k 個(gè)插入的數(shù)后面的數(shù)（當(dāng) k 為 0 時(shí)，表示刪除頭結(jié)點(diǎn)）。
I k x，表示在第 k 個(gè)插入的數(shù)后面插入一個(gè)數(shù) x（此操作中 k 均大于 0）。
輸出格式
共一行，將整個(gè)鏈表從頭到尾輸出。

數(shù)據(jù)范圍
1≤M≤100000
所有操作保證合法。

輸入樣例：

10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6

輸出樣例：

6 4 6 5 #include <iostream>using namespace std;const int N = 100010;// head 是頭結(jié)點(diǎn)的下標(biāo) // e[i] 是節(jié)點(diǎn) i 的值 // ne[i] 表示節(jié)點(diǎn) i 的 next 指針是多少 // idx 表示最新用到了哪個(gè)位置,一直只會(huì)增加 int head, e[N], ne[N], idx;void init() {idx = 0;head = -1; }// 在頭部加入節(jié)點(diǎn) void add_to_head(int x) {e[idx] = x;ne[idx] = head;head = idx;idx ++ ; }// x 這個(gè)點(diǎn)插入到下標(biāo)為 k 的后面 void add(int k, int x) {e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx ++ ; }// 刪除下標(biāo)為 k 的后面的點(diǎn) void remove(int k) {ne[k] = ne[ne[k]]; // 刪除了就不管了，空間不用釋放 }int main() {int m;cin >> m;init();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 != -1; i = ne[i]) cout << e[i] << ' ';cout << endl;return 0; }

雙鏈表

核心
0 作為 head， 1 作為 tail
int l[N], r[N];

827 雙鏈表

實(shí)現(xiàn)一個(gè)雙鏈表，雙鏈表初始為空，支持 5 種操作：

在最左側(cè)插入一個(gè)數(shù)；
在最右側(cè)插入一個(gè)數(shù)；
將第 k 個(gè)插入的數(shù)刪除；
在第 k 個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)；
在第 k 個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)
現(xiàn)在要對(duì)該鏈表進(jìn)行 M 次操作，進(jìn)行完所有操作后，從左到右輸出整個(gè)鏈表。

注意:題目中第 k 個(gè)插入的數(shù)并不是指當(dāng)前鏈表的第 k 個(gè)數(shù)。例如操作過程中一共插入了 n 個(gè)數(shù)，則按照插入的時(shí)間順序，這 n 個(gè)數(shù)依次為：第 1 個(gè)插入的數(shù)，第 2 個(gè)插入的數(shù)，…第 n 個(gè)插入的數(shù)。

輸入格式
第一行包含整數(shù) M，表示操作次數(shù)。

接下來 M 行，每行包含一個(gè)操作命令，操作命令可能為以下幾種：

L x，表示在鏈表的最左端插入數(shù) x。
R x，表示在鏈表的最右端插入數(shù) x。
D k，表示將第 k 個(gè)插入的數(shù)刪除。
IL k x，表示在第 k 個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)。
IR k x，表示在第 k 個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)。
輸出格式
共一行，將整個(gè)鏈表從左到右輸出。

數(shù)據(jù)范圍
1≤M≤100000
所有操作保證合法。

輸入樣例：

10 R 7 D 1 L 3 IL 2 10 D 3 IL 2 7 L 8 R 9 IL 4 7 IR 2 2

輸出樣例：

8 7 7 3 2 9

初始狀態(tài)

#include <iostream>using namespace std;const int N = 100010;int m; // idx 是最新的數(shù)值下標(biāo)位置 // e[N] 是當(dāng)前位置的數(shù)值是多少 // l[N] 是某個(gè)節(jié)點(diǎn)左邊的位置 // r[N] 是某個(gè)節(jié)點(diǎn)右邊的位置 int l[N], r[N], e[N], idx;// 默認(rèn) 0 是頭的位置, 1 是尾的位置 void init() {r[0] = 1;l[1] = 0;idx = 2; // idx 從2開始 }// 在 k 后面加上節(jié)點(diǎn) x void add(int k, int x) {e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx; // 先左后右邊，保證 k 的有效性r[k] = idx;idx ++ ; }// 刪除第 k 個(gè)點(diǎn) void remove(int k) {r[l[k]] = r[k];l[r[k]] = l[k] }

棧與隊(duì)列

棧就是先進(jìn)后出
隊(duì)列就是先進(jìn)先出

模擬棧

#include <iostream>using namespace N = 100010;// stk[N] 棧 // tt 棧頂, 已經(jīng)有數(shù)據(jù) int stk[N], tt;// 插入 stk[++ t] = x; // 彈出 tt -- ;// 判斷棧是否為空 if (tt > 0) not empty else empty// 棧頂 stk[tt];

隊(duì)列

// **************** 隊(duì)列// q[N] 隊(duì)列 // hh 隊(duì)頭 // tt 隊(duì)尾，tt 位置上是原有的數(shù)據(jù) // 隊(duì)尾插入，隊(duì)頭彈出 int q[N], hh, tt = -1;// 插入 q[++ tt] = x;// 彈出 hh ++ ;// 判斷空 if (hh << tt) not empty else empty// 取出隊(duì)頭元素 q[hh]

單調(diào)棧
找到每個(gè)數(shù)左邊滿足某個(gè)條件的最近的數(shù)

830 單調(diào)棧

給定一個(gè)長(zhǎng)度為 N 的整數(shù)數(shù)列，輸出每個(gè)數(shù)左邊第一個(gè)比它小的數(shù)，如果不存在則輸出 ?1。

輸入格式
第一行包含整數(shù) N，表示數(shù)列長(zhǎng)度。

第二行包含 N 個(gè)整數(shù)，表示整數(shù)數(shù)列。

輸出格式
共一行，包含 N 個(gè)整數(shù)，其中第 i 個(gè)數(shù)表示第 i 個(gè)數(shù)的左邊第一個(gè)比它小的數(shù)，如果不存在則輸出 ?1。

數(shù)據(jù)范圍
1≤N≤105
1≤數(shù)列中元素≤109
輸入樣例：
5

3 4 2 7 5

輸出樣例：

-1 3 -1 2 2 #include <iostream>using namespace std;const int N = 100010;int n; int stk[N], hh, tt;int main() {cin >> n;while (n -- ) {int x;cin >> x;while (tt && stk[tt] >= x) tt -- ;if (tt) cout << stk[tt] <<' ';else cout << "-1 ";stk[++ tt] = x;}return 0; }

這里的 tt 初始數(shù)值不能是 -1

kmp

831 kmp字符串

給定一個(gè)模式串 S，以及一個(gè)模板串 P，所有字符串中只包含大小寫英文字母以及阿拉伯?dāng)?shù)字。

模板串 P 在模式串 S 中多次作為子串出現(xiàn)。

求出模板串 P 在模式串 S 中所有出現(xiàn)的位置的起始下標(biāo)。

輸入格式
第一行輸入整數(shù) N，表示字符串 P 的長(zhǎng)度。

第二行輸入字符串 P。

第三行輸入整數(shù) M，表示字符串 S 的長(zhǎng)度。

第四行輸入字符串 S。

輸出格式
共一行，輸出所有出現(xiàn)位置的起始下標(biāo)（下標(biāo)從 0 開始計(jì)數(shù)），整數(shù)之間用空格隔開。

數(shù)據(jù)范圍
1≤N≤105
1≤M≤106
輸入樣例：

3 aba 5 ababa

輸出樣例：

0 2 S[N], p[M]for (int i = 1; i <= n; i ++ ) {bool flag = true;for (int j = 1; j <= m; j ++ ) {if (s[i] != p[j]) {flag = false;break;}} }

主串的某一個(gè)子串等于模式串的某一個(gè)前綴

#include <iostream>using namespace std;const int N = 10010, M = 100010;int n, m; char p[N], s[M]; int ne[N];int main() {cin >> n >> p + 1 >> m >> s + 1;// 求 next 數(shù)組// ne[0] ne[1] 自動(dòng)全局設(shè)置為 0, 因此第 3 個(gè)字母不匹配才會(huì)有回退的選擇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) {// 匹配成功printf("%d ", i - n);j = ne[j];}} }

匹配成功的時(shí)候 j = ne[j] 是為了最快的開始下一個(gè)匹配

總結(jié)

以上是生活随笔為你收集整理的第二章 数据结构(一)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。