【数据结构】第二章 线性表

线性表的逻辑结构（定义）

线性表是具有相同数据类型的\(n\left( n\geqslant 0 \right)\)个数据元素的有限序列，其中\(n\)为表长，当\(n = 0\)时线性表是一个空表。若用\(L\)命名线性表，则其一般表示为 \[ L=\left( a_1, a_2, \dots , a_i, a_{i+1}, \dots , a_n \right). \]

【注意】

• 相同数据类型：线性表中元素的类型必须一致

• 有限序列：必须是有限的、区分先后顺序的序列

  e.g.：所有的整数按递增次序排列就不是线性表

几个概念：

• \(i\)是线性表中的“第\(i\)个”元素在线性表中的位序

• \(a_1\)是表头元素；\(a_n\)是表尾元素

• 除第一个元素外，每个元素有且仅有一个直接前驱

• 除最后一个元素外，每个元素有且仅有一个直接后继

【注意】

位序从1开始，数组下标从0开始。

线性表的基本操作

为什么要实现对数据结构的基本操作？

• 团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）
• 将常用的操作/运算封装成函数，避免重复工作，降低出错风险

• 创建与销毁
  • InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
  • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
• 增、删
  • ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
• 查
  • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
  • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
• 其他常用操作
  • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
  • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

说明：

• 对数据的操作——创销、增删查

• C语言函数的定义：

  返回值类型 函数名(参数1类型 参数1, 参数2类型 参数2, ...)

  为什么这里没有说明各个参数的具体类型？

  这是因为这里的类型可以根据实际需要来确定，这里仅给出抽象的数据结构。

• 实际开发中，可根据实际需求定义其他的基本操作

• 函数名和参数的形式、命名都可改变，但需要具有可读性（Ref：严蔚敏版《数据结构》）

• 什么时候要传入引用&？——对参数的修改结果需要“带回来”

• 在线实验工具：C++ 在线工具 | 菜鸟工具 (runoob.com)

小结

小结

线性表的物理结构

顺序表：线性表的顺序表示

在顺序表中，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的内存结构示意图

由于线性表中的元素具有相同数据类型，各个元素在内存中的占用空间大小相同，而在顺序表中各个元素又按逻辑顺序依次连续存放，故可以采用访问LOC(L)+(i-1)*sizeof(ElemType)（首元素地址＋第i个元素的位置偏移量）地址的方式来访问顺序表中的任意的第i个元素。

实现方式

静态分配实现

#define MaxSize 10           // 定义最大长度
typedef struct{
    ElemType data[MaxSize];  // 用静态的“数组”存放数据元素
    int length;              // 顺序表的当前长度
} SqList;                    // 顺序表的类型定义（静态分配方式）
                             // Sq: Sequence，顺序，序列

声明SqList时，系统会给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)。

Q：如果“数组”存满了怎么办？

A：可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）

动态分配实现

#define InitSize 10 // 顺序表的初始长度
typedef struct{
    ElemType *data; // 指示动态分配数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
} SeqList;          // 顺序表的类型定义（动态分配方式）

动态申请和释放内存空间

• C语言：malloc、free函数

  malloc函数用于申请一整片连续的存储空间，返回空间的首地址（返回void *类型，需要转换为ElemType *）。

  e.g.：L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);

  注意：malloc前必须加上强制转换符(ElemType *)，这是因为具体的类型为编译器标示了如何确定数组各个元素的大小，下标运算符[]才能通过这一大小确定元素的位置。

• C++语言：new、delete关键字

顺序表的特点

1. 随机访问，即可以在O(1)时间内找到第i个元素

   无论是静态分配还是动态分配都可使用L.data[i-1]来访问第i个元素。

2. 存储密度高，每个节点只存储数据元素

3. 拓展容量不方便

   即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高（需要逐一复制原有的元素到新地址）。

4. 插入、删除操作不方便，需要移动大量元素

基本操作

注：在未说明的情况下，本节代码建立在顺序表的“静态分配”实现方式之上，“动态分配” 实现类似。

#define MaxSize 10           // 定义最大长度
typedef struct{
    int data[MaxSize];       // 用静态的“数组”存放整型元素
    int length;              // 顺序表的当前长度
}SqList;                     // 顺序表的类型定义

