顺序表：数据结构中的高效存储方案

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改

三、顺序表的分类

顺序表分为两种：静态顺序表和动态顺序表，每一种都属于它自己的价值，在实际中。一般使用动态顺序表多，比如我们经常用的通讯录(因为静态顺序表只适合事前知道需要多少内存的情况下，不然会出现申请多少内存问题)，接下来我们将实现动态顺序表

四、顺序表接口实现

4.1 顺序表的初始化

初始化顺序表，为其分配初始的内存空间并设置初始的有效数据个数和容量：

// 初始化顺序表：为顺序表分配初始内存空间，并设置初始状态 void SeqListInit(SeqList* ps) { // 初始分配能存储4个SLDataType类型元素的内存空间（小容量起步，避免初始内存浪费） ps->arr = (SLDataType*)malloc(4 * sizeof(SLDataType)); // 检查内存分配是否成功：若malloc返回NULL，说明分配失败 if (ps->arr == NULL) { perror("malloc failed: "); // 打印错误信息（如内存不足） return; // 分配失败则退出初始化，避免后续操作出错 } // 初始化有效元素个数为0（刚创建的顺序表暂无数据） ps->size = 0; // 初始化容量为4（与实际分配的内存空间大小对应） ps->capacity = 4; }

我习惯先开辟4个空间的容量，你也可以选择先不开空间

4.2 顺序表的扩容

当顺序表的空间不足时，需要进行扩容操作，以保证新数据能够顺利存储：

// 检查顺序表容量，若空间已满则进行扩容 void CheckCapacity(SeqList* ps) { // 当有效元素个数等于容量时，说明空间已满，需要扩容 if (ps->size == ps->capacity) { // 采用二倍扩容策略：平衡扩容效率与空间浪费（避免频繁扩容） size_t newCapacity = ps->capacity * 2; // 调用realloc调整内存大小：新空间为newCapacity个SLDataType类型 SLDataType* newArray = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType)); // 若realloc失败（返回NULL），打印错误信息并退出函数 if (newArray == NULL) { perror("realloc failed: "); // 补充失败提示，更清晰 return; } // 扩容成功后，更新顺序表的数组指针（先验证newArray有效，避免原数据丢失） ps->arr = newArray; // 更新容量为新的大小 ps->capacity = newCapacity; } }

4.4 顺序表的尾插与尾删

尾插是在顺序表的末尾插入一个新元素，尾删则是删除顺序表末尾的元素：

