【文件属性】：
文件名称：从数组到向量-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2021-07-10 17:12:15
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
§2.1 从数组到向量
2.1.1 数组
C、C++和Java等程序设计语言，都将数组作为一种内置的数据类型，支持对一组相关元素
的存储组织与访问操作。具体地，若集合S由n个元素组成，且各元素之间具有一个线性次序，则
可将它们存放于起始于地址A、物理位置连续的一段存储空间，并统称作数组（array），通常
以A作为该数组的标识。具体地，数组A[]中的每一元素都唯一对应于某一下标编号，在多数高
级程序设计语言中，一般都是从0开始编号，依次是0号、1号、2号、...、n-1号元素，记作：
A = { a0, a1, ..., an-1 } 或者
A[0, n) = { A[0], A[1], ..., A[n - 1] }
其中，对于任何0 i < j < n，A[i]都是A[j]的前驱（predecessor），A[j]都是A[i]
的后继（successor）。特别地，对于任何i 1，A[i - 1]称作A[i]的直接前驱（intermediate
predecessor）;对于任何i n - 2，A[i + 1]称作A[i]的直接后继（intermediate
successor）。任一元素的所有前驱构成其前缀（prefix），所有后继构成其后缀（suffix）。
采用这一编号规范，不仅可以使得每个元素都通过下标唯一指代，而且可以使我们直接访问
到任一元素。这里所说的“访问”包含读取、修改等基本操作，而“直接”则是指这些操作都可
以在常数时间内完成只要从数组所在空间的起始地址A出发，即可根据每一元素的编号，经
过一次乘法运算和一次加法运算，获得待访问元素的物理地址。具体地，若数组A[]存放空间的
起始地址为A，且每个元素占用s个单位的空间，则元素A[i]对应的物理地址为：
A + i s
因其中元素的物理地址与其下标之间满足这种线性关系，故亦称作线性数组（linear array）。