顺序表的插入

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置（位序，从1开始计数）上插入指定元素e。

bool ListInsert(SqList &L, int i, int e) {
    if(i < 1 || i > L.length + 1)       // 判断i的范围是否有效
        return false;
    if(L.length >= MaxSize)             // 判断存储空间是否已满
        return false;
    for(int j = L.length; j >= i; j--)  // 将第i个以及之后的元素后移1位
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;                    // 在位置i处放入e
    L.length++;                         // 长度加1
    return true;
}

插入操作的时间复杂度

问题规模n = L.length（表长）

• 最好情况：新元素插入到表尾，不需要移动元素

  i = n+1，循环 0 次；最好时间复杂度O(1)

• 最坏情况：新元素插入到表头，需要将原有的 n 个元素全都向后移动

  i = 1，循环 n 次；最坏时间复杂度O(n)

• 平均情况：假设新元素插入到任何一个位置的概率相同，即\(i=1,2,3,\dots ,n+1\)的概率\(p=\frac{1}{n+1}\)。

  i = 1，循环 n 次；i = 2，循环 n-1 次；i = 3，循环 n-2 次，……，i = n+1，循环 0 次。

  故循环次数的期望为 \[ np+(n-1)p+(n-2)p+\cdots +1\cdot p=\frac{n(n+1)}{2}\cdot \frac{1}{n+1}=\frac{n}{2}=O(n) \]

顺序表的删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置（位序，从1开始计数）的元素， 并用e返回删除元素的值。

bool ListDelete(SqList &L, int i, int &e) {
    if(i < 1 || i > L.length + 1)       // 判断i的范围是否有效
        return false;
    e = L.data[i-1];                    // 将被删除的元素赋值给e
    for(int j = i; j < L.length; j++)   // 将第i个以及之后的元素后移1位
        L.data[j-1] = L.data[j];
    L.length--;                         // 长度减1
    return true;
}

删除操作的时间复杂度

问题规模n = L.length（表长）

• 最好情况：删除表尾元素，不需要移动其他元素

  i = n，循环 0 次；最好时间复杂度O(1)

• 最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动

  i = 1，循环 n-1 次；最坏时间复杂度O(n)

• 平均情况：假设新元素插入到任何一个位置的概率相同，即\(i=1,2,3,\dots ,n\)的概率\(p=\frac{1}{n}\)。

  i = 1，循环 n-1 次；i = 2，循环 n-2 次；i = 3，循环 n-3 次，……，i = n，循环 0 次。

  故循环次数的期望为 \[ (n-1)p+(n-2)p+\cdots +1\cdot p=\frac{n(n-1)}{2}\cdot \frac{1}{n}=\frac{n-1}{2}=O(n) \]

顺序表的按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

// 静态分配实现
#define MaxSize 10           // 定义最大长度
typedef struct{
    ElemType data[MaxSize];  // 用静态的“数组”存放数据元素
    int length;              // 顺序表的当前长度
} SqList;                    // 顺序表的类型定义（静态分配方式）

ElemType GetElem(SqList L, int i){
    return L.data[i-1];
}

// 动态分配实现
#define InitSize 10 // 顺序表的初始长度
typedef struct{
    ElemType *data; // 指示动态分配数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
} SeqList;          // 顺序表的类型定义（动态分配方式）

ElemType GetElem(SeqList L, int i){
    return L.data[i-1];
}

按位查找操作的时间复杂度

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素（“随机存取”特性），故按位查找操作的时间复杂度为\(O(1)\)。

顺序表的按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

// 动态分配实现
#define InitSize 10      // 顺序表的初始长度
typedef struct{
    ElemType *data;      // 指示动态分配数组的指针
    int MaxSize;         // 顺序表的最大容量
    int length;          // 顺序表的当前长度
} SeqList;               // 顺序表的类型定义（动态分配方式）

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e){
    for(int i=0; i<L.length; i++)
        if(L.data[i] == e)
        	return i+1;  // 数组下标为i的元素值等于e，返回其位序i+1
    return 0;            // 退出循环，说明查找失败
}

手写代码与机试的区别

