C语言数据结构-数组广义表-矩阵加法-实现三元组表示的两个稀疏矩阵的加法

素颜马尾好姑娘i 2023-01-13 01:55 169阅读 0赞

# **矩阵加法** #

实现三元组表示的两个稀疏矩阵的加法。相关定义如下：

#define MAXSIZE 100     //假设非零元个数的最大值为100
    typedef struct {
        int i,j;		//非零元的行下标和列下标，i 和 j 从 1 开始计数，与数学中矩阵元素的编号一致
        ElemType e;		//非零元的值
    }Triple;
    
    typedef struct {
        Triple data[MAXSIZE];	// 非零元三元组表
        int    m, n, len;		// 矩阵的行数、列数和非零元个数
    }TSMatrix;

在三元组中，i 和 j 从 1 开始计数，与数学中矩阵元素的编号一致  
矩阵加法函数的原型为：

bool add_matrix(const TSMatrix *pM, const TSMatrix *pN, TSMatrix *pQ);

pM, pN, pQ 分别指向三个矩阵，当 pM 和 pN 两个矩阵不可加时，函数返回 false，否则函数返回 true，且 pQ 指向两个矩阵的和。

**题目代码**

#include <stdio.h>
    #include <stdlib.h>
    #include "tsmatrix.h"
    
    bool add_matrix(const TSMatrix *pM, const TSMatrix *pN, TSMatrix *pQ){
    
    
    }

**参考代码**

