【数据结构系列】双向链表-蒲公英云

课后习题

上一篇文章中我们说到单链表，然后最后有一道习题，不知道大家有没有做出来，为了照顾一些还不太会的同学，这里专门对这道题进行一个简单的讲解，先来看看原题内容：

有一个带头结点的单链表L = {a1,b1,a2,b2,…,a(n),b(n)}，试设计一个算法将其拆分成两个带头结点的单链表L1和L2，L1 = {a1,a2,…,a(n)}，L2 = {b(n),b(n - 1),…,b(1)}，要求L1使用L的头结点。

从题目中我们就可以看出，L1通过尾插法建立，L2通过头插法建立。

这道题本身并没有太大难度，我们通过画图的方式来分析一下，如下图是单链表L的一部分：
在这里插入图片描述

既然是要拆分成两个链表，我们需要定义出两个结点类型的变量p，q，可以先让p指向第一个有效结点，即：存放数据a1的结点，然后将a1插入到L1中；接着让q指向p的下一个结点，即：存放数据b1的结点，然后将b1插入到L2中，以此循环，即可完成。

看代码如何实现：

PNode split(PNode L){ 
    PNode L1,L2,R1,p,q;
    L1 = L;//这里我们仍然使用链表L的头结点作为链表L1的头结点
    R1 = L1;//R1为链表L1的尾结点，初始指向头结点
    p = L->next;//p初始指向链表L的第一个有效结点，用于找出链表L1的结点
    //创建链表L2的头结点
    L2 = (PNode) malloc(sizeof(Node));
    if(L2 == NULL){ 
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    L2->next = NULL;//L2的头结点初始指针域为NULL
    while(p != NULL){ 
        q = p->next;//q初始指向链表L的第二个有效结点，用于找出链表L2的结点
        //尾插法插入结点到链表L1
        R1->next = p;
        R1 = p;
        //判断q是否空
        if(q == NULL){ 
            break;
        }
        //将p后移
        p = q->next;
        //头插法插入结点到链表L2
        q->next = L2->next;
        L2->next = q;
    }
    //L1尾结点指针域为NULL
    R1->next = NULL;
    return L2;//返回链表L2的头结点
}

如果你掌握了头插法和尾插法的话，这道题相信难不倒你，唯一需要注意的就是循环里有一个判断条件，为什么要判断q非空？而且该判断语句的位置可不能乱写，否则程序就会出错。这里其实涉及到两种情况，链表L的结点数为奇数个或者结点数为偶数个，我们先看奇数个(假设链表L1有三个有效结点)：
在这里插入图片描述

那么一开始，p将指向存储数据1的结点，而循环体的第一条语句就是找到了q，q为存储数据2的结点，当把p插入到链表L1之后，我们需要找出链表L1的下一个结点，也就是q->next，即：存放数据3的结点；之后把q结点插入到了链表L2，我们又需要找出链表L2的下一个结点，也就是p->next，而此时p为链表L的尾结点，它的指针域为NULL，所以此时q为NULL，而如果你没有对q进行非空判断的话，执行p=q->next语句时就会报错，程序就出现问题了，所以要在使用q变量之前对q进行一个非空的判断。

而如果是偶数个，就比如上面的这个链表，再加入一个结点，那么p就不会是链表的尾结点，而当执行p=q->next语句后，尾结点q的指针域为NULL，所以p为NULL，此时循环就终止了，也就不会出现程序错误。

编写测试代码：

void main(){ 
    PNode pHead,L2;
    int a[] = { 1,2,3,4,5,6,7,8};
    pHead = create_listT(a,8);
    traverse_list(pHead);
    L2 = split(pHead);
    printf("链表L1:\t");
    traverse_list(pHead);
    printf("\n链表L2:\t");
    traverse_list(L2);
    getchar();
}

首先你肯定得建立一个链表作为链表L，如何建立链表在这里就不重复说了，不了解的可以看上一篇文章，然后将头结点传入，就拆分成了两个链表。

运行结果：

1 2 3 4 5 6 7 8 9
链表L1: 1 3 5 7
链表L2: 8 6 4 2

双链表定义

在文章开头我们对单链表进行了一个简单的复习，下面我们进入本篇文章的主题，双链表。

先来看看定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

从定义中能够知道，双链表和单链表的唯一区别就是，双链表多了一个能够指向直接前驱结点的指针域，能够实现双向访问。

那么在双链表中，我们假设每个结点的类型用Node表示，它应该有一个存储元素的数据域，这里用data表示，有一个存储直接后继结点地址的指针域，这里用next表示，还应该有一个存储直接前驱结点地址的指针域，这里用prior表示，Node类型定义如下：

typedef struct Node{ 
    int data;
    struct Node *next;
    struct Node *prior;
}Node,*PNode;

在这里插入图片描述

双链表的初始化

那么如何建立一个空的双链表呢？

PNode create_list(){ 
    //创建头结点
    PNode pHead = (PNode) malloc(sizeof(Node));
    pHead->next = NULL;
    pHead->prior = NULL;
    return pHead;
}

非常简单，分配一块内存用于头结点，然后将头结点的两个指针域都置为NULL即可。

对于非空双链表的建立，我们同样需要掌握头插法和尾插法两种建立方式。

先看头插法：

在这里插入图片描述

这是一个双链表的头结点，如何通过头插法将一个结点插入到该链表上呢？

在这里插入图片描述

这样便完成了插入，如何实现呢？假设头结点为p，第一个结点为s，则s = p->next，此时s的指针域为NULL，然后s->prior = p，此时s结点指向它的直接前驱结点p(头结点)，最后p->next = s，此时头结点指向第一个结点s。

貌似没有什么问题，然而再插入一个元素你就会发现，第一个结点的prior指针域没有改变，它仍然指向的是头结点，而事实上它应该指向第二个结点。
在这里插入图片描述

那该如何解决呢？我们可以发现一个规律，就是如果向一个空链表插入结点，也就是p->next = NULL的时候，是没有出现问题的，然而插入第二个结点的时候出现问题，所以我们可以对p的指针域做一个非空的判断，下面看代码实现：

PNode create_listH(int *a,int n){ 
    PNode pHead,pNew;
    int i;
    //创建头结点
    pHead = (PNode) malloc(sizeof(Node));
    if(pHead == NULL){ 
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    pHead->next = NULL;//头结点初始指针域为NULL
    for(i = 0;i < n;i++){ 
        //创建新结点
        pNew = (PNode) malloc(sizeof(Node));
        if(pNew == NULL){ 
            printf("内存分配失败，程序终止！\n");
            exit(-1);
        }
        //保存数据
        pNew->data = a[i];
        pNew->next = pHead->next;//将新结点指针域置为NULL，该结点为链表的尾结点
        //判断头结点后面是否有结点
        if(pHead ->next != NULL){ 
            //将头结点指向的结点的prior指针域指向新创建的结点
            pHead->next->prior = pNew;
        }
        pHead->next = pNew;//头结点指向新结点
    }
    return pHead;
}

为了验证代码的正确性，我们编写一个遍历函数，双链表的遍历方式和单链表一样，这里就直接贴代码了：

PNode create_list(){ 
    //创建头结点
    PNode pHead = (PNode) malloc(sizeof(Node));
    pHead->next = NULL;
    pHead->prior = NULL;
    return pHead;
}

编写测试代码：

void main(){ 
    PNode pHead;
    int a[] = { 1,2,3,4,5,6};
    pHead = create_listH(a,6);
    traverse_list(pHead);
    getchar();
}

运行结果：

6 5 4 3 2 1

下面看看尾插法如何建立双链表。
在这里插入图片描述

同样是这样的一个头节点，如何将第一个结点插入到链表上呢？
在这里插入图片描述

我们暂且把头节点叫做p，第一个结点叫做s，和单链表一样，我们仍然需要定义一个结点类型的pTail作为指向链表的尾结点，初始指向头结点pTail = p，然后我们只需pTail->next = s，也就是让头结点指向第一个结点，接着s->prior = pTail，让第一个结点指回头结点，最后pTail = s，此时插入的结点为链表的尾结点，不要忘了在结尾将pTail的next指针域置为空。

下面看代码实现：

PNode create_listR(int *a,int n){ 
    PNode pHead,pNew,pTail;
    int i;
    //创建头结点
    pHead = (PNode) malloc(sizeof(Node));
    if(pHead == NULL){ 
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    pTail = pHead;//初始指向头结点
    for(i = 0;i < n;i++){ 
        //创建新结点
        pNew = (PNode) malloc(sizeof(Node));
        if(pNew == NULL){ 
            printf("内存分配失败，程序终止！\n");
            exit(-1);
        }
        //保存数据
        pNew->data = a[i];
        pTail->next = pNew;
        pNew->prior = pTail;
        pTail = pNew;
    }
    pTail->next = NULL;//尾结点指针域为NULL
    return pHead;
}

我们测试一下：

void main(){ 
    PNode pHead;
    int a[] = { 1,2,3,4,5,6};
    pHead = create_listR(a,6);
    traverse_list(pHead);
    getchar();
}

运行结果：

1 2 3 4 5 6

求双链表长度

这个和单链表的操作一样，没什么说的，直接看代码：

int length_list(PNode pHead){ 
    int i = 0;
    PNode p = pHead->next;
    while(p != NULL){ 
        i++;
        p = p->next;
    }
    return i;
}

这个在单链表中已经说过了，我就不测试了。

判断是否为空表

判断是否为空表也和单链表操作相同，看代码：

int isEmpty_list(PNode pHead){ 
    if(pHead->next == NULL){ 
        return 1;
    }else{ 
        return 0;
    }
}

插入结点

接下来又到了比较难的环节了，在双链表中的插入、删除操作和单链表十分类似，但又有些许不同，在双链表中，插入和删除的操作涉及到两个指针域的变化，所以相对要更复杂一些，但仔细品味，也很容易理解。
在这里插入图片描述
假设现在我需要将结点s插入到q的位置，则插入完成后链表结构如下：

那么如何实现插入呢？同样地，我们需要找到插入位置的前一个结点，例如在这里，需要将结点s插入到节点q的位置，则需要找到q的前一个结点也就是结点p，然后将结点s的指针域next指向p结点的指针域next，也就是让结点s指向结点q。
在这里插入图片描述

接着让结点q的指针域prior指向结点s，从而建立起结点s和结点q的双向关系。
在这里插入图片描述

然后让结点s的指针域prior指向结点p，最后让结点p的指针域next指向结点s，建立起结点p和结点s的双向关系。

在这里插入图片描述

这样即可完成插入。

下面看代码实现：

int insert_list(PNode pHead,int pos,int val){ 
    PNode p,pNew;
    int len,i = 0;
    p = pHead;//p初始指向头结点
    len = length_list(pHead);
    //判断pos值的合法性
    if(pos < 1 || pos > len + 1){ 
        return 0;
    }
    //找到插入位置的前一个结点
    while(i < pos - 1 && p != NULL){ 
        i++;
        p = p->next;
    }
    if(p == NULL){ 
        return 0;
    }
    //此时p为插入位置的前一个结点
    //创建新结点
    pNew = (PNode) malloc(sizeof(Node));
    if(pNew == NULL){ 
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    //保存数据
    pNew->data = val;
    //插入结点
    pNew->next = p->next;
    //判断p是否为尾结点
    if(p->next != NULL){ 
        p->next->prior = pNew;
    }
    pNew->prior = p;
    p->next = pNew;
    return 1;
}

插入操作中同样需要注意一个问题，那就是插入的位置如果是链表的末尾的话，通过循环找到的结点p即为链表的尾结点，而尾结点的指针域next为NULL，就无需考虑后面结点的指针域prior的指向问题，如果不加以判断，当你插入结点到链表末尾时，程序就会报错。

编写测试代码：

void main(){ 
    PNode pHead;
    int a[] = { 1,2,3,4,5,6};
    pHead = create_listR(a,6);
    traverse_list(pHead);
    if(insert_list(pHead,5,50)){ 
        printf("插入后：\n");
        traverse_list(pHead);
    }else{ 
        printf("插入失败！\n");
    }
    getchar();
}

运行结果：

1 2 3 4 5 6
插入后：
1 2 3 4 50 5 6

删除结点

看下面一个双链表：
在这里插入图片描述

如何将结点s从链表中删除呢？

原理很简单，首先将结点p的指针域next指向结点s的指针域，也就是p->next = p->next->next，然后将结点q的指针域prior指向结点p，也就是q->prior = p，此时结点p和结点q之间建立起了双向关系，最后释放结点s的内存即可。
在这里插入图片描述
看代码如何实现：

int delete_list(PNode pHead,int pos,int *val){ 
    PNode p,q;
    int len,i = 0;
    len = length_list(pHead);
    p = pHead;//初始指向头结点
    //判断pos值的合法性
    if(pos < 1 || pos > len){ 
        return 0;
    }
    //找到待删除结点的前一个结点
    while(i < pos - 1 && p != NULL){ 
        i++;
        p = p->next;
    }
    //此时p为待删除结点的前一个结点
    q = p->next;//q为待删除结点
    //保存数据
    *val = q->data;
    //删除结点
    p->next = q->next;
    if(p->next!= NULL){ 
        p->next->prior = p;
    }
    free(q);
    return 1;
}

这里同样需要考虑删除尾结点的问题，如果要删除的是尾结点，那么尾结点后面已经没有结点了，所以直接后继结点可以不用处理，处理就会报错，我们应该对p的指针域next进行非空判断，千万不要把p->next != NULL写成q != NULL，有些同学想当然地认为，q = p->next，所以if语句里也就写了q != NULL，这样是错误的。因为在判断之前，p的指针域next已经被改变了，只有判断p是否为空，当删除尾结点时，p指向q的指向，而q是尾结点，所以p的指向为NULL，q并不为空，它是尾结点，这是需要注意的一点。

下面是测试代码：

void main(){ 
    PNode pHead;
    int a[] = { 1,2,3,4,5,6};
    int val;
    pHead = create_listR(a,6);
    traverse_list(pHead);
    if(delete_list(pHead,6,&val)){ 
        printf("删除后：\n");
        traverse_list(pHead);
        printf("删除结点的元素值为：%d\n",val);
    }else{ 
        printf("删除失败！\n");
    }
    getchar();
}

运行结果：

1 2 3 4 5 6
删除后：
1 2 3 4 5
删除结点的元素值为：6

至于查找指定元素值的结点位置，或者是查找指定结点位置的元素值，还有链表的销毁，这些操作都与单链表的操作一模一样，也就没有必要重复讲解了。不了解的可以看我的上一篇文章。

课后习题

按照惯例，我同样留下一道算法题：

有一个带头结点的双链表L，试设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，……，最后一个元素变为第1个元素。

同样简单分析一下，这道题其实很简单，通过遍历双链表L，然后使用头插法建立链表即可完成，具体如何实现就看大家的了。我会在下一篇专栏文章中揭晓此题答案。

【数据结构系列】双向链表

课后习题

双链表定义

双链表的初始化

求双链表长度

判断是否为空表

插入结点

删除结点

课后习题

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【数据结构】双向链表

相关数据结构 - 双向链表

相关【数据结构】双向链表

相关数据结构-链表-双向链表

相关【数据结构】双向链表

相关【数据结构系列】双向链表

相关数据结构：双向链表

相关数据结构双向链表

相关【数据结构】双向链表

相关数据结构-双向链表&双向循环链表

随便看看

JVM 白小白——基本认识（一）

Bootstrap 探索之旅

JavaScript（三）——DOM操作之如何创建DOM对象

Error in render: "TypeError: Cannot read property 'accessCount' of null" found in

精心整理Java及架构资料

javascript面试题，关于连续赋值let a = {n: 1}; let b = a; a.x = a = {n: 2}; 的坑？

教程文章

热评文章

1江湖小白之一起学Python （二）爬取数据的保存

2Java Shiro：简化身份验证和授权的安全框架

3Java中try()catch{}的使用方法

4Swagger注解-@ApiModel 和 @ApiModelProperty

5windows下强制杀死tomcat进程

6uni-app 条形码(一维码)/二维码生成实现

标签列表