稀疏矩阵的乘法实现.doc

稀疏矩阵的乘法实现
程序：HYPERLINK\l""printHYPERLINK\l""?
#include<stdio.h>
#include<stdlib.h>
#defineNULL0
#defineOK1
#defineERROR0
#defineMAXSIZE100/*矩阵中非零元的最大值*/
#defineMAXRC10/*矩阵的最大行值*/

typedefintstatus;

/**********稀疏矩阵的行逻辑链接的顺序表存储表示**********/

typedefstruct/*非零元的三元组*/
{
inti,j;/*非零元的行下标和列下标*/
inte;
}Triple;

typedefstruct/*稀疏矩阵的行逻辑链接的顺序表*/
{
Tripledata[MAXSIZE+1];/*非零三元组表，data[0]未用，以下定义的数组都是从1开始*/
intrpos[MAXRC+1];/*代表各行第一个非零元的序号表，其值为data的下标*/
intmu,nu,tu;/*矩阵的行数、列数、非零元的个数*/
}RLSMatrix;/*R:rowL:logicS:sequence*/

/*********基本操作的函数原型的声明*********/

statusCreateSMatrix_RL(RLSMatrix*matrix);
//创建一个稀疏矩阵；
//输入行数、列数，支持乱序输入三元组，并计数；
//以行为主序进行重新排列，并记录每行起始位置于matrix->rpos[row]；
//若非零元超过MAXSIZE或行数超过MAXRC，则返回ERROR，否则OK；

voidPrintSMatrix_RL(RLSMatrix*matrix);
//输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵；

statusMultSMatrix_RL(RLSMatrix*M,RLSMatrix*N,RLSMatrix*Q);
//输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q；
//如果M->mu!=N->nu或列数大于MAXRC或者计算出的非零元个数大于MAXSIZE，都返回ERROR,否则OK；
//计算过程如下：
//1.由于矩阵M和Q的行数相等并且C语言以行为主序进行存储，所以以M进行逐行的扫描。
//2.使Q的此行逻辑表的序号等于其非零元个数Q.tu+1，以表示其行的首个元素的序号。
//3.从行中找到M的非零元，并以它的列值为N的行号，对N进行行的扫描，若存在，则依次计算它们，并把其值累加到一个以N中这个对应非零元的列值为序号的临时数组ctemp[ccol]中。
//4.在M的当前行完成扫描后，将ctemp[ccol]不为0的值，压入到Q矩阵的三元组，累加++Q.tu，若Q.tu大于了MAXSIZE，这返回ERROR。

/************main()函数对矩阵乘法的实现************/

voidmain()
{
RLSMatrix*M,*N,*Q;
if(!(M=(RLSMatrix*)malloc(sizeof(RLSMatrix))))
exit(ERROR);
if(!(N=(RLSMatrix*)malloc(sizeof(RLSMatrix))))
exit(ERROR);
if(!(Q=(RLSMatrix*)malloc(sizeof(RLSMatrix))))
exit(ERROR);
if(CreateSMatrix_RL(M)&&CreateSMatrix_RL(N))
{
printf("/nputoutM:/n");
PrintSMatrix_RL(M);/*打印出M*/
printf("/nputoutN:/n");
PrintSMatrix_RL(N);/*打印出N*/
if(MultSMatrix_RL(M,N,Q))
{
printf("/n/n/nM*N:/n");
PrintSMatrix_RL(Q);/*计算结果*/
}
else
printf("M.muandN.nuarenotmathing/n");
}
else
printf("inputerror./n");
}

/***********基本操作的算法描述****************/

statusCreateSMatrix_RL(RLSMatrix*matrix)
//创建一个稀疏矩阵；
//输入行数、列数，支持乱序输入三元组，并计数；
{
intnum=0,p,q,min,temp;//中间变量；
introw;
printf("inputthetotalrowandcol:/n");
scanf("%d%d",&ma