文件名称：从数组到向量-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2024-07-30 10:58:55
数据结构 邓俊辉 清华大学 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）。