《数据结构》考研初试中，手写代码可以直接用==，无论ElemType是基本数据类型还是 结构类型，手写代码主要考察学生是否能理解算法思想，不会严格要求代码完全可运行。

• 基本数据类型（int、char、double、float等）可以直接用运算符==比较
• 结构体数据类型是不能直接用运算符==比较的，需要
  • 依次对比各个分量来判断两个结构体是否相等；
  • 或者要求使用者定义一个判断相等的函数，再在LocateElem代码中调用这一函数

删除操作的时间复杂度

问题规模n = L.length（表长）

• 最好情况：目标元素在表头，循环 0 次，时间复杂度O(1)

• 最坏情况：目标元素在表尾，循环 n 次，时间复杂度O(n)

• 平均情况：假设目标元素出现在任何一个位置的概率相同，都为\(p=\frac{1}{n}\)。

  目标元素在第 1 位，循环 1 次；在第 2 位，循环 2 次；……；在第 n 位，循环 n 次。

  故循环次数的期望为 \[ 1\cdot p+2\cdot p+\cdots +n\cdot p=\frac{n(n+1)}{2}\cdot \frac{1}{n}=\frac{n+1}{2}=O(n) \]

小结

顺序表的定义思维导图

顺序表的插入删除思维导图

顺序表的查找思维导图

单链表：线性表的链式表示（1）

顺序表与单链表的结构对比

	顺序表	单链表
优点	可随机存取，存储密度高	不要求大片连续空间，改变容量方便
缺点	要求大片连续空间，改变容量不方便	不可随机存取，要耗费一定空间存放指针

单链表的定义

struct LNode {				// 定义单链表结点类型
    ElemType data;			// 数据域：每个节点存放一个数据元素
    struct LNode *next; 	// 指针域：指针指向下一个节点
};

// 增加一个新的结点：在内存中申请一个结点所需空间，并用指针 p 保存这个结点的地址
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

typedef关键字用于对数据类型重命名。

用法：typedef <数据类型> <别名>

利用typedef关键字，可以将上面的增加结点代码改写为：

// 增加一个新的结点：在内存中申请一个结点所需空间，并用指针 p 保存这个结点的地址
typedef struct LNode LNode;
LNode *p = (LNode *)malloc(sizeof(LNode));

或者直接在定义结构体时就改写：

typedef struct LNode {		// 定义单链表结点类型
    ElemType data;			// 数据域：每个节点存放一个数据元素
    struct LNode *next; 	// 指针域：指针指向下一个节点
} LNode, *LinkList;			// LinkList表示单链表，它是LNode的指针

今后我们都将采用这一改写形式。

要表示一个单链表时，只需声明一个头指针 L，指向单链表的第一个结点：

LinkList L;

• LinkList 强调这是一个单链表
• 使用LNode * 强调这是一个结点

不带头结点的单链表

// 初始化一个空的单链表
bool InitList(LinkList &L) {
    L = NULL; // 空表，暂时还没有任何结点，置空防止脏数据
    return true;
}

// 判断单链表是否为空
bool Empty(LinkList L) {
    return L == NULL;
}

带头结点的单链表

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

// 判断带头结点的单链表是否为空
bool Empty(LinkList L) {
    return L->next == NULL;
}

Tips：头结点不存储数据！

带/不带头结点的区别

• 带头结点，代码更方便
  • 空表判断：L == NULL
• 不带头结点，写代码更麻烦
  • 对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
  • 对空表和非空表的处理需要用不同的代码逻辑
  • 空表判断：L->next == NULL

小结

链表的定义思维导图

基本操作：插入

按位序插入

ListInsert(&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e。

思路：遍历节点并计数，找到第i-1个结点，将新结点插入其后。

带头结点

注意：头结点可以看作“第0个”结点，不需要对第1个结点特殊处理。

// 在第i个位置插插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ELlemType e){
    if (i < 1)
    	return false;
    // 指针p指向当前扫描到的结点
    LNode *p;
    // 当前p指向的是第几个结点
    int j = 0;
    // L指向头结点,头结点是第0个结点(不存数据)
    p = L;
    // 循环找到第i-1个结点
    while (p != NULL && j < i-1){
        p = p->next;
        j++;
    }
    // i值不合法
    if(p==NULL)
    	return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data=e;
    // 将结点s接入到p的下一个结点之前
    s->next=p->next;	// ▲
    // 将结点s接入到p之后
    p->next=s;			// ▲
    //插入成功
    return true;
}

