形式陈述

长度为 $n$ 的数组可抽象为函数

$$A:\{0,1,\dots ,n-1\}\to V,$$

并提供按下标读取与更新。顺序存储实现通常使随机访问为 $O(1)$，但插入、删除和扩容代价取决于位置与实现模型。

直觉

数组把有限序列映到连续整数下标。抽象层面是定长索引映射；内存连续属于常见实现及其性能原因。

例子与边界

数组 $[a_0,a_1,a_2]$ 的合法下标为 $0,1,2$，访问 $A[3]$ 越界。动态数组通过预留容量和偶尔搬迁实现摊还常数尾插，但它与固定数组不是完全相同的 ADT。

推论与应用

数组是二分查找、堆、矩阵和表格数据的基础表示。缓存局部性使它在工程中常优于指针结构，但该优势不属于纯功能定义。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapter 10。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, §1.4。