---

單向鏈表

題目描述

題目解析

這道題因為有大量的任意位置插入刪除，所以肯定不能用數組，用鏈表是最合適的，而在算法競賽通常都用靜態鏈表，所以這道題我們選用靜態單鏈表。
這道題題目規定保證任何時間表中所有數字均不相同，所以我們可以用mp輸入登記插入數據所在位置，高效率完成find操作。
三個操作每一個操作都需要先找到x的物理結構下標，所以我們先借助mp數組將x的下標存到p中，靜態鏈表的插入刪除操作小編專門出了一篇博客，感興趣的讀者可以移步：點擊此處
需要注意的是首先刪除操作時需要先將x在mp數組中刪除再erase x，如果先erase x的話，后面刪除x在mp數組的標記的操作就是刪除的x的下一個結點在mp數組的標記了。然后題目規定一開始鏈表里除了哨兵位還有一個存1的結點。

代碼

using namespace std;
#include <iostream>const int N = 1e6 + 10;  //單個數值的范圍
const int M = 1e5 + 10;  //數量范圍
int e[M], ne[M], mp[N],id, h;int main()
{id++;e[id] = 1;mp[1] = id;int q;cin >> q;int op, x, y;while (q--){cin >> op >> x;//p是x存的物理結構下標int p = mp[x];   if (op == 1){cin >> y;id++;e[id] = y;mp[y] = id;ne[id] = ne[p];ne[p] = id;}else if(op == 2){cout << e[ne[p]] << endl;}else{if (ne[p] != 0){mp[e[ne[p]]] = 0;ne[p] = ne[ne[p]];}}}return 0;
}

隊列安排

題目描述

題目解析

我們先分析一下，這道題有頻繁的任意位置插入刪除，不能用順序表只能用鏈表，而且是在指定位置的前面或者后面插入刪除，那么只能用雙向鏈表。
這道題很特殊，因為它的按順序插入的，所以它的插入的順序就是數組的物理下標，也等于e[
]數組里的值，所以id就等于插入的順序j，(有就是for循環里的j的值)我們要之前要借助mp[
]才能找到的插入位置的數組下標在這道題就等于k。刪除時題目規定不能重復刪，那創建一個數組st來標記某個物理下標是否被刪除過，被刪除過就置為true，若判斷當前位置為true，直接continue跳過當次循環操作。
最后因為數組的物理下標直接等于e[ ]數組里的值，所以直接循環遍歷打印數組的物理下標。

代碼

using namespace std;
#include <iostream>const int Q = 1e5 + 10;
int ne[Q], pre[Q], h;
bool st[Q]; //用來標記x位置是否被刪除int main()
{ne[1] = h;pre[1] = h;ne[h] = 1;pre[h] = 1;int N;cin >> N;//插入int k, p;for (int j = 2; j <= N; j++){cin >> k >> p;if (p == 0){ne[j] = k;pre[j] = pre[k];ne[pre[k]] = j;pre[k] = j;}else{ne[j] = ne[k];pre[j] = k;pre[ne[k]] = j;ne[k] = j;}}//刪除  int M, x;cin >> M;while (M--){cin >> x;if (st[x] == true)continue;ne[pre[x]] = ne[x];pre[ne[x]] = pre[x];st[x] = true;}//輸出  for (int i = ne[h]; i; i = ne[i]){cout << i << " ";}return 0;
}

約瑟夫問題

題目描述

題目解析

這道題思路很多，小編這里創建一個雙向循環鏈表來解決，要注意根據題意我們要用循環鏈表來模擬一個圈，所以不能帶哨兵位。
首先創建出一個n個結點的鏈表。然后從下標為0開始，每遍歷m個結點就把當前結點打印出來，然后刪除當前結點，指針再指向刪除結點的下一個結點，最后把所有結點刪除停止循環們也就是循環n次。

代碼

using namespace std;
#include <iostream>const int N = 100 + 10;
int e[N], ne[N], pre[N], id, h;int main()
{int m, n;cin >> n >> m;//初始化e[0] = 1;ne[0] = 0;pre[0] = 0;for (int i = 1; i < n; i++){e[i] = i + 1;ne[i] = 0;pre[i] = i - 1;pre[h] = i;ne[i - 1] = i;}//循環打印刪除int cur = 0;while (n--){int tmp = m;while (--tmp){cur = ne[cur];}cout << e[cur] << " ";//刪除cur所在結點ne[pre[cur]] = ne[cur];pre[ne[cur]] = pre[cur];cur = ne[cur];}return 0;
}

以上就是小編分享的全部內容了，如果覺得不錯還請留下免費的關注和收藏如果有建議歡迎通過評論區或私信留言，感謝您的大力支持。
一鍵三連好運連連哦~~