当前课程知识点：数据结构 > 第4章 数组 > 4.2 数组的顺序实现 > 讲解
本节，我们来学习数组的顺序实现
先来看存储结构
我们刚才给出的这样一个二维数组，如何存放在内存当中呢
我们知道，内存永远是一个一维的结构
无论是PC机、服务器、手机
无论插了几根内存条
无论内存条上有多少颗存储颗粒
整个系统的内存空间，都是一个一维的线性结构
我们现在要将二维数组
包括多维数组，存放在内存当中
势必要做转换
也就是将多维数组映射为一维的数组
那怎样映射呢
有两种方式
第一种，叫以行为主序的映射方式
具体来说
就是先存放第一行当中的n个元素
再存放第二行的n个元素
一直往后，这叫以行为主序
像C语言、C++、Java、C#
这些编程语言
它们都是以行为主序的编程语言
我们看右边这个图
它实际上就是将左边的m行n列的元素，把它们串行成了
映射成了一个m*n个元素的一维数组
这样，就映射成了一维结构
以便存放在内存当中
还有一些编程语言
是以列为主序的
比如Fortran
它是先存放第一列的m个元素
再存放第二列的m个元素
一直往后
考虑到编程语言的流行程度
我们通常掌握行为主序的，就可以了
因为，列为主序跟行为主序，其实本质差不多
只不过是计算方式有点不一样而已
我们刚才也提到过
所有的高级语言都原生支持数组的语法
所以，在我们这门课当中
没有为数组去定义抽象数据类型
我们也没有去专门编写对应的结构体
我们后面在使用数组的时候
都是直接使用编程语言所提供的数组语法。有一些资料
在讲数组这种数据结构的时候
可能有意地没有用编程语言的数组语法
而是用其他的语法
比如指针，来实现数组
我个人认为
通常是没有必要的
既然编程语言都提供了数组的语法
而且数组这种数据结构对于各种编程语言
它的语法特性
它所支持的操作
在内存当中的存储实质，其实都是差不多的
所以，从这个角度来说
我们直接用数组语法就可以了
没必要去专门地
为了实现数组，而故意不用数组语法
还有一点需要注意
我们这里描述的是二维数组，m行n列
我们用行和列，来描述这两维
如果是多维数组(三维以上)的数组
可能没有一个合适的数学模型，来对应多维数组
所以
这时候，我们用行、列、层这样的概念
描述，就不太合适了
我们现在统一地
最右边的维，就是最低维
最左边的维
就是最高维
我们用高维、低维来描述每一维
这种称法更通用一些
接下来，我们看随机存取
Random Access
简称RA
之前第一章讲顺序表的时候
曾经提到过随机存取
随机存取是顺序存储才具有的特性
它的本质
实际上是做一个加法
我们在一段连续的存储空间当中，找任意一个元素
它的存放位置
应该是这一段连续存储空间的首地址
加上一个偏移量
这里的偏移量就是指目标元素
相对于首地址之间相隔的字节数
我们来看一维数组
我们要在一维数组当中找ai
这个元素的地址，也就是Loc(i)
它等于a0
这个元素的地址，加上i*d
因为，在ai之前一共存放了i个元素
下标是从0开始的，每个元素
占d个字节
所以就是i*d
讲到一维数组的随机存取
我们就不得不提一下
C语言当中，有这样一个等价的写法
ai元素它的地址是等价于a+i的
a作为数组名，在C语言当中表示的是数组所占连续存储空间的首地址
加上i
这样一个偏移量，就是ai元素所占的地址
有些同学可能会问：这里
i为什么没有乘上d呢
主要有两方面原因
第一，C语言是一门高级语言
高级语言的编译器
在处理这个表达式的时候
它会自动地将i乘上d
因为它知道每一个元素的类型
然后看这个类型占多少个字节
从而计算出ai和a0之间的字节相差偏移量
第二个原因
同样是因为C语言是高级语言
高级语言通常不关心一个占据了多个字节的变量当中
除了首字节之外的其他字节，毕竟不是低级语言
毕竟不是汇编，只有汇编这样的语言
它才关心若干个字节当中的非首字节
现在，我们来看二维数组，二维数组
去找某一个元素
它的位置
必须告诉系统两个下标，也就是i、j
我们刚才已经说了
我们是以行序为主序来存放的
先存放下第一行，一直往下，我们存的第一个元素
当然是a00
现在aij的地址
应该是a00的地址
加上(i*n+j)*d
这个很好分析
因为，在aij这一行上面，一共存了i行
注意，i、j下标都是从0开始的
所以，在它上面有i行
每一行
有n列；在aij所在的这一行，位于它前面
一共有j列
所以，再加上j
换句话说
aij前面，一共存了这么多个元素
再乘上每个元素占的字节数d
就是二维数组的随机存取公式
讲到随机存取
我们就不得不提一下内存这种硬件
我们知道，内存它的英文是Random
Access Memory，随机存取存储器
为什么内存叫做随机存取存储器呢
我们知道，内存就是由若干字节线性排列构成的存储空间
每个字节有一个唯一的编号
这个编号
叫做该字节的地址
CPU去访问内存当中的任何一个地址
所耗费的时间，都是一样的
因为，CPU知道这个地址之后
就通过地址总线寻址到该内存单元
然后读写里面的内容
这就是随机存取。内存是一种随机存取设备
那其他的设备呢
有没有不是随机存取的设备呢
我们来看磁带
磁带这种硬件设备
今天我们可能见得比较少了
这是因为硬盘的容量比较大
价格也比较便宜
磁带它的工作原理是这样的
在上面有一个读写头
然后有两个轴，这两个轴
沿着相同的方向转动
在这两个轴上
卷动着一些磁性的存储介质
就是磁带
这些磁带
都缠绕在这两个轴上
磁带转到读写头下面的时候
读写头才能读写这一块区域的数据
假设现在我们要分别读写磁带上两个区域的数据
读写这两个区域的数据所耗费的时间是否一样呢
很明显不一样
而且，读写B区域的数据所耗费的时间要长些
因为B处于靠里的位置
马达得花比较多的时间
才能让B区域的数据转到读写头之下
就像我们小时候用的单放机
当前放的歌，我们不想听了
我们想快进到下第2首歌，或者快进到后面第5首歌
很明显
快进到第5首歌
按快进键的时间是要长一些的
这就是非随机存取，或者说叫顺序存取
它跟随机存取是相对的
现在，我们来看三维数组
我们定义了一个p*m*n的三维数组
为了方便描述
我们用层
行
列
分别描述这三维，根据我们前面讲的
如果以行为主序
也就是以最高维为主序，来存放这个三维数组
先存放的是蓝色背景的这一层
我只画出了前两行
这一层存完了之后，一直往下，存到黄色背景的这一层
最终存放的是绿色背景的这一层
在存放每一层的过程当中
我们依然是按照前面讲的二维数组，先存放
每一行，再存放下一行
这就是三维数组它的存放方式
如果我们找三维数组当中某一个元素aijk
要给出3个下标
它的地址是多少呢
同样，是a000的地址
也就是
存放的第一层左上角的这个地址，加上i*m*n
再加上j*n+k
这个是怎么得来的呢
也很简单
因为，黄色的这一层
在它之前，一共存了i层
每一层有
m*n个元素
在黄色的这一层上面，一共存了j行元素
i、j、k都是从0开始的
这j行，一共有j*n个元素
因为每一行有n列
在aijk所在的这一行之前
一共存了k个元素
所以是这三者之和
再乘上每个元素占的字节数d
这就是三维数组的随机存取公式
现在，我们扩展到多维数组
对于多维数组
可能没有合适的数学模型与多维数组相对应
这时候，我们注意要从本质上理解
多维数组是如何映射到一维结构的
从高到低
如果假设各维的长度是bi
那么，就可以写出多维数组的随机存取公式
这里之所以给出n个下标
是因为我们现在是n维数组
必须给出n个下标
才能唯一确定其中一个元素
它应该是第一个存的这个元素
加上这样一个偏移量
后面这个项
看起来比较复杂
实际上，我们利用数学归纳法
也容易证明出来
大家在课下可以尝试着推导一下
这里，我还想提一下的是，不同的高级语言
对数组特别是多维数组，在内存当中的具体组织方式，可能有所差别
我们刚才描述的这些多维数组
它们在内存当中，是严格地
占据连续的存储单元的
但有些高级语言可能不是这样
比如Java
我们这里给出了一个Java的二维数组
它在内存当中的结构
Java的数组名
并不代表首地址
而是一个对象
实际上是一个引用
比如，我们这里定义了一个3行若干列的
一个二维数组
我们依然可以按照前面讲的
将这样一个二维数组当作一个特殊的一维数组
它包含3个元素
也就是a0、a1、a2
它们分别代表着这个二维数组的3行
它们本质上也是引用
第1行
它包含一个长度为2的一维数组
而第2行，包含一个长度为4的一维数组
也就是这个，大家看到，Java的二维数组每行的列长度是可以不一样的
它不像C语言
这是第一个区别；第二个区别
大家注意到
Java的二维数组，行与行之间所占的内存并不连续
它有可能是断的
这就使得Java的多维数组更加的灵活
对内存的使用更加的灵活
这也是跟我们刚才讲的不太一样的地方
但不管怎么样
这三行元素
它们对应的引用，实际上就是指针
这三个指针占据的内存却是连续的
如果我们把它改成三维数组
比如，这里不是某一个具体的元素
而是另外一个指针
它又指向其他的元素
这也是一个指针
它们的列数也可以不一样
这两个指针占的内存却是连续的
从这个角度来说呢
Java的多维数组，其实本质上跟我们刚才讲的
多维数组依然是吻合的
只不过有一些细节不一样
比如，列数可以不同
比如，每一行所占的空间可以不连续
这个需要注意
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
