马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
【线性表】顺序存储相关操作的动画演示及源代码
线性表是一种常见的数据结构，用于存储元素的有序集合。
线性表的顺序存储是指使用连续的内存空间来存储线性表的元素，通常使用数组来实现。
本篇将涵盖以下操作：
- 初始化线性表
- 判断是否为空表
- 获取线性表长度
- 获取第 i 个数据元素
- 查找数据元素
- 插入数据元素
- 删除数据元素
- 清空线性表
- 销毁线性表
初始化线性表
线性表顺序存储时，可以选择静态分配或动态分配内存来实现。二者的主要区别在于内存分配的时机和方式，以及内存使用的灵活性。
静态分配
静态分配是在编译时就确定内存大小的分配方式。在 C 语言中，这通常是通过声明一个数组实现的。
优点：
- 简单易于实现。
- 由于内存位置是连续的，访问速度快。
- 不存在运行时内存分配导致的开销。
缺点：
- 分配的内存大小在编译时就固定了，不够灵活。
- 如果声明的数组过大，会浪费内存；如果声明的数组过小，可能不足以满足实际需要。
- 程序运行过程中无法改变数组的大小。
时间复杂度：O(1)
动画演示：
实现代码：
#define MAX_SIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义元素类型
// 定义顺序线性表的结构
typedef struct {
ElemType data[MAX_SIZE]; // 用数组存储
int length; // 线性表当前长度
} SqList;
// 初始化线性表
void InitList(SqList *L) {
L->length = 0;
}
动态分配是在程序运行时根据需要分配内存的方式。在 C 语言中，这通常通过 malloc、calloc 或 realloc 等函数实现。
优点：
- 内存使用更加灵活。可以根据实际需要分配内存，不必在编译时确定大小。
- 可以在程序运行时调整内存大小，例如使用 realloc 函数。
缺点：
- 管理复杂度高，需要手动管理内存的分配和释放，避免内存泄漏和野指针。
- 动态内存分配和释放可能导致内存碎片。
- 相对于静态分配，动态分配可能会有更大的性能开销。
时间复杂度：O(1)
动画演示：
实现代码：
#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)
动画演示：
实现代码：
// 获取线性表中第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;
}
查找数据元素
时间复杂度：O(n)
动画演示：
实现代码：
// 在线性表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;
}
插入数据元素
时间复杂度：O(n)
动画演示：
实现代码：
// 在线性表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;
}
删除数据元素
时间复杂度：O(n)
动画演示：
实现代码：
// 删除线性表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;
}
清空线性表
时间复杂度：O(1)
实现代码：
// 清空线性表L
void ClearList(SqList *L) {
L->length = 0;
}
销毁线性表
时间复杂度：O(1)
如果使用的是静态分配的数组，实际上并不需要进行销毁操作。
直接将 length 设置为 0 即可（同清空线性表）：
// 销毁线性表L
void DestroyList(SqList *L) {
L->length = 0;
}
如果不这样做，程序结束后内存不会被自动释放，从而可能导致内存泄露：
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[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个数据元素的值
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的位置
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
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;
}
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;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-1-16 01:03:53
置顶卡
千斤顶
显身卡
发表于 2024-4-7 18:10:41