⇧
❮
❯
↻
🍀计算机基础🍀 9232字 47分钟

数据结构强化笔记（2）：线性表

作者

本文介绍一种最基础的线性结构——线性表。

Hyplus目录

1 线性表的逻辑结构

线性表（Linear List）：具有相同类型的n\ (n≥0)个数据元素的有限序列。当n=0时，称为空表。第一个元素为表头，最后一个为表尾。除表头外元素都有一个直接前驱，除表尾外元素都有一个直接后继。

特点：

  1. 表中元素数量有限。
  2. 元素具有顺序性，表中元素具有先后次序。
  3. 表中元素数据类型相同，每个元素占用相同相同大小的空间。

抽象数据类型定义：

ADT List {
    数据对象：a_i
    数据关系：(a_{i-1}, a_i)
    基本操作：
        initList(&L)    // 构造⼀个空的表L
        clearList(&L)   // 将表L置为空表
        isEmpty(L)  // 判空操作
        getLength(L)    // 返回L中数据元素个数（表⻓）
        getElem(L, i, &e)   // 按位查找，⽤e返回表L中第i个数据元素的值
        locateElem(L, e)    // 按值查找，返回表L中第⼀个与e相同元素在表L中的位置
        insertElem(&L, i, e)    // 插⼊操作，在表L中第i个位置之前插⼊新数据元素e
        deleteElem(&L, i)   // 删除操作，删除表L中第i个数据元素
        printList(L)    // 遍历并打印表L中的每个数据元素
        destroyList(&L) // 销毁操作
} ADT List

2 顺序表

顺序表（Sequence List）：一种顺序存储结构，用一组连续地址的存储单元依次存储线性表中的元素，使逻辑上相邻的数据在物理位置上也相邻。

地址计算：已知第⼀个数据元素的起始地址为\text{LOC}(A)，则

  • 第i个元素的起始地址：\text{LOC}(A) + (i-1)\times \text{sizeof}(\text{ElemType})
  • 可存储的最后一个元素的起始地址：\text{LOC}(A) + (\text{MAXSIZE}-1)\times \text{sizeof}(\text{ElemType})

特点：

  • 优点：
    1. 既能顺序存取⼜能随机存取（随机访问），即通过⾸地址和元素序号可用O(1)的时间复杂度按位查找元素
    2. 存储密度⾼（元素连续分布，故存储密度等于1），对于单个元素空间利⽤率⾼
  • 缺点：插⼊和删除需要移动⼤量元素，故对于需要反复插删的情形不适合⽤顺序表

2.1 顺序表的存储结构

静态分配存储：直接使⽤数组，容量事先固定，后期⽆法更改。有溢出的⻛险，当元素数量超出容量MAXSIZE时发生溢出

#define MAXSIZE 110

typedef struct SqList {
    ElemType data[MAXSIZE];
    int length;
} SqList;

在本文中，有时亦通过定义全局常量N等来表示数组长度：

const int N = 110, M = 11;

动态分配存储：利⽤指针，C语⾔中由函数malloc()分配⼀块连续存储空间作为当前容量，⽆需⼀次性分配⼤量空间，也⽆需担⼼发⽣溢出，空间占满后可进行重分配操作，重新分配⼀块更⼤的空间

typedef struct SqList {
    ElemType *data;
    int length;
    int maxsize;    // 顺序表的当前最大容量
}

/* 重分配顺序表容量为n（n >= 当前表⻓） */
bool resize(SqList &L, int n) {
    if (n < L.length) return false;

    ElemType *temp = (ElemType*) malloc(n * sizeof ElemType)
    if (!temp) return false;

    for (int i = 0; i < L.length; i++)
        temp[i] = L.data[i];

    free(L.data);
    L.data = temp;
    L.maxsize = n;
    return true;
}

2.2 操作性能分析

