阅读:0       作者:严长生

数据结构之多维数组

数组,所有的程序设计语言学习之初都有它的身影。根据数组中存储的数据元素之间的逻辑关系,可以将数组分为 : 一维数组、二维数组、…、n维数组。

n维数组中,维数 n 的判断依据是:根据数组中为确定元素所在位置使用的最少的下标个数。例如,二维数组中想唯一确定一个元素的位置,至少需要使用 2 个下标, a[1][1]代表二维数组中行坐标为 1,列坐标为 1 的数据元素的值。

数组VS顺序表

数组和顺序表的本质不同。数组作为一种数据类型,作用是将类型相同的数据存储在一整块内存中,数组中存储的数据之间没有任何逻辑关系,谁也不认识谁。

顺序表作为线性表的存储结构,存储的这些数据元素在物理存储结构上相邻的同时,在逻辑结构上也相邻,每个数据元素都清楚地知道紧挨着它的前边的元素和后边的元素。

如果用一句话来描述两者之间的关系,就是:用数组来存储的线性表是顺序表

数组的逻辑结构

一维数组由于本身存储的数据元素类型相同、且各数据元素在逻辑结构上相邻(物理结构上也相邻),是线性表的顺序存储结构的具体实现。可以说:一维数组是线性表的一种表示形式。

一维数组中存储的各成员如果还是一维数组,就变成了二维数组:
图1 二维数组的逻辑结构

图1中,一维数组 b[6] 中每个单元都存放着长度为 6 的数组(例如:b[0] 存放的是 a[6] ,b[1] ~ b[5] 也和 b[0] 一样),就组成了 array[6][6] 的二维数组。

同样,三维数组,也就可以看作是存储二维数组的一维数组;对于 n 维数组来说,可以看作是存储有 (n-1) 维数组的一维数组。

所以,n 维数组可以看作是线性表的一种扩展。

数组的顺序存储结构

数组在存储时有两种存储方式:
  • 以列序为主(先列后行)
  • 以行序为主(先行后列)

例如,a[6][6]以列序存储:
图2 数组的列序存储
以行序存储:
图3 数组的行序存储
C语言中,使用的是以行序为主的顺序存储方式。

数组中调取数据元素

在n维数组中调取数据元素,需要知道以下因素:
  1. 数组存放的起始位置(也就是数组中第一个元素的存储位置)。
  2. 被调取元素在 n 维数组中的具体位置(例如,二维数组需要知道被调取元素 aij 在数组中的行标 i 和列标 j )。
  3. 数组中单个数据元素占用的内存空间,一般用 L 表示(数组中存放的数据的类型都一样)。

如果在以行序存储的二维数组 anm 中查找某个数据元素 aij 的存储位置,方法是:
LOC(i,j) = LOC (0,0) + (i*m+j)*L;
LOC(i,j) :  aij 在内存中的地址;LOC(0,0) : a00 存储的地址,其实就是整个二维数组存放的起始地址。

同样,以列序存储的查找方法是:
LOC(i,j) = LOC (0,0) + (i*n+j)*L;