线性表的顺序表示¶

顺序表的定义¶

顺序表（Sequence List），即线性表的顺序存储结构，用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，通常基于数组实现。

数组 vs 顺序表

数组（Array）：

• 更倾向于一个具象且底层的概念，是物理存储结构，几乎是每一个高级编程语言中原生的数据结构（包括底层的 C）

• 各个编程语言的封装有所差异，概念上往往只关注储存和索引

顺序表（Sequence List）：

• 偏抽象一些，是抽象数据类型/逻辑结构

• 在数据结构中是一个通用的概念，通常封装一些基本操作（如动态扩容、插入、删除等）

顺序表在本质上可看作是数组，其“顺序存储”的特性在编程语言中通常基于数组实现，故二者的数据结构特征基本相同：如连续存储、随机访问（时间复杂度为 \(O(1)\)）等；因此二者在大多数情况下都可理解为同一个东西。

Tip

• 数据结构首先是抽象数据类型（ADT, Abstract Data Type）：定义元素组织、操作集合与复杂度；其实现依语言选取（数组/链表/哈希/树等），同一 ADT 可有多种实现与权衡。

• 编程语言与数据结构中的某些概念之间具有一些微妙的关系。无论是上面提到的顺序表还是后面的各种线性表（如栈、队列等），其在数据结构中的概念都是抽象的逻辑结构，在实际应用中都需要基于不同编程语言中对应的封装来实现，理解二者之间的区别与联系对于进一步理解数据结构的抽象概念是学习过程中可能会遭遇到的重难点。

• 静态分配

  #define MAXSIZE 100
  typedef int ElemType;
  typedef struct {
      ElemType data[MAXSIZE]; // 顺序表的元素
      int length; // 顺序表的长度
  } SqList; // 顺序表的类型定义
  

• 动态分配

  #define INIT_SIZE 100
  typedef int ElemType;
  typedef struct {
      ElemType *data; // 动态分配数组的指针
      int length; // 当前长度
      int MaxSize; // 最大容量
  } SqList; // 顺序表的类型定义
  
  int main() {
      SqList L;
      // 初始动态分配语句
      L.data = (ElemType *)malloc(INIT_SIZE * sizeof(ElemType));
  }
  

  // C++
  L.data = new ElemType[INIT_SIZE];
  

优缺点¶

优点¶

• 空间效率高：元素存储在连续的内存空间，且无需考虑因为表示表中元素之间的逻辑关系而产生额外的结构开销

• 支持随机访问：可在 \(O(1)\) 时间内访问表中的任意元素

缺点¶

• 插入与删除效率低：执行插入或删除元素操作时需要大批量移动表中元素，时间复杂度为 \(O(n)\)

• 定长数组模型约束：当线性表长度变化较大时，难以确定存储空间的容量；若需扩容，开销很大

• 空间利用率不高：

  • 静态分配（基于定长数组）时大小可能会超过实际需求，造成内部内存碎片化

  • 动态扩容（基于动态数组）时，编程语言的扩容策略会导致一些空间浪费，形成外部内存碎片

顺序表上基本操作的实现¶

初始化¶

• 静态分配的顺序表初始化:

  在这种分配模式下，数组空间在初始化时就已确定。

  void InitList(SqList &L) {
      L.length = 0;   // 初始化长度为0
  }
  

• 动态分配的顺序表初始化:

  在初始化时先分配一个预定义的数组空间，并将长度置0；MaxSize 指示顺序表当前分配的存储容量，当存储空间不足时就进行再分配。

  void InitList(SqList &L) {
      L.data = (ElemType *)malloc(INIT_SIZE * sizeof(ElemType));
      L.length = 0;   // 初始化长度为0
      L.MaxSize = INIT_SIZE;   // 初始化最大容量
  }
  

插入¶

在顺序表L的第i个位置插入新的元素e。

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {    // 判断i的范围是否有效
        return false;
    }
    if (L.length >= L.MaxSize) {        // 当前存储空间已满，不能插入
        return false;
    }
    for (int j = L.length; j >= i; j--) {   // 将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;   // 在第i个位置插入新元素
    L.length++;   // 表长加1
    return true;
}

顺序表插入的算法时间复杂度推导如下:

• 最好情况: 在表尾插入 \((i = n + 1)\)，元素后移语句将不执行，时间复杂度为 \(O(1)\)

• 最坏情况: 在表头插入 \((i = 1)\)，元素后移语句将执行 \(n\) 次，时间复杂度为 \(O(n)\)

• 平均情况: 假设在表中任一位置插入的概率相同，即 \(p_i = \frac{1}{n + 1}\)，则元素后移语句的平均执行次数为:

  \[ \frac{1}{n + 1} \sum_{i = 1}^{n + 1} (n - i + 1) = \frac{1}{n + 1} \sum_{j = 1}^{n} j = \frac{1}{n + 1} \cdot \frac{n(n + 1)}{2} = \frac{n}{2} \]

  因此，平均时间复杂度为 \(O(n)\)

删除¶

在顺序表L中删除第i个位置的元素，用引用变量e返回被删除元素的值。

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {    // 判断i的范围是否有效
        return false;
    }
    e = L.data[i - 1];   // 将被删除元素赋值给e
    for (int j = i; j < L.length; j++) {   // 将第i个元素后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--;   // 表长减1
    return true;
}

顺序表删除的算法时间复杂度推导如下:

• 最好情况: 在表尾删除 \((i = n)\)，元素前移语句将不执行，时间复杂度为 \(O(1)\)

• 最坏情况: 在表头删除 \((i = 1)\)，需移动除表头元素外的所有元素，时间复杂度为 \(O(n)\)

• 平均情况: 假设在表中任一位置删除的概率相同，即 \(p_i = \frac{1}{n}\)，则元素前移语句的平均执行次数为:

  \[ \sum_{i=1}^{n} \frac{1}{n}(n - i) = \frac{1}{n} \sum_{j=1}^{n - 1} j = \frac{1}{n} \cdot \frac{(n - 1)n}{2} = \frac{n - 1}{2} \]

  因此，平均时间复杂度为 \(O(n)\)

按值查找¶

在顺序表L中查找第一个值为e的元素，并返回其位序。

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

顺序表按值查找的算法时间复杂度推导如下:

• 最好情况: 查找的元素在表头，仅需比较一次，时间复杂度为 \(O(1)\)

• 最坏情况: 查找的元素在表尾或不存在，需要比较 \(n\) 次，时间复杂度为 \(O(n)\)

• 平均情况: 假设在表中任一位置查找的概率相同，即 \(p_i = \frac{1}{n}\)，则查找语句的平均执行次数为:

  \[ \sum_{i = 1}^{n} \frac{1}{n} i = \frac{1}{n} \sum_{j = 1}^{n} j = \frac{1}{n} \cdot \frac{n(n + 1)}{2} = \frac{n + 1}{2} \]

  因此，平均时间复杂度为 \(O(n)\)

这就是顺序查找. 哨兵写法、有序表上的提前失败, 以及和折半 / 分块的对比见该笔记.