#include <stdio.h>
    #include <stdlib.h>
    //#include "tsmatrix.h"
    #include<stdbool.h>
    #define ElemType int
    #define MAXSIZE 100					//假设非零元个数的最大值为100
    typedef struct {
        int i, j;						//非零元的行下标和列下标，i 和 j 从 1 开始计数，与数学中矩阵元素的编号一致
        ElemType e;						//非零元的值
    }Triple;
    
    typedef struct {
        Triple data[MAXSIZE];			// 非零元三元组表
        int    m, n, len;				// 矩阵的行数、列数和非零元个数
    }TSMatrix;
    
    bool add_matrix(const TSMatrix* pM, const TSMatrix* pN, TSMatrix* pQ) {
    
    	int i_M, j_M, i_N, j_N, M, N, Q;
    
    	pQ->m = pM->m;
    	pQ->n = pM->n;
    
    	if (pM->m != pN->m || pM->n != pN->n) {
    		return false;
    	}
    
    	//同时遍历两个三元组，当pM或者pN中其一元素取完循环终止
    	for (M = 0, N = 0, Q = 0; M < pM->len  && N < pN->len;)
    	{
    
    		i_M = pM->data[M].i;//M矩阵元素的行号
    		i_N = pN->data[N].i;//N矩阵元素的行号
    		j_M = pM->data[M].j;//M矩阵元素的列号
    		j_N = pN->data[N].j;//N矩阵元素的列号
    
    		//因为三元组是按行和列排好序的所以比较行数先判断是否来自同一行
    		if (i_M > i_N)//N的行号小于M直接将N中元素加入Q矩阵
    		{
    			//复制N到Q
    			pQ->data[Q].i = pN->data[N].i;
    			pQ->data[Q].j = pN->data[N].j;
    			pQ->data[Q].e = pN->data[N].e;
    			N++;//N矩阵地址加一表示向后取一个元素
    			Q++;//Q矩阵地址加一表示下一元素存放的地址
    		}
    		else if (i_M < i_N)//B的行号大于A直接将A中元素加入C矩阵
    		{
    			//复制M到Q
    			pQ->data[Q].i = pM->data[M].i;
    			pQ->data[Q].j = pM->data[M].j;
    			pQ->data[Q].e = pM->data[M].e;
    			M++;//M矩阵地址加一表示向后取一个元素
    			Q++;//Q矩阵地址加一表示下一元素存放的地址
    		}
    		else//行号相同时
    		{
    			//在判断列好号是否来自同一行
    			if (j_M > j_N)//B的列号小于A直接将B中元素加入C矩阵
    			{
    				//复制N到Q
    				pQ->data[Q].i = pN->data[N].i;
    				pQ->data[Q].j = pN->data[N].j;
    				pQ->data[Q].e = pN->data[N].e;
    				N++;//N矩阵地址加一表示向后取一个元素
    				Q++;//Q矩阵地址加一表示下一元素存放的地址
    			}
    			else if (j_M < j_N)//B的列号小于A直接将B中元素加入C矩
    			{
    				//复制M到Q
    				pQ->data[Q].i = pM->data[M].i;
    				pQ->data[Q].j = pM->data[M].j;
    				pQ->data[Q].e = pM->data[M].e;
    				M++;//M矩阵地址加一表示向后取一个元素
    				Q++;//Q矩阵地址加一表示下一元素存放的地址
    			}
    			else//相等
    			{
    				//判断元素相加是否为零
    				if ((pM->data[M].e + pN->data[N].e))//相加不为零
    				{
    					pQ->data[Q].i = pM->data[M].i;
    					pQ->data[Q].j = pM->data[M].j;
    					pQ->data[Q].e = pM->data[M].e+ pN->data[N].e;
    					Q++;
    				}
    				//无论相加是否为零都执行
    				M++;
    				N++;
    			}
    		}
    	}
    
    	while (M < pM->len)//N取完M未取完
    	{
    		//将M中所剩元素依次加入到Q中
    		pQ->data[Q].i = pM->data[M].i;
    		pQ->data[Q].j = pM->data[M].j;
    		pQ->data[Q].e = pM->data[M].e;
    		M++;
    		Q++;
    	}
    
    	while (N < pN->len)//M取完N未取完
    	{
    		//复制N到Q
    		pQ->data[Q].i = pN->data[N].i;
    		pQ->data[Q].j = pN->data[N].j;
    		pQ->data[Q].e = pN->data[N].e;
    		N++;
    		Q++;
    	}
    	pQ->len = Q+1;
    	return true;
    }
    
    void print(const TSMatrix* C)
    {
    	int i;
    	for (i = 0; i < 8; i++)
    	{
    		printf("%3d", C->data[i].i);
    	}
    	printf("\n");
    	for (i = 0; i < 8; i++)
    	{
    		printf("%3d", C->data[i].j);
    	}
    	printf("\n");
    	for (i = 0; i < 8; i++)
    	{
    		printf("%3d", C->data[i].e);
    	}
    	printf("\n");
    }
    
    void test01()
    {
    	int i;
    	int a[8] = { 1,1,3,3,4,5,6,6 };
    	int b[8] = { 2,3,1,6,3,2,1,4 };
    	int c[8] = { 12,9,-3,14,24,18,15,-7 };
    	TSMatrix *A;
    	TSMatrix *B;
    	TSMatrix *C;
    	A = (TSMatrix*)malloc(sizeof(TSMatrix));
    	B = (TSMatrix*)malloc(sizeof(TSMatrix));
    	C = (TSMatrix*)malloc(sizeof(TSMatrix));
    	A->n = 8;
    	A->m = 1;
    	A->len = 8;
    	for (i = 0; i < 8; i++)
    	{
    		A->data[i].i = a[i];
    		A->data[i].j = b[i];
    		A->data[i].e = c[i];
    	}
    	B->n = 8;
    	B->m = 1;
    	B->len = 8;
    	for (i = 0; i < 8; i++)
    	{
    		B->data[i].i = a[i];
    		B->data[i].j = b[i];
    		B->data[i].e = c[i];
    	}
    	add_matrix(A, B, C);
    	print(C);
    }
    
    int main()
    {
        test01();
        return 0;
    }

**运行结果**

1  1  3  3  4  5  6  6
      2  3  1  6  3  2  1  4
     24 18 -6 28 48 36 30-14

** 手写分析**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/6d758fddbd39496699b9cad4eb33732e.png