数据结构基础5.ppt

第五章数组和广义表 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,col,k; int num[0..a.n],copt[0..a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”\n); for(col=1;col=a.u;++col) num[col]=0; for(k=1;k=a.t;++k) ++num[a.data[k].j]; cpot[0]=1; for(col=2;col=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++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，其值在稀疏矩阵的初始化函数中确定。 矩阵乘法的精典算法: 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) 当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为： 0 0 5 0 -1 0 0 2 0 0 0 M= 0 2 1 0 -2 4 0 0 N= 则Q=M*N为： 0 6 -1 0 0 4 Q= 它们的三元组、和分别为： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data Q初始化； if Q是非零矩阵 { // 逐行求积 for (arow=1; arow=M.mu; ++arow) { // 处理M的每一行 ctemp[] = 0; // 累加器清零 计算Q中第arow行的积并存入ctemp[] 中； 将ctemp[] 中非零元压缩存储到Q.data； } // for