线性表的定义与顺序表

复习定位

线性表是最简单、最常用的数据结构——同一类型数据元素的有限序列。顺序表(数组)和链表是线性表的两种存储实现——它们的差异贯穿于所有后续的数据结构选择中。顺序表随机访问O(1)但插入/删除需要O(n)移动元素——适合读多写少的场景。

线性表的定义

线性表(Linear List)是由n(n≥0)个类型相同的数据元素a1,a2,...,an组成的有限序列。n=0时称为空表。相邻元素之间存在有序的前驱-后继关系——同一个线性表中元素不能有多个前驱或后继(集合和树图不是线性关系)。元素的"位置"由序号决定——第i个元素是指第i个下标处的元素。

线性表的抽象数据类型ADT包括：初始化列表/销毁列表/清空元素/判断是否为空/获取长度/按位查找/按值查找/插入元素/删除元素。

顺序表的存储

顺序表用地址连续的内存单元一次存储线性表的各元素——C语言中的数组是天然的顺序表实现。只要知道基地址base和第i个元素——base + (i-1)×sizeof(ElemType)——随机存取—O(1)时间访问任何位置的元素。这是顺序表的最大优势——数组下标直接转换成内存地址。

顺序表需要预分配最大容量MAXSIZE——以及一个变量记录当前元素个数length。插入和删除操作需要移动之后的全部元素以填补空缺——平均移动约一半的元素——时间复杂度O(n)：

// 在第i个位置插入元素e——i从1到length+1
int ListInsert(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length+1) return ERROR; // 位置不合法
    if (L->length >= MAXSIZE) return ERROR; // 已满
    for (int k = L->length-1; k >= i-1; k--)
        L->data[k+1] = L->data[k]; // 从末尾开始后移
    L->data[i-1] = e;
    L->length++;
    return OK;
}

删除第i个元素——从i+1开始到尾部所有元素前移一个位置——O(n)。

顺序表的动态扩容

固定容量(MAXSIZE定的太小)不够灵活。动态顺序表在插入时检测容量——如果length==totalSize——重新分配更大的内存块(通常是原容量的2倍)并复制所有元素到新内存——释放旧内存。均摊分析——n次连续插入的总复杂度O(n)——单次均摊O(1)。

顺序表的优缺点总结

特性	效率	说明
按位查找	O(1)	通过下标直接计算地址
按值查找	O(n)	需要遍历全表(无序时)
插入	O(n)	需要后移元素
删除	O(n)	需要前移元素
空间	连续	预分配、浪费或扩容

顺序表适用于：已知数据规模且以查找为主的场景(如存储32个字节的IP地址表)。不适用于：频繁插入/删除或不确定数据规模的场景。

复习检查

1. 顺序表随机访问L.data[i-1]——计算机是如何将L.data[i-1]这个C语言表达式转换为内存地址的(以base=0x1000,i=5,struct ElemType=8字节为例计算)？

2. 顺序表在第i个位置插入——为什么元素从最后一个开始往后移而不是从i开始往后移——如果从i开始后移——下一步覆盖了什么数据？

3. 顺序表动态扩容使用2倍增长率——每次扩容复制原数组的数据到新数组——为什么这个操作的均摊时间是O(1)而不是O(n)？

4. 插入和删除中i的范围——什么情况下允许i=length+1(在表尾插入)？i=length(删除最后一个元素)是不是不需要移动元素(复杂程度如何)？

5. 顺序表和链表的相比——在什么场景下顺序表明显优于链表——在什么场景下链表更加合适？