e[0]=1 e[1]=2 e[2]=3 e[3]=4 e[4]=5 e[5]=6
ne[0]=1 ne[1]=2 ne[2]=3 ne[3]=4 ne[4]=5 ne[5]=-1
用ne来存储e的下一个下标
初始化
我们规定，将-1设置为空节点
1. void init() 2. { 3. head = -1; 4. idx = 0; 5. }
头插
首先将新的节点开辟出来
e[idx]=x;
然后让改节点的下一个节点指向现在的第一个节点（head）
ne[idx]=head;
然后断开head与原来第一个节点的连接，head指向插入的这个节点，最后idx++；
1. head = idx; 2. idx++;
因此头插的代码为:
1. void add_to_head(int x) 2. { 3. e[idx] = x; 4. ne[idx] = head; 5. head = idx; 6. idx++; 7. }
在下标为k的元素后面插入x
1. void add(int k, int x) 2. { 3. e[idx] = x; 4. ne[idx] = ne[k]; 5. ne[k] = idx; 6. idx++; 7. }
删除
1. void move(int k) 2. { 3. ne[k] = ne[ne[k]]; 4. }
题目:
AC代码：
1. #include<iostream> 2. using namespace std; 3. const int N = 100010; 4. int head, e[N], ne[N], idx; 5. 6. void init() 7. { 8. head = -1; 9. idx = 0; 10. } 11. 12. void add_to_head(int x) 13. { 14. e[idx] = x; 15. ne[idx] = head; 16. head = idx; 17. idx++; 18. } 19. //在下标为k的元素后面插入x 20. void add(int k, int x) 21. { 22. e[idx] = x; 23. ne[idx] = ne[k]; 24. ne[k] = idx; 25. idx++; 26. } 27. //将下标为k的点后面的点删除掉 28. void move(int k) 29. { 30. ne[k] = ne[ne[k]]; 31. } 32. 33. int main(void) 34. { 35. int m; 36. cin >> m; 37. init(); 38. while (m--) 39. { 40. int k, x; 41. char op; 42. cin >> op; 43. if (op == 'H') 44. { 45. cin >> x; 46. add_to_head(x); 47. } 48. else if (op == 'D') 49. { 50. cin >> k; 51. if (k == 0) 52. { 53. head = ne[head]; 54. } 55. move(k - 1); 56. } 57. else 58. { 59. cin >> k >> x; 60. add(k - 1, x); 61. } 62. } 63. for (int i = head; i != -1; i = ne[i]) 64. { 65. cout << e[i] << ' '; 66. } 67. return 0; 68. }
