【线性表】顺序存储相关操作的动画演示及源代码

小甲鱼

【线性表】顺序存储相关操作的动画演示及源代码

线性表是一种常见的数据结构，用于存储元素的有序集合。

线性表的顺序存储是指使用连续的内存空间来存储线性表的元素，通常使用数组来实现。

本篇将涵盖以下操作：

• 初始化线性表
• 判断是否为空表
• 获取线性表长度
• 获取第 i 个数据元素
• 查找数据元素
• 插入数据元素
• 删除数据元素
• 清空线性表
• 销毁线性表
  

初始化线性表

线性表顺序存储时，可以选择静态分配或动态分配内存来实现。二者的主要区别在于内存分配的时机和方式，以及内存使用的灵活性。

静态分配

静态分配是在编译时就确定内存大小的分配方式。在 C 语言中，这通常是通过声明一个数组实现的。

优点：

• 简单易于实现。
• 由于内存位置是连续的，访问速度快。
• 不存在运行时内存分配导致的开销。
  

缺点：

• 分配的内存大小在编译时就固定了，不够灵活。
• 如果声明的数组过大，会浪费内存；如果声明的数组过小，可能不足以满足实际需要。
• 程序运行过程中无法改变数组的大小。
  

时间复杂度：O(1)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

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;
   
10. 
    
11. // 初始化线性表
    
12. void InitList(SqList *L) {
    
13.     L->length = 0;
    
14. }

复制代码

动态分配

动态分配是在程序运行时根据需要分配内存的方式。在 C 语言中，这通常通过 malloc、calloc 或 realloc 等函数实现。

优点：

• 内存使用更加灵活。可以根据实际需要分配内存，不必在编译时确定大小。
• 可以在程序运行时调整内存大小，例如使用 realloc 函数。
  

缺点：

• 管理复杂度高，需要手动管理内存的分配和释放，避免内存泄漏和野指针。
• 动态内存分配和释放可能导致内存碎片。
• 相对于静态分配，动态分配可能会有更大的性能开销。
  

时间复杂度：O(1)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

1. #define MAX_SIZE 100     // 定义线性表的最大长度
   
2. 
   
3. typedef int ElemType;    // 定义元素类型
   
4. 
   
5. // 定义顺序线性表的结构
   
6. typedef struct {
   
7.     ElemType *data;    // 用指针代替数组
   
8.     int length;        // 线性表当前长度
   
9.     int capacity;      // 线性表的总容量
   
10. } SqList;
    
11. 
    
12. // 初始化线性表
    
13. void InitList(SqList *L) {
    
14.     L->data = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));  // 动态分配内存
    
15.     if (L->data == NULL) {
    
16.         exit(EXIT_FAILURE);
    
17.     }
    
18.     L->length = 0;             // 初始化线性表的当前长度为0
    
19.     L->capacity = MAX_SIZE;    // 设置线性表的容量
    
20. }

复制代码

判断是否为空表

时间复杂度：O(1)

实现代码：

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

复制代码

获取线性表长度

时间复杂度：O(1)

实现代码：

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

复制代码

获取第 i 个数据元素

时间复杂度：O(1)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

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. }

复制代码

查找数据元素

时间复杂度：O(n)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

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. }

复制代码

插入数据元素

时间复杂度：O(n)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

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. }

复制代码

删除数据元素

时间复杂度：O(n)

动画演示：

如果无法播放，请点击此处在新窗口打开

实现代码：

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. }

复制代码

清空线性表

时间复杂度：O(1)

实现代码：

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

复制代码

小甲鱼：这就是为啥 steam 删除一部 80G 的游戏，用不到一秒钟就能完成的原因……


销毁线性表

时间复杂度：O(1)

如果使用的是静态分配的数组，实际上并不需要进行销毁操作。

直接将 length 设置为 0 即可（同清空线性表）：

1. // 销毁线性表L
   
2. void DestroyList(SqList *L) {
   
3.     L->length = 0;
   
4. }

复制代码

如果是动态分配，必须显式地调用 free 函数来释放动态分配的内存。

如果不这样做，程序结束后内存不会被自动释放，从而可能导致内存泄露：

1. void DestroyList(SqList *L) {
   
2.     // 先判断指针是否为NULL，防止重复释放
   
3.     if (L->data != NULL) {
   
4.         free(L->data);     // 释放动态分配的内存
   
5.         L->data = NULL;    // 将指针设置为NULL，避免产生野指针
   
6.     }
   
7.     L->length = 0;      // 重置线性表的当前长度为0
   
8.     L->capacity = 0;    // 重置线性表的容量
   
9. }

复制代码

完整源码

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. #define MAX_SIZE 100     // 定义线性表的最大长度
   
5. 
   
6. typedef int ElemType;    // 定义元素类型
   
7. 
   
8. // 定义顺序线性表的结构
   
9. typedef struct {
   
10.     ElemType data[MAX_SIZE];    // 用数组存储
    
11.     int length;                 // 线性表当前长度
    
12. } SqList;
    
13. 
    
14. // 初始化线性表
    
15. void InitList(SqList *L) {
    
16.     L->length = 0;
    
17. }
    
18. 
    
19. // 判断线性表是否为空
    
20. bool ListEmpty(SqList L) {
    
21.     return L.length == 0;
    
22. }
    