代码中▲部分的两个语句顺序不能颠倒，否则原p的下一个结点（以及原来链表里之后的节点）就找不到了。

正确的结点接入方式

颠倒后错误的接入方式

不带头结点

注意：不存在“第0个”结点，因此i=1时需要特殊处理。

bool ListInsert(LinkList &L, int i, ElemType 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;              // p指向第1个结点（注意：不是头结点）
    while (p != NULL && j < i - 1) {    // 循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if (p == NULL)      // i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;        // 插入成功
}

不带头结点写代码更不方便，推荐用带头结点。

除非特别声明，之后的代码默认带头结点!

注意：考试中带头、不带头都有可能考察，注意审题

按位序插入操作的时间复杂度

问题规模n = L.length（表长）

• 最好情况：插在表头，时间复杂度O(1)

• 最坏情况：插在表尾，时间复杂度O(n)

• 平均情况：时间复杂度O(n)

在给定节点前后插入

在给定节点之后插入

// 后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)  // 内存分配失败（不写问题也不大）
        return false;
    s->data = e;    // 用结点s保存数据元素e
    s->next = p->next;
    p->next = s;    // 将结点s连到p之后
    return true;
}

时间复杂度：O(1)

ListInsert的简化版本

利用InsertNextNode函数，可以简化之前写的按位序插入操作ListInsert（以带头结点版本为例）：

// 在第i个位置插插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ELlemType e){
    if (i < 1)
    	return false;
    // 指针p指向当前扫描到的结点
    LNode *p;
    // 当前p指向的是第几个结点
    int j = 0;
    // L指向头结点,头结点是第0个结点(不存数据)
    p = L;
    // 循环找到第i-1个结点
    while (p != NULL && j < i-1){
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e);
}

在给定节点之前插入

思路1：如果能额外给出线性表的头指针，则可以通过遍历到给定节点的前一个节点来实现插入，但是这样的算法时间复杂度为O(n)，不推荐；

思路2：虽然不能很快地找到原p结点的前驱，但是可以通过将数据域替换的方式“曲线救国”，将前插操作转化为后插操作，即将结点p的数据域替换为需要插入的节点的值，然后在节点p后插入一个节点，其数据域为原p结点的数据域：

// 前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e) {
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)      // 内存分配失败
        return false;
    s->next = p->next;
    p->next = s;        // 新结点s连到p之后
    s->data = p->data;  // 将p中元素复制到s中
    p->data = e;        // p中元素覆盖为e
    return true;
}

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

基本操作：删除

按位序删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。

后文都将以带头结点的版本为例！

注意：头结点可以看作“第0个”结点，不需要对第1个结点特殊处理。

bool ListDelete(LinkList &L, int i, ElemType &e) {
    if (i < 1)
        return false;
    LNode *p;               // 指针p指向当前扫描到的结点
    int j = 0;              // 当前p指向的是第几个结点
    p = L;                  // L指向头结点
    while (p != NULL && j < i - 1) {    // 循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if (p == NULL)          // i值不合法
        return false;
    if (p->next == NULL)    // 第i-1个结点之后已无其他结点
        return false;
    LNode *q = p->next;     // 令q指向被删除结点
    e = q->data;            // 用e返回元素的值
    p->next = q->next;      // 将*q结点从链中“断开”
    free(q);                // 释放结点的存储空间
    return true;            // 删除成功
}

按位序删除操作的时间复杂度

问题规模n = L.length（表长）

• 最好情况：时间复杂度O(1)

• 最坏情况：时间复杂度O(n)

• 平均情况：时间复杂度O(n)

删除给定结点（BUG版）

思路：类似于给定节点前插操作的思路2，将结点p的数据域替换为后继节点的数据域，然后删除后继节点：

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

类似于给定节点前插操作的思路2，时间复杂度为O(1)。

这一算法实际上是错误的，因为它不能正确处理删除链表最后一个节点的情况（此时不存在后继节点，无法替换）。

因此，要在单链表中正确实现删除给定结点操作，只能对最后一个节点（通过判断指针域next是不是空来确定是否为末节点）采用给定节点前插操作的思路1，即遍历链表，找到前驱的方式删除（此时，时间复杂度为O(n)），考试也不会考。

可见，单链表具有【无法逆向检索】的局限性，有时候不太方便。

基本操作：查找

按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

// 按位查找,返回第i个元素（带头结点）
LNode *GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    LNode *p;   // 指针p指向当前扫描到的结点
    int j = 0;  // 当前p指向的是第几个结点
    p = L;      // L指向头结点,头结点是第0个结点（不存数据）
    while (p != NULL && j < i) {    // 循环找到第i个结点
        p = p->next;
        j++;
    }
    return p;
}

