JZTXT

线性表(3)链表

发布时间 2023-10-28 01:04:04作者: 5yi33

线性表(3)链表

单链表

前面我们讲了线性表的顺序存储，本文要将的是链式存储，链式存储这个名字很形象，我们通过一条条链子，把一个个数据元素连接起来，而我们具体实现中的链子，就是指针。

对于每一个链表的结点，我们分成两部分：

data next

其中，data部分存放实际的数据，next部分存放指向后继元素的指针。每个结点只存放一个指向下一个结点的指针，因此叫单链表。通过指针，我们并不需要连续的空间存放表，而是通过指针定位表，只要我们记录了第一个结点的位置，就可以通过指针找到表中所有元素的位置。具体实现代码如下：

typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

这里依然用到了typedef这个语法，具体的内容在顺序表一节讲过了，不再复述。这段代码定义了一个链表结点是长什么样的，一个data变量用于存放数据，一个next变量是指向下一个结点的指针。细心的你应该已经注意到了，我们给了LNode这个结构体两个名字，这里没有本质区别，只做语义上的强调，LNode强调这是一个结点，而LinkList用于强调这是一个链表，前面我们说到了，需要存放第一个结点的地址，那么指向第一个结点的指针就可以用LinkList来申明，用于强调这是一个链表，而我们也把这个指针叫做头指针，比如LinkList L就是这样一个指针。

链表相较于前面说过的顺序表，最大的特点就是，插入和删除操作很容易，并且由于不需要连续的内存，在动态分配上也天然优于顺序表，这一点我们后面会看到，另外链表相较于顺序表也有缺点，链表需要额外的空间用于存放指针next，这就导致链表的存储密度更低，同时由于存放结点的地址不连续，链表不支持随机访问，这也是一个缺点。

在链表的具体实现上，我们一般有两种方案：

  • 带头结点
  • 不带头结点

头指针我们知道了，那头结点是什么？头结点是一个不存放数据的结点，头指针不指向链表的存放数据的第一个结点，而是指向头结点，这样的好处是使得很多操作更容易，这在后面的讨论里会看到。而不带头结点的链表，头指针直接指向链表的第一个结点。

另外，头结点可以用来存放一些额外的数据，比如表长等。这就相当于我们有了一个表头，表头可以存放链表的全局信息，这也使得部分操作更加简单。相应的，如果没有头结点，我们如何存放这些额外的数据呢？似乎用任何一个结点都不是很合适吧？

操作

单链表的操作同顺序表一样，大致也分为增删查改，创建销毁这几类，下面分别介绍。

  • 插入

插入操作包括前插和后插，即给定一个结点以及新元素的值，将新元素插入到给定结点的前面或者后面。对于后插操作，只需要将给定结点\(p\)与其后继的连接断开，申请一个新的结点，将新结点插入两者中间即可，代码如下：

bool InsertElem(LNode *p, ElemType e) {
    if (p == NULL)
        return false;
    LNode *q = (LNode *)malloc(sizeof(LNode));
    if (q == NULL)
        return false;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return ture;
}

这里我们判断了两次指针是否为空，要注意：

对于所有需要用到指针的相关操作，都需要时刻注意解引用的合法性，因为编译器往往难以发现这样的错误，这种错误会带来意想不到的结果，比如RTE(run time error)

后插操作是简单明了的，那么前插操作呢？注意到，如果我们要将一个新节点插入链表，就需要修改改结点插入位置的上一个结点的next指针，这意味着我们需要找到该结点的前一个结点，由于链表的特性，其不支持随机访问，同时我们也并没有指向前一个结点的指针，这就导致前插操作相较于后插操作更复杂了，因为我们需要遍历链表，找到该结点的前一个结点。但是有没有方法，我们不需要找到所给结点的上一个结点，就可以插入新的结点呢？答案当然是有的。

bool InsertElem(LNode *p, ElemType e) {
    if (p == NULL)
        return false;
    LNode *q = (LNode *)malloc(sizeof(LNode));
    if (q == NULL)
        return false;
    q->data = p->data;
    p->data = e;
    q->next = p->next;
    p->next = q;
    return ture;
}

这段代码相当于，将新节点插入到所给的结点后面，然后交换新节点和所给结点的值，这就等效为一个前插操作。

删除

删除操作可以是删除某一个给定的结点p，同样的，删除了一个给定的结点p会导致链表的顺序发生变化，我们需要修改被删除结点的前一个结点的next指针，一般的做法也是遍历找到前一个结点，同时，我们也有不用找到前一个结点的删除方法，这个方法和前插的思路类似。

bool DeleteNode(LNode *p, ElemType &e) {
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->next = q;
    p->data = q->data;
    free(q);
    return ture;
}

其实这段代码是有问题的，如果这是一个只有一个结点的链表，我们在对\(q\)进行解引用的时候就会出错，所有这并不是一份健壮的代码，最好的办法还是遍历查找被删除结点的前驱。

插入和删除第\(i\)个结点

当然，插入和删除操作还有对第\(i\)个点进行操作的模式，在这种插入/删除的要求下，我们别无他法，必须先找到第\(i-1\)个结点，再对\(i\)个结点进行插入/删除。当然，如果我们使用的是带头结点的链表，这里的操作会比使用不带头结点的链表简单太多了，我们先看带头结点的实现：

