线性表的顺序存储及其基本操作：实现与复杂度分析

1. 什么是顺序存储？

顺序存储（Sequence Storage）也称为顺序表，是指用地址连续的一段存储空间依次存放线性表中的元素，使得“逻辑相邻”与“物理相邻”一一对应。

• 定义：设线性表长度为 n，在内存中申请 n 个相邻的单元 elem[0…n−1]，即构成线性表 SqList 的基础结构 (维基百科)。

2. 基本操作的实现

2.1 访问（随机读取）

• 功能：根据下标 i 直接访问元素 elem[i]。

• 伪代码：

  c 复制代码

  Element GetElem(SqList *L, int i) {
      if (i < 0 || i >= L->length) error;
      return L->elem[i];
  }

2.2 插入

• 功能：在位置 i 之前插入新元素 x。

• 实现思路：

  1. 检查 i 合法性；
  2. 从 length−1 向 i 依次后移元素；
  3. 将 elem[i] = x，length++。

• 伪代码：

  c 复制代码

  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 的元素并返回该元素。

• 实现思路：

  1. 检查 i 合法性；
  2. 保存 elem[i]；
  3. 从 i+1 到尾部依次前移元素；
  4. length--；
  5. 返回保存的元素。

• 伪代码：

  c 复制代码

  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. 动态顺序表（扩容机制）

静态数组容量固定；当元素个数接近或超过容量时，需要重新分配更大的连续空间：

1. 新开辟 newsize = oldsize + Δ（或 oldsize * 2）的内存；
2. 将旧数据复制到新空间；
3. 释放旧内存，更新指针和容量。

动态顺序表示例（C 语言）详见维基教程 (维基百科)。

4. 操作复杂度分析

5. 小结与外链资源

本文从顺序存储的概念、基本操作实现、动态扩容机制到时间复杂度分析，全面梳理了线性表的顺序存储。

• 外链推荐：

  • 《顺序表（SeqList）详解》—维基百科 (维基百科)
  • 《顺序表基本操作及复杂度》—知乎专栏 (知乎专栏)
  • C 语言实现示例 — steve.z 博客 (博客园)

希望这篇原创导读能帮助你快速掌握线性表顺序存储与基本操作！

投资学习数据结构，你的算法之路更平坦。加油！