2.2.1 顺序表：连续地址如何换来随机访问

顺序表用一段连续存储空间依次保存线性表元素。若首元素地址为 $LOC(a_1)$，每个元素占 $s$ 字节，则
$$LOC(a_i)=LOC(a_1)+(i-1)s.$$
因此按位访问只需一次地址计算，时间为 $O(1)$。这里要求同类型元素等长，否则无法只靠位序算出地址。

静态分配把容量写死：

#define MAXSIZE 100
typedef struct { int data[MAXSIZE]; int length; } SqList;

length 是当前元素数，MAXSIZE 是最多能放多少，二者不能互换。合法元素占 data[0] 到 data[length-1]，未用空间不是线性表成员。

动态分配把容量变成运行时状态：

typedef struct { int *data; int length, capacity; } SeqList;

初始化时申请空间；满表扩容时申请更大区域、复制旧元素、释放旧区域并更新指针。扩容后的基地址可能改变，因此不能保留指向旧数组内部的裸指针。单次扩容要 $O(n)$，若容量每次翻倍，连续尾插的均摊成本可为 $O(1)$；每次只增加一个位置则会反复复制，总成本趋于 $O(n^2)$。

陪做：容量 8、长度 5 的表，第 5 个元素位于下标 4；尾部可用位置从下标 5 开始。不能访问下标 5 说它是第 6 个已有元素，它只是预留空间。

错解反馈：认为动态表的物理地址永远连续是错的——某一时刻内部元素连续，但扩容前后基址可变；认为顺序表“无需考虑容量”也错，连续区域必须有明确边界。

迁移练习：初始容量 2，采用二倍扩容，连续尾插 5 个元素时容量序列是什么？答案 2、2、4、4、8；发生两次搬移，分别复制 2 和 4 个元素。独立验收：能根据 length/capacity 画出已用区与空闲区，并解释随机访问为何是 $O(1)$。