『西工大-数据结构-NOJ』 012-以三元组表为存储结构实现矩阵相加(耿5.7) 『西北工业大学』

解题思路：

这道题要求用三元组表的储存结构储存稀疏矩阵，并进行加法运算。 首先我们要了解一下为什么要用三元组表，对于一个稀疏矩阵，尤其是高维度时，如果以多维数组的形式开辟空间，会造成很大的不必要空间浪费，于是我们用三元组表，只存储稀疏矩阵中的非零元素，来达到储存稀疏矩阵的目的。 常见的三元组和三元组表的宏定义如下：

typedef struct{//定义三元组 int i,j; int val; }Triple; typedef struct{//定义三元组表 Triple *data;//多个三元组 int mu,nu,tu;//最大行，最大列，有效元素个数 }TSMatrix;

再进行三元组操作的时候很重要的的一点是要注意三元组表的规范性，即三元组表中的三元组储存次序是按照：①行由低到高；②列由低到高 来储存的。 故本题的难点在于在进行三元组表储存到稀疏矩阵的加法运算时，不仅要利用旧三元组表的规范性，而且还要保证新三元组表的规范性，为实现这些我们要在加法运算中进行全面的分类执行。 具体操作见代码，代码中有部分注释。

题解代码：

#include<stdio.h> #include<stdlib.h> typedef struct{//定义三元组 int i,j; int val; }Triple; typedef struct{//定义三元组表 Triple *data;//多个三元组 int mu,nu,tu;//最大行，最大列，有效元素个数 }TSMatrix; void CreatTSMatrix(TSMatrix *p,int n){//申请一个容量为n的三元组表 p->data = (Triple*)malloc(sizeof(Triple)*n); p->tu = n; } void AddTwoTSMatrix(TSMatrix *A, TSMatrix *B, TSMatrix *C){ int i=0,j=0,sum,C_tu=0; while(i<A->tu && j<B->tu){//当还有AB均有值未进行加法运算 if(A->data[i].i==B->data[j].i && A->data[i].j==B->data[j].j){//当A与B元素行列均相等 sum = A->data[i].val + B->data[j].val; if(sum!=0){ C->data[C_tu].i = A->data[i].i; C->data[C_tu].j = A->data[i].j; C->data[C_tu].val = sum; C_tu++; } i++; j++; } else if(A->data[i].i < B->data[j].i){//当A的行数小 C->data[C_tu].i = A->data[i].i; C->data[C_tu].j = A->data[i].j; C->data[C_tu].val = A->data[i].val; C_tu++; i++; } else if(A->data[i].i > B->data[j].i){//当B的行数小 C->data[C_tu].i = B->data[j].i; C->data[C_tu].j = B->data[j].j; C->data[C_tu].val = B->data[j].val; C_tu++; j++; } else if(A->data[i].j < B->data[j].j){//当行数相等时A的列数小 C->data[C_tu].i = A->data[i].i; C->data[C_tu].j = A->data[i].j; C->data[C_tu].val = A->data[i].val; C_tu++; i++; } else{//当行数相等时B的列数小 C->data[C_tu].i = B->data[j].i; C->data[C_tu].j = B->data[j].j; C->data[C_tu].val = B->data[j].val; C_tu++; j++; } } //处理一下不需要做加法运算的剩余元素 while(i<A->tu){ C->data[C_tu].i = A->data[i].i; C->data[C_tu].j = A->data[i].j; C->data[C_tu].val = A->data[i].val; C_tu++; i++; } while(j<B->tu){ C->data[C_tu].i = B->data[j].i; C->data[C_tu].j = B->data[j].j; C->data[C_tu].val = B->data[j].val; C_tu++; j++; } C->tu = C_tu; } void PrintTSMatrix(TSMatrix *C){ for(int i=0;i<C->tu;i++){ printf("\n%d %d %d",C->data[i].i,C->data[i].j,C->data[i].val); } } int main(){ int t1,t2; scanf("%d %d",&t1,&t2); TSMatrix *pa,*pb,*pc; pa = (TSMatrix*)malloc(sizeof(TSMatrix)); pb = (TSMatrix*)malloc(sizeof(TSMatrix)); pc = (TSMatrix*)malloc(sizeof(TSMatrix)); CreatTSMatrix(pa,t1); CreatTSMatrix(pb,t2); CreatTSMatrix(pc,t1+t2); for(int i=0;i<t1;i++){ scanf("%d %d %d",&pa->data[i].i,&pa->data[i].j,&pa->data[i].val); } for(int i=0;i<t2;i++){ scanf("%d %d %d",&pb->data[i].i,&pb->data[i].j,&pb->data[i].val); } AddTwoTSMatrix(pa,pb,pc); PrintTSMatrix(pc); return 0; }