线性表 - 线性表的链式表示 - 《数据结构与算法》

单链表的定义
单链表上基本操作的实现
双链表
循环链表
- 循环单链表
- 循环双链表
静态链表

顺序表可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表中结点类型的描述如下：

typedef struct LNode {
    int data;             // 每个结点存放的一个数据元素
    struct LNode *next;   // 指针指向下一个结点
} LNode, *LinkList;

data为数据域，存放数据元素;
next为指针域，存放其后继结点的地址。
```
// 初始化不带头结点的空单链表函数
bool InitList(LinkList &L){
  L = nullptr; 
  return true;
}
```
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

通常用头指针来标识一个单链表，如单链表 L，头指针为 nullptr 时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

// 初始化带头结点的空单链表函数
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode)); // 分配一个头结点
    if(L == nullptr){ // 内存不足，分配失败
        return false;
    }
    L->next = nullptr; // 头结点之后暂时还没有结点 
    return true;
}

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点后，可以带来两个优点：

由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表上基本操作的实现

按位序插入（带头结点）

// 按位序插入（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }

    // 找到第i-1个结点 GetElem
    LNode *p;   // 指针p指向当前扫描到的结点
    int j = 0;  // 当前p指向的是第几个结点
    p = L;      // L指向头结点，头结点是第0个结点
    while (p != nullptr && j < i - 1) {  // 循环找到第 i-1 个结点
        p = p->next;
        j++;
    }

    if (p == nullptr) {  // i值不合法
        return false;
    }

    // 将e插入到i-1结点之后 InsertNextNode
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;  // 将结点s连接到p之后
    return true;
}

最好情况：插入的元素就在表头，时间复杂度为 $线性表的链式表示 - 图1$ #card=math&code=O%281%29&id=OjdLg)。
最坏情况：插入的元素在表尾时，时间复杂度为 $线性表的链式表示 - 图2$ #card=math&code=O%28n%29&id=CEXei)。
平均时间复杂度： $线性表的链式表示 - 图3$ #card=math&code=O%28n%29&id=VA6cN)。

按位序插入（不带头结点）

// 按位序插入（不带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }

    if (i == 1) {  // 插入第1个结点操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }

    LNode *p;   // 指针p指向当前扫描到的结点
    int j = 1;  // 当前p指向的是第几个结点
    p = L;      // L指向头结点，头结点是第0个结点
    while (p != nullptr && j < i - 1) {  // 循环找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == nullptr) {  // i值不合法
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;  // 将结点s连接到p之后
    return true;
}

指定结点的后插操作

// 后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == nullptr) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == nullptr) {  // 内存分配失败
        return false;
    }
    s->data = e; 
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度： $线性表的链式表示 - 图4$ #card=math&code=O%281%29&id=ONPWq)。

指定结点的前插操作

// 前插操作
bool InsertPriorNode(LNode *p, int element) {
    if (p == nullptr) {
        return false;
    }
    auto *s = (LNode *)malloc(sizeof(LNode));
    if (s == nullptr) {
        return false;
    }
    s->next = p->next;
    p->next = s;        // 新结点s连到p之后 ⭐
    s->data = p->data;  // 将p中元素覆盖到s中 
    p->data = element;  // p中元素覆盖为e
    return true;
}

指针后插，数据交换。

时间复杂度： $线性表的链式表示 - 图5$ #card=math&code=O%281%29&id=rOK2V)。

按位序删除（带头结点）

// 按位序删除
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    // 找
    LNode *p;
    int j = 0;
    p = L;
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    // 判断
    if (p == nullptr || p->next == nullptr) {
        return false;
    }
    // 删除
    LNode *q = p->next;  // 使q指向被删除的结点
    e = q->data;         // 用e返回元素的值
    p->next = q->next;   // 将*q结点从链中断开
    free(q);             // 释放结点储存空间
    return true;
}

最好情况：删除的元素就在表头，时间复杂度为 $线性表的链式表示 - 图6$ #card=math&code=O%281%29&id=nAveT)。
最坏情况：删除的元素在表尾时，时间复杂度为 $线性表的链式表示 - 图7$ #card=math&code=O%28n%29&id=NtOz9)。
平均时间复杂度： $线性表的链式表示 - 图8$ #card=math&code=O%28n%29&id=oCyFi)。

删除指定结点

bool DeleteNode(LNode *p) {
    if (p == nullptr) {
        return false;
    }
    LNode *q = p->next;      // 使q指向*p的后继结点
    p->data = p->next->data; // 和后继结点交换数据域
    p->next = q->next;       // 将*q结点从链中断开
    free(q);                 // 释放后继结点的储存空间
    return true;
}

时间复杂度： $线性表的链式表示 - 图9$ #card=math&code=O%281%29&id=tkARU)。

注意：上段代码无法解决 p 结点时尾结点时的删除问题，删除尾结点需要从头开始查找

按位查找（带头结点）

