01 线性表及其实现

01-线性表及其实现

定义

线性表（Linear List）：由同类型数据元素构成有序序列的线性结构

• 长度：表中元素个数
• 空表：没有元素的线性表
• 表起始位置称为表头，表结束位置称为表尾

ADT 描述

类型名：线性表（List）

数据对象集：线性表是 \(n(\geqslant 0)\) 个元素构成的有序序列 \((a_1, a_2, \ldots, a_n)\)

操作集：线性表 \(\text{L}\in \text{List}\)，整数 \(i\) 表示位置，元素 \(\text{X}\in \text{ElementType}\)，线性表基本操作主要有：

1. List MakeEmpty() 初始化一个空线性表 \(\text{L}\)
2. ElementType FindKth(int K, List L) 根据索引 \(\text{K}\)，返回相应元素
3. int Find(ElementType X, List L) 在线性表 \(\text{L}\) 中查找 \(\text{X}\) 的第一次出现位置
4. void Insert(ElementType X, int i, List L) 在索引 \(i\) 处插入一个新元素 \(\text{X}\)
5. void Delete(int i, List L) 删除指定索引 \(i\) 的元素
6. int Length(List L) 返回线性表 \(\text{L}\) 的长度 \(n\)

const int kMaxSize = (int)1e4;
struct LNode {
    ElementType data[kMaxSize]; // 储存的数据
    int last;                   // 最后一个元素的下标
};

顺序存储实现

利用数组的连续存储空间存放线性表的各个元素

查找

按索引查找的方式实现起来十分简单，不多解释。

按值查找的代码有很巧妙的实现：

/* 在线性表中查找 X 第一次出现的位置索引 */
Index find(ElementType X, List ptrL) {
    int i = 0;
    while (i <= ptrL->last && ptrL->data[i] != X)
        i++;
    if (i > ptrL->last)
        return -1; // 没找到返回 -1
    return i;      // 找到了返回位置索引
}

实现的关键点在于，在循环外初始化一个计数变量。这么做的目的是能够记录下循环终止时的状态，从而判断查找的结果如何。

如上例。根据循环条件，终止时，只有两种情况：

1. i > ptrL->last ，代表直到最后都没有查找到该值出现的位置
2. ptrL->data[i] == X ，代表找到了值

因此，可以在循环结束后用条件语句来进行上面分支的处理。

代码实现

#include <iostream>
#include <cmath>

using ElementType = double;
using Index = int;

const int kMaxSize = (int)1e4; // 线性表最大长度

struct LNode {
    ElementType data[kMaxSize]; // 储存的数据
    int last;                   // 最后一个元素的下标
};

using List = LNode*;

/* 初始化一个空线性表 */
List makeEmpty() {
    List ptrL;
    ptrL = new LNode;
    ptrL->last = -1;
    return ptrL;
}

/* 根据索引 K 返回相应元素 */
ElementType findKth(Index K, List ptrL) {
    if (K < 0 || K > ptrL->last) {
        std::cout << "The position is invalid\n";
        return NAN; /* 对于 double 类型，返回 NaN 表示错误 */
    }
    return ptrL->data[K];
}

/* 在线性表中查找 X 第一次出现的位置索引 */
Index find(ElementType X, List ptrL) {
    int i = 0;
    while (i <= ptrL->last && ptrL->data[i] != X)
        i++;
    if (i > ptrL->last)
        return -1; // 没找到返回 -1
    return i;      // 找到了返回位置索引
}

/* 在下标 i 处插入 X 元素 */
bool insertByIndex(ElementType X, Index i, List ptrL) {
    if (ptrL->last == kMaxSize - 1) { /* 表空间已满 */
        std::cout << "The list is full\n";
        return false;
    }
    if (i < 0 || i > ptrL->last + 1) { /* 插入位置不合法 */
        std::cout << "The position is invalid\n";
        return false;
    }
    for (int j = ptrL->last; j >= i; --j) {
        ptrL->data[j + 1] = ptrL->data[j]; // a_i 到 a_n 向后移动一位
    }
    ptrL->data[i] = X; // 插入新元素
    ++ptrL->last;      // last 指向最后一个元素
    return true;
}

/* 删除指定下标 i 的元素 */
bool deleteByIndex(Index i, List ptrL) {
    if (i < 0 || i > ptrL->last) { /* 删除位置不合法 */
        std::cout << "The position is invalid\n";
        return false;
    }
    for (int j = i; j < ptrL->last; ++j) {
        ptrL->data[j] = ptrL->data[j + 1]; // a_{i+1} 到 a_n 向前移动一位
    }
    --ptrL->last; // last 指向最后一个元素
                  // 当删除数组最后一个元素之后，last=-1，代表为空表
    return true;
}

/* 返回线性表的长度 n */
int length(List ptrL) { return ptrL->last + 1; }

链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻，可以是分散存储的。

• 插入、删除不需要移动数据元素，只需要修改“链”

插入操作

在第 \(i-1(1 \leq i \leq n+1)\)个结点后插入一个值为 \(X\) 的新结点

1. 找到链表的第 \(i-1\) 个结点，用 p 指向；
2. 构造一个新结点，用 newNode 指向；
3. 修改指针，插入结点（p 之后插入新结点是 newNode）

p = findKth(i - 1, ptrL); // 找到第 i-1 个元素
newNode = new LNode; // 为新结点分配内存
newNode->data = X;
newNode->next = p->next;
p->next = newNode; // 新节点插入在 p 之后

删除操作

删除链表的第 \(i(1 \leq i \leq n)\) 个位置上的结点

