|
|
|
|
|
数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但是用不同的下标来访问（引用）。例如int a[6]，表示一个一维整型数组a，其中各个整型元素组成了一个向量：a[0],a[1],a[2],a[3],a[4],a[5]。
|
|
|
|
数组还可以是多维数组，但二维以上的多维数组不是线性结构。
|
|
|
|
n维数组是一维数组（向量）的推广。二维数组（也叫矩阵）可看作是其元素是一维数组的一维数组（线性表、向量），n维数组可看作是其元素是n-1维数组的一维数组（线性表、向量）。n维数组的每个元素处于n个向量中，有n个前驱，也有n个后继。
|
|
|
|
对二维数组来说，给定维数和下标，如何得到数组元素的存储位置？设每个数组占用1个内存单元，则二维数组Amn，按行优先顺序（下标从1开始）计算，aij的地址为：
|
|
|
|
LOC(aij)=LOC(a11)+((i-1)*n+(j-1))*1
|
|
|
|
二维数组Amn按列优先顺序（下标从1开始）计算，aij的地址为：
|
|
|
|
LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*1
|
|
|
|
在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而言，如下图所示。如按行将all，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行的元素个数为：
|
|
|
|
|
|
因而，矩阵元素aij在B中的存储位置为k=i(i-1)/2+j(i≥j)。
|
|
|
|
|
|
|
|
对三对角矩阵，其某个矩阵元素在一维数组中的存储位置可类似确定。
|
|
|
|
|
|
若已知某个特殊矩阵的非零元素在一维数组中的存储位置，如何得到该矩阵元素的行和列坐标呢？下面就以下三角矩阵在一维数组中的存储位置求相应矩阵元素的行和列来加以说明。
|
|
|
|
对本小节"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<ij]来表示，其中，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,4,-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指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。
|
|
|
|
|
|
|
