AI 助理
备案控制台
开发者社区 人工智能 文章 正文

线性表的链式实现(二)

2023-09-14 40
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 线性表的链式实现(二)

@[toc]

本篇文章将讲解线性表的链式实现。

循环链表的定义

上篇文章我们学习了单链表，并掌握了单链表的一些基本操作，本篇文章我们继续学习循环链表和双链表的内容。
先来看看循环链表的定义：

循环链表是一种头尾相连的链表，即表中最后一个结点的指针域不再为NULL，而是指向头结点，整个链表形成一个环。

下图为带头结点的循环链表：
在这里插入图片描述
由于循环链表的特性，使其从表中任一结点出发都可以找到表中其它结点。

对于上面的循环链表：
如果想要查找a1结点，只需要通过头指针扫描一次即可找到，时间复杂度为O(1)；
而如果想要查找an结点，就需要通过头指针扫描n次才能找到，时间复杂度为O(n)。
可以知道，如果想要查找循环链表末尾的结点，是比较耗时的，这时候，我们可以考虑在循环链表的末尾也加上一个指针，它指向的是尾结点，通过尾指针可以很方便地获取到a1结点和an结点。
综上所述：若是经常在循环链表的表头和表尾进行操作，则可以增设一个尾指针方便处理。

合并两个循环链表

关于循环链表的其它操作就不多说了，它和单链表是一模一样的，这里讲解一下如何合并两个循环链表。
假设有如下两个带尾指针的循环链表：
在这里插入图片描述
如何将Tb合并到Ta后面呢？
步骤如下：
第一个循环链表的尾指针Ta不再指向自己的头结点，而是指向第二个循环链表的首元结点：
在这里插入图片描述
这样第二个循环链表的头结点就没有作用了，我们可以将其释放掉。
然后将第二个循环链表的尾指针Tb指向第一个循环链表的头结点，完成合并。
在这里插入图片描述
综上所述，操作步骤如下：

  1. 保存第一个循环链表的头结点
  2. 尾指针Ta指向第二个循环链表的首元结点
  3. 尾指针Tb指向第一个循环链表的头节点
  4. 释放第二个循环链表的头结点

合并两个循环链表的算法实现如下：

LinkList Connect(LinkList Ta,LinkList Tb){
   
   
    LinkList p;
    //保存Ta头结点
    p = Ta->next;
    //让Ta指向Tb的首元结点
    Ta->next = Tb->next->next;
    //释放Tb头结点
    free(Tb->next);
    //让Tb指向Ta的头结点
    Tb->next = p;
    return Tb;//此时Tb为合并后的循环链表的尾指针
}

该算法的时间复杂度为O(1)。

当然了，还需要注意一些问题，比如在单链表中，遍历结束的条件是p->next == NULL，此时说明已经扫描到尾结点；而循环链表因为是呈环形的，所以这个条件就不能用了，循环链表的遍历结束条件为p->next == L,当循环链表的尾指针指向头结点的时候，说明已经扫描到尾结点；

双向链表的定义

对于单链表，它能够通过头结点按顺序扫描整个链表，但是，它有一个缺陷，就是只能找到一个结点的直接后继结点，而无法通过一个结点找到其直接前驱结点，因为它是单向的。
为此，我们可以在结点中增设一个指向其直接前驱结点的指针域，这样链表中就形成了有两个不同方向的链，我们称这样的链表为双向链表，也叫双链表。
下图为带头结点的双向链表：
在这里插入图片描述
所以，其结构如下：

#define ElemType int

typedef struct Node{
   
   
    ElemType data;//数据域
    struct Node *prior;//前驱指针
    struct Node *next;//后继指针
}Node,*LinkList;

双向链表的基本操作

对于双向链表，其遍历、查找、计算长度等等算法都和单链表类似，我就不另外说了，这里强调一些与单链表不太一样的操作。

双向链表的初始化

双向链表的初始化非常简单，直接看代码：

LinkList create_list(){
   
   
    //创建头结点
    LinkList l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始前驱和后继指针均为NULL
    l->next = l->prior = NULL;
    return l;//返回头结点
}

很简单，接下来我们同样分析一下两种初始化双向链表的方式：

  1. 头插法
  2. 尾插法

这两种方法在单链表中已经讲解过，但在双向链表中有些许不同，还是有必要说一说。

头插法

首先我们创建一个头结点，初始前驱指针和后继指针都指向头结点本身。
在这里插入图片描述

我们暂且称头结点为l，插入结点为s，步骤如下：
先插入第一个结点。
在这里插入图片描述
让新结点的后继指针指向头结点的后继，即：s->next = l->next。
这样只是建立了单向的连接，我们还需让新结点的前驱指针指向头结点，即：s->prior = l。
在这里插入图片描述
当然了，事情远没有这么简单，这样的连接方式并不适用于所有结点，它只是插入第一个结点时的特殊情况。

