前言顺序表是数据结构中最基础、也是最重要的线性表实现方式之一。理解顺序表的原理和实现是后续学习链表、栈、队列等结构的基础。本文将从概念、存储结构、基本操作、代码实现、时间复杂度分析等几个方面带大家彻底搞懂顺序表。一、什么是顺序表顺序表Sequence List是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。简单来说顺序表 数组 一组对数据进行增删查改的接口。顺序表分为两种静态顺序表使用定长数组存储元素。动态顺序表使用动态开辟的数组存储根据需要动态调整容量。由于静态顺序表在空间不够时无法扩容容量给小了不够用给大了浪费所以实际中更常用动态顺序表。顺序表的访问方式和数组类似变量名下标物理地址连续并且类型确定说明线性结构指的是数据排成一条直线每个元素最多只有一个前面、一个后面就是线性结构。 比如数组、链表、栈、队列、字符串。物理地址可以不连续但逻辑上是连续的二、顺序表的结构定义2.1 静态顺序表了解即可#define N 100 typedef int SLDataType; typedef struct SeqList { SLDataType array[N]; // 定长数组 int size; // 有效数据个数 } SeqList;静态顺序表的缺陷很明显N给多大都不合适所以工程中一般不用。2.2 动态顺序表重点typedef int SLDataType; typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 int size; // 有效数据个数 int capacity; // 容量大小 } SeqList;三、顺序表的基本操作顺序表常见的接口包括初始化、销毁、打印、检查容量、尾插、尾删、头插、头删、指定位置插入、指定位置删除、查找等。3.1 初始化与销毁// 初始化 void SLInit(SeqList* ps) { ps-array NULL; ps-size 0; ps-capacity 0; } // 销毁 void SLDestroy(SeqList* ps) { if (ps-array) { free(ps-array); } ps-array NULL; ps-size ps-capacity 0; }3.2 检查容量扩容这是顺序表的核心逻辑之一当有效数据个数等于容量时需要扩容。void SLCheckCapacity(SeqList* ps) { if (ps-size ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; //重新开辟空间将原来顺序表里面的内容拷贝到新的空间 SLDataType* tmp (SLDataType*)realloc(ps-array, newCapacity * sizeof(SLDataType)); if (tmp NULL) { perror(realloc fail); exit(-1); } ps-array tmp; ps-capacity newCapacity; } }扩容一般采用倍增策略如2倍这样可以有效降低扩容的频率均摊时间复杂度更优。3.3 尾插与尾删// 尾插 void SLPushBack(SeqList* ps, SLDataType x) { SLCheckCapacity(ps); ps-array[ps-size] x; ps-size; } // 尾删 void SLPopBack(SeqList* ps) { assert(ps-size 0); // 判断顺序表是否为空 ps-size--; }3.4 头插与头删头部操作需要挪动数据效率较低。// 头插 void SLPushFront(SeqList* ps, SLDataType x) { SLCheckCapacity(ps); // 数据整体后移一位 for (int i ps-size; i 0; i--) { ps-array[i] ps-array[i - 1]; } ps-array[0] x; ps-size; } // 头删 void SLPopFront(SeqList* ps) { assert(ps-size 0); // 数据整体前移一位 for (int i 0; i ps-size - 1; i) { ps-array[i] ps-array[i 1]; } ps-size--; }3.5 指定位置插入与删除// 在pos位置插入x void SLInsert(SeqList* ps, int pos, SLDataType x) { assert(pos 0 pos ps-size); SLCheckCapacity(ps); for (int i ps-size; i pos; i--) { ps-array[i] ps-array[i - 1]; } ps-array[pos] x; ps-size; } // 删除pos位置的数据 void SLErase(SeqList* ps, int pos) { assert(pos 0 pos ps-size); for (int i pos; i ps-size - 1; i) { ps-array[i] ps-array[i 1]; } ps-size--; }3.6 查找​int SLFind(SeqList* ps, SLDataType x) { for (int i 0; i ps-size; i) { if (ps-array[i] x) { return i; // 返回下标 } } return -1; // 未找到 }3.7 打印void SLPrint(SeqList* ps) { for (int i 0; i ps-size; i) { printf(%d , ps-array[i]); } printf(\n); }四、完整测试代码int main() { SeqList sl; SLInit(sl); SLPushBack(sl, 1); SLPushBack(sl, 2); SLPushBack(sl, 3); SLPrint(sl); // 1 2 3 SLPushFront(sl, 0); SLPrint(sl); // 0 1 2 3 SLInsert(sl, 2, 100); SLPrint(sl); // 0 1 100 2 3 SLErase(sl, 2); SLPrint(sl); // 0 1 2 3 int pos SLFind(sl, 2); printf(2的下标是: %d\n, pos); SLDestroy(sl); return 0; }五、时间复杂度分析操作时间复杂度说明尾插/尾删O(1)不涉及数据搬移头插/头删O(N)需要整体挪动数据指定位置插入/删除O(N)平均需要挪动一半数据查找O(N)需要遍历随机访问下标O(1)数组天然支持随机访问优点支持随机访问效率高O(1)空间利用率相对紧凑CPU高速缓存命中率较高。缺点头部/中间插入删除效率低需要搬移大量数据扩容存在一定的时间开销且可能造成空间浪费增容一般是原容量的2倍可能会造成一定的空间浪费。六、总结顺序表是学习数据结构的第一站虽然原理简单但扩容策略、数据搬移、边界条件assert判断这些细节都需要格外注意。掌握好顺序表能为后面学习链表、栈、队列、甚至STL中的vector打下坚实的基础。如果这篇文章对你有帮助欢迎点赞收藏后续会持续更新数据结构与算法相关内容