Question

编写实现C=A×B操作的函数，设矩阵A、B和C均为采用压缩存储方式的n阶对称矩阵，矩阵元素均为整型。

数据结构

Answer 1

#include <stdio.h>
#define MAXSIZE 100
#define MAXROW 100
typedef struct {
int row, col, e;
} Triple;
typedef struct {
Triple data[MAXSIZE+1];
int first[MAXROW+1];
int m, n, len;
} TsMatrix;
int MulSMatrix(TsMatrix *M, TsMatrix *N, TsMatrix *Q)
{
int qrow, qcol, p, q;
int num[MAXSIZE], position[MAXSIZE], qtemp[MAXSIZE];
if (M->n!=N->m) return 0;
Q->m=M->m; Q->n=N->n; Q->len=0;
if (M->len*N->len)
{

for (qrow=1; qrow<=Q->m; qrow++)
{
for (qcol=1; qcol<=Q->n; qcol++)
qtemp[qcol]=0;
Q->first[qrow]=Q->len+1;
for (p=M->first[qrow]; p<M->first[qrow+1]; p++)
for (q=N->first[M->data[p].col]; q<N->first[M->data[p].col+1]; q++)
qtemp[N->data[q].col]+=M->data[p].e*N->data[q].e;
for (qcol=1; qcol<=Q->n; qcol++)
if (qtemp[qcol])
{
(Q->len)++;
Q->data[Q->len].col=qcol;
Q->data[Q->len].row=qrow;
Q->data[Q->len].e=qtemp[qcol];
}
}
}
return 1;
}
void Display(TsMatrix *A)
{
int i, j, k=1;
for (i=1; i<=A->m; i++)
{
for (j=1; j<=A->n; j++)
if ((A->data[k].row==i) && (A->data[k].col==j))
{
printf("%2d ", A->data[k].e);
k++;
} else
printf("%2d ", 0);
printf("\n");
}
}
main()
{
int m, n, i, j, v, num[MAXROW+1];
TsMatrix A, B, C;
printf("输入A行数、列数："); scanf("%d %d",&m,&n);
printf("输入A行号、列号、值：\n"); scanf("%d %d %d",&i,&j,&v);
A.len=0;
while ((i>0) && (i<=m) && (j>0) && (j<=n) && (v!=0))
{
A.data[++A.len].row=i;
A.data[A.len].col=j;
A.data[A.len].e=v;
scanf("%d %d %d",&i,&j,&v);
}
A.m=m; A.n=n;
for (i=1; i<=A.m; i++)
num[i]=0;
for (i=1; i<=A.len; i++)
num[A.data[i].row]++;
A.first[1]=1;
for (i=2; i<=A.m; i++)
A.first[i]=A.first[i-1]+num[i-1];
A.first[A.m+1]=A.len+1;
printf("输入B行数、列数："); scanf("%d %d",&m,&n);
printf("输入B行号、列号、值：\n"); scanf("%d %d %d",&i,&j,&v);
B.len=0;
while ((i>0) && (i<=m) && (j>0) && (j<=n) && (v!=0))
{
B.data[++B.len].row=i;
B.data[B.len].col=j;
B.data[B.len].e=v;
scanf("%d %d %d",&i,&j,&v);
}
B.m=m; B.n=n;
for (i=1; i<=B.m; i++)
num[i]=0;
for (i=1; i<=B.len; i++)
num[B.data[i].row]++;
B.first[1]=1;
for (i=2; i<=B.m; i++)
B.first[i]=B.first[i-1]+num[i-1];
B.first[B.m+1]=B.len+1;
puts("********************************************");
puts("* 算法5.3 基于三元组表的矩阵乘法（结果） *");
puts("********************************************");
printf("\n矩阵A：\n"); Display(&A);
printf("\n矩阵B：\n"); Display(&B);
MulSMatrix(&A, &B, &C);
printf("\nC=A*B的矩阵：\n"); Display(&C);
}