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

小鱼儿 2022-09-28 11:46 156阅读 0赞

think:  
1顺序输出双向链表+双向链表中查询关键字元素所在结点+双向链表中输出关键字结点的前驱结点关键字和关键字结点的后驱结点关键字  
2注意需要判断关键字所在结点前驱结点和后驱结点是否存在，如果首结点为空结点，需要判断前驱结点是否为空结点

[sdut原题链接][sdut]

数据结构实验之链表九：双向链表  
Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

Example Input  
10 3  
1 2 3 4 5 6 7 8 9 0  
3  
5  
0

Example Output  
2 4  
4 6  
9

Hint

Author

以下为accepted代码

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int Data;
        struct node *front;//指向前驱结点
        struct node *next;//指向后驱结点
    }*head, *tail;
    void Build(int n);//顺序建立双向链表
    void Search(struct node *h, int x);//寻找双向链表中的关键字
    int main()
    {
        int n, m, x;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            head = (struct node *)malloc(sizeof(struct node));
            head->front = NULL;
            head->next = NULL;
            tail = head;
            Build(n);//顺序建立双向链表
    
            while(m--)
            {
                scanf("%d", &x);
                Search(head, x);//寻找双向链表中的关键字
            }
        }
        return 0;
    }
    void Build(int n)//顺序建立双向链表
    {
        struct node *p;
        for(int i = 0; i < n; i++)
        {
            p = (struct node *)malloc(sizeof(struct node));
            scanf("%d", &p->Data);
            p->next = tail->next;//指向后驱结点
            p->front = tail;//指向前驱结点
            tail->next = p;//将结点p入链表
            tail = p;//尾结点后移
        }
    }
    void Search(struct node *h, int x)//寻找双向链表中的关键字
    {
        struct node *p;
        p = h->next;
        while(p != NULL)
        {
            if(p->Data == x)
            {
                int flag = 0;//flag变量判断输出后驱结点之前前驱结点是否输出
                int cnt = 0;//cnt变量记录是否有关键字输出，进而判断是否需要输出换行
                if(p->front != NULL && p->front != head)
                {
                    cnt = 1;
                    flag = 1;
                    printf("%d", p->front->Data);//输出前驱结点的关键字
                }
                if(p->next != NULL)
                {
                    cnt = 1;
                    if(flag)
                        printf(" %d", p->next->Data);//输出后驱结点关键字
                    else
                        printf("%d", p->next->Data);//输出后驱结点关键字
                }
                if(cnt)
                    printf("\n");
            }
            p = p->next;//继续寻找
        }
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-03-10 20:04:14
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2024/pid/2054