void SeqListPushBack(SeqList* ps, SLDataType x) { //先判断是否需要扩容 CheckCapacity(ps); psl->arr[ps->size] = x; ps->size++; } void SLPopBack(SL* ps) { assert(ps);//顺序表不能为空 assert(ps->size);//有效数据个数也不能为0 ps->size--; //从逻辑上来说，对于顺序表的尾删，只需要更新有效数据的个数即可，因为在后续插入新元素时，会覆盖原来最后一个元素所占用的空间，所以不需要真正去 “删除” 最后一个元素的数据，这样可以提高操作的效率 }

4.4 顺序表的头插与头删

头插是在顺序表的开头插入一个新元素，这需要将原有的元素依次向后移动一位；头删则是删除顺序表开头的元素，后面的元素依次向前移动一位：

void SeqListPushFront(SeqList* ps, SLDataType x) { CheckCapacity(ps); for (size_t i = psl->size; i > 0; --i) { psl->arr[i] = psl->arr[i - 1]; } psl->arr[0] = x; psl->size++; } void SeqListPopFront(SeqList* ps) { assert(ps);//顺序表不能为空 assert(ps->size);//有效数据个数不能为0 for (int i = 0; i < ps->size - 1; i++)//从第二个有效数据开始，依次往前覆盖，既可达成删除第一个数据的效果 { ps->arr[i] = ps->arr[i + 1]; } ps->size--;//有效数据个数-1 }

4.5 顺序表的任意位置插入与删除

在顺序表的指定位置插入或删除元素，同样需要移动相应位置之后的元素：

void SeqListInsert(SeqList* ps, size_t pos, SLDataType x) { assert(ps);//ps不能为空 assert(pos >= 0 && pos <= ps->size);//判断插入的位置是否有效 //扩容判断 SLCheckcapacity(ps); 让pos及其以后的数据向后挪动一位 for (int i = ps->size; i>pos; i--) { ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos]; } ps->arr[pos] = x;//插入数据 ps->size++;//有效数据个数+1 } void SeqListErase(SeqList* ps, size_t pos) { //ps不能为空 assert(ps); //删除的位置得是有效位置 assert(pos >= 0 && pos<ps->size); for (int i = pos; i<ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; }

4.6 顺序表的查找

// 顺序表查找，返回元素所在位置下标，未找到返回 -1 int SeqListFind(SeqList* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; ++i) { if (ps->arr[i] == x) { return i; } } return -1; }

4.7 顺序表的销毁

// 顺序表销毁，释放动态开辟的内存 void SeqListDestroy(SeqList* ps) { assert(ps); if (ps->arr != NULL) { free(ps->arr); ps->array = NULL; ps->size = 0; ps->capacity = 0; } }

4.8 顺序表的打印

// 顺序表打印 void SeqListPrint(SeqList* ps) { for (size_t i = 0; i < psl->size; ++i) { printf("%d ", ps->arr[i]); } printf("\n"); }

五、顺序表的优缺点

优点：

随机访问效率高：由于元素存储在连续的内存空间中，我们可以通过数组下标直接访问任意位置的元素，时间复杂度为 O (1)。

缓存利用率高：连续存储的特性使得 CPU 缓存能够充分发挥作用，在访问相邻元素时，大概率能从缓存中获取数据，减少对内存的访问次数，提高数据访问效率。

空间利用率高：不需要额外的指针来表示元素之间的逻辑关系，存储密度大，能有效利用内存空间。

缺点：

插入和删除效率低：在顺序表中间或开头插入、删除元素时，需要移动大量的元素，时间复杂度为 O (n)。

空间管理不够灵活：静态顺序表需要预先确定数组大小，容易造成空间浪费或空间不足；动态顺序表虽然可以扩容，但扩容操作也有一定的时间和空间开销。

六、顺序表相关面试题

27. 移除元素 - 力扣（LeetCode）

class Solution { public: int removeElement(vector<int>& nums, int val) { // dst：指向有效元素的下一个位置（待覆盖的位置） int dst = 0; // src：遍历数组，寻找非val的元素 int src = 0; while(src < nums.size()) { // 找到非val元素，覆盖到dst位置，有效区间长度+1 if(nums[src] != val) { nums[dst] = nums[src]; dst++; } // 无论是否找到，继续遍历下一个元素 src++; } // dst的值就是有效元素的个数 return dst; } };

26. 删除有序数组中的重复项 - 力扣（LeetCode）

class Solution { public: int removeDuplicates(vector<int>& nums) { // dst dst：指向当前最后一个不重复的有效元素（初始为第一个元素） int dst = 0; // src：从第二个元素开始遍历，寻找与dst位置不同的元素 int src = 1; while (src < nums.size()) { // 当找到与当前有效元素不同的值时 if (nums[dst] != nums[src]) { // 先将dst后移一位（指向新的待填充位置），再存入当前不重复元素 nums[++dst] = nums[src]; } // 无论是否找到，继续遍历下一个元素 src++; } // 有效元素个数 = 最后一个有效元素的索引 + 1 return dst + 1; } };

88. 合并两个有序数组 - 力扣（LeetCode）

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { // s1：指向nums1中有效元素的最后一位（初始为第m-1个位置） int s1 = m - 1; // s2：指向nums2中有效元素的最后一位（初始为第n-1个位置） int s2 = n - 1; // s3：指向nums1中待填充位置的最后一位（合并后总长度为m+n，初始为m+n-1） int s3 = m + n - 1; // 从后往前比较两个数组的元素，将较大值放入nums1的末尾 // 循环条件：两个数组都还有未处理的元素 while (s1 >= 0 && s2 >= 0) { // 若nums1当前元素更大，将其放到s3位置，同时s1和s3左移 if (nums1[s1] > nums2[s2]) { nums1[s3--] = nums1[s1--]; } // 否则将nums2当前元素放到s3位置，同时s2和s3左移 else { nums1[s3--] = nums2[s2--]; } } // 若nums2还有剩余元素（nums1已处理完），直接将剩余元素依次放入nums1前端 while (s2 >= 0) { nums1[s3--] = nums2[s2--]; } // 若nums1还有剩余元素，无需处理（已在正确位置） } };

以上是我顺序表的笔记，感谢大家的观看！！！

顺序表：数据结构中的高效存储方案

Ne0inhk

一、线性表的概念