【正确答案】三元组顺序表
三元组顺序表的C表示如下：
#define MAXSIZE 12500
typedef struct
{
int i, j; //非零元的行列下标
ElemType e;
}Triple;
typedef union
{
Triple a_Data[MAXSIZE + 1]; //三元组表，a_Data[0]未用
int mu, nu, tu;
}TSMatrix;
算法：
注意：在稀疏矩阵的三元组顺序表表示中，a_Data域中的非零元排列是有序的，即以行序为主序排列，在一行中，数据元素按列序排列。因此整个算法可以集中到如下问题：在已知A和B阵的某一行的起始位置的情况下，如何得到C的该行的内容。
如图示：
其中kA，kB，kC分别为矩阵A,B,C的a_Data域的当前位置。kX到kX’的位置是矩阵X中第i行的非零元元素。
两个矩阵的加法运算转化为第i行元素的加法。而第i行中第j元素的加法可以描述为：
取A和B的当前元素，若列号相同，则相加，若和非零，把结果放在C中，kA，kB，kC分别移到下一个位置；若和为零，则kA，kB移到下一个位置；
否则，若A的列号小于B，则C的元素等于A的元素，kA，kC分别移到下一个位置；
否则，则C的元素等于B的元素，kB，kC分别移到下一个位置；
程序：
// 以知A和B，求矩阵C = A + B，其中矩阵采用三元组顺序表表示
status MatrixAdd_TSMatrix( TSMatrix A, TSMatrix B, TSMatrix &C)
{
// 若矩阵A和B的行列不同，返回错误！
if( A.mu != B.mu || A.nu != B.nu )
{
return ERROR;
}
// 矩阵C的行列赋值
C.mu = A.mu;
C.nu = B.nu;
kA = kB = kC = 1; // 初始化
for ( i = 0; i < C.mu; i++) // 处理每一行
{
// 每列元素，从kA和kB开始，依次比较A和B中元素。
while( A.a_Data[kA].i == i && B.a_Data[kB].i == i ) //在一行内
{
if( A.a_Data[kA].j == B.a_Data[kB].j ) //A和B元素在同一列
{
C.a_Data[kC].e = A.a_Data[kA].e + B.a_Data[kB].e;
if( C.a_Data[kC] != 0) //非零，作为C中的一项存在
{
C.a_Data[kC].i = i;
C.a_Data[kC].j = A.a_Data[kA].j;
kC++;
}
kA++;
kB++;
}
else if ( A.a_Data[kA].j < B.a_Data[kB].j ) // A元素所在列小，
{
C.a_Data[kC].i = i;
C.a_Data[kC].j = A.a_Data[kA].j;
C.a_Data[kC].e = A.a_Data[kA].e;
kA++;
kC++;
}
else // B元素所在列小，kB指针移动
{
C.a_Data[kC].i = i;
C.a_Data[kC].j = B.a_Data[kB].j;
C.a_Data[kC].e = B.a_Data[kB].e;
kB++;
kC++;
}
}//while
// 若同一行内A和B元素个数不同，则需要把A或B的剩余元素拷贝到C中。
while ( A.a_Data[kA].i == i ) // A元素多
{
C.a_Data[kC].i = i;
C.a_Data[kC].j = A.a_Data[kA].j;
C.a_Data[kC].e = A.a_Data[kA].e;
kA++;
kC++:
}
while ( B.a_Data[kB].i == i ) // B元素多
{
C.a_Data[kC].i = i;
C.a_Data[kC].j = B.a_Data[kB].j;
C.a_Data[kC].e = B.a_Data[kB].e;
kB++;
kC++:
}
} // for
C.tu = kC - 1; //kC指向下一个可用位置！
return OK;
}// MatrixAdd_TSMatrix;
2．行逻辑联接顺序表
C表示：
#define MAXSIZE 12500
#define MAXRC 100
typedef struct
{
int i, j; //非零元的行列下标
ElemType e;
}Triple;
typedef struct
{
Triple a_Data[MAXSIZE + 1];
int rpos[MAXRC + 1];
Int mu, nu, tu;
}RLSMatrix;
算法同1。只是要更新该表示法中的rpos数组。
3．十字链表
typedef struct OLNode
{
int i, j;
ElemType e;
Struct OLNode *pRight, *pDown;
}OLNode, *Olink;
typedef struct
{
Olink *pRHead, *pCHead; //行和列链表头指针向量所在数组的基地址；
int mu, nu, tu;
}CrossList;
算法：在本算法中，首先把A和B按行序处理，在处理完行结点后，再通过遍历处理列链表。
// 以知A和B，求矩阵C = A + B，其中矩阵采用十字链表表示
status MatrixAdd_CrossList( CrossList A, CrossList B, CrossList C)
{
// 若矩阵A和B的行列不同，返回错误！
if( A.mu != B.mu || A.nu != B.nu )
{
return ERROR;
}
// 矩阵C的行列赋值
C.mu = A.mu;
C.nu = B.nu;
C.tu = 0;
for(i = 1; i <= C.mu, i++) //针对每一行
{
//设置指针pa，pb和pc，分别指向A，B和C的当前行结点。
pa = A.pRHead[i];
pb = B.pRHead[i];
pc = C.pRHead[i];
while( pa && pb ) // 矩阵A和B的行链表
{
if( pa->j == pb->j ) // 同一列结点
{
if( pa->e + pb->e != 0 )
{
// 申请一个结点
pc->pRight = (OLink)malloc(sizeof(OLNode));
if(!pc->pRight)
{
return ERROR; //分配内存失败
}
pc = pc->pRight;
pc->i = i;
pc->j = pa->j;
pc->e = pa->e + pb->e;
C.tu++; //增加一个结点
pc->pDown = NULL; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
}
pa = pa->pRight;
pb = pb->pRight;
}
else if ( pa->j < pb->j) //把A矩阵中的元素加入到链表中
{
// 申请一个结点
pc->pRight = (OLink)malloc(sizeof(OLNode));
if(!pc->pRight)
{
return ERROR; //分配内存失败
}
pc = pc->pRight;
pc->i = i;
pc->j = pa->j;
pc->e = pa->e;
pc->pDown = NULL; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
C.tu++; //增加一个结点
pa = pa->pRight;
}
else //把B矩阵中的元素加入到链表中
{
// 申请一个结点
pc->pRight = (OLink)malloc(sizeof(OLNode));
if(!pc->pRight)
{
return ERROR; //分配内存失败
}
pc = pc->pRight;
pc->i = i;
pc->j = pb->j;
pc->e = pb->e;
pc->pDown = NULL; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
C.tu++; //增加一个结点
pb = pb->pRight;
}
}// while
while( pa ) // pa非空。把A中的结点加入到C中
{
// 申请一个结点
pc->pRight = (OLink)malloc(sizeof(OLNode));
if(!pc->pRight)
{
return ERROR; //分配内存失败
}
pc = pc->pRight;
pc->i = i;
pc->j = pa->j;
pc->e = pa->e;
pc->pDown = NULL; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
C.tu++; //增加一个结点
pa = pa->pRight;
}
while( pb )
{
// 申请一个结点
pc->pRight = (OLink)malloc(sizeof(OLNode));
if(!pc->pRight)
{
return ERROR; //分配内存失败
}
pc = pc->pRight;
pc->i = i;
pc->j = pb->j;
pc->e = pb->e;
pc->pDown = NULL; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
C.tu++; //增加一个结点
pb = pb->pRight;
}
}// for
//处理列链表
for(j = 1; j <= C.nu; j++) //对于每一列
{
pc = C.pCHead[j]; //当前列链表的头指针
//依次在每一行中，寻找列号为j的结点，若有，加入链表中。
for( i = 1; i <= C.mu; i++)
{
pa = C.pRHead[i]; //第i行的头结点
while( pa && pa->j < j )
{
pa = pa->pRight; //取下一个结点
}//while
if ( pa ) // pa非空，说明pa->j = j，即该行中第j列有非零结点
{
//把该结点加入到列链表中
pc->pDown = pa;
pc = pc->pDown;
}//if
}// for i
}// for j
return OK;
}MatrixAdd_CrossList
【答案解析】