全屏显示专题章节

数组（array）是由n（n＞1）个相同类型数据元素a₀,a₁,…,a_i,…,a_n－1构成的有限序列,n是数组的长度。其中,数组中的数据元素a_i是一个数据结构,即a_i既可以是线性表中的一个元素,其本身也可以是一个线性表,而线性子表中的每一个数据元素还可以再进行分解。根据数组元素a_i的组织形式不同,数组可以分为一维数组、二维数组及多维（n维）数组等。其中,二维数组又称为矩阵（matrix）。

矩阵中的每一个元素都是一个定长的线性表（一维数组）,都要受到两个关系（即行关系和列关系）的约束,也就是说每个元素都同属于两个线性表。

设A是一个有m行和n列的矩阵,则A可以表示为以下形式。

行向量表示矩阵:A＝（（a₀₀,a₀₁,…,a_0n－1）,（a₁₀,a₁₁,…,a_1n－1）,…,（a_m－10,a_m－11,…,

列向量表示矩阵:A＝（（a₀₀,a₁₀,…,a_m－10）,（a₀₁,a₁₁,…,a_m－11）,…,（a_0n－1,a_1n－1,…,

矩阵中的每个元素由元素值a_ij及一组下标（i,j）来确定。a_ij既属于第i行的行向量,又

属于第j列的列向量。也就是说,除边界元素外,每个元素都恰好有两个直接前驱结点和两个直接后继结点（行向量上的直接前驱结点为a_ij－1和后继结点为a_ij＋1,列向量上的直接前驱结点为a_i－1j和后继结点为a_i＋1j）。并且矩阵只有一个开始结点a₀₀,它没有前驱结点；仅有一个终端结点a_m－1n－1,它没有后继结点。

数组一般不进行插入和删除操作,即结构中元素个数和元素间的关系不变；并且计算机的内存是一维的,多维数组的元素应排成线性序列后存入存储器,所以采用顺序存储方法存储矩阵。

由于矩阵中的数据元素分别属于行向量和列向量,则采用顺序存储结构存储矩阵时,按照存取方式不同,可分为以行为主序存储和以列为主序存储两种方式。

1.以行为主序的存储方式

矩阵以行为主序存储是指将数组中的元素一行接一行地顺序存储在计算机的连续存储空间中,即先存储第1行,然后存储第2行……第i＋1个行向量紧接在第i个行向量后面,依此类推,每一行的元素以从左到右的顺序存储。例如,有m×n矩阵A,在计算机中以行为主的顺序存储序列为:a₀₀,a₀₁,…,a_0,n－1,a₁₀,a₁₁,…,a_1,n－1,…,a_m－1,0,a_m－1,1,a_m－1,n－1,存储形式如图5－1所示。

在矩阵的以行为主序的顺序存储中,假设矩阵中第一个元素a₀₀在计算机中的存储地址为LOC（a₀₀）（基址）,并且每个数据元素占L个存储单元,则矩阵A中任一元素a_ij的存储位置为

在PASCAL和C语言中矩阵按行优先顺序存储。

2.以列为主序的存储方式

矩阵以列为主序存储是指将数组中的元素一列接一列地顺序存储在计算机的连续存储空间中,即先存储第1列,然后存储第2列,依次类推,第j＋1个列向量紧接在第j个列向量后面,每一列的元素以从上到下的顺序存储。对于m×n的矩阵A,在计算机中以列为主的顺序存储序列为:a₀₀,a₁₀,…,a_m－1,0,a₀₁,a₁₁,…,a_m－1,1,…,a_0,n－1,a_1,n－1,…,a_m－1,n－1。其存储形式如图5－2所示。

在矩阵的以列为主序的顺序存储中,假设矩阵中第一个元素a₀₀在计算机中的存储地址为LOC（a₀₀）,且每个数据元素占L个存储单元,则矩阵A中任一元素a_ij的存储位置为

在FORTRAN语言中,矩阵就是按列优先顺序存储的。

下面的例子分别介绍了矩阵的运算和简单应用。

【例5－1】　对于给定的矩阵int a[3][4],若矩阵a的起始地址为1000,并且每个元素长度为4字节,试计算以下内容。

（1）矩阵a中的元素数目。

（2）按行存储时,元素a[1][2]的内存地址。

（3）按列存储时,元素a[1][2]的内存地址。

【解】　（1）由于矩阵的行、列下标值的下界均为0,该矩阵的行上界为3－1＝2,列上界为4－1＝3,所以该矩阵的元素数目共有3×4＝12个。

（2）按行存储时,LOC（1,2）＝LOC（a₀₀）＋（i×n＋j）＝1000＋（1×4＋2）×4＝1024

（3）按列存储时,LOC（1,2）＝LOC（a₀₀）＋（j×m＋i）＝1000＋（2×3＋1）×4＝1028

【例5－2】　有m名学生,每人考n门功课,试编写求任一学生总分数和任一课程总分数的数据结构和算法。

【解】　把学生的考试成绩存放在m行n列的二维数组中,则第i（0≤i＜m）行第j（0≤j＜n）列中存放了第i个学生的第j门课程考试成绩。即其数据结构为: