【线性表】顺序存储相关操作的动画演示及源代码
【线性表】顺序存储相关操作的动画演示及源代码线性表是一种常见的数据结构，用于存储元素的有序集合。
线性表的顺序存储是指使用连续的内存空间来存储线性表的元素，通常使用数组来实现。
本篇将涵盖以下操作：
[*]初始化线性表
[*]判断是否为空表
[*]获取线性表长度
[*]获取第 i 个数据元素
[*]查找数据元素
[*]插入数据元素
[*]删除数据元素
[*]清空线性表
[*]销毁线性表
初始化线性表
线性表顺序存储时，可以选择静态分配或动态分配内存来实现。二者的主要区别在于内存分配的时机和方式，以及内存使用的灵活性。
静态分配
静态分配是在编译时就确定内存大小的分配方式。在 C 语言中，这通常是通过声明一个数组实现的。
优点：
[*]简单易于实现。
[*]由于内存位置是连续的，访问速度快。
[*]不存在运行时内存分配导致的开销。
缺点：
[*]分配的内存大小在编译时就固定了，不够灵活。
[*]如果声明的数组过大，会浪费内存；如果声明的数组过小，可能不足以满足实际需要。
[*]程序运行过程中无法改变数组的大小。
时间复杂度：O(1)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialInit1.mp4
实现代码：
#define MAX_SIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义元素类型
// 定义顺序线性表的结构
typedef struct {
ElemType data; // 用数组存储
int length; // 线性表当前长度
} SqList;
// 初始化线性表
void InitList(SqList *L) {
L->length = 0;
}
动态分配
动态分配是在程序运行时根据需要分配内存的方式。在 C 语言中，这通常通过 malloc、calloc 或 realloc 等函数实现。
优点：
[*]内存使用更加灵活。可以根据实际需要分配内存，不必在编译时确定大小。
[*]可以在程序运行时调整内存大小，例如使用 realloc 函数。
缺点：
[*]管理复杂度高，需要手动管理内存的分配和释放，避免内存泄漏和野指针。
[*]动态内存分配和释放可能导致内存碎片。
[*]相对于静态分配，动态分配可能会有更大的性能开销。
时间复杂度：O(1)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialInit2.mp4
实现代码：
#define MAX_SIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义元素类型
// 定义顺序线性表的结构
typedef struct {
ElemType *data; // 用指针代替数组
int length; // 线性表当前长度
int capacity; // 线性表的总容量
} SqList;
// 初始化线性表
void InitList(SqList *L) {
L->data = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));// 动态分配内存
if (L->data == NULL) {
exit(EXIT_FAILURE);
}
L->length = 0; // 初始化线性表的当前长度为0
L->capacity = MAX_SIZE; // 设置线性表的容量
}
判断是否为空表
时间复杂度：O(1)
实现代码：
// 判断线性表是否为空
bool ListEmpty(SqList L) {
return L.length == 0;
}
获取线性表长度
时间复杂度：O(1)
实现代码：
// 返回线性表的长度
int ListLength(SqList L) {
return L.length;
}
获取第 i 个数据元素
时间复杂度：O(1)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialGetElem.mp4
实现代码：
// 获取线性表中第i个数据元素的值
bool GetElem(SqList L, int i, ElemType *e) {
if (L.length == 0 || i < 1 || i > L.length)
return false;
*e = L.data;
return true;
}
查找数据元素
时间复杂度：O(n)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialLocateElem.mp4
实现代码：
// 在线性表L中查找数据元素e的位置
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++) {
if (L.data == e)
return i + 1;
}
return 0;
}
插入数据元素
时间复杂度：O(n)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialInsert.mp4
实现代码：
// 在线性表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 = L->data;
}
L->data = e;
L->length++;
return true;
}
删除数据元素
时间复杂度：O(n)
动画演示：
https://fishc.oss-cn-hangzhou.aliyuncs.com/Videos/DSA(PEE)/SequentialDelete.mp4
实现代码：
// 删除线性表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;
for (int j = i; j < L->length; j++) {
L->data = L->data;
}
L->length--;
return true;
}
清空线性表
时间复杂度：O(1)
实现代码：
// 清空线性表L
void ClearList(SqList *L) {
L->length = 0;
}
小甲鱼：这就是为啥 steam 删除一部 80G 的游戏，用不到一秒钟就能完成的原因……
销毁线性表
时间复杂度：O(1)
如果使用的是静态分配的数组，实际上并不需要进行销毁操作。
直接将 length 设置为 0 即可（同清空线性表）：
// 销毁线性表L
void DestroyList(SqList *L) {
L->length = 0;
}
如果是动态分配，必须显式地调用 free 函数来释放动态分配的内存。
如果不这样做，程序结束后内存不会被自动释放，从而可能导致内存泄露：
void DestroyList(SqList *L) {
// 先判断指针是否为NULL，防止重复释放
if (L->data != NULL) {
free(L->data); // 释放动态分配的内存
L->data = NULL; // 将指针设置为NULL，避免产生野指针
}
L->length = 0; // 重置线性表的当前长度为0
L->capacity = 0; // 重置线性表的容量
}
完整源码
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义元素类型
// 定义顺序线性表的结构
typedef struct {
ElemType data; // 用数组存储
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个数据元素的值
bool GetElem(SqList L, int i, ElemType *e) {
if (L.length == 0 || i < 1 || i > L.length)
return false;
*e = L.data;
return true;
}
// 在线性表L中查找数据元素e的位置
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++) {
if (L.data == e)
return i + 1;
}
return 0;
}
// 在线性表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 = L->data;
}
L->data = 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;
for (int j = i; j < L->length; j++) {
L->data = L->data;
}
L->length--;
return true;
}
// 清空线性表L
void ClearList(SqList *L) {
L->length = 0;
}
// 销毁线性表L
void DestroyList(SqList *L) {
// 由于这里使用的是静态数组，实际上并不需要进行销毁操作
// 如果使用动态数组，则需要释放内存
// free(L->data);
L->length = 0;
}
int main() {
SqList myList;
ElemType e;
bool result;
// 初始化列表
InitList(&myList);
printf("初始化列表。\n");
// 测试列表是否为空
result = ListEmpty(myList);
printf("列表是否为空： %s\n", result ? "是" : "否");
// 插入元素
for (int i = 1; i <= 5; i++) {
result = ListInsert(&myList, i, i * 10);
printf("在位置 %d 插入元素 %d，结果： %s\n", i, i * 10, result ? "成功" : "失败");
}
// 打印列表长度
printf("列表长度为：%d\n", ListLength(myList));
// 获取第3个元素
result = GetElem(myList, 3, &e);
if (result) {
printf("第3个元素的值为：%d\n", e);
} else {
printf("获取第3个元素失败。\n");
}
// 查找元素位置
int pos = LocateElem(myList, 20);
printf("元素 20 的位置是：%d\n", pos);
// 删除第3个元素
result = ListDelete(&myList, 3, &e);
if (result) {
printf("删除第3个元素，删除的元素是：%d\n", e);
} else {
printf("删除第3个元素失败。\n");
}
// 再次打印列表长度
printf("删除元素后，列表长度为：%d\n", ListLength(myList));
// 清空列表
ClearList(&myList);
printf("清空列表后，列表长度为：%d\n", ListLength(myList));
// 销毁列表
DestroyList(&myList);
printf("销毁列表后，列表长度为：%d\n", ListLength(myList));
return 0;
}
线性表是具有零个或多个数据元素的有限序列，是最常用也最简单的一种数据结构。线性表主要考察有限性、有序性和线性结构（一对一）。本节首先讲解了线性表的抽象数据类型（ADT），即用数学语言来描述线性表的数据特性与其基本操作的封装。对某种数据结构抽象数据类型的学习，有助于我们深刻理解该数据结构的作用及内涵。
线性表可采用顺序存储（如数组）和链式存储。顺序存储可以通过直接寻址访问任何元素。不同的存储方式，决定了各基本操作不同的具体实现方式。
数据结构这门课程强调算法的思想和步骤，而不拘泥于代码实际的可执行性。正如时间复杂度的估计，要有“大格局”，不拘小节，方能领悟这门课程的精髓！
页:
[1]