设顺序表的长度为n，数据从下标\text{0}位置开始存储：

  1. 按位查找：顺序表支持随机存取，故T(n)=O(1)
  2. 按值查找：有效查找范围为[0,n-1]（共n个合法查找位置）
    • 最好情况：查找元素在表头，仅需比较\text{1}次，T_{\text{best}}(n)=O(1)
    • 最坏情况：查找元素在表尾或不存在（查找失败），需比较n次，T_{\text{worst}}(n)=O(n)
    • 平均情况：在第i \in [0,n-1]个位置上查找的概率p_i=\dfrac{1}{n}，则共需比较\dfrac{(n+1)n}{2}次，故平均查找长度\text{ASL}=\dfrac{n+1}{2}，T_{\text{avg}}(n)=O(n)
    • 若顺序表有序，则还可使用折半查找，T(n)=O(\log_2 n)
  3. 插入：有效插入范围为[0,n]（不溢出；包括表尾之后的位置，共n+1个合法插入位置）
    • 最好情况：在表尾之后插入，无需后移元素，T_{\text{best}}(n)=O(1)
    • 最坏情况：在表头插入，所有元素均需后移\text{1}位（共后移n次），T_{\text{worst}}(n)=O(n)
    • 平均情况：在第i个位置上插入的概率p_i=\dfrac1{n+1}，从表头到表尾之后，各情况分别需后移n,n-1,\cdots,1,0次，则共需比较\dfrac{n(n+1)}{2}次，故平均后移次数为\dfrac{n}2，T_{\text{avg}}(n)=O(n)
  4. 删除：有效删除范围为[0,n-1]（共n个合法删除位置）
    • 最好情况：删除表尾元素，无需后移元素，T_{\text{best}}(n)=O(1)
    • 最坏情况：删除表头元素，除表头外均需后移\text{1}位（共后移n-1次），T_{\text{worst}}(n)=O(n)
    • 平均情况：删除第第i个位置上插入的概率p_i=\dfrac1{n}，从表头到表尾，各情况分别需后移n-1,n-2,\cdots,1次，则共需比较\dfrac{n(n-1)}{2}次，故平均后移次数为\dfrac{n-1}{2}，T_{\text{avg}}(n)=O(n)

由此可⻅，顺序表在最后进⾏插⼊删除操作效率依旧很⾼，与链表持平

3 单链表

单链表（Single Linked List）：由⼀组任意的存储结点存储元素，每个结点还存储指向后继结点的指针，因此相⽐顺序存储结构能更⽅便地表示各种逻辑结构

特点：

  • 优点：
    1. 与顺序表完全相反，进⾏插⼊和删除运算操作⽆需移动元素，只需改变指针，T(n)=O(1)
    2. ⽆需提前分配⼤量连续空间，故当难以估计线性表的⻓度或存储规模时，宜采⽤链表
  • 缺点：
    1. 不⽀持随机访问，只能进⾏顺序存取
    2. 存储密度低（存储密度⼩于1），且额外消耗空间存放指针

注：链表结点内存储单元地址⼀定连续，相邻结点存储空间不⼀定连续

3.1 单链表的存储结构

单链表的结构体如下所示：

typedef struct LNode {
    ElemType data;
    struct LNode *next; // 后继指针
} LNode, *LinkList;

特殊结构单元：

  • 头结点：在第⼀个元素结点（开始结点）前附加的结点，使头指针指向它。可不记录信息（或记录表⻓），指针域指向开始结点
  • 头指针：指向链表第⼀个结点的指针，通常⽤它来指代整个链表。当有头结点时指向头结点，⽆头结点时指向开始结点

根据有无头结点，单链表可分为两类：

  1. 带头链表：表空状态为L->next == NULL

  1. 无头链表：表空状态为L == NULL

3.2 链表基本操作

插⼊结点：将结点s插⼊单链表中结点p之后（或⽆头链表在表头插⼊）

  • 插入节点时需保证不断链，故将更改p的后继指针（或无头的头指针）操作放到最后
  • 对于带头链表，在表头或表中插入操作一致： 
    /* 将结点s插⼊带头单链表L中结点p之后（p可为头结点L） */
s->next = p->next;
p->next = s;
  • 对于⽆头链表，需特判在表头插⼊的情况： 
    /* 1° 将结点s插⼊⽆头单链表L的表头 */
s->next = L;
L = s;
/* 2˚ 将结点s插⼊⽆头单链表L中结点p之后（同带头情况） */
s->next = p->next;
p->next = s;

删除结点：删除结点p的后继结点（或⽆头链表删除表头）

  • 让⼀个指针指向待删结点，p的后继指针（或⽆头的头指针）指向待删结点的后继即可
  • 注意！最后使⽤函数free()释放结点空间（C++中为delete关键字）
  • 对于带头链表，在表头或表中删除操作⼀致： 
    /* 删除带头链表L中结点p的后继结点 */
q = p->next;
p->next = q->next;
free(q);
  • 对于⽆头链表，需特判在表头删除的情况： 
    /* 1˚ 删除⽆头链表L的表头结点 */
p = L;
L = p->next;
/* 2˚ 删除⽆头链表L中结点p的后继结点（同带头情况） */
q = p->next;
p->next = q->next;
free(q);

建⽴链表：根据元素的存放顺序，存在两种建表方法，都极为重要

  1. 尾插法：元素存放顺序与输⼊顺序相同。需要⼀个总是指向表尾的尾指针r辅助
    • 建⽴带头链表，操作全程统⼀： 
      LNode *r = L->next;
/* 尾插建⽴带头链表【局部操作】 */
s->next = r->next;
r = s;
/* 建表结束后将尾结点r的后继指针置空 */
r->next = NULL;
    • 建⽴⽆头链表，需特判初次插⼊空表的情况： 
      LNode *r = NULL;