1. 找到链表的第 \(i-1\) 个结点，用 p 指向
2. 用指针 del 指向要被删除的结点（p 的下一个结点）
3. 修改指针，删除 del 所指结点
4. 释放 del 所指结点的空间

p = findKth(i - 1, ptrL);           // 找到第 i-1 个元素
del = p->next;       // 需要删除的节点
p->next = del->next; // 删除第 i 个节点
delete del;          // 释放被删除节点的内存

代码实现

#include <iostream>

using ElementType = double; // 线性表中元素的数据类型
using List = struct LNode*; // 线性表类型定义

struct LNode {
    ElementType data; // 该节点的数据
    List next;        // 指向下一个元素的指针
};

/* 初始化一个空线性表 */
List makeEmpty() { return nullptr; }

/* 根据下标 K 返回相应元素 */
List findKth(int K, List ptrL) {
    List p = ptrL;
    int i = 0;
    while (p != nullptr && i < K) {
        p = p->next;
        ++i;
    }
    if (i == K)
        return p; /*  找到第K个元素，返回指针 */
    else
        return nullptr; /* 未找到，返回 nullptr */
    // 其实直接 return p; 也是等价的，不过可读性相对较差
}

/* 在线性表中查找 X 第一次出现的结点 */
List find(ElementType X, List ptrL) {
    List p = ptrL;
    while (p != nullptr && p->data != X) {
        p = p->next;
    }
    return p; /* 找到返回指针，未找到返回nullptr */
}

/* 在下标 i 的元素处插入 X 元素 */
List insert(ElementType X, int i, List ptrL) {
    List p, newNode;
    if (i == 0) {            /* 新节点插入在表头 */
        newNode = new LNode; // 为新结点分配内存
        newNode->data = X;
        newNode->next = ptrL;
        return newNode; // 返回新的表头指针
    }
    p = findKth(i - 1, ptrL); // 找到第 i-1 个元素
    if (p == nullptr) {       /* 第 i-1 个元素不存在 */
        std::cout << "the " << i << " is incorrect!\n";
        return ptrL; // 返回原表头指针
    } else {
        newNode = new LNode; // 为新结点分配内存
        newNode->data = X;
        newNode->next = p->next;
        p->next = newNode; // 新节点插入在 p 之后
        return ptrL;       // 返回原表头指针
    }
}

/* 删除指定下标 i 的元素 */
List deleteByIndex(int i, List ptrL) {
    List p, del;
    if (i == 0) { /* 需要删除的是表头节点 */
        del = ptrL;
        ptrL = ptrL->next; // 删除表头节点
        delete del;
        return ptrL; // 返回新的表头指针
    }
    p = findKth(i - 1, ptrL);                 // 找到第 i-1 个元素
    if (p == nullptr || p->next == nullptr) { /* 第 i-1 或第 i 个元素不存在 */
        std::cout << "the " << i << " is incorrect!\n";
        return nullptr; // 返回空指针表示删除失败
    } else {
        del = p->next;       // 需要删除的节点
        p->next = del->next; // 删除第 i 个节点
        delete del;          // 释放被删除节点的内存
        return ptrL;
    }
}

/* 返回线性表的长度 n */
int length(List ptrL) {
    int i = 0;
    List p = ptrL;
    while (p != nullptr) {
        ++i;
        p = p->next;
    }
    return i;
}

广义表与多重链表

广义表

广义表是线性表的推广。

在广义表中，n个元素不仅可以是单元素，也可以是另一个广义表。

using GList = struct GNode*;
using ElementType = double;
struct GNode {
    int tag; // 标志域，0表示顶点，1表示广义表
    union {  /* 子表指针域与单元素数据域共用存储空间 */
        ElementType data;
        GList sub_list;
    } URegion;
    GList next; // 指向下一个结点的指针
};

多重链表

链表中的结点可能同时隶属于多个链

• 结点指针域会有多个，如前面的例子包含了 Next 和 SubList 两个指针域
• 有多个指针域的链表不一定是多重链表，如双向链表

多重链表用途广泛，基本上树、图这种相对复杂的数据结构都可以用多重链表进行存储。

十字链表存储稀疏矩阵

二维数组表示稀疏矩阵会造成大量的存储空间浪费。

我们提出使用一种典型的多重链表——十字链表来存储稀疏矩阵

• 只存储非零元素项
  • 结点的数据域：行坐标 Row、列坐标 Col、数值 Value
• 每个节点通过两个指针域把同行、同列串起来
  • 行指针/向右指针 Right
  • 列指针/向下指针 Down

例如表示矩阵：

\[ A=\begin{bmatrix} 18 & 0 & 0 & 2 & 0 \\ 0 & 27 & 0 & 0 & 0 \\ 0 & 0 & 0 & -4 & 0 \\ 23 & -1 & 0 & 0 & 12 \end{bmatrix} \]

• 左上角的 Term 结点储存的是行、列以及非零元素的数量
• 第 \(i\) 行、第 \(i\) 列的 Head 结点其实是同一个结点。左边存储列指针 Down，右边存储行指针 Right
• 每一行、每一列都是一个循环链表

十字链表的结点表示

用一个标识域 Tag 区分头结点和非零元素结点

在中间区域的表示上，就可以使用联合体 union

链表

常见类型

• 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
• 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
• 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
• 多重链表

典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

• 栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
• 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
• 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

• 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
• 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
• LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

• 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
• 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

数组 vs 链表

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	\(O(1)\)	\(O(n)\)
添加元素	\(O(n)\)	\(O(1)\)
删除元素	\(O(n)\)	\(O(1)\)

关键收获

1. 使用十字链表存储稀疏矩阵