线性表的顺序存储及其基本操作：实现与复杂度分析
温馨提示：
本文最后更新于 2025年07月20日，已超过 5 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
1. 什么是顺序存储？
顺序存储（Sequence Storage）也称为顺序表，是指用地址连续的一段存储空间依次存放线性表中的元素，使得“逻辑相邻”与“物理相邻”一一对应。
- 定义：设线性表长度为 n，在内存中申请 n 个相邻的单元
elem[0…n−1]，即构成线性表SqList的基础结构 (维基百科)。
2. 基本操作的实现
2.1 访问（随机读取）
- 功能：根据下标 i 直接访问元素
elem[i]。 伪代码：
Element GetElem(SqList *L, int i) { if (i < 0 || i >= L->length) error; return L->elem[i]; }
2.2 插入
- 功能：在位置 i 之前插入新元素
x。 实现思路：
- 检查 i 合法性；
- 从
length−1向 i 依次后移元素； - 将
elem[i] = x，length++。
伪代码：
Status ListInsert(SqList *L, int i, Element x) { if (i < 0 || i > L->length) return FALSE; for (int j = L->length - 1; j >= i; j--) L->elem[j+1] = L->elem[j]; L->elem[i] = x; L->length++; return TRUE; }
2.3 删除
- 功能：删除位置 i 的元素并返回该元素。
实现思路：
- 检查 i 合法性；
- 保存
elem[i]； - 从
i+1到尾部依次前移元素； length--；- 返回保存的元素。
伪代码：
Element ListDelete(SqList *L, int i) { if (i < 0 || i >= L->length) error; Element ret = L->elem[i]; for (int j = i; j < L->length - 1; j++) L->elem[j] = L->elem[j+1]; L->length--; return ret; }
3. 动态顺序表（扩容机制）
静态数组容量固定；当元素个数接近或超过容量时，需要重新分配更大的连续空间：
- 新开辟
newsize = oldsize + Δ（或oldsize * 2）的内存； - 将旧数据复制到新空间；
- 释放旧内存，更新指针和容量。
4. 操作复杂度分析
| 操作 | 时间复杂度 | 说明 | |
|---|---|---|---|
| 访问 | O(1) | 直接根据下标计算地址 | |
| 插入/删除 | O(n) | 最坏情况需移动 n / n−1 个元素 | |
| （扩容） | O(n) | 重新分配并复制所有元素；摊还复杂度一般为 O(1) 或 O(n) 视实现而定 | (知乎专栏) |
5. 小结与外链资源
本文从顺序存储的概念、基本操作实现、动态扩容机制到时间复杂度分析，全面梳理了线性表的顺序存储。
希望这篇原创导读能帮助你快速掌握线性表顺序存储与基本操作！
投资学习数据结构，你的算法之路更平坦。加油！
正文到此结束
- 本文标签： 线性表 数据结构 初始化
- 本文链接： https://code.itptg.com/article/80
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