/* 尾插建⽴⽆头链表【局部操作】 */
if (!L) s->next = NULL;
else s->next = r->next;
r = s;
/* 将尾结点r的后继指针置空（此前已置空，故可不写这句） */
r->next = NULL;
  2. 头插法：元素存放顺序与输⼊顺序相反。始终在表头执⾏添加元素，故⽆需额外指针辅助。
    • 建立带头链表： 
      s->next = L->next;
L->next = s;
    • 建立无头链表： 
      s->next = L;
L = s;

3.3 操作性能分析

  1. 按位插⼊/删除结点：仅需修改指针即可，T(n)=O(1)
    • 顺序表在表尾插⼊的时间复杂度同样为O(1)
  2. 建⽴链表：相当于对⼀个空链表执⾏n次插⼊操作，T(n)=O(n)
    • 建⽴有序单链表的时间复杂度为O(n^2)
  3. 按位或按值查找结点：遍历单链表的操作与顺序表类似（实质都是顺序查找），T_{\text{avg}}(n)=O(n)
  4. 按值、按给定序号插⼊/删除结点：插⼊/删除操作本身时间消耗仅为O(1)，但每次操作需从头遍历查找结点，故T(n)=O(n)

【例】给定有n个元素的⼀维数组，建⽴⼀个有序单链表的最低时间复杂度是？

【解】O(n \log_2 n)。将数组排序的最好时间复杂度为O(n \log_2 n)，建⽴链表的时间复杂度为O(n)，抓⼤头得总的时间复杂度为O(n \log_2 n)。

4 其他链表结构

双链表为重点，其他了解为主。

4.1 双链表

双链表（Double Linked List）在单链表的基础上额外增加了⼀个指向前驱结点的指针域，因⽽实现了双⽅向遍历整个表。其他各种操作都类似单链表。

typedef struct DLNode {
    ElemType data;
    struct DLNode *prior;   // 前驱指针
    struct DLNode *next;    // 后继指针
} DLNode, *DLinkList;

操作（以带头双链表为例，⽆头双链表与此类似）：

  1. 插⼊结点：将结点s插⼊双链表中结点p之后
    • 类似单链表的插⼊操作，注意被插结点的后继指针p->next必须在待插结点s已完成双向链接p的后继结点后才能修改，否则会断链 
      /* 将结点s插⼊双链表中结点p之后 */
s->next = p->next;  // 1
p->next->prior = s; // 2
p->next = s;        // 3（该操作3必须放在操作1、2后进⾏，与操作4可互换，否则会发⽣断链）
s->prior = p;       // 4

  1. 删除结点：删除结点p的后继结点
    • 指针q指向该待删除结点（p的后继），让p的后继指针指向q的后继，q的后继结点的前驱指针q->next->prior指向p，最后释放结点空间 
      /* 删除双链表中结点p的后继结点 */
q = p->next;
q->next->prior = p;
p->next = q->next;
free(q);

4.2 循环链表

循环单链表（Circular Single Linked List）：在单链表的基础上，规定表尾的后继指针指向第⼀个结点（有头结点时指向头结点，⽆头结点时指向第⼀个元素结点）

循环双链表（Circular Double Linked List）：在双链表的基础上，规定表尾的后继指针指向第⼀个结点（同循环单链表），第⼀个结点的前驱指针指向表尾

常见考点：

  1. 当head->next->next == head时，循环单链表的长度为1或2（假设表非空）
    • 带头情况：有1个元素结点，故⻓度为1（长度不计入头结点）
    • ⽆头情况：有2个元素结点，故⻓度为2（画图即可知）
  2. 循环单链表中设置尾指针⽐设置头指针好吗？
    【解】循环单链表中设置尾指针要优于头指针，更⽅便查找链表的开始结点和终端结点，时间复杂度都为O(1)；⽽头指针查找终端结点则需遍历整个表，时间复杂度为O(n)
  3. 循环双链表中设置尾指针与设置头指针⼀样好吗？
    【解】循环双链表中⽆论设置尾指针还是头指针，查找开始结点和终端结点都⼗分⽅便，时间复杂度都为O(1)

4.3 静态链表

静态链表（Static Linked List）借助数组来表述线性表的链式存储，和顺序表⼀样，需预先分配⼀⽚连续的存储空间。和通常的动态链表⼀样，（逻辑上）不⽀持随机存储。插⼊/删除操作只需修改指针域（即数组下标，称为游标），⽆需移动元素

#define MAXSIZE 110

struct StaticList {
    ElemType data;
    int next;   // 存储后继结点的数组下标
} L[MAXSIZE];

受益于数组本身的随机存取特性，在算法题中常用于模拟各类容器。

A 线性表编程练习

本文所有编程练习题均来自历年统考或自命题试题真题，难度由易至难，但远易于各类算法考试竞赛，只适用于考研备考或自学。专业算法考试竞赛辅导请参阅PAT等算法题解。

A.1 顺序表基本操作

【例1】将顺序表L中的元素逆置，要求算法的空间复杂度为O(1)

