数组

数组是“以自然数初始段为定义域的有限函数”在机器上的直接化身：下标算术取代了查找，这就是随机访问快的全部原因——地址由一次乘加算出，与 $n$ 无关。对比链式结构，访问第 $i$ 项必须沿指针走 $i$ 步；数组用“位置可计算”换来了“长度难伸缩”，这一取舍贯穿数据结构设计的始终。抽象与实现宜分开看：接口层面数组只是索引映射，内存连续性属于实现层，但由它带来的缓存局部性正是工程中数组常胜过指针结构的原因。

数组 $[a_0,a_1,a_2]$ 的合法下标是 $0,1,2$，访问 $A[3]$ 越界——抽象函数在 $3$ 处根本无定义，而实现层面可能读到无关内存，这是大量安全漏洞的来源。行主序的具体一例：$2$ 行 $3$ 列的数组中，$A[1][2]$ 的线性偏移为 $1\cdot 3+2=5$，恰是最后一个元素。

边界情形多源于“数组”一词的多义。定长数组与动态数组不是同一个 ADT：后者添加了改变长度的操作，其尾部追加的 $O(1)$ 是摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。意义下的，单次搬迁仍是 $\mathrm{\Theta }(n)$。$O(1)$ 随机访问依赖顺序存储：若用链表公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。实现同一接口，按下标读取退化为 $O(i)$。下标从 $0$ 还是 $1$ 开始只是约定，但混用两种约定是差一错误的高发地。

长度为 $n$ 的零基数组合法索引为 $0,\dots ,n-1$，地址公式为 base + i * sizeof(T)。越界访问在低级语言中不自动产生合法元素；尾部追加、容量翻倍及其摊还证明由动态数组条目统一处理。

数组是大量上层结构的底座：二分查找公理库二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。依赖 $O(1)$ 定位中点；二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。用下标算术隐式编码完全二叉树；前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。与差分技巧在数组上完成区间统计与批量更新。矩阵与表格数据按行主序或列主序落成数组，图的邻接矩阵也用二维下标把边查询化为常数时间；哈希表的桶、原地排序的工作区以及强调顺序扫描与缓存命中的算法同样以连续数组承载。动态数组公理库动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。另加长度和容量状态，其尾部追加只给摊还 $O(1)$，不改变本页定长数组的接口中心。

“随机访问 $O(1)$”必须绑定到能在一个机器字中表示下标并按字寻址的 RAM 模型。简洁位向量公理库简洁位向量succinct bit vector · rank-select bit vector以 n+o(n) 位表示静态位串，并在 Word-RAM 上常数时间支持 rank 与 select。仍呈现数组式 bit 序列，却把空间压到接近信息下界并额外支持 rank/select；在外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。中，顺序扫描和随机访问应按块传输次数计费，缓存无关模型公理库缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。又要求算法在不知道块大小 $B$ 与缓存容量 $M$ 时维持良好局部性。这些模型解释连续布局的不同成本，不属于数组 ADT 的定义。