51 数组的类型定义.ppt

特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 对称矩阵 三对角矩阵 对称矩阵的压缩存储 设有一个 n?n 的对称矩阵 A。 为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 n + ( n - 1 ) + ??? + 1 = n*(n+1)/2 个元素。 三对角矩阵的压缩存储 三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B[0]。 在三条对角线上的元素aij 满足 0 ? i ? n-1, i-1 ? j ? i+1 在一维数组 B 中 A[i][j] 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 A[i][j] 在 B 中位置为 k = 2*i + j。 Col = M.data[p].j; q = cpot[col]; T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col] 分析算法FastTransposeSMatrix的时间复杂度： 时间复杂度为: O(M.nu+M.tu) for (col=1; col=M.nu; ++col) … … for (t=1; t=M.tu; ++t) … … for (col=2; col=M.nu; ++col) … … for (p=1; p=M.tu; ++p) … … 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。 二、行逻辑联接的顺序表 #define MAXMN 500 typedef struct { Triple data[MAXSIZE + 1]; int rpos[MAXMN + 1]; int mu, nu, tu; } RLSMatrix; // 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos, 其值在稀疏矩阵的初始化函数中确定。 例如：给定一组下标，求矩阵的元素值 ElemType value(RLSMatrix M, int r, int c) { p = M.rpos[r]; while (M.data[p].i==r M.data[p].j c) p++; if (M.data[p].i==r M.data[p].j==c) return M.data[p].e; else return 0; } // value 矩阵乘法的精典算法: for (i=1; i=m1; ++i) for (j=1; j=n2; ++j) { Q[i][j] = 0; for (k=1; k=n1; ++k) Q[i][j] += M[i][k] * N[k][j]; } 其时间复杂度为: O(m1×n2×n1) Q初始化; if Q是非零矩阵 { // 逐行求积 for (arow=1; arow=M.mu; ++arow) { // 处理M的每一行 ctemp[] = 0; // 累加器清零 计算Q中第arow行的积并存入ctemp[] 中； 将ctemp[] 中非零元压缩存储到Q.data； } // for arow } // if 两个稀疏矩阵相乘（Q?M?N）的过程可大致描述如下： Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix Q) { if (M.nu != N.mu) re