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

引言

在数据结构的学习中，线性表是最基础也是最重要的数据结构之一。线性表是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; // 最大容量 };

结构体成员说明：

第二部分：顺序表的基础操作

一、初始化

原理：将顺序表的元素个数设为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--; // 继续检查当前位置（原i+1已移到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; }

第七部分：顺序表操作复杂度总结

总结

一、顺序表核心要点

二、常用操作速查表

三、memmove vs memcpy

本文详细介绍了顺序表的实现，涵盖了：

• 初始化、判空、判满

• 各种插入和删除操作（头、尾、按位置、按值）

• 反转和加法等高级操作

• 每个操作的时间复杂度分析

顺序表是数据结构学习的起点，理解其原理对于后续学习链表、栈、队列等数据结构至关重要。

学习建议：

1. 自己动手实现一遍所有函数

2. 理解每个操作的时间复杂度

3. 注意边界条件的处理

4. 学会使用断言（assert）进行参数检查