sparsematrix.cpp

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//稀疏矩阵类操作的实现
#include "SparseMatrix.h"
template <class E>
SparseMatrix<E>::SparseMatrix (int Rw, int Cl, int Tm, Triple<E>* sma) {
    Rows = Rw;   Cols = Cl;   Terms = Tm; smArray = sma;	
    if (smArray == NULL) smArray = new Triple<E>[Terms];          //三元组表
    if (smArray == NULL) {
         cerr << "存储分配失败!" << endl;  exit(1);
    }	
};  

template <class E>
void SparseMatrix<E> ::
Transpose (SparseMatrix<E>& B) {
//转置this矩阵,转置结果由B返回
     B.Rows = Cols;   B.Cols = Rows; 
     B.Terms = Terms;
        //转置矩阵的列数,行数和非零元素个数
     if (Terms > 0) {				
          int CurrentB = 0;   //转置三元组表存放指针
          int i, k;
         for (k = 0; k < Cols; k++)       //处理所有列号
      	      for (i = 0; i < Terms; i++) 		
				  if (smArray[i].col == k) {
					  B.smArray[CurrentB].row = k;	
	                B.smArray[CurrentB].col = smArray[i].row;
	                B.smArray[CurrentB].value=smArray[i].value;	
 	                CurrentB++;					
				  }
     }
};    

template <class E> 
void SparseMatrix<E>::
      FastTranspos (SparseMatrix<E>& B) {
    int *rowSize = new int[Cols];       //列元素数数组
    int *rowStart = new int[Cols];      //转置位置数组
    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 [ ] rowSize;   delete [ ] rowStart;
}

template <class E>
SparseMatrix<E> SparseMatrix<E>::Add(SparseMatrix<E>& b) {
//两个稀疏矩阵A (*this 指示) 与B (参数表中的b) 相加, 结果在Result 中
	SparseMatrix<E> result(Rows,Cols); //结果矩阵的三元组表
	if ( Rows != b.Rows || Cols != b.Cols) {
		cout << "Incompatible matrices" << endl; //两个矩阵规格不一样
		return result; //返回空矩阵
	}
	int i = 0, j = 0, index_a, index_b; result.Terms = 0;
	while (i < Terms && j < b.Terms) {
		index_a = Cols*smArray[i].row+smArray[i].col;
		index_b = Cols*b.smArray[j].row+b.smArray[j].col;
		if (index_a < index_b) { //smArray[i]在b.smArray[j]前
			result.smArray[result.Terms] = smArray[i];
			i++;
		}
		else if (index_a > index_b) { //smArray[i]在b.smArray[j]后
			result.smArray[result.Terms] = b.smArray[j];
			j++;
		}
		else { //smArray[i]和b.smArray[j]在相同位置
			result.smArray[result.Terms] = smArray[i];
			result.smArray[result.Terms].value= smArray[i].value + b.smArray[j].value;
			i++; j++;
		}
		result.Terms++;
	}
	//复制剩余元素
	for ( ; i < Terms; i ++) {
		result.smArray[result.Terms] = smArray[i];
		result.Terms++;
	}
	for ( ; j < b.Terms; j++) {
		result.smArray[result.Terms] = b. smArray[i];
		result.Terms++;
	}
	return result;
};

template <class E>
SparseMatrix<E> SparseMatrix<E>::Multiply(SparseMatrix<E>& b) {
//两个稀疏矩阵a（*this 指示）与b（参数表中的b）相乘, 结果在Result 中
	SparseMatrix<E> result(Rows, b.Cols); //结果矩阵的三元组表
	if (Cols != b.Rows) {
		cout << "Incompatible matrices" << endl; //A 列数与B 行数不等
		return result; //返回空矩阵
	}
	if (Terms == maxTerms || b.Terms == maxTerms) {
		cout << "One additional space in a or b needed" << endl;
		return result; //空间不足，返回空矩阵
	}
	int *rowSize = new int[b.Rows]; //矩阵B 各行非零元素个数
	int *rowStart = new int[b.Rows+1]; //矩阵B 各行在三元组开始位置
	E *temp = new E[b.Cols]; //暂存每一行计算结果
	int i, Current, lastInResult, RowA, ColA, ColB;
	for (i = 0; i < b.Rows; i++) rowSize[i] = 0;
	cout << "success" << endl;
	for (i = 0; i < b.Terms; i++) rowSize[b.smArray[i].row]++;
	
	rowStart[0] = 0; //B第i 行非零元素开始位置
	for (i = 1; i <= b.Rows; i++)
		rowStart[i] = rowStart[i-1]+rowSize[i-1];
	
	
	Current = 0; lastInResult = -1; //a 扫描指针及result 存指针
	
	while (Current < Terms) { //生成result 的当前行temp
		RowA = smArray[Current].row; //当前行的行号
	//	cout <<  RowA << ' ' << Current << endl;
		for (i = 0; i < b.Cols; i++) temp[i] = 0;
		while (Current < Terms && smArray[Current].row == RowA) {
			ColA = smArray[Current].col; //矩阵A 当前扫描到元素的列号
			for (i = rowStart[ColA]; i < rowStart[ColA+1]; i++) {
				ColB = b.smArray[i].col; //矩阵B 中相乘元素的列号
				temp[ColB] += smArray[Current].value*b.smArray[i].value;
			} //A的RowA 行与B 的ColB 列相乘
			Current++;
		}
	//	cout << "success2" << endl;
		for (i = 0; i < b.Cols; i++)
			if (temp[i] != 0) { //将temp 中的非零元素压缩到result 中去
				lastInResult++;
				cout << RowA << ' ' << i << ' ' << temp[i] << ' ' << lastInResult << endl;
				result.smArray[lastInResult].row = RowA;
				result.smArray[lastInResult].col = i;
				result.smArray[lastInResult].value = temp[i];
			}
	}
	result.Rows = Rows; result.Cols = b.Cols;
	result.Terms = lastInResult+1;
	
	//delete []rowSize; delete []rowStart; delete []temp;
	cout << "ss" << endl;
	return result;
	
};