第004讲：线性表（顺序存储）

小甲鱼

第004讲：线性表（顺序存储）

知识点回顾：

0. 本节视频




1. 线性表的概念

线性表（List），是最常用且最简单的一种数据结构，它是具有零个或多个数据元素的有限序列。

如果用数学的语言来定义，通常我们会将线性表记为 $L = (a_{1}, a_{2}, \dots, a_{i-1}, a_{i}, a_{i+1}, \dots, a_{n})$ 这么一个式子。

其中，a_{1} 是唯一的第一个数据元素，也称为表头元素，a_{n} 则是唯一的最后一个元素，又称为表尾元素。

除第一个元素之外的每一个元素，有且仅有一个直接前驱（比如 a_{i} 的直接前驱是 a_{i-1}）。

同样的道理，除最后一个元素之外的每一个元素，也会有一个直接后继（正如 a_{i} 的直接后继是 a_{i+1}）。


2. 有关线性表概念的考点

• 有限性：线性表是零个或多个数据元素的有限序列。也就是说，一个线性表中的元素数量是有限的。
• 有序性：线性表中的元素是有序的，每个元素都有一个唯一的前驱和后继（除了第一个元素没有前驱，最后一个元素没有后继）
• 线性结构：也就是说，线性表的数据元素之间必须是呈现一对一的关系。
  

3. 抽象数据类型

抽象数据类型（Abstract Data Type，简称 ADT）其实是一种对数据和操作的封装，它只描述了数据和操作的特性，而不涉及具体的实现方法。

简单地说，ADT 就像是一件家用电器的使用手册，它会告诉你这个东西有哪些功能，以及如何操作，但它不需要告诉你这些功能背后到底是如何实现的。

线性表的 ADT：

ADT List {
    数据对象：$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
  
    数据关系：$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
    
    基本操作：

    InitList(*L)
      操作结果：构造一个空的线性表 L

    ListEmpty(L)
      操作结果：判断线性表是否为空

    ListLength(L)
      操作结果：返回线性表 L 中数据元素的个数

    GetElem(L, i, *e)
      操作结果：获取 L 中第 i 个数据元素的值，并通过 e 返回

    LocateElem(L, e)
      操作结果：在线性表 L 中查找数据元素 e 的位置

    ListInsert(*L, i, e)
      操作结果：在线性表 L 中第 i 个位置上插入新的数据元素 e

    ListDelete(*L, i, *e)
      操作结果：删除线性表 L 中第 i 个数据元素，并用 e 返回其值

    ClearList(*L)
      操作结果：清空线性表 L

    DestroyList(*L)
      操作结果：销毁线性表 L

} ADT List

数据对象：$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$

定义数据对象 D 为一个元素集合，其中每个元素 $a_{i}$ 都属于一个叫 ElemSet 的元素集，通常这个元素集会被假定为一个通用集合。

在具体实现时，ElemSet 可以被指定为特定的类型，比如整数、浮点数、字符串、或者更复杂的结构等。

但在 ADT 的定义层面，ElemSet 是抽象的，它可以代表任何可能的元素集合。

然后，i 就是元素的位置，从 1 开始，表示第一个元素，n 是线性表的长度。

数据关系：$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$

定义一个数据关系 R1，它表示线性表中相邻元素之间的顺序关系。

$<a_{i-1}, a_{i}>$ 表示一个有序对（cordered pair），强调了元素之间的顺序，也就是 $a_{i-1}$，必须是在 $a_{i}$ 之前的。

基本操作

基本操作的具体实现，要取决于采用哪种存储结构，存储结构不同，算法的实现肯定也大相径庭。

那么线性表有两种不同的存储方式：顺序存储（也就是我们 C 语言中的数组），和链式存储（包括单链表、双链表、循环链表这些）。


4. 顺序存储

对于顺序存储结构来讲，假设线性表的每个数据元素需要占用 s 个存储单元，那么线性表中第 i+1 个数据元素的存储位置，和第 i 个数据元素的存储位置将满足以下关系：

$LOC(a_{i+1}) = LOC(a_{i}) + s$

因此，线性表的第 i 个数据元素 $a_{i}$ 的存储位置为：

$LOC(a_{i}) = LOC(a_{1}) + (i-1) * s$

不难看出，顺序存储结构可以通过直接寻址访问任何元素，这就意味着访问第 i 个元素的时间复杂度是 O(1)，即常数时间。


5. 顺序存储的基本操作

定义部分：

#define MAX_SIZE 100     // 定义线性表的最大长度

typedef int ElemType;    // 定义元素类型

// 定义顺序线性表的结构
typedef struct {
    ElemType data[MAX_SIZE];    // 用数组存储
    int length;                 // 线性表当前长度
} SqList;

初始化线性表：

// 初始化线性表
void InitList(SqList *L) {
    L->length = 0;
}

判断线性表是否为空：

// 判断线性表是否为空
bool ListEmpty(SqList L) {
    return L.length == 0;
}

获取线性表的长度：

// 返回线性表的长度
int ListLength(SqList L) {
    return L.length;
}

获取线性表中第 i 个数据元素的值：

// 获取线性表中第 i 个数据元素的值
bool GetElem(SqList L, int i, ElemType *e) {
    if (L.length == 0 || i < 1 || i > L.length)
        return false;
    
    *e = L.data[i - 1];
    return true;
}

在线性表 L 中查找数据元素 e 的位置：

// 在线性表 L 中查找数据元素 e 的位置
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;
}

在线性表 L 的第 i 个位置上，插入数据元素 e：

// 在线性表 L 中第 i 个位置上插入新的数据元素 e
bool ListInsert(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE) 
        return false;

    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;
    L->length++;

    return true;
}

删除线性表中的元素：

// 删除线性表 L 中第 i 个数据元素，并用 e 返回其值
bool ListDelete(SqList *L, int i, ElemType *e) {
    if (L->length == 0 || i < 1 || i > L->length)
        return false;

    *e = L->data[i - 1];
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;

    return true;
}

清空线性表：

// 清空线性表 L
void ClearList(SqList *L) {
    L->length = 0;
}

销毁线性表：

// 销毁线性表 L
void DestroyList(SqList *L) {
    // 由于这里使用的是静态数组，实际上并不需要进行销毁操作
    // 如果使用动态数组，则需要释放内存
    // free(L->data);
    L->length = 0;
}

6. 顺序存储相关操作的动画演示及源代码

很重要，建议保存 -> https://fishc.com.cn/thread-239016-1-1.html


7. 思维导图