中南大学数据结构与算法第5章数组和广义表课后作业答案(2)

5.11 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。 解：

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。

#define MaxSize 10 //用户自定义 typedef int DataType; //用户自定义 typedef struct { //定义三元组 int i,j; DataType v; }TriTupleNode;

typedef struct { //定义三元组表

TriTupleNode data[MaxSize];

int m,n,t;//矩阵行，列及三元组表长度 }TriTupleTable;

//以下为矩阵加算法

void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C) {//三元组表表示的稀疏矩阵A,B相加 int k,l; DataType temp; C->m=A->m;//矩阵行数 C->n=A->n;//矩阵列数

C->t=0; //三元组表长度 k=0; l=0;

while (kt&&lt)

{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)) {temp=A->data[k].v+B->data[l].v; if (!temp)//相加不为零，加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=temp; } k++;l++; }

if ((A->data[k].i==B->data[l].i)&&(A->data[k].jdata[l].j)) ||(A->data[k].idata[l].i)//将A中三元组加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=A->data[k].v; k++; }

if ((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j)) ||(A->data[k].i>B->data[l].i)//将B中三元组加入C {C->data[c->t].i=B->data[l].i; C->data[c->t].j=B->data[l].j; C->data[c->t++].v=B->data[l].v; l++; } }

while (kt)//将A中剩余三元组加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j;

C->data[c->t++].v=A->data[k].v; k++; }

while (lt)//将B中剩余三元组加入C {C->data[c->t].i=B->data[l].i; C->data[c->t].j=B->data[l].j; C->data[c->t++].v=B->data[l].v; l++; } }