5.1 数组定义和表示在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节开始我们讨论第5章数组

首先介绍一下数组的定义

在这里，我们把数组看成是一种特殊的线性表

其特殊性在于表中的数据元素本身也是一个线性表

我们以二维数组为例

如果把二维数组的每行或者每列看成是一个数据元素的话

因每行或者每列本身就是一个线性表

那么二维数组就是一个数据元素为线性表的线性表

下面我们通过数据类型的定义方式来说明一下这个问题

我们首先定义了一个数组类型array2

它是一个的数据元素为elemtype的m行n列的二维数组类型

好，下面我们换一种定义方式

首先定义了一个数组类型array1

它是一个数据元素为elemtype的长度为n的一维数组类型

随后我们又定义了一个数组类型array2

它是一个数据元素为array1的长度为m的一维数组类型

两个array2虽然从他们的定义方式来看不同

但是从效果来看，两种定义的结果是等价的

都是定义一个M行和n列的二维数组类型

第2种定义方式

把一维数组类型array1看做一个元素类型

体现了二维数组是一个数据元素是为一维线性表的线性表

那么，同样的道理

三维数组可以看成是以二维数组为数据元素的线性表

依次类推

n维数组可以看成是以n-1为数组为数据元素的线性表

下面我们看一下数组的顺序表示和实现

数组一旦定义以后，其存储的元素类型就确定

存储元素的个数也被确定

也就是说，数组需要的存储空间大小

也就确定下来了

在已经明确存储空间大小的情况下

用顺序存储实现数组就比较自然了

数组的存储，会遇到一个问题

由于计算机的内存结构是一维的

不管它内存有多大，内存地址都是连续编号的

图中给出了内存结构的一个实例

内存地址从0000000连续编址

那么，我们分配给数组的存储空间

也是一维的一块连续空间

但数组呢？

在逻辑结构上是多维的

我们遇到的问题就是

要把逻辑结构上多维的数组存储到一维的内存空间中

为了实现多维数组的存储，就必须按照某种次序

把多维数组中的数组元素排成一个一维的序列

然后按照这个一维的序列把数组存储到一维的内存当中

下面我们仍然以二维数组为例，看一下它的存储实现

示例是一个M行和n列的二维数组

要把这样一个二维的结构变成一个一维的序列

有两种方式，称为行序和列序

行序意思就是说，在一维空间中存储的时候

先存第0行，再存第一行

依次类推，最后存m-1行

类似的，以列序存放的时候

我们先存第0列，再存第1列

最后存n-1列，以这样的方式

就把一个二维结构转为一个一维的序列

用这样的方式实现了二维数组的存储

下面我们看一下以行序实现二维数组存储的图示

以行序为主序存放

具体来说就是先存第1个元素a00，随后存a01

一直到a0,n-1，把第一行的n个元素存完

随后从a10开始存第2行，以此类推。最后存，第n-1行

不管是行序也好列序也好

我们都可以实现二维数组的存储

这个时候，我们又需要考虑一个问题

就是二维数组元素的存取，大家在编程的时候

可能都注意到了，我们存取二维数组元素的时候

是按逻辑结构来使用它的，也就是用下标

比如说存取a[i][j],意思就是说我们现在需要存取

二维数组中第i行第j列的这个元素

从刚才的讨论当中，我们注意到

二维数组是被化为一维的序列来实现存储的

那么,我们就需要解决一个问题

如何从数组元素的逻辑下标找到该元素在内存单元当中的具体地址

以实现对该元素的存取

我们以行序为例，要存取a[i][j]

如何从下标i,j计算出该元素在内存中的存储地址

数组空间的起始地址LOC(0,0)我们是知道的

C语言中数组名就是数组空间的起始地址

那么，求LOC(i,j)的核心问题实际上是要求一个偏移

也就是要求出按行序存放的时候

a[i][j]这个元素之前他存了多少个元素？

设列数是b2，就是每行有b2个元素

从0行开始，在第i行前面

存了0到i-1行，共i行

b2*i求出这i行元素的总数

在第i行中，a[i][j]是第j个

我们用b2*i+j就得到了a[i][j]这个元素之前他存了多少个元素

由此得到LOC(i,j)的计算公式

LOC(i, j)=LOC(0, 0)+(b2*i+j))

总的来说，求数组当中某个元素的具体存储地址

就是用数组起始地址加上在该元素之前已存储的数据元素的个数

当然，编程时我们并不用关心这个问题

系统内部会进行计算和映射

但是我们应该明白其原理

类似的套路，我们会在矩阵压缩中使用

这样行序和列序的方式

可以推广到多维数组的情况

分别称为行优先顺序和列优先顺序

行优先顺序就是规定，先排最右的下标

随后从右到左，最后排最左的下标

二维数组中就是，a00之后后排a01，a 02

排完a0，n-1之后

排左边的一个下边，那么下一个排的就是a10

列优先的话

就是a00之后排a10，a20，先排最左的下标

排完am-1,0以后

排右边的一个下标，下一个呢排a01以此类推

多维数组不过是下标的个数多一些

道理是一样的

多维数组具体的计算公式大家可以看一下教材当中的内容

同学们，这节课我们就讲到这儿

下次课再见