void reverseList(SqList &L) {
    for (int i = 0; i < L.length / 2; i++) {
        int tmp = L.data[i];
        L.data[i] = L.data[L.length - 1 - i];
        L.data[L.length - 1 - i] = tmp;
    }
}

【例2】将顺序表L的第i个位置插入新元素e。若i的输入不合法则返回false，表示插入失败；否则将第i个元素及以后所有元素依次后移1位，腾出空位插入新元素e，顺序表表长加1，插入成功，返回true

bool insertElem(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;    // 判i不合法
    if (L.length == MAXSIZE) return false;  // 判表满

    for (int j = L.length - 1; j >= i - 1; j--)
        L.data[j + 1] = L.data[j];
    L.data[i - 1] = e;  // 第i个位置对应于下标i-1
    L.length++;
    return true;
}

【例3】已知一个顺序表L，其元素递增有序排列。设计一个算法，在插入元素x（int型）后保持该顺序表依旧递增有序排列（假设插入操作一定成功），插入后返回插入元素所在位置

int insertElem(SqList &L, int x) {  // 表L递增有序
    int i;  // i记录元素x的插⼊位置（下标）
    for (i = 0; i < L.length; i++)
        if (L.data[i] > x)  // x应当插在第⼀个⼤于它的元素处
            break;
    for (int j = L.length; j >= i + 1; j--)
        L.data[j] = L.data[j - 1];
    L.data[i] = x;
    L.length++;
    return i;
}

【例4】删除顺序表L中第i个位置的元素。若i的输入不合法则返回false；否则将被删元素赋给引用变量e，并将第i+1个元素及其后的所有元素依次前移一位，返回true

bool deleteElem(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) return false;    // 判i不合法
    e = L.data[i - 1];  // 第i个位置对应下标i-1
    for (int j = i - 1; j < L.length - 1; j++)
        L.data[j] = L.data[j + 1];
    L.length--;
    return true;
}

【例5】从顺序表L中删除最小值元素并由函数返回被删元素的值（假设L存在最小值且唯一）

int deleteMin(SqList &L) {
    int min = L.data[0], minPos = 0;    // 记录最小值及其下标（初始为表头）
    for (int i = 1; i < L.length; i++)  // 遍历表，查找最小值
        if (L.data[i] < min) {
            min = L.data[i];
            minPos = i;
        }
    for (int j = pos; j < L.length - 1; j++)    // 删除最小值
        L.data[j] = L.data[j + 1];
    L.length--;
    return min;
}

【例6】删除顺序表L中所有值为x的数据元素，要求时间复杂度为O(n)、空间复杂度为O(1)

/* 法1：跨步前移 */
void deleteElem1(SqList &L, int x) {
    int cnt = 0;    // 记录要删除元素的个数
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == x) cnt++   // 若值为x，则要删元素个数+1
        else L.data[i - cnt] = L.data[i];   // 若不需删除，则前移cnt个位置
    }
    L.length -= cnt;    // 更新表长，减去删除元素的个数
}
/* 法2：重建新表 */
void deleteElem2(SqList &L, int x) {
    int len = 0;    // 记录保留元素的表尾位置（新表尾/新表长）
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x) // 判断是否保留该元素
            L.data[len++] = L.data[i];  // 是则去新表尾，随后新表长+1
    L.length = len; // 更新表长为新表长
}

【例7】从顺序表中删除值在定值s与t之间（含两端，要求s < t）的所有元素。若s、t不合理或表空则返回false；执行成功则返回true

/* 法1：跨步前移 */
bool deleteElem1(SqList &L, int s, int t) {
    if (s >= t || L.length == 0) return false;

    int cnt = 0;    // 记录要删除元素的个数（同第6题法1）
    for (int i = 0; i < L.length; i++) {
        if (s <= L.data[i] && L.data[i] <= t) cnt++;
        else L.data[i - cnt] = L.data[i];
    }
    L.length -= cnt;
    return true;
}
/* 法2：重建新表 */
bool deleteElem2(SqList &L, int s, int t) {
    if (s >= t || L.length == 0) return false;

    int len = 0;    // 记录保留元素的表尾位置（新表尾/新表长，同第6题法2）
    for (int i = 0; i < L.length; i++)
        if (L.data[i] < s || L.data[i] > t)
            L.data[len++] = L.data[i];
    L.length = len;
    return true;
}

【例8】从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不同

void deleteSame(SqList &L) {    // L为有序表
    int len = 1;    // 记录保留元素的表尾位置（新表尾/新表长，类似第6题法2）
    for (int i = 1; i < L.length; i++)
        if (L.data[i] != L.data[i - 1])
            L.data[len++] = L.data[i];
    L.length = len;
}

【例9】从有序顺序表中删除值在定值s与t之间（含两端，要求s < t）的所有元素。若s、t不合理或表空，或无元素可删，则返回false；执行成功则返回true

