顺序表完全指南：从原理到实现

引言在数据结构的学习中线性表是最基础也是最重要的数据结构之一。线性表是n个数据元素的有限序列这些元素具有相同的特性。线性表从存储结构上分为两种顺序表物理地址连续数组链表物理地址不连续逻辑上连续通过指针连接顺序表采用数组存储数据元素在内存中物理地址连续可以通过下标直接访问任意元素时间复杂度为O(1)。今天我们将从零开始实现一个完整的顺序表涵盖初始化、增删改查、反转、合并等核心操作。第一部分顺序表的基本概念一、什么是顺序表顺序表是用一段连续的物理内存来存储数据元素的线性结构。在C语言中通常使用数组来实现。二、顺序表结构体设计#include stdio.h #include assert.h #include stdlib.h #include string.h #include stdbool.h #define MAX_SIZE 100 // 顺序表结构体 struct SeqList { int arr[MAX_SIZE]; // 存储数据的数组固定大小 int seqsize; // 当前元素个数 int capacity; // 最大容量 };结构体成员说明成员类型作用arrint数组存储实际数据seqsizeint记录当前有多少个有效元素capacityint记录数组的最大容量第二部分顺序表的基础操作一、初始化原理将顺序表的元素个数设为0容量设为最大值。void InitSeqList(struct SeqList* ps) { assert(ps ! NULL); // 断言确保指针不为空 ps-capacity MAX_SIZE; // 设置容量 ps-seqsize 0; // 初始没有元素 }二、判空与判满判空用于判断顺序表是否为空在删除操作前需要检查。bool IsEmpty(struct SeqList* ps) { assert(ps ! NULL); return ps-seqsize 0; }判满用于判断顺序表是否已满在插入操作前需要检查。bool IsFull(struct SeqList* ps) { assert(ps ! NULL); return ps-seqsize ps-capacity; }三、打印顺序表void Print(struct SeqList* ps) { assert(ps ! NULL); for (int i 0; i ps-seqsize; i) { printf(%d , ps-arr[i]); } printf(\n); }第三部分插入操作一、尾插在末尾插入原理直接在seqsize位置放入新元素因为数组下标从0开始seqsize正好是下一个空闲位置。// 时间复杂度O(1) bool Insert_Back(struct SeqList* ps, int val) { assert(ps ! NULL); if (IsFull(ps)) return false; ps-arr[ps-seqsize] val; ps-seqsize; return true; }示意图二、头插在头部插入原理将所有元素向后移动一位然后将新元素放在第一个位置。// 时间复杂度O(n) bool Insert_Front(struct SeqList* ps, int val) { assert(ps ! NULL); if (IsFull(ps)) return false; // 将arr[0]到arr[seqsize-1]整体向后移动1位 memmove(ps-arr 1, ps-arr, sizeof(ps-arr[0]) * ps-seqsize); ps-arr[0] val; ps-seqsize; return true; }示意图三、按下标插入原理将index位置含之后的元素向后移动一位然后在index位置放入新元素。// 时间复杂度O(n) bool Insert_Index(struct SeqList* ps, int val, int index) { assert(ps ! NULL); if (IsFull(ps)) return false; if (index ps-seqsize || index 0) return false; // 将index及之后的元素向后移动 memmove(ps-arr index 1, ps-arr index, sizeof(ps-arr[0]) * (ps-seqsize - index)); ps-arr[index] val; ps-seqsize; return true; }四、按位置插入位置从1开始原理与按下标插入类似但位置从1开始计数更符合人的习惯。位置pos对应的下标是pos-1。// 时间复杂度O(n) bool Insert_Pos(struct SeqList* ps, int val, int pos) { assert(ps ! NULL); if (IsFull(ps)) return false; if (pos 1 || pos ps-seqsize 1) return false; // pos-1 是实际的下标 memmove(ps-arr pos, ps-arr pos - 1, sizeof(ps-arr[0]) * (ps-seqsize - pos 1)); ps-arr[pos - 1] val; ps-seqsize; return true; }第四部分删除操作一、尾删在末尾删除原理只需将seqsize减1即可原来最后一个元素变为“无效”下次插入会覆盖。// 时间复杂度O(1) bool Pop_Back(struct SeqList* ps) { assert(ps ! NULL); if (IsEmpty(ps)) return false; ps-seqsize--; return true; }二、头删删除头部原理将第二个元素开始的所有元素向前移动一位覆盖第一个元素。// 时间复杂度O(n) bool Pop_Front(struct SeqList* ps) { assert(ps ! NULL); if (IsEmpty(ps)) return false; memmove(ps-arr, ps-arr 1, (--ps-seqsize) * sizeof(int)); return true; }示意图三、按下标删除// 时间复杂度O(n) bool Pop_Index(struct SeqList* ps, int index) { assert(ps ! NULL); if (IsEmpty(ps)) return false; if (index 0 || index ps-seqsize) return false; memmove(ps-arr index, ps-arr index 1, sizeof(int) * (ps-seqsize - index - 1)); ps-seqsize--; return true; }四、按位置删除// 时间复杂度O(n) bool Pop_Pos(struct SeqList* ps, int pos) { assert(ps ! NULL); if (IsEmpty(ps)) return false; if (pos 1 || pos ps-seqsize) return false; memmove(ps-arr pos - 1, ps-arr pos, sizeof(int) * (ps-seqsize - pos)); ps-seqsize--; return true; }五、按值删除删除所有匹配的元素原理使用双指针法将所有不等于val的元素保留下来覆盖到数组前面。// 方法1遍历删除边删边移动 bool Pop_Val1(struct SeqList* ps, int val) { assert(ps ! NULL); if (IsEmpty(ps)) return false; bool found false; for (int i 0; i ps-seqsize; i) { if (val ps-arr[i]) { // 删除找到的元素后面的元素前移 memmove(ps-arr i, ps-arr i 1, sizeof(int) * (--ps-seqsize - i)); i--; // 继续检查当前位置原i1已移到i found true; } } return found; } // 方法2双指针法更高效一次遍历完成 bool Pop_Val2(struct SeqList* ps, int val) { assert(ps ! NULL); if (IsEmpty(ps)) return false; int j 0; // 新数组的写入位置 for (int i 0; i ps-seqsize; i) { if (ps-arr[i] ! val) { ps-arr[j] ps-arr[i]; } } // 如果所有元素都被保留说明没有找到val if (j ps-seqsize) return false; ps-seqsize j; return true; }双指针法示意图第五部分顺序表的高级操作一、交换函数辅助函数void swap(int* a, int* b) { // 不使用临时变量的交换加减法 *a *a *b; *b *a - *b; *a *a - *b; // 注意此方法可能导致溢出生产环境中使用临时变量更安全 } // 更安全的版本 void swap_safe(int* a, int* b) { int temp *a; *a *b; *b temp; }二、反转顺序表原理双指针法从两端向中间交换元素。// 时间复杂度O(n) void Reverse_SeqList(struct SeqList* ps) { assert(ps ! NULL); if (IsEmpty(ps)) return; int left 0; int right ps-seqsize - 1; while (left right) { swap(ps-arr[left], ps-arr[right]); left; right--; } }示意图三、顺序表相加大数加法原理将两个顺序表当作数字每个元素是一位数字相加得到新的顺序表。// 类似大数加法的思路 void Add_SeqList1_SeqList2(struct SeqList* ps1, struct SeqList* ps2, struct SeqList* result) { assert(ps1 ! NULL ps2 ! NULL result ! NULL); // 如果两个都为空直接返回 if (IsEmpty(ps1) IsEmpty(ps2)) return; // 如果其中一个为空直接复制另一个 if (IsEmpty(ps1)) { memmove(result-arr, ps2-arr, ps2-seqsize * sizeof(ps2-arr[0])); result-seqsize ps2-seqsize; return; } if (IsEmpty(ps2)) { memmove(result-arr, ps1-arr, ps1-seqsize * sizeof(ps1-arr[0])); result-seqsize ps1-seqsize; return; } int carry 0; // 进位 int i ps1-seqsize - 1; int j ps2-seqsize - 1; // 从最低位数组末尾开始相加 while (i 0 || j 0 || carry) { if (i 0) carry ps1-arr[i--]; if (j 0) carry ps2-arr[j--]; // 头插结果保证顺序正确 Insert_Front(result, carry % 10); carry / 10; } }示例ps1: [1, 2, 3] → 数字 123 ps2: [9, 8, 7] → 数字 987 相加123 987 1110 结果[1, 1, 1, 0]第六部分综合测试int main() { struct SeqList s1, s2, result; // 初始化顺序表1 InitSeqList(s1); Insert_Front(s1, 1); Insert_Front(s1, 2); Insert_Front(s1, 3); printf(顺序表1: ); Print(s1); // 3 2 1 // 初始化顺序表2 InitSeqList(s2); Insert_Front(s2, 9); Insert_Front(s2, 8); Insert_Front(s2, 7); printf(顺序表2: ); Print(s2); // 7 8 9 // 顺序表相加 InitSeqList(result); Add_SeqList1_SeqList2(s1, s2, result); printf(相加结果: ); Print(result); // 1 1 1 0 // 反转测试 Reverse_SeqList(result); printf(反转后: ); Print(result); return 0; }第七部分顺序表操作复杂度总结操作时间复杂度说明尾插O(1)直接写入头插O(n)需要移动所有元素按位置插入O(n)需要移动插入位置后的元素尾删O(1)直接减小size头删O(n)需要移动所有元素按位置删除O(n)需要移动删除位置后的元素按值删除O(n)需要遍历查找反转O(n)双指针交换按值查找O(n)遍历查找按下标访问O(1)数组直接索引总结一、顺序表核心要点概念说明物理存储连续内存数组逻辑结构线性结构访问方式下标访问 O(1)插入/删除尾部O(1)中间/头部O(n)容量限制固定大小静态或可扩容动态二、常用操作速查表操作函数名关键点初始化InitSeqList设置seqsize0判空IsEmptyseqsize 0判满IsFullseqsize capacity尾插Insert_Back直接放入seqsize位置头插Insert_Front整体后移再放头部尾删Pop_Back直接seqsize--头删Pop_Front整体前移按值删除Pop_Val双指针法高效反转Reverse_SeqList双指针交换三、memmove vs memcpy函数特点适用场景memmove支持内存重叠元素移动源和目标重叠memcpy不支持内存重叠不重叠的拷贝本文详细介绍了顺序表的实现涵盖了初始化、判空、判满各种插入和删除操作头、尾、按位置、按值反转和加法等高级操作每个操作的时间复杂度分析顺序表是数据结构学习的起点理解其原理对于后续学习链表、栈、队列等数据结构至关重要。学习建议自己动手实现一遍所有函数理解每个操作的时间复杂度注意边界条件的处理学会使用断言assert进行参数检查