数组和广义表教学幻灯片讲义.pptVIP

例如: ? a (x, y) ((x)) LS=( a, (x,y), ((x)) ) 思路二 按照M.data中三元组的次序进行转置，并将转置后置入T中恰当的位置。要找到这个恰当位置，必须预先知道M中每一列的非零元在T中的位置。 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 2 1 14 5 1 -5 2 2 -7 1 3 36 4 3 28 M T 那么如何确定每一行的第一个非零元在三元组中的位置？ cpot[1] = 1; for (col=2; col=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; M的第col列的第一个非零元转置后在T的位置 Status FastTransposeSMatrix(TSMatrix M, TSMatrix T){ T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col=M.nu; ++col) num[col] = 0; for (t=1; t=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p=M.tu; ++p) { } } // if return OK; } // FastTransposeSMatrix 转置矩阵元素 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]//第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, 其值在稀疏矩阵的初始化函数中确定（目的是增加其随机存储特性）。 图4-6 （矩阵T） 例如：给定一组下标，求矩阵的元素值 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 时间复杂度为O（c） 接近于常数阶，具有一定随机存储特征 矩阵相乘 矩阵乘法的精典算法: for (i=1; i=m1; ++i) for (j=1; j=n2; ++j) { Q[i][j] = 0; for (k=1; k=n1; ++k) Q[i]