【数据结构】—— 顺序表的实现与优化：空间管理与增容策略

文章目录

顺序表的基本概念与结构
顺序表的分类
- 静态顺序表
- 动态顺序表
顺序表问题与思考
- 插入与删除的时间复杂度
- 增容的开销
- 如何解决空间浪费问题？

顺序表作为一种常见的线性数据结构，广泛应用于各种编程任务中。它通过连续的物理内存存储数据元素，提供了高效的随机访问功能。在这篇博客中，我们将深入探讨顺序表的结构、分类、实现方法以及它的一些问题与优化策略，尤其是如何解决空间浪费和增容问题。

顺序表的基本概念与结构

顺序表（Sequential List）是一种线性数据结构，它使用一段连续的内存空间来存储数据元素，通常以数组的形式存储。顺序表的优点在于可以通过索引快速访问任意元素，时间复杂度为O(1)。但是，顺序表也有它的缺点，尤其是在元素的插入和删除时，因为它可能需要移动大量元素，导致时间复杂度达到O(N)。

顺序表与数组的区别在于，顺序表通常对数组进行了封装，提供了常用的增删改查等操作接口，使得开发者可以更方便地使用。

顺序表的分类

顺序表主要分为两种类型：静态顺序表和动态顺序表。

静态顺序表

静态顺序表使用固定大小的数组存储数据元素。在初始化时就为数组分配好一定的空间，因此它的容量是固定的。静态顺序表的缺点在于，当数据量较大时，空间可能不足；而当数据量较小且数组容量过大时，又会浪费大量空间。

#include <stdio.h>#define MAX_SIZE 100 // 定义顺序表的最大容量typedef int SeqListDataType; // 顺序表存储的数据类型// 顺序表结构体
typedef struct {SeqListDataType data[MAX_SIZE]; // 存储数据的数组int size; // 当前顺序表中的有效元素个数
} SeqList;// 初始化顺序表
void SeqListInit(SeqList* list);// 销毁顺序表
void SeqListDestroy(SeqList* list);// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list);// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index);// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value);// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index);// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value);// 清空顺序表
void SeqListClear(SeqList* list);

#include <stdio.h>#define MAX_SIZE 100 // 定义顺序表的最大容量typedef int SeqListDataType; // 顺序表存储的数据类型// 顺序表结构体
typedef struct {SeqListDataType data[MAX_SIZE]; // 存储数据的数组int size; // 当前顺序表中的有效元素个数
} SeqList;// 初始化顺序表
void SeqListInit(SeqList* list) {list->size = 0; // 初始化时，顺序表为空
}// 销毁顺序表
void SeqListDestroy(SeqList* list) {list->size = 0; // 重置顺序表大小
}// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list) {for (int i = 0; i < list->size; i++) {printf("%d ", list->data[i]);}printf("\n");
}// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index) {if (index >= 0 && index < list->size) {return list->data[index];} else {printf("Index out of bounds.\n");return -1; // 错误返回}
}// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value) {if (index < 0 || index > list->size || list->size == MAX_SIZE) {printf("Invalid index or sequence full.\n");return;}for (int i = list->size; i > index; i--) {list->data[i] = list->data[i - 1];}list->data[index] = value;list->size++;
}// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index) {if (index < 0 || index >= list->size) {printf("Invalid index.\n");return;}for (int i = index; i < list->size - 1; i++) {list->data[i] = list->data[i + 1];}list->size--;
}// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value) {for (int i = 0; i < list->size; i++) {if (list->data[i] == value) {return i;}}return -1; // 未找到
}// 清空顺序表
void SeqListClear(SeqList* list) {list->size = 0;
}int main() {SeqList list;SeqListInit(&list);SeqListInsert(&list, 0, 10);SeqListInsert(&list, 1, 20);SeqListInsert(&list, 2, 30);SeqListPrint(&list);SeqListRemove(&list, 1);SeqListPrint(&list);printf("Element at index 1: %d\n", SeqListGet(&list, 1));int index = SeqListFind(&list, 30);printf("Found 30 at index: %d\n", index);SeqListClear(&list);SeqListPrint(&list);return 0;
}