bool deleteSorted(SqList &L, int s, int t) {    // L为有序表
    if (s >= t || L.length == 0) return false;

    int l, r;   // l, r：分别记录待删元素的起始位置和结束位置
    for (l = 0; l < L.length && L.data[l] < s; l++);    // 找起始位置
    if (l == L.length) return false;    // 所有元素均小于s则无元素可删，直接返回false
    for (r = l; r < L.length && L.data[r] <= t; r++);   // 找结束位置

    for (; r < L.length ; l++, r++) // 将结束位置后的保留元素前移、覆盖待删元素
        L.data[l] = L.data[r];
    L.length = l;   // 更新表长，此时表长即为l
    return true;
}

【例10】将两个非递减顺序表A和B合并为新的非递减顺序表C（使用动态分配存储），若合并成功则返回true，否则返回false

bool mergeList(SqList A, SqList B, SqList &C) {
    if (A.length + B.length > C.maxsize) return false;  // 判定C存储空间能否容纳A和B

    int i = 0, j = 0, k = 0;    // i、j、k分别遍历A、B、C
    while (i < A.length && j < B.length) {  // 挑选A、B当前所指较小值尾插C
        if (A.data[i] <= B.data[j]) C.data[k++] = A.data[i++];
        else C.data[k++] = B.data[j++];
    }
    while (i < A.length) C.data[k++] = A.data[i++];
    while (j < B.length) C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}

A.2 单链表基本操作

以下若⽆特别注明⽆头链表，皆默认链表带头结点

【例1】有一个带头结点的单链表L，查找其第i个结点，若存在则返回指向该结点的指针，否则返回NULL

LNode *findElemById(LinkList L, int i) {
    if (i < 1) return NULL; // 检查i的合法性
    int cnt = 1;    // 计数器（从1开始，表示第1个结点）
    LNode *p = L->next; // 遍历指针
    while (p && cnt < i) {
        p = p->next;
        cnt++;
    }
    return p;
}

【例2】有一个带头结点的单链表L，查找其第1个值为e的结点，若存在则返回指向该结点的指针，否则返回NULL

LNode *findElemByValue(LinkList L, int e) {
    LNode *p = L->next;
    while (p && p->data != e) p = p->next;
    return p;
}

【例3】使用头插法建立带头结点的单链表L，输入-1表示结束，结果返回建立的单链表

LinkList createListHeadInsert(LinkList &L) {
    L = (LinkList) malloc(sizeof LNode);    // 创建头结点
    L->next = NULL; // 初始化头结点，置头结点后继为空
    int x;
    scanf("%d", &x);
    while (x != -1) {
        LNode *s = (LNode*) malloc(sizeof LNode);
        s->data = x;
        s->next = L->next;  // 头插核心
        L->next = s;    // 头插核心
        scanf("%d", &x);
    }
    return L;
}

【例3改】使用尾插法建立带头结点的单链表L，输入-1表示结束，结果返回建立的单链表

LinkList createListTailInsert(LinkList &L) {
    L = (LinkList) malloc(sizeof LNode);    // 创建头结点
    // L->next = NULL;  // 尾插可以不先置头结点后继为空
    LNode *r = L;   // 尾插核心：尾指针
    int x;
    scanf("%d", &x);
    while (x != -1) {
        LNode *s = (LNode*) malloc(sizeof LNode);
        s->data = x;
        r->next = s;    // 尾插核心
        r = s;  // 尾插核心，更新尾指针位置
        scanf("%d", &x);
    }
    r->next = NULL; // 尾插核心：建表结束后置尾指针后继为空
    return L;
}

【例4】将带头结点的单链表L就地逆置（就地：空间复杂度为O(1)）

void reverse(LinkList &L) {
    LNode *p = L->next, *r; // p：遍历指针；r：防断链指针，防止p断链
    L->next = NULL; // 断头—分离出L作为空表的头结点
    while (p) {
        r = p->next;    // 防断链指针指向下一个需要遍历的结点
        p->next = L->next;  // 头插核心
        L->next = p;    // 头插核心
        p = r;
    }
}

【例5】将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得表A中含有原表中序号为奇数的元素，表B中含有原表中序号为偶数的元素，且保持相对顺序不变，最后返回B表

LinkList separateAB(LinkList &A) {
    LinkList B = (LinkList) malloc(sizeof LNode);   // 创建B表头结点
    LNode *p = A->next, *ra = A, *rb = B;   // p：遍历指针；ra，rb：表A和表B的尾指针（尾插法）
//  A->next = NULL; // 表A断头（也可不断头）
    while (p) { // 遍历原表
        ra->next = p;   // 先插表A（奇数——第1，3，5...个）
        ra = p;
        p = p->next;
        if (p) {    // 防止最后一轮循环因只有一个结点而报错
            rb->next = p;   // 再插表B（偶数—第2，4，6...个）
            rb = p;
            p = p->next;
        }
    }
    ra->next = NULL;    // 表A尾结点后继置空
    rb->next = NULL;    // 表B尾结点后继置空
}