平均/最坏时间复杂度：O(n)

ListInsert的进一步简化

在定义GetElem函数后，就可以将按位序插入函数ListInsert（以带头结点版本为例）进一步简化为：

// 在第i个位置插插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ELlemType e){
    if (i < 1)
    	return false;
    // 找到第i-1个结点
    LNode *p = GetElem(L, i - 1);
    return InsertNextNode(p, e);
}

按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

// 按值查找，找到数据域为e的结点
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    // 从第1个结点开始查找数据域为e的结点
    while (p != NULL && p->data != e)
        p = p->next;
    return p; // 找到后返回该结点指针,否则返回NULL
}

平均/最坏时间复杂度：O(n)

再次提醒==/!=的使用注意事项

• 基本数据类型（int、char、double、float等）可以直接用运算符==/!=比较
• 结构体数据类型是不能直接用运算符==/!=比较的，需要
  • 依次对比各个分量来判断两个结构体是否相等；
  • 或者要求使用者定义一个判断相等的函数，再在LocateElem代码中调用这一函数

求表长

Length(LinkList L)：求表长操作。返回表L的数据节点个数。

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

平均/最坏时间复杂度：O(n)

基本操作：建表

“尾插法”

思路：为了避免每次从头查找链表的尾部节点（会导致时间复杂度增加到$O\left( n^2\right)$），可以设置一个指向表尾结点的指针用于辅助连续的在表尾插入节点。

