数据结构课件110章全第五章数组和广义表幻灯片.ppt

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){ 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]; } }return OK; } 算法分析 这个算法仅比前一个算法多用了两个辅助向量，然而其时间复杂度降为O(nu+tu)，当tu和mu*nu等数量级时，其时间复杂度为O(mu*nu) ，与经典算法的时间复杂度相同。 二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下： typedef struct{ triple data[MAXSIZE+1]; int rpos[MAXRC+1]; int mu,nu,tu; }RLSMatrix; 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。 两个矩阵相乘的经典算法也是大家所熟悉的。若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。 当n1=m2时有： 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*n1*n2)。 当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 e i j e i j e 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 稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。 （1） 为求Q的值，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。为了找到N中匹配的数据，可以利用N的rpos值。 （2）对Q的每一个元素设计一累计和的变量，其初值为零，其累加值Q[i][j]也可能为零。因此乘积矩阵Q中的元素是否为非零元，只有在求得其累加值后才能得知。 （3）由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序，因此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩到Q.data中去。 计算Q＝M × N的过程大致如