【例6】将一个带头结点的单链表A = \{a_1,b_1,a_2,b_2,...,a_n,b_n\}分解为两个带头结点的单链表A和B，使得A = \{a_1,a_2,...,a_n\},\ B = \{b_n,...,b_2,b_1\}

LinkList separateABReversed(LinkList &A) {
    LinkList B = (LinkList) malloc(sizeof LNode);   // 创建B表头结点
    B->next = NULL; // 初始化头结点，置头结点后继为空
    LNode *p = A->next, *r = A, *q; // p：遍历指针；r：表A尾指针；q：表B防断链指针
//  A->next = NULL; // 表A断头（也可不断头）
    while (p) { // 遍历原表
        r->next = p;    // 先插表A（尾插）
        r = p;
        p = p->next;
        if (p) {    // 防止最后一轮循环因只有一个结点而报错
            q = p->next;    // 防止使用头插出现断链
            p->next = B->next;  // 再插表B（头插）
            B->next = p;
            p = q;
        }
    }
    r->next = NULL; // 表A尾结点后继置空
    return B;
}

【例7】有两个按元素值递增次序排列的单链表，将两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表

LinkList mergeList(LinkList &A, LinkList &B) {
    LNode *p = A->next, *q = B->next, *r;   // p, q：A、B的遍历指针；r：防断链指针
    A->next = NULL; // 使用头插法前先断头
    while (p && q) {    // 挑选p、q当前所指较小值头插A
        if (p->data <= q->data) {
            r = p->next;
            p->next = A->next;
            A->next = p;
            p = r;
        } else {
            r = q->next;
            q->next = A->next;
            A->next = q;
            q = r;
        }
    }
    if (q) p = q;   // p、q链表中最多只有一条会有剩余
    while (p) { // 将剩余的链表结点依次头插A
        r = p->next;
        p->next = A->next;
        A->next = p;
        p = r;
    }
    free(B);    // 最后释放B头结点空间
    return A;
}

【例8】在带头结点的单链表L中删除一个最小值结点