// 按位查找，返回第i个元素
LNode *GetElement(LinkList L, int i) {
    if (i < 0) {
        return nullptr;
    }
    LNode *p;
    int j = 0;
    p = L;
    while (p != nullptr && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

最好情况：查找的元素就在表头，时间复杂度为 $线性表的链式表示 - 图10$ #card=math&code=O%281%29&id=mqDuV)。
最坏情况：查找的元素在表尾时，时间复杂度为 $线性表的链式表示 - 图11$ #card=math&code=O%28n%29&id=NbJ1Y)。
平均时间复杂度： $线性表的链式表示 - 图12$ #card=math&code=O%28n%29&id=aPnDZ)。

按值查找

LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    // 从第一个结点开始查找数据域为e的结点
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p;
}

最好情况：查找的元素就在表头，时间复杂度为 $线性表的链式表示 - 图13$ #card=math&code=O%281%29&id=VoGEP)。
最坏情况：查找的元素在表尾（或不存在）时，时间复杂度为 $线性表的链式表示 - 图14$ #card=math&code=O%28n%29&id=APg2b)。
平均时间复杂度： $线性表的链式表示 - 图15$ #card=math&code=O%28n%29&id=tC8EY)。

求单链表的长度

// 求表的长度
int Length(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p->next != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}

时间复杂度： $线性表的链式表示 - 图16$ #card=math&code=O%28n%29&id=a3o9z)。

头插法建立单链表

#include <iostream>

using namespace std;

LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = nullptr;  // 初始空链表
    cin >> x;
    while (x > 9999) {  // 输入值大于9999表示结束
        s = (LNode *)malloc(sizeof(LNode));  // 后插操作
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin >> x;
    }
    return L;
}

重要应用：链表逆置

尾插法建立单链表

#include <iostream>

using namespace std;

LinkList List_TailInsert(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode)); // 建立头结点
    LNode *s, *r = L;  // r指针为表尾指针
    int x;
    cin >> x;  // 输入结点的数据
    while (x > 9999) {   // 输入值大于9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;    // r指向新的表尾结点
        cin >> x;
    }
    r->next = nullptr;
    return L;
}

时间复杂度： $线性表的链式表示 - 图17$ #card=math&code=O%28n%29&id=aiKow)

双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为 $线性表的链式表示 - 图18$ #card=math&code=O%281%29&id=qcbUa) ，访问前驱结点的时间复杂度为 $线性表的链式表示 - 图19$ #card=math&code=O%28n%29&id=MMNAX)。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点，双链表中结点类型的描述如下：

typedef struct DNode {
    int data;  // 数据域
    struct DNode *prior, *next;  // 前驱指针和后继指针
} DNode, *DLinklist;

双链表在单链表的结点中增加了一个指向其前驱的 prior 指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对 prior 指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为 $线性表的链式表示 - 图20$ #card=math&code=O%281%29&id=SBgLQ)。

双链表的插入

线性表的链式表示 - 图21

bool InertNextDNode(DNode *p, DNode *s) {
    if (p == nullptr || s == nullptr) {
        return false;
    }
    s->next = p->next;  // ① 将结点*s插入到结点*p之后
    if (p->next != nullptr) {
        p->next->prior = s; // ②
    }
    s->prior = p; // ③
    p->next = s;  // ④
}

上述代码的语句顺序不是唯一的，但也不是任意的，① 和 ② 两步必须在 ④ 步之前，否则 *p 的后继结点的指针就会丢掉，导致插入失败。

双链表的删除

线性表的链式表示 - 图22

#include <cstdlib>

// 双链表的删除操作
bool DeleteNextDNode(DNode *p) {
    if (p == nullptr) {
        return false;
    }
    DNode *q = p->next;  // 找到p的后继结点q
    if (q == nullptr) {
        return false;  // p没有后继结点
    }
    p->next = q->next; // ①
    if (q->next != nullptr) {
        q->next->prior = p; // ②
    }
    free(q);
    return true;
}

双链表的循环

// 后向遍历
while(p != nullptr){
    // 相关处理...
    p = p->next;
}

// 前向遍历
while (p != nullptr){
    // 相关处理...
    p = p->prior;
}

// 前向变量（跳过头结点）
while (p->prior != nullptr){
    // 相关处理...
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 $线性表的链式表示 - 图23$ #card=math&code=O%28n%29&id=Wjcy2)。

循环链表

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是 nullptr，而改为指向头结点，从而整个链表形成一个环。

typedef struct LNode {
    int data;             // 每个结点存放的一个数据元素
    struct LNode *next;   // 指针指向下一个结点
} LNode, *LinkList;

// 初始化带头结点的空单链表函数
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode)); // 分配一个头结点
    if(L == nullptr){ // 内存不足，分配失败
        return false;
    }
    L->next = L; // 头结点next指向头结点
    return true;
}

// 判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next == L){
        return true;
    }else{
        return false;
    }
}

// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
    if(p->next == L){
        return true;
    }else{
        return false;
    }
}

循环双链表

// 初始化空的循环双链表
bool InitDLinkList(Dlinklist &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L == nullptr){
        return false;
    }
    L->prior = L;
    L->next = L;
    return true;
}

// 判断循环双链表是否为空
bool Empty(DLinkList L){
    if(L->next == L){
        return true;
    }else{
        return false;
    }
}

// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){
    if(p->next == L){
        return true;
    }else{
        return false;
    }
}

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

静态链表结构类型的描述如下：

#define MaxSize 10  // 静态链表的最大长度
struct Node {       // 静态链表结构类型的定义
    int data;       // 存储数据元素
    int next;       // 下一个元素的数组下标
};

静态链表以 next==-1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言（如 Basic）中，这是一种非常巧妙的设计方法。

王道书中对静态链表定义：

#include <iostream>
using namespace std;

#define MaxSize 10  // 静态链表的最大长度
struct Node {       // 静态链表结构类型的定义
    int data;       // 存储数据元素
    int next;       // 下一个元素的数组下标
};
typedef struct {
    int data;
    int next;
} SLinkList[MaxSize];

void testSLinkList() {
    struct Node x;
    printf("size x = %d\n", sizeof(x)); // 8

    struct Node a[MaxSize];
    printf("size a = %d\n", sizeof(a)); // 80

    SLinkList b;
    printf("size b = %d\n", sizeof(b));  // 80
}

int main() {
    testSLinkList();
    system("pause");
}

优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景：不支持指针的语言；数据元素量固定不变的场景（如操作系统的文件分配表 FAT）