顺序表原理与实现：数据结构基础与C语言实践-育师

1. 顺序表基础概念解析

顺序表（Sequential List）是线性表在计算机内存中最基础的存储实现方式。它采用一组地址连续的存储单元依次存放线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。这种"物理相邻反映逻辑相邻"的特性，使得顺序表成为数据结构入门阶段必须掌握的核心内容。

1.1 顺序表的本质特征

顺序表的本质是通过数组实现的线性结构，具有三个关键特性：

物理连续性：所有元素占用一整块内存空间
随机访问能力：通过下标可在O(1)时间内访问任意元素
预分配机制：需要预先分配固定大小的存储空间

在C语言中，典型的顺序表声明如下：

#define MAXSIZE 100 // 最大容量 typedef struct { int data[MAXSIZE]; // 存储数组 int length; // 当前长度 } SeqList;

1.2 顺序表与链表的本质区别

与链表相比，顺序表的优势体现在：

访问效率：随机访问时间复杂度O(1) vs 链表的O(n)
空间利用率：无指针域开销，存储密度=1
缓存友好性：连续存储符合局部性原理

而劣势主要在于：

插入/删除需要移动元素
需要预分配固定空间
扩容成本高昂

2. 顺序表的核心操作实现

2.1 初始化与销毁

顺序表的初始化需要完成两件事：

分配存储空间（静态分配或动态分配）
设置初始长度为0

// 静态初始化 void InitList(SeqList *L) { L->length = 0; } // 动态初始化（更灵活） typedef struct { int *data; // 动态数组指针 int maxSize; // 最大容量 int length; // 当前长度 } DynSeqList; void InitDynList(DynSeqList *L, int size) { L->data = (int*)malloc(size * sizeof(int)); L->maxSize = size; L->length = 0; }

注意：动态分配的顺序表使用后必须手动释放内存，否则会造成内存泄漏

2.2 插入操作的实现细节

插入操作需要考虑三种边界情况：

表满（需扩容或报错）
位置非法（i<1或i>length+1）
正常插入（需移动元素）

// 在位置i插入元素e int ListInsert(DynSeqList *L, int i, int e) { if (i < 1 || i > L->length + 1) return 0; // 位置非法 if (L->length >= L->maxSize) { // 需要扩容 int newSize = L->maxSize * 2; int *newData = (int*)realloc(L->data, newSize * sizeof(int)); if (!newData) return 0; // 扩容失败 L->data = newData; L->maxSize = newSize; } // 移动元素（从后往前） for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j-1]; } L->data[i-1] = e; L->length++; return 1; }

时间复杂度分析：

最好情况（尾部插入）：O(1)
最坏情况（头部插入）：O(n)
平均情况：O(n)

2.3 删除操作的优化实现

删除操作同样需要考虑边界条件，但不需要处理扩容问题：

int ListDelete(DynSeqList *L, int i, int *e) { if (i < 1 || i > L->length) return 0; *e = L->data[i-1]; // 移动元素（从前往后） for (int j = i; j < L->length; j++) { L->data[j-1] = L->data[j]; } L->length--; return 1; }

实用技巧：删除元素后可以考虑缩容，但频繁缩容/扩容会影响性能，建议设置缩容阈值

3. 顺序表的高级应用与优化

3.1 动态扩容策略优化

常见的扩容策略有三种：

固定步长：每次增加固定大小（如+10）
- 优点：实现简单
- 缺点：可能造成空间浪费或多次扩容
倍数扩容：容量变为原来的n倍（通常n=2）
- 优点：摊还时间复杂度O(1)
- 缺点：可能浪费最多n-1的空间
自适应策略：根据历史使用情况动态调整
- 优点：更智能
- 缺点：实现复杂

// 优化的动态扩容实现 int ExpandList(DynSeqList *L) { int newSize = L->maxSize * 1.5; // 1.5倍扩容 if (newSize < L->maxSize + 10) { // 保证最小增量 newSize = L->maxSize + 10; } int *newData = (int*)realloc(L->data, newSize * sizeof(int)); if (!newData) return 0; L->data = newData; L->maxSize = newSize; return 1; }

3.2 特殊顺序表的实现

3.2.1 环形顺序表

通过模运算实现逻辑上的环形结构：

#define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int front; // 队首 int rear; // 队尾 } CircularQueue;

3.2.2 多维顺序表

二维顺序表的两种实现方式：

行优先存储：a[i][j]的位置 = i×列数 + j
列优先存储：a[i][j]的位置 = j×行数 + i

4. 顺序表的典型问题与解决方案

4.1 常见问题排查指南

问题现象	可能原因	解决方案
访问越界	下标未校验	添加边界检查
内存泄漏	未释放动态数组	添加销毁函数
插入失败	表满未扩容	实现自动扩容
性能下降	频繁扩容	调整扩容策略

4.2 经典算法题实战

问题1：删除顺序表中所有值为x的元素

高效解法（时间复杂度O(n)，空间复杂度O(1)）：

void DeleteAllX(DynSeqList *L, int x) { int k = 0; // 记录不等于x的元素个数 for (int i = 0; i < L->length; i++) { if (L->data[i] != x) { L->data[k++] = L->data[i]; } } L->length = k; }

问题2：合并两个有序顺序表

归并思路实现：

void MergeLists(SeqList A, SeqList B, SeqList *C) { int i = 0, j = 0, k = 0; while (i < A.length && j < B.length) { if (A.data[i] <= B.data[j]) { C->data[k++] = A.data[i++]; } else { C->data[k++] = B.data[j++]; } } // 处理剩余元素 while (i < A.length) C->data[k++] = A.data[i++]; while (j < B.length) C->data[k++] = B.data[j++]; C->length = k; }