数组

• 2023-08-09 06:19:45 来源：博客园

学习数据结构和算法中...此文是我学习笔记中的一部分。

(资料图)

数组它是存放数据的基础结构，它必须要申请空间才能使用，并且一旦申请无法改变空间大小。

一维数组

一维数组（或单维数组）是一种线性数组。访问其元素涉及单个下标，该下标可以表示行索引或列索引。例如：datas[0],datas[1],datas[2];

索引从零开始编号

为什么索引从 0 开始编号？

自然数解释

1982 年，Edsger W. Dijkstra 在他的相关笔记《为什么编号应该从零开始》中认为数组下标应该从零开始，因为后者是最自然的数字。

索引从 0 开始，是正确的计算；

for i=0; datas.count; i++; data = datas[i];

索引从 1 开始， i = 1，每次都会 i--；

for i=1; datas.count; i++;  if (i-- == 0) F; else if(i-- == 2) F; // 不可变化的中间逻辑  else data = datas[i];

索引从 1 开始， i = 0，每次都会 i++；

for i=0; datas.count; i++;  if (i == 0) F; else if(i == 2) F;   else data = datas[i++]; // 不影响中间逻辑

索引从 1 开始会多出计算量。

上面伪代码从第一位数据和第三位数据开始处理，其中 0 和 2 是必须的操作，因为不一定是 if 也许是需要别的中间逻辑。

寻址解释

需要将自然数解释的代码代入寻址逻辑，假设 B是固定基址，C是固定常量（有时称为地址增量或步幅）。

如果数组索引从 1 开始，公式是 B+C x (i +1);或者有中间逻辑出现 f(i--);B + C × i;。

数组索引从 0 开始，对于具有线性寻址的向量，具有索引 i 的元素位于地址 B + C × i处。

多维数组

对于多维数组，索引为 i，j的元素的地址为 B+ c·i+ d·j，其中系数 c和 d分别是行地址增量和列地址增量。例如：datas[2][2];

紧凑布局

通常选择系数，以便元素占据连续的内存区域。但是，这不是必需的。即使数组始终使用连续元素创建，某些数组切片操作也可能从中创建不连续的子数组。

二维数组有两种系统的紧凑布局。例如矩阵，假设有这样一个数据 d = [[1,2,3],[4,5,6],[7,8,9]]

行主顺序：假如一行有三条连续摆放。d[0][0] d[0][1] d[0][2] ， d[1][0] = 1 2 3 ，4；

列主顺序：假如一列有三条连续摆放。d[0][0] d[1][0] d[2][0] ， d[0][1] = 1 4 7 ，2；

对于具有三个或更多索引的数组，“行主顺序”将索引元组在最后一个索引中仅相差一个的任意两个元素放在连续位置。“列主顺序”类似于第一个索引。

调整大小

静态数组的大小在创建时是固定的，因此不允许插入或删除元素。但是，通过分配新数组并将旧数组的内容复制到其中，可以有效地实现数组的动态版本（动态数组）;如果不经常执行此操作，则在数组末尾插入只需要摊销的常量时间。

非线性公式

偶尔会使用更复杂的（非线性）公式。例如，二维三角形数组。

尺寸

数组的维度是选择元素所需的索引数。因此，如果将数组视为一组可能的索引组合上的函数，则它是其域是离散子集的空间维度。因此，一维数组是数据列表，二维数组是数据的矩形，三维数组是数据块，等等。这不应与具有给定域的所有矩阵的集合的维度（即数组中元素的数量）混淆。例如，具有 5 行和 4 列的数组是二维的，但这样的矩阵形成 20 维空间。类似地，三维向量可以用大小为三的一维数组表示。

标签：

推荐阅读

猜您喜欢