问题 C: DS双向链表—前驱后继
时间限制: 1 Sec 内存限制: 128 MB
提交: 169 解决: 129
[提交][状态][讨论版]
题目描述
在双向链表中,A有一个指针指向了后继节点B,同时,B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。
对于给定的一列数据,按照给定的顺序建立双向链表,按照关键字找到相应节点,输出此节点的前驱节点关键字及后继节点关键字。
输入
第一行两个正整数n(代表节点个数),m(代表要找的关键字的个数)。
接下来输入n个整数为关键字key(数据保证关键字在数列中没有重复)。
接下来有m个要查找的关键字,每个占一行。
输出
对给定的每个关键字,输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继,则不输出。给定关键字为每个输出占一行。
样例输入
10 3
1 2 3 4 5 6 7 8 9 0
3
1
0
样例输出
2 4
2
9
#include <iostream> using namespace std; class ListNode { public: int data; ListNode *prior; ListNode *next; ListNode() { prior = NULL; next = NULL; } }; int main(void) { int i, n, m, temp; cin >> n >> m; ListNode *p=NULL, *q, *r=NULL; for (i = 0; i < n; i++) { cin >> temp; if (!i) { p = new ListNode; p->data = temp; r = p; } else { q = new ListNode; q->data = temp; q->prior = r; r->next = q; r = q; } } for (i = 0; i < m; i++) { cin >> temp; q = p; while (q->data != temp) q = q->next; if (q->prior && q->next) cout << q->prior->data << ' ' << q->next->data << endl; else if (q->prior && !q->next) cout << q->prior->data << endl; else cout << q->next->data << endl; } }