|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但是用不同的下标来访问（引用）。如int a[6]；说明了一个一维整型数组a，其中各个整型元素组成了一个向量：a[0], a[1], a[2], a[3], a[4], a[5]。
|
|
|
|
数组还可以是多维数组，但二维以上的多维数组不是线性结构。
|
|
|
|
n维数组是一维数组（向量）的推广。二维数组（也叫矩阵）可看作其元素是一维数组的一维数组（线性表、向量），n维数组可看作其元素是n-1维数组的一维数组（线性表、向量）。n维数组的每个元素处于n个向量中，有n个前驱，也有n个后继。
|
|
|
|
对二维数组来说，给定维数和下标，如何得到数组元素存储位置？设每个数组占用L个内存单元，则二维数组Amn按行优先顺序（下标从0开始），aij的地址为：
|
|
|
|
LOC（i, j）=LOC（0, 0）+（i*n+j）*L
|
|
|
|
二维数组Amn按列优先顺序（下标从0开始），aij的地址为：
|
|
|
|
LOC（i,j）=LOC（0, 0）+（j*m+i）*L
|
|
|
|
对n维数组而言，一旦规定了数组的维数和各维的上下界限，便可为它分配存储空间；反之，只要给出一组下标便可求得相应数组元素的存储位置。以行序为例，设每个数据元素占L个存储单元，则n维数组任意元素的存储位置为：
|
|
|
|
|
|
|
|
|
|
在C语言中，二维数组是按行优先存储的，数组float a[4][5]；的存储顺序为a[0][0], a[0][1], …, a[0][4], …, a[3][0], …, a[3][4], a[2][3]的地址为S+（2×5+3）×4=42，其中S为起始地址。
|
|
|
|
|
|
特殊矩阵是值相同或零元素在矩阵中的分布有一定的规律的矩阵，为了节约空间，常对下列特殊矩阵进行压缩存储。
|
|
|
|
对n阶对称矩阵或下三角矩阵A而言，如下图所示，如按行将a11,a21,a22,a31,a32, …，an1,an2, …, ann存放在某一维数组B[1…（n+1）n/2]中，则某个aij（i≥j）在B中的存储位置可通过数列求和得到。由于第i行前共有i-1行，且元素个数分别为1, 2, …,i-1，则前i-1行的元素个数为：
|
|
|
 n阶对称矩阵或下三角矩阵A
|
|
|
|
|
|
因而，矩阵元素aij在B中的存储位置为k=i（i-1）/2+j（i≥j）。
|
|
|
|
对于三角矩阵，其某个矩阵元素在一维数组中的存储位置可使用此方法类似确定。
|
|
|
|
|
|
若已知某个特殊矩阵的非零元素在一维数组中的存储位置，如何得到该矩阵元素的行和列坐标？下面就以下三角矩阵在一维数组中的存储位置求相应矩阵元素的行和列来加以说明。
|
|
|
|
对4.2.1.2节中的A和B，若k为某个下三角矩阵元素aij在B中的存储位置，则：
|
|
|
|
|
|
初始化i=1，若i（i-1）/2≤k，则i++，直到i（i-1）/2>k，因而可得到行为i-1，列为k-i（i-1）/2。由k求i和j的算法如下：
|
|
|
|
|
|
|
|
稀疏矩阵指矩阵中非零元素很少，且分布没有规律。设二维数组Am×n有N个非零元素，N<<m*n，但它不是特殊矩阵（如对角矩阵）。对稀疏矩阵而言，只存储非零元素。用线性表存储稀疏矩阵的非零元素，除非零元素的值外，还应有一些辅助信息。顺序存储节省存储空间，但插入和删除不方便。稀疏矩阵的表示可用三元组[i,j,aij]来表示，其中，i、j、aij分别表示行列位置和值。由此可见，稀疏矩阵可由表示非零元的三元组和其行列数唯一确定。节点中除元素值外，还有元素所在行、列信息。节点结构如下：
|
|
|
|
|
|
对如下图所示的稀疏矩阵，其三元组表示为（1, 2, 12），（1, 3, 9），（3, 1, -3），（3, 6, 14），（4, 3, 24），（5, 2, 18），（6, 1, 15），（6, 3, -7）。
|
|
|
|
|
|
|
|
|
|
|
|
可利用三元组表实现矩阵的运算（以行序为主序），如矩阵的转置和矩阵的相乘等。
|
|
|
|
对于矩阵am×n转置为bn×m，使a[i, j]=b[j, i]，其中，1≤i≤n, 1≤j≤m，其实现步骤如下。
|
|
|
|
|
|
|
|
|
|
按a.data中三元组的次序进行转置，将转置后的三元组置入b中恰当的位置，如能预先确定M中每一列的第一个非零元在b.data中的相应位置，则转置时可直接放入b.data恰当的位置。先求每一列非零元的个数，设num、cpot两个向量，num[col]表示M中第col列非零元个数，cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
链式存储可方便插入与删除。十字链表为每行和每列的非零元链成循环链表，每个非零元用一个节点表示，其形式如下图所示。
|
|
|
|
|
|
|
|
i、j分别表示该数组某非零元素的行、列值，e表示该非零元素的值。down指向该行的下一行具有相同列的非零元素，right指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