当插入第二个结点时，同样先让新结点的后继指针指向头结点的后继：
在这里插入图片描述
然后让新结点的前驱指向头结点：
在这里插入图片描述
可以看到，这样并没有建立起双向关系，所以我们还需让头结点的后继结点的前驱指向新结点，即：l->next->prior = s。
在这里插入图片描述
最后让头结点的后继指向新结点，完成插入。
在这里插入图片描述
综上所述，在插入结点的过程中，我们需要进行如下操作：

  1. 让新结点的后继指向头结点的后继
  2. 判断当前插入的结点是否为首元结点，判断条件：l->next == NULL
  3. 若插入的结点不为首元结点，则需额外进行一步操作，即：让头结点的后继结点的前驱指向新结点
  4. 让头结点的后继指向新结点
  5. 让新结点的前驱指向头结点

头插法代码实现如下：

LinkList create_listH(int *a,int length){
   
   
    LinkList l,s;
    int i;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始前驱和后继指针均为NULL
    l->next = l->prior = NULL;
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //头插法插入结点
        s->next = l->next;
        if(l->next != NULL){
   
   //此时说明l不为头结点
            l->next->prior = s;
        }
        l->next = s;
        s->prior = l;
    }
    return l;
}

尾插法

尾插法就简单很多了，因为每个结点的插入方式都是一样的，没有特殊情况需要考虑，比如下面的一个空结点：
在这里插入图片描述
插入第一个结点：
和单链表一样，我们仍然需要一个结点类型变量t辅助插入，初始变量t指向头结点，然后让t的后继指向新结点：
在这里插入图片描述
接着让新结点的前驱指向头结点：
在这里插入图片描述
最后将新结点赋值给变量t，使新结点变为尾结点，完成插入。

尾插法代码实现如下：

LinkList create_listT(int *a,int length){
   
   
    LinkList l,s,t;
    int i;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始t指向头结点
    t = l;
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //t的后继指向新结点
        t->next = s;
        //新结点的前驱指向t
        s->prior = t;
        //新结点成为尾结点
        t = s;
    }
    //尾结点指针域置为NULL
    t->next = NULL;
    return l;//返回头结点
}

双向链表的插入

双向链表的插入和单链表类似，我们同样需要找到插入位置的前一个结点。
比如下面的一个双向链表，要想在位置为3的位置插入一个结点，该如何实现呢？
在这里插入图片描述
我们找到插入位置的前一个结点，即：元素值为2的结点，暂且称其为p。通过结点p的后继指针就能够找到插入位置，即：元素值为3的结点，暂且称其为q。
插入步骤如下：
先让新结点s的后继指向结点p的后继，即：s->next = p->next。
在这里插入图片描述
然后让结点p的后继结点的前驱指向新结点s，即：p->next->prior = s。
在这里插入图片描述
接着让新结点的前驱指向结点p，即：s->prior = p。
在这里插入图片描述
最后让结点p的后继指向新结点s，即：p->next = s。
在这里插入图片描述
这样即可完成插入。

我们还得考虑插入的极端情况，比如插入位置为链表的表尾，此时如果执行p->next->prior = s，显然会出错，因为p为插入位置的前一个结点，所以如果在表尾插入，p的位置就是尾结点，而p的指针域为NULL，此时程序就会出错。而事实上，在表尾插入，因为插入位置的后面已经没有结点了，所以无需考虑后面结点与插入结点的关系。

代码实现如下：

int InsertList(LinkList l,int pos,int val){
   
   
    LinkList p,s;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1 || pos > length + 1){
   
   
        return -1;
    }
    //
    while(p != NULL && i < pos - 1){
   
   
        i++;
        p = p->next;
    }
    //此时p为插入位置的前一个结点
    //创建新结点
    s = (LinkList) malloc(sizeof(Node));
    if(s == NULL){
   
   
        return -1;
    }
    s->data = val;
    //插入结点
    s->next = p->next;
    if(p->next != NULL){
   
   //若p不为尾结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return 1;//插入成功，返回1
}

双向链表的删除

接下来介绍一下双向链表的删除操作。
比如下面的一个双向链表：
在这里插入图片描述
要想删除位置为2的元素，该如何实现呢？
删除操作比较简单，步骤如下：
先让结点p的后继指向结点q的后继，即：p->next = q->next。
在这里插入图片描述
然后要讨论一下要删除的结点是否为链表的尾结点，若为尾结点，那么只需释放删除结点的内存即可；若不为尾结点，则需再让结点p的后继结点的前驱指向结点p，即：p->next->prior = p。
在这里插入图片描述
最后释放结点q的内存即可，两条语句的顺序不能颠倒。
删除算法代码如下：

