算法基礎——鏈表-CSDN博客

一、排隊順序

題?來源：洛?

題?鏈接：B3630 排隊順序 - 洛谷

難度系數：★

1. 題目描述

2. 算法原理

????????本題相當于告訴了我們每?個點的后繼，使?靜態鏈表的存儲?式能夠很好的還原這個隊列。

????????數組中?[1, n]?的下標可以當做數據域，根據題意修改指針域即可。

?

注意：可以不需要 e[N] 數組，輸出下標即可?

3. 參考代碼?

#include <iostream>using namespace std;const int N = 1e6 + 10;int n, h;
int ne[N];int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> ne[i];cin >> h;// 遍歷鏈表for(int i = h; i; i = ne[i]){cout << i << " ";}return 0;
}

二、單向鏈表

題?來源：洛?

題?鏈接：B3631 單向鏈表 - 洛谷

難度系數：★

1. 題目描述

2. 算法原理

????????鏈表模板題，直接實現?個單鏈表即可。

3. 參考代碼

#include <iostream>using namespace std;const int N = 1e5 + 10, M = 1e6 + 10;// 鏈表
int h, id, e[N], ne[N];
int mp[M]; // mp[i] 用來標記 i 這個元素存在什么位置int main()
{int q; cin >> q;// 初始化id++;e[id] = 1;mp[1] = id;while(q--){int op, x, y;cin >> op >> x;int p = mp[x]; // x 存的位置if(op == 1) // x 后面插入{cin >> y;id++;e[id] = y;ne[id] = ne[p];ne[p] = id;mp[y] = id; // 標記 y 這個元素存的位置}else if(op == 2) // 查詢 x 后面的元素{cout << e[ne[p]] << endl;}else // 刪除 x 后面的元素{ne[p] = ne[ne[p]];}}return 0;
}

三、隊列安排

題?來源：洛?

題?鏈接：P1160 隊列安排 - 洛谷

難度系數：★★

1. 題目描述

2. 算法原理

????????頻繁的在某?個位置之前和之后插?元素，因此可以?雙向循環的鏈表來模擬。

3. 參考代碼

#include <iostream>using namespace std;const int N = 1e5 + 10;// 雙向鏈表
int h, pre[N], ne[N];
bool st[N]; // st[x] 表示 x 這個元素是否已經被刪除int n, m;int main()
{cin >> n;// 初始化pre[1] = h;ne[h] = 1;for(int i = 2; i <= n; i++){int k, p; cin >> k >> p;if(p == 0){// i 放在 k 的左邊ne[i] = k;pre[i] = pre[k];ne[pre[k]] = i;pre[k] = i;}else{// i 放在 k 的右邊pre[i] = k;ne[i] = ne[k];pre[ne[k]] = i;ne[k] = i;}}cin >> m;while(m--){int x; cin >> x;// 將 x 刪除if(st[x] == true) continue;ne[pre[x]] = ne[x];pre[ne[x]] = pre[x];st[x] = true; // 標記 x 已經被刪除}for(int i = ne[h]; i; i = ne[i]){cout << i << " ";}return 0;
}

四、約瑟夫問題

題?來源：洛?

題?鏈接：P1996 約瑟夫問題 - 洛谷

難度系數：★

1. 題目描述

2. 算法原理

????????使?循環鏈表模擬即可。

3. 參考代碼

#include <iostream>using namespace std;const int N = 110;int n, m;
int ne[N];int main()
{cin >> n >> m;// 創建循環鏈表for(int i = 1; i < n; i++) ne[i] = i + 1;ne[n] = 1;// 模擬約瑟夫游戲的過程int t = n;for(int i = 1; i <= n; i++) // 執行 n 次出圈操作{for(int j = 1; j < m; j++) // 讓 t 向后移動 m - 1 次{t = ne[t];}cout << ne[t] << " ";ne[t] = ne[ne[t]];}return 0;
}