数据结构三元顺序表稀疏矩阵的加法程序

三元顺序表稀疏矩阵的加法

三元顺序表是什么？稀疏矩阵又是什么？稀疏矩阵的加法和普通矩阵的加法有什么不同？你看到这些是不是都有些困惑。那么现在我们就来讲讲这些陌生的东西。

• 三元顺序表

将稀疏矩阵非零元素对应的三元组所构成的集合，按照行优先的顺序排列成一个线性表，毫无疑问，这是需要定义一个结构体

struct Node {
     int row, col, elem; //分别表示行号，列号，非零元素具体数值
}

• 稀疏矩阵

矩阵中有许多的0元素，并且没有分布规律。注意，稀疏矩阵并不是特殊矩阵，而我们所知道的特殊矩阵(上、下)三角矩阵、对称矩阵、对角矩阵等等。

• 稀疏矩阵的加法

稀疏矩阵的加法和普通矩阵的加法并没有特别之处。但利用三元组顺序表来实现加法运算有着不同的逻辑思维。下面我们来看看三元组顺序表稀疏矩阵的加法算法。

对于A和B都是3*3的稀疏矩阵，我们用(行、列、非零元素的具体值)这种形式来输入输出。对于A的第i个非零元素的行(或列)与B的第j个非零元素的行(或列)有一种大小关系，且A、B的非零元素的个数不一定相同。这些是我们所需要知道的。接下来就是如何实现我们的算法了。

I.我们从矩阵的行比较开始说起。当行相同时，我们就比较列，矩阵的列可能相同可能不相同，还有可能相同，那么我们以以来说一说。

(1)当矩阵的列相同时，新矩阵C的三元组顺序表的行、列就会等于矩阵A(或矩阵B)的行、列，C的非零元素具体值就等于A的具体值加B的具体值。然后A、B、C的三元组顺序表都加加。

(2)当矩阵A的列<矩阵B的列时，C的列就等于A的列，也就是等于列较小的矩阵的列。C的非零元素具体值等于A的非零元素具体值。C的行等于A的行，最后A、C的三元组顺序表加加。

(3)当A的列>B的列时，与(2)类似，这里不在赘述。

II.当A、B的行不相同时,则就是大、小关系。我们就说一种，A的行<B的行时的情况。

这种情况下，直接将A的行、列、非零元素具体值赋给C，同时A、C的三元组顺序表都加加。

III.处上述列举的可能，是不是还有可能A(或B)的非零元素有剩余，没有赋给C，那么这里我们就说一说A有剩余的情况。(B剩余的情况和A类似，不再赘述)

这种情况下，直接把A所剩余的非零元素全部赋给C。

下面我们来看代码：

int i=1,j=1,count=1;
	while(i<=A.tu&&j<=B.tu){
		if(A.data[i].row==B.data[j].row){			//矩阵A当前元素行号等于矩阵B当前元素行号 
			if(A.data[i].col==B.data[j].col){		//矩阵A当前元素列号等于矩阵B当前元素列号 
				C.data[count]=A.data[i];
				C.data[count].elem+=B.data[j].elem;
				++i;++j;++count;
			}else if(A.data[i].col<B.data[j].col){	//矩阵A当前元素列号小于矩阵B当前元素列号 
				C.data[count]=A.data[i];
				++i;++count;
			}else if(A.data[i].col>B.data[j].col){	//矩阵A当前元素列号大于矩阵B当前元素列号 
				C.data[count]=B.data[j];
				++j;++count;
			}
		}else if(A.data[i].row<B.data[j].row){		//矩阵A当前元素行号小于矩阵B当前元素行号 
			C.data[count]=A.data[i];
			++i;++count;
		}else if(A.data[i].row>B.data[j].row){		//矩阵A当前元素行号大于矩阵B当前元素行号 
			C.data[count]=B.data[j];
			++j;++count;
		}
	}
	while(i<=A.length){
		C.data[count]=A.data[i];
		++i;++count;
	}
	while(j<=B.length){
		C.data[count]=B.data[j];
		++j;++count;
	}
	C.length=--count;

那么到这里我们的三元组顺序表稀疏矩阵的加法算法就到此结束啦！！！