//DEV开发环境 ，稀疏矩阵三元组表示
//作者:赵自明
//其中乘法代码参考严蔚敏数据结构
//开发完成日期：07年11月8日
//测试环境:window xp,vista
#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
#define MAXRC 50
using namespace std;
typedef int ElemType;
typedef struct{
int i,j;//非零元在矩阵中的真实位置
ElemType e;//非零元
}Triple;//定义存放非零元素的结构体
typedef struct{
Triple data[MAXSIZE+1];//在使用过程有效位置也是从下标1开始
int mu,nu,tu;//行，列，非零元个数
int rpos[MAXRC+1];//从下标为1的位置开始存放每一行的第一个元素对应的在data中的位置
}TSMatrix;//定义存放稀疏矩阵的数据类型
int
MultSMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
//两个稀疏矩阵相乘,由于不改变M，N，结果存放到Q中，所以给M,N参数加CONST限定
{
if(M.nu!=N.mu)
{printf("M.nu!=N.mu\n");
return 0;}
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;
if(M.tu*N.tu){
int arow;
int ctemp[N.nu+1];////////这里能这样定义吗？？？？？？？？？？？？
for(arow=1;arow<=M.mu;++arow)
{ int i;
for(i=1;i<=N.nu;i++)ctemp[i]=0;//////////这啥意思呢？？？？？？？？？？？
Q.rpos[arow]=Q.tu+1;///////////还有这里？？？？？？？
int tp;
if(arow<M.mu)tp=M.rpos[arow+1];
else{tp=M.tu+1;}
int brow,t,ccol,p;
for(p=M.rpos[arow];p<tp;++p)
{ brow=M.data[p].j;
if(brow<N.mu)t=N.rpos[brow+1];
else {t=N.tu+1;}
int q;
for(q=N.rpos[brow];q<t;++q)
{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
for(ccol=1;ccol<=Q.nu;++ccol)
if(ctemp[ccol]){if(++Q.tu>MAXSIZE)return 0;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}
}
}
return 1;
}
int
CreateSMatrix(TSMatrix &M)
//创建新的稀疏矩阵
{
//以下是对寻找每行的第一个非零元在data动态数组中的位置
int num[MAXRC];
int t;
for(t=1;t<=M.mu;t++)num[t]=0;
for(t=1;t<=M.tu;++t)++num[M.data[t].i];
M.rpos[1]=1;
//求第ran行第一个非零元在Q.data中的位置
int ran=1;
for( ran=2;ran<=M.mu;++ran){ M.rpos[ran]=M.rpos[ran-1]+num[ran-1];
}
return 1;
}
int