双向链表
Time Limit: 1000MS Memory limit: 65536K
题目描述
学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。
输入
第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。接下来n行每行有一个整数为关键字key（数据保证关键字在数列中没有重复）。接下来有m个关键字，每个占一行。
输出
对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。给定关键字为每个输出占一行。
示例输入
10 3
1 2 3 4 5 6 7 8 9 0
3
5
0
示例输出
2 4
4 6
9
1 #include<stdio.h>
2 #include<stdlib.h>
3 struct node
4 {
5 int data;
6 struct node *prev,*
next;
7 };
8 int main()
9 {
10 int n,m,x;
11 struct node *head,*p,*
tail;
12 head = (
struct node *)malloc(
sizeof(
struct node));
13 head->prev =
NULL;
14 head->next =
NULL;
15 tail =
head;
16 scanf(
"%d %d",&n,&
m);
17 for(
int i =
1; i <= n; i++
)
18 {
19 p = (
struct node *)malloc(
sizeof(
struct node));
20 scanf(
"%d",&p->
data);
21 p->next =
NULL;
22 tail->next =
p;
23 p->prev =
tail;
24 tail =
p;//建立双向链表
25 }
26 while(m--
)
27 {
28 scanf(
"%d",&
x);
29 p = head->
next;
30 while(p)
31 {
32 if(p->data ==
x)
33 {
34 if(p == head->
next)
35 {printf(
"%d\n",p->next->data);
break;}
36 else if(p->next ==
NULL)
37 {printf(
"%d\n",p->prev->data);
break;}
38 else
39 {printf(
"%d %d\n",p->prev->data,p->next->data);
break;}
40 }
41 else p = p->
next;
42 }
43 }
44 return 0;
45 }
46
转载于:https://www.cnblogs.com/LK1994/p/3143128.html
相关资源：双向链表实现结点类