void deleteMin(LinkList &L) {
        LNode *pre = L, *p = L->next;   // 遍历指针p及其前驱指针pre
        LNode *minpre = pre, *minp = p; // 最小值结点记录指针minp及其前驱指针minpre
        while (p) {
            if (p->data < minp->data) {
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        minpre->next = minp->next;  // 删除最小值结点
        free(minp);
}

【例8改】在无头结点的单链表L中删除一个最小值结点

/* 法1：特判第一个数据结点（开始结点） */
void deleteMinNoHead1(LinkList &L) {    // 无头链表的头指针L指向开始结点
        LNode *pre, *p = L;
        LNode *minpre, *minp = p;
        while (p) {
            if (p->data < minp->data) {
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        if (minp == L) {    // 特判开始结点：更新头指针位置
            L = L->next;
            free(minp);
        } else {    // 非开始结点则直接删除
            minpre->next = minp->next;
            free(minp);
        }
}
/* 法2：自行补上头结点，完成操作后再删除所创建的头结点 */
void deleteMinNoHead2(LinkList &L) {
        LinkList head = (LinkList) malloc(sizeof LNode);    // 创建头结点
        head->next = L; // 将原始链表链接在所创建的头结点之后，后续操作同带头情况
        LNode *pre = head, *p = head->next;
        LNode *minpre = pre, *minp = p;
        while (p) {
            if (p->data < minp->data) {
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        minpre->next = minp->next;
        free(minp);
        L = head->next; // 更新头指针位置
        free(head); // 删除所创建的头结点
}

【例9】在带头结点的无序单链表L中，删除所有值为x的结点，并释放其空间（假设值为x的结点不唯一）

void deleteElem(LinkList &L, int x) {
    LNode *pre = L, *p = L->next;   // 遍历指针p及其前驱指针pre
    while (p) {
        if (p->data == x) {
            pre->next = p->next;    // 当场删除值为x的结点
            free(p);
            p = pre->next;  // 遍历指针顺移至下一位置
        } else {
            pre = p;
            p = p->next;
        }
    }
}

【例10】在带头结点的无序单链表L中，删除所有值介于定值s与t之间（含两端，且s < t）的结点，参数不合法则返回false，否则返回true。

bool deleteElem(LinkList &L, int s, int t) {
    if (s >= t) return false;
    LNode *pre = L, *p = L->next;
    while (p) {
        if (s <= p->data && p->data <= t) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
    return true;
}

【例11】有一个带头结点的非递减有序单链表L，设计算法删除表L中数值重复的结点，使表中结点值不再重复（【例】\{7,10,10,23,55,55,90\}变为\{7,10,23,55,90\}）

void deleteSame(LinkList &L) {
    if (!L->next) return;   // 空表无需处理，直接返回
    LNode *pre = L->next, *p = pre->next;   // 这里p从第2个数据结点开始遍历，pre指向第1个数据结点
    while (p) {
        if (p->data == pre->data) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

【例12】有两个带头结点的升序单链表A和B，设计算法从A和B中找出值相同的结点并生成一个新的单链表C，要求不破坏两条链表中的结点

LinkList createCommon(LinkList A, LinkList B) {
    LNode *p = A->next, *q = B->next;   // p，q：表A和B的遍历指针
    LinkList C = (LinkList) malloc(sizeof LNode);   // 创建C表头结点
    LNode *r = C;   // r：表C的尾指针
    while (p && q) {    // 谁小谁后移，相同即新建结点尾插C
        if (p->data < q->data) p = p->next;
        else if (p->data > q->data) q = q->next;
        else {
            LNode *s = (LNode*) malloc(sizeof LNode);
            s->data = p->data;
            r->next = s;    // 尾插核心
            r = s;  // 尾插核心
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL; // 插入结束后置C尾结点后继为空
    return C;
}

【例13】有两个带头结点的升序单链表A和B，设计算法求两个表的交集，并存放于表A中，其他结点均释放空间

LinkList unionAB(LinkList &A, LinkList &B) {
    LNode *p = A->next, *q = B->next;   // p，q：表A、B的遍历指针
    LNode *r = A, *u;   // r：表A的尾指针；u：释放无用结点所需的辅助指针
    while (p && q) {    // 谁小谁被删、后移，相同即找到一个交集结点
        if (p->data < q->data) {
            u = p;
            p = p->next;
            free(u);
        } else if (p->data > q->data) {
            u = q;
            q = q->next;
            free(u);
        } else {
            r->next = p;    // 找到交集结点，将其中一个尾插
            r = p;
            p = p->next;
            u = q;  // 删除另一个交集结点
            q = q->next;
            free(u);
        }
    }
    while (p) { // 若原表A有剩余则全部删除释放空间
        u = p;
        p = p->next;
        free(u);
    }
    while (q) { // 若原表B有剩余则全部删除释放空间
        u = q;
        q = q->next;
        free(q);
    }
    r->next = NULL; // 最后将A尾指针指针域置空
    free(B);    // 释放B表头结点空间
    return A;
}

【例14】有一个带头结点的单链表，其头指针为head，编写算法按递增次序输出表中各结点的值，并释放所有结点所占空间（不允许使用数组作为辅助空间）

void printMinAndClear(LinkList &head) {
    while (head->next) {    // 循环寻找最小值，直至所有结点都被找到、输出
        LNode *pre = head, *p = head->next;
        LNode *minpre = pre, *minp = p;
        while (p) {
            if (p->data < minp->data) {
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        printf("%d ", minp->data);  // 输出本轮最小值结点数据
        minpre->next = minp->next;  // 删除本轮最小值结点
        free(minp);
    }
    free(head); // 最后释放头结点空间
}

【例15】有两个整数序列A和B分别存在两个单链表中，设计算法判断B是否是A的连续子序列（简单模式匹配）

bool pattern(LinkList A, LinkList B) {
    LNode *p = A->next, *q = A->next;
    LNode *pre = A->next;   // 回溯指针，记录此次比较的开始元素位置
    while (p && q) {
        if (p->data == q->data) {   // 当前两数据域相同则继续遍历
            p = p->next;
            q = q->next;
        } else {    // 当前两数据域不同则此次匹配失败，指针回溯
            pre = pre->next;    // p借助pre回溯至下一次比较的开始位置
            p = pre;
            q = B->next;    // q重新指向表B（相当于模式串）开始结点
        }
    }
    if (!q) return true;    // q遍历结束则表面模式匹配成功
    return false;   // 否则匹配失败
}

A.3 其他链表操作

【例1】设计算法判断单链表L是否有环

bool isLoop(LinkList L) {
    LNode *fast = L, *slow = L; // 快、慢指针
    while (fast && fast->next) {    // 每轮循环需考虑之后两步非空（fast一次走两步）
        slow = slow->next;  // 慢指针每次遍历走一步
        fast = fast->next->next;    // 快指针每次遍历走两步
        if (fast == slow) return true;  // 快指针遇见慢指针则说明有环
    }
    return false;   // 若循环结束则说明无环
}

【例2】有两个无头结点的循环单链表，链表头指针分别为h1和h2，设计算法将表h2链接到h1之后，要求链接后的链表仍循环

LinkList linkCircularList(LinkList &h1, LinkList &h2) {
    LNode *p = h1, *q = h2; // 遍历指针
    while (p->next != h1) p = p->next;  // 让p指向表h1的尾结点
    while (q->next != h2) q = q->next;  // 让q指向表h2的尾结点

    p->next = h2;   // 表h1的尾结点链接在h2的开始结点前
    q->next = h1;   // 表h2的尾结点链接在h1的开始结点前
    return h1;
}

【例3】有一个带头结点的循环单链表L，结点值均为正整数。设计算法反复找出表中最小值结点并输出，然后将该结点删除，直至表空，再删除头结点

void printMinAndClearCircular(LinkList &L) {
    while (L->next != L) {
        LNode *pre = L, *p = L->next;
        LNode *minpre = pre, *minp = p;
        while (p != L) {
            if (p->data < minp->data) {
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        printf("%d ", minp->data);  // 输出本轮最小值结点数据
        minpre->next = minp->next;  // 删除本轮最小值结点
        free(minp);
    }
    free(L);    // 删除头结点
}

【例4】判断带头结点的循环双链表L是否对称

bool isSymmetricalCircular(DLinkList L) {
    DLNode *p = L->next, *q = L->prior; // 两遍历指针以头结点为中心分别遍历两侧
    while (p != q && q->next != p) {    // 分别对应结点数为奇数、偶数的情况，画图理解
        if (p->data == q->data) {   // 数据域相同则继续遍历
            p = p->next;
            q = q->next;
        } else return false;    // 数据域不同则表明不对称
    }
    return true;    // 跳出循环则表明对称
}

【例5】有一个带头结点的单链表L，元素类型为字符型，判断该链表的全部n个字符是否中心对称（【例】xyx、xyyx都是中心对称）【使用辅助栈】

bool isSymmetrical(LinkList L, int n) {
    Stack S;    // 辅助栈（最大容量至少为n / 2）
    initStack(S);
    LNode *p = L->next; // 遍历指针
    for (int i = 0; i < n / 2; i++) {   // 对称轴左边字符依次入栈
        S.data[++S.top] = p->data;
        p = p->next;
    }
    if (n % 2 == 1) p = p->next;    // 关键：若字符数为奇数，则p后移一步（因为最中心字符无需考虑）
    while (p) { // 对称轴字符一次与栈顶字符遍历
        if (p->data == S.data[S.top]) { // p所指与栈顶字符相等则继续比对下一组字符
            S.top--;
            p = p->next;
        } else return false;    // 不相等则表面不对称，直接返回false
    }
    return true;    // 跳出循环则表面对称，返回true
}

B 链式前向星*

实际应用中常用链式前向星（静态链表的一种）模拟链表的定义、遍历与增删改查（对树、图同样可使用该思路存储）。要想在各类考试竞赛中快速解题，应熟练掌握该种写法。

  1. 无头单链表：元素结点地址idx从0开始分配，表尾空指针记为-1。

单链表

int head, e[N], ne[N], idx;
// head为无头单链表的头指针
// e[i]存储结点i的值
// ne[i]指向结点i的后继
// idx为分配给结点的"地址"

/* 初始化 */
void init() {
    head = -1;  // 头指针初始为-1
    idx = 0;    // 这里设定第1个插入的结点在0号下标
}

/* 头插一个数x */
void insertHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;   // 后继为开始结点
}

/* 在结点k之后插入一个数x */
void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;  // 后继为k的后继
}

/* 删除头结点（需保证链表非空） */
void removeHead() {
    head = ne[head];
}

/* 删除结点k之后的结点 */
void remove(int k) {
    ne[k] = ne[ne[k]]
}

/* 遍历整条链表 */
for (int i = head; ~i; i = ne[i]) {
    int u = e[i];
    // ...
}
  1. 带头循环双链表：规定0为头结点/左端点，只有后继；1为尾结点/右端点，只有前驱。元素结点地址idx从2开始分配，每个元素结点都不含空指针。常用于实现双端队列。

对于删除操作，为避免繁杂通常不直接将结点移出链表，而是通过开bool数组st[]标记结点来实现逻辑删除，st[i]记录结点i是否被删除。
为避免额外时间开销，本文大部分数据结构均采用此删除方法。

双链表

int e[N], l[N], r[N], idx;
// l[i]、r[i]分别指向结点i的前驱、后继
// 特殊规定：0为头结点/左端点，只有后继；1为尾结点/右端点，只有前驱

/* 初始化 */
void init() {
    r[0] = 1, l[1] = 0; // 左右端点分别指向对方
    idx = 2;    // 第1个结点从下标2开始存储
}

/* 在结点k的右边插入一个数x */
void insertR(int k, int x) {
    e[idx] = x;
    l[idx] = k;     // 前驱为k
    r[idx] = r[k];      // 后继为k的后继
    l[r[k]] = idx;      // k后继的前驱、k的后继（须最后修改）即为该结点
    r[k] = idx++;
}

/* 在结点k的左边插入一个数x */
void insertL(int k, int x) {
    insert_r(l[k], x);  // 等价于在结点k的前驱（l[k]）的右边插入
}

/* 删除结点k */
void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

/* 遍历整条链表 */
for (int i = r[0]; i != 1; i = r[i]) {
    int u = e[i];
    // ...
}

发表评论