本文共 2855 字，大约阅读时间需要 9 分钟。

行逻辑链表的顺序表

为了便于随机存取任意一行的非零元，则需要知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵中的算法创建的，指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种"带行链接信息"的三元组表为行逻辑链接的顺序表。

描述如下：

typedef struct{	Triple data[MAXSIZE + 1];	//非零元三元组表	int rpos[MAXRC + 1];	//各行第一个非零元的位置表	int mu, nu, tu;		//矩阵的行数、列数和非零元个数}RLSMatrix;

这里的MAXSIZE在上一节有交代。这个data[MAXSIZE+1]为什么要加一呢，因为data[0]未用，同样rpos[MAXRC+1]也是这个道理。

如下图所示：

P·S:本人字丑，大家将就看吧。

另外大家要知道矩阵相乘的条件：矩阵只有当左边矩阵的列数等于右边矩阵的行数时,它们才可以相乘,乘积矩阵的行数等于左边矩阵的行数,乘积矩阵的列数等于右边矩阵的列数。

这样我们就知道，当一个不用三元组表示的矩阵M(m1行n1列)和一个矩阵n(m2行n2列)相乘时，有一个经典算法，就和上面那数学运算一模一样。

代码如下：

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];		}	}}

因为产生的矩阵是m1行n2列的矩阵，所以第一个for里面限定条件是m1,第二个for限定条件是n2,第三个for就是把第一个矩阵里面的行和第二个矩阵的列相乘并且加起来。这个Q[i][j]的作用就是先把存储到那一块的内存初始化，免得有其他数据影响。

也就是说当M和N是稀疏矩阵并用三元组表作存储结构时，不能用上面那个算法。

如下面这个例子：

那么，他们的三元组M.data、N.data和Q.data分别为：

在此补充下rpos

矩阵N的rpos值(代码中会用到)

矩阵M的rpos值

下面给出书中的伪代码：

2017年版的严蔚敏版数据结构

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {	// 求矩阵乘积Q=M*N，采用行逻辑链接存储表示。	int arow, brow, p, q, t, ctemp[30], l, ccol, tp;	if (M.nu != N.mu) 		return ERROR;	Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;       // Q初始化	if (M.tu*N.tu != 0) 	{   // Q是非零矩阵		for (arow = 1; arow <= M.mu; ++arow) 		{      // 处理M的每一行			for (l = 1; l <= M.nu; ++l) 				ctemp[l] = 0; // 当前行各元素累加器清零			Q.rpos[arow] = Q.tu + 1;			if (arow < M.mu) 				tp = M.rpos[arow + 1];			else 				tp = M.tu + 1;			for (p = M.rpos[arow]; p < tp; ++p) 			{ // 对当前行中每一个非零元    				brow = M.data[p].j;          // 找到对应元在N中的行号				if (brow < N.mu) 					t = N.rpos[brow + 1];				else 					t = N.tu + 1;				for (q = N.rpos[brow]; q< t; ++q) 				{					ccol = N.data[q].j;            // 乘积元素在Q中列号					ctemp[ccol] += M.data[p].e * N.data[q].e;				} // for q			} // 求得Q中第crow( =arow)行的非零元			for (ccol = 1; ccol <= Q.nu; ++ccol) // 压缩存储该行非零元			if (ctemp[ccol]) 			{				if (++Q.tu > MAXSIZE) 					return ERROR;				Q.data[Q.tu].i = arow;				Q.data[Q.tu].j = ccol;				Q.data[Q.tu].e = ctemp[ccol];			} // if		} // for arow	} // if   	return OK;} // MultSMatrix

分析下：

这里，我们要有一个思路：在经典算法里面，无论M(i,k)和N(k,j)的值是否为0，都要进行一次乘法运算，而实际上，这两者有一个值不为0时，其乘积也是0.所以，在稀疏矩阵进行运算时，要避免这种无效果操作，只需要在M.data和N.data中找到相应的各对元素(即M.data中的j值和N.data中的i值相等的各元素)乘积即可。

此函数一开始的M.nu!=N.mu就返回ERROR，这就是我刚刚说的矩阵要相乘应该满足的条件。

在if语句M.tu*N.tu!=0,这是为了判断他是不是非0矩阵，如果是非0矩阵，就直接返回。

在这个for(l=1;l<=M.nu;++l)里面这个是把nu是列。这时可能有人会问，为什么nu是列，而注释里面是把当前行各元素累加器清0，原因是他把当前行的元素清0，当前行到底有多少个元素，只能靠列来算。

随后的Q.rpos[arow]=Q.tu+1;这里有网友可能会问两个问题，一个是这个这个Q.rpos[arow]有什么用把后面那个赋值给他有什么含义，第二个就是为什么要Q.tu+1（为什么要总元素+1）。Q.rpos[arow]这个东西就是Q中各行第一个非零元的位置表。Q.tu+1是因为第一个就是1，这里面不可能从0开始。

下面这个if(aow<M.mu)else这个，这个tp是得到了下一行的第一个元素的位置。所以拿他当下面那个for循环的限制条件。

剩下的代码和上面的有很多相似之处，在此不再说明了。

转载地址：https://it1995.blog.csdn.net/article/details/54970287 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！