#define STOP_SIGNAL 9999                    // 输入这一信号表示停止输入
LinkList List_TailInsert(LinkList &L) {     // 正向建立单链表
    int x;                                  // 设ElemType为整型
    L = (LinkList)malloc(sizeof(LNode));    // 建立头结点
    L->next = NULL;                         // 初始为空链表
    LNode *s, *r = L;                       // r为表尾指针
    scanf("%d", &x);                        // 输入结点的值
    while (x != STOP_SIGNAL) {              // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                              // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;                         // 尾结点指针置空
    return L;
}

平均/最坏时间复杂度：O(n)

“头插法”

#define STOP_SIGNAL 9999                    // 输入这一信号表示停止输入
LinkList List_HeadInsert(LinkList &L) {     // 逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));    // 创建头结点
    L->next = NULL;                         // 初始为空链表
    scanf("%d", &x);                        // 输入结点的值
    while (x != STOP_SIGNAL) {              // 输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode)); // 创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                        // 将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

平均/最坏时间复杂度：O(n)

小结

单链表的插入删除思维导图

单链表的查找思维导图

单链表的建表总结

双链表：线性表的链式表示（2）

由于单链表具有“无法逆向检索”的缺点，我们在单链表的基础上进行改进，进一步牺牲了存储密度，使其“可进可退”。

双链表的定义

typedef struct DNode {          // 定义双链表结点类型
    ElemType data;              // 数据域
    struct DNode *prior, *next; // 前驱和后继指针，prior表示先前的
} DNode, *DLinklist;

初始化双链表（带头结点）与判空

// 初始化一个空的带头结点的双链表
bool InitDLinkList(DLinklist &L) {
    // 分配一个头结点
    L = (DNode *)malloc(sizeof(DNode));
    // 内存不足，分配失败
    if (L == NULL)						
    	return false;
    // 头结点的prior永远指向NULL
    L->prior = NULL;
    // 头结点之后暂时还没有节点
    L->next = NULL;
    return true;
}

// 判断带头结点的双链表是否为空
bool Empty(DLinklist L) {
    return L->next == NULL;
}

基本操作：后插

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {
    if(p==NULL || s == NULL) // 非法参数
        return false;
    s->next = p->next;      // ▲ 将结点*s插入到结点*p之后
    if(p->next != NULL)     // ▲ 如果p结点后还有结点
        p->next->prior = s; // ▲ 
    s->prior = p;           // ▲ 
    p->next = s;            // ▲ 
    return true;
}

标▲的几行代码的顺序，不一定必须是这个顺序，但写的时候一定要注意功能的实现是否正常，最好画图验证一下。

基本操作：删除

删除结点

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p) {
    if (p == NULL)
        return false;
    DNode *q = p->next;  // 找到p的后继结点q
    if (q == NULL)
        return false;    // p没有后继
    p->next = q->next;
    if (q->next != NULL) // ▲ q结点不是最后一个结点
        q->next->prior = p;
    free(q);             // 释放结点空间
    return true;
}

删除链表

bool DestroyList(DLinklist &L){
    if (L == NULL)
        return false;
    // 循环释放各个数据结点
    while(L->next){
        if(!DeleteNextDNode(L))
            return false;
    }
    // 删除头结点
    free(L);
    // 链表置空
    L = NULL;
    return true;
}

基本操作：遍历

后向遍历

while (p) {
    // 对结点p做相应处理，如打印
    p = p->next;
}

前向遍历

while (p) {
    // 对结点p做相应处理
    p = p->prior;
}

前向遍历（跳过头结点）

while (p->prior) {
    // 对结点p做相应处理
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现，故时间复杂度O(n)

小结

双链表的思维导图

循环链表：线性表的链式表示（3）

循环单链表

循环单链表与普通单链表的结构对比

• 普通单链表
  • 表尾结点的next指针指向NULL
  • 从一个结点出发只能找到后续的各个结点
• 循环单链表
  • 表尾结点的next指针指回头结点
  • 从一个结点出发可以找到其他任何一个结点

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

// 判断带头结点的单链表是否为空
bool Empty(LinkList L) {
    return L->next == L;
}

// 判断是否为表尾结点
bool isTail(LinkList L, LNode *p) {
    return p->next == L;
}

对于循环单链表来说，

• 从头结点找到尾结点，时间复杂度为O(n)
• 从尾结点找到头结点，时间复杂度为O(1)

但事实上，很多时候对链表的操作都是在头部或尾部，故可以让L指针指向表尾元素以方便操作。

注意：这样做以后，插入、删除时可能需要修改L指针。

循环双链表

循环双链表与普通双链表的结构对比

• 普通双链表

  • 表头结点的prior指向NULL
  • 表尾结点的next指针指向NULL

• 循环双链表

  • 表头结点的prior指向表尾结点

    相当于循环双链表中的prior指向构成了一个闭环

  • 表尾结点的next指针指回头结点

    相当于循环双链表中的next指向也构成了一个闭环

// 初始化一个空的带头结点的循环双链表
bool InitDLinkList(DLinklist &L) {
    // 分配一个头结点
    L = (DNode *)malloc(sizeof(DNode));
    // 内存不足，分配失败
    if (L == NULL)						
    	return false;
    // 头结点的prior指向表尾结点 循环
    L->prior = L;
    // 头结点的next指向头结点 循环
    L->next = L;
    return true;
}

// 判断带头结点的双链表是否为空
bool Empty(DLinklist L) {
    return L->next == L;
}

// 判断是否为表尾结点
bool isTail(DLinklist L, DNode *p) {
    return p->next == L;
}

对于循环双链表，后插结点操作不再需要判断是否为表尾结点：

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {
    if(p==NULL || s == NULL) // 非法参数
        return false;
    s->next = p->next;      // ▲ 将结点*s插入到结点*p之后
    // if(p->next != NULL)  // ▲ 如果p结点后还有结点
    p->next->prior = s;     // ▲ 
    s->prior = p;           // ▲ 
    p->next = s;            // ▲ 
    return true;
}

删除节点也不再需要判断是否为表尾结点：

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p) {
    if (p == NULL)
        return false;
    DNode *q = p->next;     // 找到p的后继结点q
    // if (q == NULL)
    //     return false;    // p不可能没有后继（循环）
    p->next = q->next;
    // if (q->next != NULL) // 无需判断q结点不是最后一个结点
    q->next->prior = p;
    free(q);                // 释放结点空间
    return true;
}

小结

循环链表的思维导图

静态链表：线性表的链式表示（4）

静态链表：用数组的方式实现的链表

• 链表：各个结点在内存中星罗棋布、散落天涯。
• 静态链表：分配一整片连续的内存空间，各个结点集中安置。

静态链表的存储结构示意图

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

// SLinkList M;       // 这一行代码将会定义大小为MaxSize
                      // 的上面所定义的结构体的数组

【优点】

• 增、删操作不需要大量移动元素

【缺点】

• 不能随机存取，只能从头结点开始依次往后查找
• 容量固定不可变

【适用场景】

• 不支持指针的低级语言
• 数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

基本操作

注：考研基本不考代码实现！

假设静态链表为SLinkList a：

• 初始化静态链表
  1. 把a[0]的next设为-1
  2. 把其他结点的next设为一个特殊值用来表示结点空闲，如-2
• 查找
  • 从头结点出发挨个往后遍历结点
• 插入位序为i的结点
  1. 找到一个空闲的结点，存入数据元素
     • 空闲判断next == -2
  2. 从头结点出发找到位序为i-1的结点
  3. 修改新结点的next
  4. 修改i-1号结点的next
• 删除某个结点
  1. 从头结点出发找到前驱结点
  2. 修改前驱结点的游标
  3. 被删除结点next设为空闲标志-2

顺序表与链表的对比

逻辑结构

顺序表和链表都属于线性表，逻辑结构都是线性结构。

物理结构

• 顺序表：顺序存储
  • 优点：支持随机存取、存储密度高
  • 缺点：大片连续空间分配不方便，改变容量不方便
• 链表：链式存储
  • 优点：离散的小空间分配方便，改变容量方便
  • 缺点：不可随机存取，存储密度低（需要额外存储指针域）

基本操作

主要考察：创（销）、增删（改）查

• 创建

  • 顺序表：需要预分配大片连续空间

    若分配空间过小，则之后不方便拓展容量；

    若分配空间过大，则浪费内存资源。

    • 静态分配（静态数组）：容量不可改变
    • 动态分配（动态数组）：容量可改变，但需要移动大量元素，时间代价高

  • 链表：只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

• 销毁

  • 顺序表
    • 静态分配（静态数组）：系统自动回收空间，无需操作
    • 动态分配（动态数组）：需要手动free释放空间
  • 链表：需要依次释放free各个结点
  • 注意：malloc和free必须成对出现

• 插入/删除结点

  • 顺序表：插入/删除元素要将后续元素都后移/前移

    时间复杂度是O(n)，时间开销主要来自移动元素，

    若单个数据元素占用的空间较大，那么移动的时间代价会很高

  • 链表：插入/删除元素只需修改指针即可

    时间复杂度虽然也是O(n)，但时间开销主要来自查找目标元素

    查找元素的时间代价更低

• 查找

  • 顺序表

    • 按位查找：O(1)（随机存取）

    • 按值查找：O(n)

      注：若表内元素有序，可利用二分法在O(log n)时间内找到

  • 链表

    • 按位查找：O(n)
    • 按值查找：O(n)

总结对比

	顺序表	链表
弹性（可扩容性）	😭	😀
增/删	😭	😀
查	😀	😭

【适用场景】

• 链表：表长难以预估、经常要增加/删除元素
• 顺序表：表长可预估、查询（搜索）操作较多

【答题模板】

Q：请描述顺序表和链表的……实现线性表时，用顺序表还是链表好？

答题套路

1. 顺序表和链表的逻辑结构都是线性结构，都属于线性表。
2. 但是二者的存储结构不同，顺序表采用顺序存储，（特点，带来的优点、缺点）；而链表采用链式存储，（特点，带来的优点、缺点）。
3. 由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时，……；当插入数据元素时，……；当删除数据元素时，……；当查找一个数据元素时……。