主题:稀疏矩阵相乘算法问题
template <class Type> class SparseMtrix{
//对象:是一个三元组<row,column,value>的集合,其中row,column是整数,记忆矩阵
//元素所在行号和列号,而value是矩阵元素的值。
public:
SparseMtrix(int MaxRow, int Maxcol);//构造函数
//建立一个MaxRow行,Maxcol列的稀疏矩阵。
SparseMtrix<Type> Multiply(SparseMtrix<Type> b);
/*按公式c[i][j]=∑(a[i][k]*b[k][j])实现矩阵a 与b相乘。k=0,1...,a、的列数-1。*/
private:
int Rows, Cols,Terms;
//Rows和 Cols分别是稀疏矩阵的行数和列数,Terms是稀疏矩阵的非零元素个数
Trituple<Type> smArray[ int MaxTerms];
// MaxTerms是在三元组表smArray中三元组个数最大值
}
template <class Type> class Trituple{
friend class SpareMtrix <Type>
private:
int row, col;//非零元素行号和列号
Type vaule;//非零元素的值
}
template <class Type> SparseMtrix <Type> SparseMtrix <Type> ::Multiply(parseMtrix<Type> b)
//两个稀疏矩阵A(*this指示)与B(参数表中b)相乘,结果在result中。
{
if (Cols != b.Rows){
//A矩阵列数与B矩阵行数不等不能做乘法的矩阵,返回空矩阵
cout<<""<<endl;
return EmptyMatrix();
}
int *rowSize = new int[b.Rows];
int *rowsStart = new int[b.Row+1];
Type * temp =new Type[b.Cols]; //临时数组,暂存每一行计算结果
SparseMtrix <Type> result(Rows,Cols); //结果局阵的三元组表result
for(int i=0;i< b.Rows;i++)
rowSize[i]=0;
for(i=1;i<=b.Terms;i++)//统计矩阵B中第i行非零元素个数
rowSize[smArray[i].row]++;
rowStart[0] = 0; //计算矩阵B中第i行非零元素个数的开始位置
for(i=1;i<=b.Rows;i++)
rowStart[i]=rowStart[i-1] + rowSize[i-1];
int Current=0, lastInResult = -1;
//a.smArray扫描指针及result存放指针
while(Current< Terms){ //生成result的当前行temp
int RowA = smArray[Current].row; //当前的行号
for(i=0;i<b.Cols;i++)
temp[i]=0; //temp初始化
while(Current<Terms && smArray[Current].row ==RowA){
int ColA=smArray[Current].col;
//矩阵A当前扫描到元素的列号
for(i=rowStart[ColA];i<rowStart[ColA+1];i++){
int ColB = b.smArray[i].col;
//矩阵B中相乘元素的列号
temp[ColB] = temp[ColB] + smArray[Current].value * b.smArray[i].vaule;
//A的RowA行与B的ColB列相乘
}
Current++
}
for(i=0;i<b.Cols;i++)
if(temp[i] != 0){
//将temp中的非零元素压缩到result中去
lastInResult++;
result.smArray[lastInResult].row = RowA;
result.smArray[lastInResult].col = i;
result.smArray[lastInResult].value = tepm[i];
}
}
result.Rows = Rows; result.Cols = b.Cols; result.Terms = lastInResult + 1;
delete[] rowSize; delete[] rowStart;delete[] temp;
return result;
}
问题是怎么都觉得temp数组只有b.cols个,而矩阵结果应该是a.rows×b.cols个哈
怎么理解呢?
//对象:是一个三元组<row,column,value>的集合,其中row,column是整数,记忆矩阵
//元素所在行号和列号,而value是矩阵元素的值。
public:
SparseMtrix(int MaxRow, int Maxcol);//构造函数
//建立一个MaxRow行,Maxcol列的稀疏矩阵。
SparseMtrix<Type> Multiply(SparseMtrix<Type> b);
/*按公式c[i][j]=∑(a[i][k]*b[k][j])实现矩阵a 与b相乘。k=0,1...,a、的列数-1。*/
private:
int Rows, Cols,Terms;
//Rows和 Cols分别是稀疏矩阵的行数和列数,Terms是稀疏矩阵的非零元素个数
Trituple<Type> smArray[ int MaxTerms];
// MaxTerms是在三元组表smArray中三元组个数最大值
}
template <class Type> class Trituple{
friend class SpareMtrix <Type>
private:
int row, col;//非零元素行号和列号
Type vaule;//非零元素的值
}
template <class Type> SparseMtrix <Type> SparseMtrix <Type> ::Multiply(parseMtrix<Type> b)
//两个稀疏矩阵A(*this指示)与B(参数表中b)相乘,结果在result中。
{
if (Cols != b.Rows){
//A矩阵列数与B矩阵行数不等不能做乘法的矩阵,返回空矩阵
cout<<""<<endl;
return EmptyMatrix();
}
int *rowSize = new int[b.Rows];
int *rowsStart = new int[b.Row+1];
Type * temp =new Type[b.Cols]; //临时数组,暂存每一行计算结果
SparseMtrix <Type> result(Rows,Cols); //结果局阵的三元组表result
for(int i=0;i< b.Rows;i++)
rowSize[i]=0;
for(i=1;i<=b.Terms;i++)//统计矩阵B中第i行非零元素个数
rowSize[smArray[i].row]++;
rowStart[0] = 0; //计算矩阵B中第i行非零元素个数的开始位置
for(i=1;i<=b.Rows;i++)
rowStart[i]=rowStart[i-1] + rowSize[i-1];
int Current=0, lastInResult = -1;
//a.smArray扫描指针及result存放指针
while(Current< Terms){ //生成result的当前行temp
int RowA = smArray[Current].row; //当前的行号
for(i=0;i<b.Cols;i++)
temp[i]=0; //temp初始化
while(Current<Terms && smArray[Current].row ==RowA){
int ColA=smArray[Current].col;
//矩阵A当前扫描到元素的列号
for(i=rowStart[ColA];i<rowStart[ColA+1];i++){
int ColB = b.smArray[i].col;
//矩阵B中相乘元素的列号
temp[ColB] = temp[ColB] + smArray[Current].value * b.smArray[i].vaule;
//A的RowA行与B的ColB列相乘
}
Current++
}
for(i=0;i<b.Cols;i++)
if(temp[i] != 0){
//将temp中的非零元素压缩到result中去
lastInResult++;
result.smArray[lastInResult].row = RowA;
result.smArray[lastInResult].col = i;
result.smArray[lastInResult].value = tepm[i];
}
}
result.Rows = Rows; result.Cols = b.Cols; result.Terms = lastInResult + 1;
delete[] rowSize; delete[] rowStart;delete[] temp;
return result;
}
问题是怎么都觉得temp数组只有b.cols个,而矩阵结果应该是a.rows×b.cols个哈
怎么理解呢?