在完成稀疏矩阵的实现时，主要遇到了两个问题：
- 复制构造函数传参数一般应该为const引用类型，否则在SparseMatrix<T> b(a.Transpose())等情况下会出问题，重载赋值符号时也一样，参数应设为const引用类型。（似乎和左右值有关？待深入研究）
- 在转置函数和快速转置函数中，数组元素三元组中的行和列都是我们输入的值，是从1开始的，而在数组中是从0开始的，这一点要千万注意。
1、SparseMatrix.h
#ifndef SparseMatrix_h
#define SparseMatrix_h
#include <iostream>
using std::ostream;
using std::istream;
const int DefaultSize = 100;
template <class T>
struct Trituple{
int row, col;
T value;
Trituple<T>& operator=(Trituple<T>& x){
row = x.row;
col = x.col;
value = x.value;
return *this;
}
};
template <class T>
class SparseMatrix{
private:
int Rows, Cols, Terms;
Trituple<T>* smArray;
int maxTerms;
public:
SparseMatrix(int maxSz = DefaultSize);
SparseMatrix(const SparseMatrix<T>& x);
~SparseMatrix(){delete []smArray;}
SparseMatrix<T>& operator=(const SparseMatrix<T>& x);
SparseMatrix<T> Transpose();
SparseMatrix<T> FastTranspose();
//SparseMatrix<T> Add(SparseMatrix<T>& b);
//SparseMatrix<T> Multiply(SparseMatrix<T>& b);
template <class U> friend ostream& operator<<(ostream& out, SparseMatrix<U>& M);
template <class U> friend istream& operator>>(istream& in, SparseMatrix<U>& M);
};
#endif /* SparseMatrix_h */
2、SparseMatrix.cpp
#include <stdio.h>
#include "SparseMatrix.h"
using std::endl;
using std::cerr;
using std::cout;
template <class T>
SparseMatrix<T>::SparseMatrix(int maxSz) : maxTerms(maxSz){
if(maxSz < 1){cerr << "矩阵初始化值错！" << endl; exit(1);}
smArray = new Trituple<T>[maxSz];
if(smArray == NULL){cerr << "存储分配错！" << endl; exit(1);}
Rows = Cols = Terms = 0;
}
template <class T>
SparseMatrix<T>::SparseMatrix(const SparseMatrix<T>& x){
Rows = x.Rows;
Cols = x.Cols;
Terms = x.Terms;
maxTerms = x.maxTerms;
smArray = new Trituple<T>[maxTerms];
if(smArray == NULL){cerr << "存储分配错误！" << endl; exit(1);}
for(int i = 0; i < Terms; i++)
smArray[i] = x.smArray[i];
}
template <class T>
SparseMatrix<T>& SparseMatrix<T>::operator=(const SparseMatrix<T>& x){
Rows = x.Rows;
Cols = x.Cols;
Terms = x.Terms;
maxTerms = x.maxTerms;
for(int i = 0; i < Terms; i++)
smArray[i] = x.smArray[i];
return *this;
}
template <class T>
ostream& operator<<(ostream& out, SparseMatrix<T>& M){
out << "row = " << M.Rows << endl;
out << "cols = " << M.Cols << endl;
out << "Nozero terms = " << M.Terms << endl;
for(int i = 0; i < M.Terms; i ++)
out << "M[" << M.smArray[i].row << "][" << M.smArray[i].col << "] = " << M.smArray[i].value << endl;
return out;
}
template <class T>
istream& operator>>(istream& in, SparseMatrix<T>& M){
cout << "Enter number of rows, columns, and terms" << endl;
in >> M.Rows >> M.Cols >> M.Terms;
if(M.Terms > M.maxTerms){cerr << "Number of terms overflow!" << endl; exit(1);}
for(int i = 0; i < M.Terms; i++){
cout << "Enter row, column, and value of term:" << i+1 << endl;
in >> M.smArray[i].row >> M.smArray[i].col >> M.smArray[i].value;
}
return in;
}
//稀疏矩阵转置算法
template <class T>
SparseMatrix<T> SparseMatrix<T>::Transpose(){
SparseMatrix<T> b(maxTerms);
b.Rows = Cols;
b.Cols = Rows;
b.Terms = Terms;
if(Terms > 0){
int k, i, CurrentB = 0;
for(k = 0; k < Cols; k ++)
for(i = 0; i < Terms; i ++)
if(smArray[i].col == k+1){
b.smArray[CurrentB].row = k;
b.smArray[CurrentB].col = smArray[i].row;
b.smArray[CurrentB].value = smArray[i].value;
CurrentB ++;
}
}
return b;
}
//稀疏矩阵快速转置算法
template <class T>
SparseMatrix<T> SparseMatrix<T>::FastTranspose(){
int* rowSize = new int[Cols];
int* rowStart = new int[Cols];
SparseMatrix<T> b(maxTerms);
b.Rows = Cols;
b.Cols = Rows;
b.Terms = Terms;
if(Terms > 0){
int i, j;
for(i = 0; i < Cols; i ++) rowSize[i] = 0;
for(i = 0; i < Terms; i ++) rowSize[--smArray[i].col]++;
rowStart[0] = 0;
for(i = 1; i < Cols; i++)
rowStart[i] = rowStart[i-1] + rowSize[i-1];
for(i = 0; i < Terms; i ++){
j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
}
delete []rowStart;
delete []rowSize;
return b;
}
3、main.cpp
#include <iostream>
#include "SparseMatrix.cpp"
using std::cin;
int main(){
SparseMatrix<int> a(100);
cin >> a;
cout << a;
SparseMatrix<int> b(100);
SparseMatrix<int> c(100);
b = a.Transpose();
c = a.FastTranspose();
cout << b;
cout << c;
return 0;
}