实现一个双链表,双链表初始为空,支持5 种操作:
- 在最左侧插入一个数;
- 在最右侧插入一个数;
- 将第k 个插入的数删除;
- 在第k 个插入的数左侧插入一个数;
- 在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M次操作,进行完所有操作后,从左到右输出整个链表。
#include <iostream> using namespace std; const int N = 100010; int e[N], l[N], r[N], idx; void init () { r[0] = 1, l[1] = 0; idx = 2; } void add (int k, int x) { e[idx] = x; l[idx] = k, r[idx] = r[k]; l[r[k]] = idx, r[k] = idx; idx++; } void remove (int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } int main() { init (); int m; cin >> m; while (m--) { string s; cin >> s; if (s == "L") { int x; cin >> x; add (0, x); } else if (s == "R") { int x; cin >> x; add (l[1], x); } else if (s == "D") { int k; cin >> k; remove (k + 1); } else if (s == "IL") { int k, x; cin >> k >> x; add (l[k + 1], x); } else { int k, x; cin >> k >> x; add (k + 1, x); } } for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " "; return 0; }
标签:idx,int,cin,else,插入,add,双链 From: https://www.cnblogs.com/leetothemoon/p/16939898.html