sdutacm-数据结构实验之链表九：双向链表

数据结构实验之链表九：双向链表

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblemDescription

学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B，他们的关系是B是A的后继，A指向了B，便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中，A有一个指针指向了节点B，同时，B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点，也能从链表尾节点开始遍历所有节点。对于给定的一列数据，按照给定的顺序建立双向链表，按照关键字找到相应节点，输出此节点的前驱节点关键字及后继节点关键字。

Input

第一行两个正整数n（代表节点个数），m（代表要找的关键字的个数）。第二行是n个数（n个数没有重复），利用这n个数建立双向链表。接下来有m个关键字，每个占一行。

Output

对给定的每个关键字，输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继，则不输出。注意：每个给定关键字的输出占一行。           一行输出的数据之间有一个空格，行首、行末无空格。

ExampleInput

10 3

1 2 3 4 5 6 7 8 9 0

3

5

0

ExampleOutput

2 4

4 6

9

Hint

Author

J#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<iostream>#include<algorithm>#include<stack>#include<queue>//#include<dqeue>using namespace std;typedef struct list{    int data;    struct list *qian,*next;}a;int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {       a* head,*last;       head = (a*)malloc(sizeof(a));       last = head;       head->next=NULL;       head ->qian = NULL;       if(n%2==0)n/=2;       else n = n*3+1;       head->data = n;       m--;       while(m--)       {          if(n%2!=0)          {             n = n*3+1;             a*p;             p =(a*)malloc(sizeof(a));             p->data = n;             p->next =NULL;             p->qian = last;             last->next = p;             last = p;          }          else          {          n = n/2;            a*p;            p = (a*)malloc(sizeof(a));            p->data=n;            p->next = head;            p->qian = NULL;            head->qian = p;            head = p;         }     }       a*tail = head;       int top =1;       while(tail)       {         if(top)top = 0;         else printf(" ");         printf("%d",tail->data);         tail = tail->next;       }       tail= head;       while(tail)       {          a*tt = tail;          tail = tail->next;          free(tt);       }       printf("/n");    }return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 32msTake Memory: 180KBSubmit time: 2017-01-14 18:27:28****************************************************/