int DeleteList(LinkList l,int pos,int *val){
   
   
    LinkList p,q;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1|| pos > length){
   
   
        return -1;
    }
    while(p != NULL && i < pos - 1){
   
   
        i++;
        p = p->next;
    }
    //此时p为待删除位置的前一个结点
    q = p->next;//q为要删除的结点
    //保存数据
    *val = q->data;
    p->next = q->next;
    if(p->next != NULL){
   
   //若当前p不为尾结点
        p->next->prior = p;
    }
    free(q);
    return 1;//删除成功，返回1
}

源代码

文章中的所有代码：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define ElemType int

typedef struct Node{
   
   
    ElemType data;//数据域
    struct Node *prior;//前驱指针
    struct Node *next;//后继指针
}Node,*LinkList;

int DeleteList(LinkList l,int pos,int *val){
   
   
    LinkList p,q;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1|| pos > length){
   
   
        return -1;
    }
    while(p != NULL && i < pos - 1){
   
   
        i++;
        p = p->next;
    }
    //此时p为待删除位置的前一个结点
    q = p->next;//q为要删除的结点
    //保存数据
    *val = q->data;
    p->next = q->next;
    if(p->next != NULL){
   
   //若当前p不为尾结点
        p->next->prior = p;
    }
    free(q);
    return 1;//删除成功，返回1
}

int InsertList(LinkList l,int pos,int val){
   
   
    LinkList p,s;
    int length,i = 0;
    length = ListLength(l);
    p = l;//p初始指向头结点
    //判断pos值的合法性
    if(pos < 1 || pos > length + 1){
   
   
        return -1;
    }
    //
    while(p != NULL && i < pos - 1){
   
   
        i++;
        p = p->next;
    }
    //此时p为插入位置的前一个结点
    //创建新结点
    s = (LinkList) malloc(sizeof(Node));
    if(s == NULL){
   
   
        return -1;
    }
    s->data = val;
    //插入结点
    s->next = p->next;
    if(p->next != NULL){
   
   //若p不为尾结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return 1;//插入成功，返回1
}

int ListLength(LinkList l){
   
   
    LinkList p;
    int i = 0;//计数器
    p = l->next;//p初始指向首元结点
    while(p != NULL){
   
   
        i++;//计数器加1
        p = p->next;//p指向下一个结点
    }
    return i;//返回单链表长度
}

LinkList create_listT(int *a,int length){
   
   
    LinkList l,s,t;
    int i;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始t指向头结点
    t = l;
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //t的后继指向新结点
        t->next = s;
        //新结点的前驱指向t
        s->prior = t;
        //新结点成为尾结点
        t = s;
    }
    //尾结点指针域置为NULL
    t->next = NULL;
    return l;//返回头结点
}

LinkList create_listH(int *a,int length){
   
   
    LinkList l,s;
    int i;
    //创建头结点
    l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始前驱和后继指针均为NULL
    l->next = l->prior = NULL;
    for(i = 0;i < length;i++){
   
   
        //创建新结点
        s = (LinkList) malloc(sizeof(Node));
        if(s == NULL){
   
   
            exit(-1);
        }
        s->data = a[i];
        //头插法插入结点
        s->next = l->next;
        if(l->next != NULL){
   
   //此时说明l不为头结点
            l->next->prior = s;
        }
        l->next = s;
        s->prior = l;
    }
    return l;
}

LinkList create_list(){
   
   
    //创建头结点
    LinkList l = (LinkList) malloc(sizeof(Node));
    if(l == NULL){
   
   
        exit(-1);
    }
    //初始前驱和后继指针均为NULL
    l->next = l->prior = NULL;
    return l;//返回头结点
}

void traverse_list(LinkList l){
   
   
    LinkList p = l->next;
    while(p != NULL){
   
   
        printf("%d\t",p->data);
        p = p->next;
    }
}
文章标签：
算法
梳中分的坤坤
目录
相关文章
唐唐思
|
7月前
链式二叉树（3）
链式二叉树（3）
唐唐思
54 0
唐唐思
|
7月前
|
C语言
链式二叉树（1）
链式二叉树（1）
唐唐思
59 0
小小unicorn
|
存储 算法
链式二叉树的基本操作实现（建议收藏！！！）（2）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
101 0
zcx-yyds
|
存储
【数据结构】二叉树的链式实现及遍历
【数据结构】二叉树的链式实现及遍历
zcx-yyds
102 0
lge101058
|
6月前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
lge101058
41 5
ZhangBlossom
|
存储 算法 C++
C/C++线性表之链式与顺序存储结构(附代码)（一）
C/C++线性表之链式与顺序存储结构(附代码)
ZhangBlossom
202 0
唐唐思
|
7月前
链式二叉树（2）
链式二叉树（2）
唐唐思
45 0
小小unicorn
链式二叉树的基本操作实现（建议收藏！！！）（1）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
60 0
小小unicorn
链式二叉树的基本操作实现（建议收藏！！！）（3）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
39 0
梳中分的坤坤
|
存储 算法
线性表的链式实现(一)
线性表的链式实现(一)
梳中分的坤坤
56 0