前言动态顺序表是一种基于数组实现的线性数据结构能够根据存储需求动态调整内存空间兼具数组的随机访问特性和动态扩容的灵活性。相比静态顺序表动态顺序表通过合理的内存管理策略如倍增扩容或固定步长扩容有效平衡了空间利用率和操作效率适用于元素数量变化较大的场景。在算法设计与程序开发中动态顺序表是实现高级数据结构如栈、队列、字符串等的基础同时也为学习更复杂的动态内存分配机制如链表、哈希表提供了重要参考。其核心操作包括插入、删除、查找和扩容需重点关注时间复杂度的优化与内存分配的合理性。一、动态顺序表的核心概念1.1 动态扩容当元素数量超过当前容量时动态顺序表会触发扩容操作。而扩展空间时有两种常见情况。1后续连续空间足够实现扩容直接在已有空间后面扩容。2如果后续连续空间不够会申请大的空间拷贝旧数据释放旧空间。1.2 扩容函数void Addcapacity(SL* sp) { //空间不够 if (sp-size sp-capacity) { int newcapacity (sp-capacity 0) ? 4 : 2 * sp-capacity; //增容 SLTDatatype* tmp (SLTDatatype*)realloc(sp-arr, newcapacity * sizeof(SLTDatatype)); if (tmp NULL) { perror(realloc fail!); exit(1); } sp-arr tmp; sp-capacity newcapacity; } }1容量检查条件if (sp-size sp-capacity),当当前元素数量size等于当前容量capacity时触发扩容表示数组已满。2采用指数级扩容策略初始容量为0时设为4否则每次扩容为原容量的2倍。3错误处理if (tmp NULL)如果扩容失败输出错误信息终止程序。4更新状态sp-arr tmp,sp-capacity newcapacity.1.3 文件组成1.4 定义结构typedef int SLTDatatype; //定义动态顺序表结构 typedef struct SeqList { SLTDatatype* arr; //存储数据 int size; //当前存储的元素个数 int capacity; //空间大小 }SL;1数据类型定义typedef int SLTDatatype;将int类型重命名为SLTDatatype便于后续统一修改存储的数据类型。例如若需改为存储float只需修改此处的int即可。2成员变量说明SLTDatatype* arr动态分配的数组指针用于实际存储数据元素。通过指针实现灵活的内存管理支持运行时扩容。int size记录当前顺序表中实际存储的元素数量。插入/删除操作需同步更新此值用于边界检查如避免越界访问。int capacity表示数组的最大容量。当size capacity时需触发扩容机制通常以固定倍数如2倍扩大内存空间。1.5 功能列表//初始化 void SLInit(SL* sp); //尾插 void SLPushBack(SL* sp,SLTDatatype x); //头插 void SLPushFront(SL* sp, SLTDatatype x); //尾删 void SLPopFront(SL* sp); //头删 void SLPopBack(SL* sp); //查找 int SLFind(SL* sp,SLTDatatype x); //指定位置之前插入 void SLInsert(SL* sp, int pos, SLTDatatype x); //删除pos位置的数据 void SLErase(SL* sp, int pos); //打印 void my_printf(SL* sp); //销毁 void SLDestroy(SL* sp);二、功能实现2.1 结构体初始化//初始化 void SLInit(SL* sp) { sp-arr NULL; sp-capacity sp-size 0; }该函数将顺序表置为空表确保所有成员变量处于初始状态。后续操作如插入元素可通过检查arr是否为NULL或capacity是否为 0触发动态内存分配逻辑。2.2 尾插函数实现1代码//尾插 void SLPushBack(SL* sp,SLTDatatype x) { //空间不够 Addcapacity(sp); //空间足够 sp-arr[sp-size] x; }2实现过程2.3 头插函数实现1代码//头插 void SLPushFront(SL* sp, SLTDatatype x) { assert(sp); //空间不够 Addcapacity(sp); //空间足够 for (int i sp-size; i 0; i--) { sp-arr[i] sp-arr[i - 1]; } sp-arr[0] x; sp-size; }2实现过程2.4 尾删函数实现1代码//尾删 void SLPopFront(SL* sp) { assert(sp sp-size); sp-size--; }2实现过程sp-size--将顺序表的逻辑长度减1。由于顺序表是连续存储前端删除元素后后续元素无需移动仅通过缩小size限制访问范围即可。原前端元素仍在内存中但被逻辑排除。2.5 头删函数实现1代码//头删 void SLPopBack(SL* sp) { assert(sp sp-size); for (int i 0; i sp-size; i) { sp-arr[i] sp-arr[i 1]; } sp-size--; }2实现过程通过数组整体向前移动一位使第一个元素被覆盖消失实现头删。2.6 查找函数实现1代码//查找 int SLFind(SL* sp, SLTDatatype x) { assert(sp); for (int i 0; i sp-size; i) { if (sp-arr[i] x) { return i; } } printf(没找到); }2.7 指定位置之前插入1代码//指定位置之前插入 void SLInsert(SL* sp, int pos, SLTDatatype x) { assert(sp possp-size pos0); Addcapacity(sp); for (int i sp-size; i pos; i--) { sp-arr[i] sp-arr[i - 1]; } sp-arr[pos] x; sp-size; }2实现过程通过SLFind查找函数找到想要的数据的位置返回到pos最后传入SLInsert函数。2.8 删除指定位置的数据1代码void SLErase(SL* sp, int pos) { assert(sp pos 0 pos sp-size); for (int i pos; i sp-size-1; i) { sp-arr[i] sp-arr[i 1]; } sp-size--; }2实现过程2.9 销毁函数1代码void SLDestroy(SL* sp) { if (sp-arr) free(sp-arr); sp-arr NULL; sp-capacity sp-size 0; }销毁函数通常用于释放动态分配的内存或资源防止内存泄漏。三、主函数测试1代码void test1() { SL sl; // 声明一个顺序表结构体变量sl // 初始化顺序表 SLInit(sl); // 测试尾插操作 printf(尾插); SLPushBack(sl, 1); // 尾部插入元素1 my_printf(sl); // 打印当前顺序表内容 SLPushBack(sl, 2); // 尾部插入元素2 my_printf(sl); SLPushBack(sl, 3); // 尾部插入元素3 my_printf(sl); SLPushBack(sl, 4); // 尾部插入元素4 my_printf(sl); // 测试头插操作 printf(头插\n); SLPushFront(sl, 9); // 头部插入元素9 my_printf(sl); SLPushFront(sl, 8); // 头部插入元素8 my_printf(sl); SLPushFront(sl, 7); // 头部插入元素7 my_printf(sl); SLPushFront(sl, 6); // 头部插入元素6 my_printf(sl); // 测试头删操作 printf(尾删\n); SLPopFront(sl); // 删除头部元素 my_printf(sl); // 测试尾删操作 printf(头删\n); SLPopBack(sl); // 删除尾部元素 my_printf(sl); // 查找元素3并返回其位置 int size_pos SLFind(sl, 3); // 在指定位置前插入元素100 printf(指定位置之前添加\n); SLInsert(sl, size_pos, 100); my_printf(sl); // 删除指定位置的元素 printf(删除pos位置的数据\n); int size_pos1 SLFind(sl, 3); SLErase(sl, size_pos1); my_printf(sl); // 销毁顺序表 SLDestroy(sl); } int main() { test1(); // 执行测试函数 return 0; }2运行现象四、总结动态顺序表结合了数组的随机访问优势和动态扩容的灵活性是数据结构中一种高效且实用的线性存储方式。通过动态内存管理它能够在运行时根据需要调整容量避免了静态数组的固定大小限制。