数组

前言

在介绍数组之前，我们先介绍下数组和顺序表这些概念。

数组和链表可以看作物理存储的概念：

数组是用一段连续的内存存储，可以随机访问；
链表不要求连续的内存；

像线性表、栈、队列、树、图等等数据结构都是逻辑层的概念。这些逻辑层的概念底层既可以用数组实现，也可以用链表实现。

逻辑结构（abstract data type[4]）

指从逻辑上元素之间是怎样组织的，比如线性表（list/sequemce[4]，元素之间只有线性的关系）、树（tree[5], 一个元素有向地和他的父亲和儿子有关系，同时也可以表示一种物理结构，见下）、图（graph，一个元素和若干元素有向或无向地有关系）。（这里也能看出来树就是一种图而已）。

作者：乔乔-缩头者
链接：https://www.zhihu.com/question/321492926/answer/1574558753

线性表用数组实现叫做顺序表，用链表实现没有特殊的称谓；
树用数组实现没有特殊的命名，用链表实现也一样没有特殊的命名；

数组的定义

数组是具有一定顺序关系的若干对象组成的集合，组成数组的对象称为数组元素。

例如：

向量对应一维数组

$A = (a_0, a_1, ... ,a_{n-1})$

矩阵对应二维数组

$A_{m*n} = \begin{bmatrix} {a_{00}}&{a_{01}}&{\cdots}&{a_{0n-1}}\\ {a_{10}}&{a_{11}}&{\cdots}&{a_{1n-1}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{m-10}}&{a_{m-11}}&{\cdots}&{a_{m-1n-1}}\\ \end{bmatrix}$

数组的存储

n维数组的定义

下标由n个数组成的数组称为n维数组。

例如：

// 一维数组
int[] a = new int[10];

// 二维数组 (面)
int[][] a = new int[2][3];

// 三维数组 (体) 类比: 书(体) [2.页码 3.行 4.列]
int[][][] a = new int[2][3][4];

数组存储的特点

数组元素在内存中按顺序连续存储；
数组的存储分配按照行(C、C++、C#等)或列(Forturn等)进行。
- 按行存储: 1->2->3->4->5->6
- 按列存储: 1->3->5->2->4->6
数组名表示该数组的首地址，是常量；

常用数组的存储

一维数组`a[n]`

个元素按下角标一次存放。

例：int[] a = new int[5];

二维数组a[m][n]

例： int[][] a = new int[2][3];

二维数组每一行由n列，所以每过一行存储空间地址变化是: i * n * c

i代表目标值存储在第几行

n代表一行有多少列，因为需要跨行

三维数组`a[m][n][l]`

第一维下标变化最慢，第三维(最后一维)下标变化最快。

例：int[][][] a = new int[2][3][4]

数组

前言