bool InsertElem(LinkList &L, int i, ElemType e) {
    //查找第i个结点
    LNode *p = L;
    int idx = 0;
    while (p != NULL && idx < i - i) {
        p = p->next;
        idx++;
    }
    if (p == NULL)
        return false;
    LNode *q = (LNode *)malloc(sizeof(LNode));
    if (q == NULL)
        return false;
    q->next = p->next;
    p->next = q;
    q->data = e;
    return true;
}

删除的代码与插入的代码类似。如果不带头结点，那么我们对于第一个结点的处理是很复杂的，我们需要修改\(L\)的值，才能保证正确，而带头结点的链表则把所有存放数据的结点的处理统一规约到了一个处理逻辑，使得各种操作的实现更简单了。

查找

查找操作分为按值查找和按位查找，其实按值查位查找我们在插入/删除第\(i\)个结点的实现里已经用到过了，我们把这一部分代码：

    LNode *p = L;
    int idx = 0;
    while (p != NULL && idx < i - i) {
        p = p->next;
        idx++;
    }

提取出来，单独作为一个函数，我们就得到了按位查找的代码。而按值查找的代码只需要修改以下循环的判断条件：

    LNode *p = L;
    int idx = 0;
    while (p != NULL && p->data != e) {
        p = p->next;
        idx++;
    }

这样，我们就实现了查找功能。注意到：

    if (p == NULL)
        return false;
    LNode *q = (LNode *)malloc(sizeof(LNode));
    if (q == NULL)
        return false;
    q->next = p->next;
    p->next = q;
    q->data = e;
    return true;

这一段代码其实就是一个后插操作，所以，插入第\(i\)个元素的操作就相当于一个查找操作和一个后插的组合，我们通过函数复用可以使代码更加简洁明了。

双链表

双链表与单链表的不同之处在于，双链表不但记录后继的指针，还记录前驱的指针。因此，我们有如下的双链表定义：

typedef struct LNode {
    ElemType data;
    struct LNode *next;
    struct LNode *prev;
}LNode, *LinkList;

前面我们在讲单链表的时候也提到了，这里把同一个结构体命名为两个不同的名字，主要还是为了强调是链表的头指针还是链表某个结点，这会增加代码的可读性。我们注意到，在双链表的定义中，我们多了一个成员变量prev，这个变量存储的就是结点的前驱，我们可以通过这个变量访问当前结点的前驱结点。

双链表的增删改查相较于单链表其实都差不多，但是可以访问前驱这个性质使得在某些操作上，双链表的实现要比单链表简单，比如前插操作，我们可以直接通过prev找到某个结点的前驱，就相当于在一个逆置的链表里进行一次后插。对于删除某一个给定的元素，我们也不用遍历找到该结点的前驱再进行删除了，因为prev就记录了该结点的前驱。

双链表的基本操作与单链表基本一致，只要注意更新prev成员即可。

循环链表

循环链表，顾名思义，我们把表尾元素的next置为头结点，把头结点的prev置为表尾元素（如果是双链表），这样子，链表就被设置成了一个环，我们从头结点开始遍历，可以回到头结点。

回想我们对线性表的定义，我们说：

除了第一个元素，每个元素都有直接前驱；除了最后一个元素，每个元素都有直接后继。

当然在逻辑上仍然如此，表尾元素仍然是表尾元素，其后在逻辑上是没有元素的，但是我们在具体实现上，给了表尾元素一个相当于后继的东西，这就使得表尾元素在物理上有了一个后继，即表头元素。

循环单链表

循环链表有哪些好处呢？我们先来看到循环单链表的情况，我们把单链表表尾的元素的next置为头结点，这样子我们就得到了一个循环单链表。如果我们需要在表尾插入一个元素，我们应该怎么做？在不循环的单链表里，我们需要先遍历整个表，找到表尾元素，再进行插入，复杂度是\(O(1)\)。有没有一种办法，既能方便找到头结点，又能方便找到表尾呢？答案是尾结点，我们设置一个尾结点用于指向表尾元素，这样，通过尾结点，我们可以方便地找到表尾元素，同时，根据循环链表的特性，我们只要从表尾再向前走一步，就可以找到头结点。

循环链表的另一个优势在于，其统一了表尾的操作和其他位置的操作，下面看看双链表的情况。

循环双链表

如果我们要在双链表的某个不是表尾的位置插入一个元素，应该做些什么呢？首先我们找到这个结点的前驱，进行一次后插，注意到，由于双链表的结点有一个prev的成员变量，这就要求我们在插入元素的时候修改后继元素的prev值，对于非表尾元素，直接修改就可以了，但是如果是在表尾插入呢？由于表尾元素的后面是没有元素的，也就是表尾元素的next=NULL，这就导致我们需要特别判断插入的位置是不是表尾，否则在对next进行解引用的时候，会出现错误。但是循环链表保证了每一个元素的next都不为空，这就把这种表尾的操作和其他位置的操作进行了统一，无需特判。

判空

我们在对普通的链表判空的时候，是判断头结点的next是否为空，为空就是空表。但是循环链表不一样，循环链表的空表下，头结点会和自己连起来，自己就是自己的前驱和后继，因此判空操作略有不同，对于循环单链表：

L->next == L

对于循环双链表：

L->next == L && L->prev == L;