第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：

1. ADT List {
   
2.     数据对象：$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
   
3.   
   
4.     数据关系：$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
   
5.    
   
6.     基本操作：
   
7. 
   
8.     InitList(*L)
   
9.       操作结果：构造一个空的线性表 L
   
10. 
    
11.     ListEmpty(L)
    
12.       操作结果：判断线性表是否为空
    
13. 
    
14.     ListLength(L)
    
15.       操作结果：返回线性表 L 中数据元素的个数
    
16. 
    
17.     GetElem(L, i, *e)
    
18.       操作结果：获取 L 中第 i 个数据元素的值，并通过 e 返回
    
19. 
    
20.     LocateElem(L, e)
    
21.       操作结果：在线性表 L 中查找数据元素 e 的位置
    
22. 
    
23.     ListInsert(*L, i, e)
    
24.       操作结果：在线性表 L 中第 i 个位置上插入新的数据元素 e
    
25. 
    
26.     ListDelete(*L, i, *e)
    
27.       操作结果：删除线性表 L 中第 i 个数据元素，并用 e 返回其值
    
28. 
    
29.     ClearList(*L)
    
30.       操作结果：清空线性表 L
    
31. 
    
32.     DestroyList(*L)
    
33.       操作结果：销毁线性表 L
    
34. 
    
35. } 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. 顺序存储的基本操作

定义部分：

1. #define MAX_SIZE 100     // 定义线性表的最大长度
   
2. 
   
3. typedef int ElemType;    // 定义元素类型
   
4. 
   
5. // 定义顺序线性表的结构
   
6. typedef struct {
   
7.     ElemType data[MAX_SIZE];    // 用数组存储
   
8.     int length;                 // 线性表当前长度
   
9. } SqList;

复制代码

初始化线性表：

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

复制代码

判断线性表是否为空：

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

复制代码

获取线性表的长度：

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

复制代码

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

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

复制代码

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

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

复制代码

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

1. // 在线性表 L 中第 i 个位置上插入新的数据元素 e
   
2. bool ListInsert(SqList *L, int i, ElemType e) {
   
3.     if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE)
   
4.         return false;
   
5. 
   
6.     for (int j = L->length; j >= i; j--) {
   
7.         L->data[j] = L->data[j - 1];
   
8.     }
   
9.     L->data[i - 1] = e;
   
10.     L->length++;
    
11. 
    
12.     return true;
    
13. }

复制代码

删除线性表中的元素：

1. // 删除线性表 L 中第 i 个数据元素，并用 e 返回其值
   
2. bool ListDelete(SqList *L, int i, ElemType *e) {
   
3.     if (L->length == 0 || i < 1 || i > L->length)
   
4.         return false;
   
5. 
   
6.     *e = L->data[i - 1];
   
7.     for (int j = i; j < L->length; j++) {
   
8.         L->data[j - 1] = L->data[j];
   
9.     }
   
10.     L->length--;
    
11. 
    
12.     return true;
    
13. }

复制代码

清空线性表：

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

复制代码

销毁线性表：

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

复制代码

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

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


7. 思维导图