23. 
    
24. // 返回线性表的长度
    
25. int ListLength(SqList L) {
    
26.     return L.length;
    
27. }
    
28. 
    
29. // 获取线性表中第i个数据元素的值
    
30. bool GetElem(SqList L, int i, ElemType *e) {
    
31.     if (L.length == 0 || i < 1 || i > L.length)
    
32.         return false;
    
33.    
    
34.     *e = L.data[i - 1];
    
35.     return true;
    
36. }
    
37. 
    
38. // 在线性表L中查找数据元素e的位置
    
39. int LocateElem(SqList L, ElemType e) {
    
40.     for (int i = 0; i < L.length; i++) {
    
41.         if (L.data[i] == e)
    
42.             return i + 1;
    
43.     }
    
44.     return 0;
    
45. }
    
46. 
    
47. // 在线性表L中第i个位置上插入新的数据元素e
    
48. bool ListInsert(SqList *L, int i, ElemType e) {
    
49.     if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE)
    
50.         return false;
    
51. 
    
52.     for (int j = L->length; j >= i; j--) {
    
53.         L->data[j] = L->data[j - 1];
    
54.     }
    
55.     L->data[i - 1] = e;
    
56.     L->length++;
    
57. 
    
58.     return true;
    
59. }
    
60. 
    
61. // 删除线性表L中第i个数据元素，并用e返回其值
    
62. bool ListDelete(SqList *L, int i, ElemType *e) {
    
63.     if (L->length == 0 || i < 1 || i > L->length)
    
64.         return false;
    
65. 
    
66.     *e = L->data[i - 1];
    
67.     for (int j = i; j < L->length; j++) {
    
68.         L->data[j - 1] = L->data[j];
    
69.     }
    
70.     L->length--;
    
71. 
    
72.     return true;
    
73. }
    
74. 
    
75. // 清空线性表L
    
76. void ClearList(SqList *L) {
    
77.     L->length = 0;
    
78. }
    
79. 
    
80. // 销毁线性表L
    
81. void DestroyList(SqList *L) {
    
82.     // 由于这里使用的是静态数组，实际上并不需要进行销毁操作
    
83.     // 如果使用动态数组，则需要释放内存
    
84.     // free(L->data);
    
85.     L->length = 0;
    
86. }
    
87. 
    
88. int main() {
    
89.     SqList myList;
    
90.     ElemType e;
    
91.     bool result;
    
92. 
    
93.     // 初始化列表
    
94.     InitList(&myList);
    
95.     printf("初始化列表。\n");
    
96. 
    
97.     // 测试列表是否为空
    
98.     result = ListEmpty(myList);
    
99.     printf("列表是否为空： %s\n", result ? "是" : "否");
    
100. 
     
101.     // 插入元素
     
102.     for (int i = 1; i <= 5; i++) {
     
103.         result = ListInsert(&myList, i, i * 10);
     
104.         printf("在位置 %d 插入元素 %d，结果： %s\n", i, i * 10, result ? "成功" : "失败");
     
105.     }
     
106. 
     
107.     // 打印列表长度
     
108.     printf("列表长度为：%d\n", ListLength(myList));
     
109. 
     
110.     // 获取第3个元素
     
111.     result = GetElem(myList, 3, &e);
     
112.     if (result) {
     
113.         printf("第3个元素的值为：%d\n", e);
     
114.     } else {
     
115.         printf("获取第3个元素失败。\n");
     
116.     }
     
117. 
     
118.     // 查找元素位置
     
119.     int pos = LocateElem(myList, 20);
     
120.     printf("元素 20 的位置是：%d\n", pos);
     
121. 
     
122.     // 删除第3个元素
     
123.     result = ListDelete(&myList, 3, &e);
     
124.     if (result) {
     
125.         printf("删除第3个元素，删除的元素是：%d\n", e);
     
126.     } else {
     
127.         printf("删除第3个元素失败。\n");
     
128.     }
     
129. 
     
130.     // 再次打印列表长度
     
131.     printf("删除元素后，列表长度为：%d\n", ListLength(myList));
     
132. 
     
133.     // 清空列表
     
134.     ClearList(&myList);
     
135.     printf("清空列表后，列表长度为：%d\n", ListLength(myList));
     
136. 
     
137.     // 销毁列表
     
138.     DestroyList(&myList);
     
139.     printf("销毁列表后，列表长度为：%d\n", ListLength(myList));
     
140. 
     
141.     return 0;
     
142. }

复制代码

小古比鱼

线性表是具有零个或多个数据元素的有限序列，是最常用也最简单的一种数据结构。线性表主要考察有限性、有序性和线性结构（一对一）。本节首先讲解了线性表的抽象数据类型（ADT），即用数学语言来描述线性表的数据特性与其基本操作的封装。对某种数据结构抽象数据类型的学习，有助于我们深刻理解该数据结构的作用及内涵。
线性表可采用顺序存储（如数组）和链式存储。顺序存储可以通过直接寻址访问任何元素。不同的存储方式，决定了各基本操作不同的具体实现方式。
数据结构这门课程强调算法的思想和步骤，而不拘泥于代码实际的可执行性。正如时间复杂度的估计，要有“大格局”，不拘小节，方能领悟这门课程的精髓！