动态顺序表

动态顺序表通过按需申请内存空间来解决静态顺序表容量固定的问题。随着数据的增加，动态顺序表会自动扩展其容量，从而避免空间浪费。动态顺序表通常采用一个初始容量，当元素数量超过容量时，动态分配更大的内存空间。

动态顺序表的实现
下面是一个动态顺序表（SeqList）的实现。我们将通过一个简单的结构体和一些常见操作来展示其基本功能。

#define INIT_CAPACITY 4
typedef int SLDataType;// 动态顺序表 -- 按需申请
typedef struct SeqList {SLDataType* a;int size;       // 有效数据个数int capacity;   // 空间容量
} SL;// 初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);// 扩容
void SLCheckCapacity(SL* ps);// 头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);// 指定位置插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

#include <stdio.h>
#include <stdlib.h>#define INIT_CAPACITY 4 // 初始容量typedef int SeqListDataType; // 顺序表存储的数据类型// 动态顺序表结构体
typedef struct SeqList {SeqListDataType* data; // 存储数据的动态数组int size; // 当前顺序表中的有效元素个数int capacity; // 顺序表的总容量
} SeqList;// 初始化顺序表
void SeqListInit(SeqList* list) {list->size = 0;list->capacity = INIT_CAPACITY;list->data = (SeqListDataType*)malloc(sizeof(SeqListDataType) * list->capacity);
}// 销毁顺序表
void SeqListDestroy(SeqList* list) {free(list->data);list->size = 0;list->capacity = 0;
}// 扩容
void SeqListCheckCapacity(SeqList* list) {if (list->size == list->capacity) {list->capacity *= 2;list->data = (SeqListDataType*)realloc(list->data, sizeof(SeqListDataType) * list->capacity);}
}// 打印顺序表中的所有元素
void SeqListPrint(SeqList* list) {for (int i = 0; i < list->size; i++) {printf("%d ", list->data[i]);}printf("\n");
}// 获取指定位置的元素
SeqListDataType SeqListGet(SeqList* list, int index) {if (index >= 0 && index < list->size) {return list->data[index];} else {printf("Index out of bounds.\n");return -1; // 错误返回}
}// 插入操作：在指定位置插入元素
void SeqListInsert(SeqList* list, int index, SeqListDataType value) {if (index < 0 || index > list->size) {printf("Invalid index.\n");return;}SeqListCheckCapacity(list); // 检查是否需要扩容for (int i = list->size; i > index; i--) {list->data[i] = list->data[i - 1];}list->data[index] = value;list->size++;
}// 删除操作：删除指定位置的元素
void SeqListRemove(SeqList* list, int index) {if (index < 0 || index >= list->size) {printf("Invalid index.\n");return;}for (int i = index; i < list->size - 1; i++) {list->data[i] = list->data[i + 1];}list->size--;
}// 查找元素：返回元素第一次出现的位置
int SeqListFind(SeqList* list, SeqListDataType value) {for (int i = 0; i < list->size; i++) {if (list->data[i] == value) {return i;}}return -1; // 未找到
}// 清空顺序表
void SeqListClear(SeqList* list) {list->size = 0;
}int main() {SeqList list;SeqListInit(&list);SeqListInsert(&list, 0, 10);SeqListInsert(&list, 1, 20);SeqListInsert(&list, 2, 30);SeqListPrint(&list);SeqListRemove(&list, 1);SeqListPrint(&list);printf("Element at index 1: %d\n", SeqListGet(&list, 1));int index = SeqListFind(&list, 30);printf("Found 30 at index: %d\n", index);SeqListClear(&list);SeqListPrint(&list);SeqListDestroy(&list);return 0;
}