[转载]C++中稀疏矩阵的一种实现

Use Sparse Matrix in C++

The following code snippet is hosted on Github Gist.

	#include <iostream>
	#include <iomanip>
	using namespace std;
	template<class T>
	//三元组
	struct Trituple
	{
	int row;
	int col;
	T val;
	};
	//稀疏矩阵声明
	template<class T>
	class SparseMatrix
	{
	public:
	SparseMatrix(int maxt=100);
	~SparseMatrix();
	bool TransposeTo(SparseMatrix &);
	bool AddTo(const SparseMatrix&);
	bool TransposeTo_Faster(SparseMatrix&);
	void Input();
	void Output();
	private:
	Trituple<T>* data;
	int rows,cols,terms;
	int maxterms;
	};
	template<class T>
	SparseMatrix<T>::SparseMatrix(int maxt)
	{
	maxterms=maxt;
	data=new Trituple<T>[maxterms];
	terms=rows=cols=0;
	}
	template<class T>
	SparseMatrix<T>::~SparseMatrix()
	{
	if (data!=NULL)
	{
	delete[] data;
	}
	}
	//普通转置
	template<class T>
	bool SparseMatrix<T>::TransposeTo(SparseMatrix &B)
	{
	if (terms>B.maxterms)
	{
	return false;
	}
	B.rows=cols;
	B.cols=rows;
	B.terms=terms;
	if (terms>0)
	{
	int p=0;
	for (int j=1;j<=cols;j++)
	{
	for (int k=0;k<terms;k++)
	{
	if (data[k].col==j)
	{
	B.data[p].row=j;
	B.data[p].col=data[k].row;
	B.data[p].val=data[k].val;
	p++;
	}
	}
	}
	}
	return true;
	}
	//快速转置
	template<class T>
	bool SparseMatrix<T>::TransposeTo_Faster(SparseMatrix& B)
	{
	if (terms>B.maxterms)
	{
	return false;
	}
	B.rows=cols;
	B.cols=rows;
	B.terms=terms;
	if (terms>0)
	{
	int *num,*cpot;
	num=new int[cols];
	cpot=new int[cols];
	for (int j=0;j<cols;j++)
	{
	num[j]=0;
	}
	for (int k=0;k<terms;k++)
	{
	num[data[k].col-1]++;
	}
	//求出B中每一行的起始下标cpot[]
	cpot[0]=0;
	for (int j=1;j<cols;j++)
	{
	cpot[j]=cpot[j-1]+num[j-1];
	}
	//执行转置操作
	for (int p,k=0;k<terms;k++)
	{
	p=cpot[data[k].col-1]++;
	B.data[p].row=data[k].col;
	B.data[p].col=data[k].row;
	B.data[p].val=data[k].val;
	}
	delete[] num;
	delete[] cpot;
	}
	return true;
	}
	template<class T>
	void SparseMatrix<T>::Input()
	{
	cout<<"intput the matrix' row:";
	int row1;
	cin>>row1;
	cout<<"intput the matrix' col:";
	int col1;
	cin>>col1;
	cout<<"input "<<row1<<"*"<<col1<<" matrix"<<endl;
	int number;
	rows=row1;
	cols=col1;
	for (int i=0;i<rows;i++)
	{
	for (int j=0;j<cols;j++)
	{
	cin>>number;
	if (number!=0)
	{
	data[terms].row=i+1;
	data[terms].col=j+1;
	data[terms].val=number;
	terms++;
	}
	}
	}
	}
	template<class T> //输出好看，但是违背了最初的原则
	void SparseMatrix<T>::Output()
	{
	T **tempArray=new T*[rows];
	for (int i1=0;i1<rows;i1++)
	{
	tempArray[i1]=new int[cols];
	}
	for (int j=0;j<rows;j++)
	{
	for (int k=0;k<cols;k++)
	{
	tempArray[j][k]=0;
	}
	}
	for (int i=0;i<terms;i++)
	{
	tempArray[data[i].row-1][data[i].col-1]=data[i].val;
	}
	for (int j=0;j<rows;j++)
	{
	for (int k=0;k<cols;k++)
	{
	cout<<setw(4)<<tempArray[j][k];
	}
	cout<<endl;
	}
	for (int l=0;l<rows;l++)
	{
	delete[] tempArray[l];
	}
	delete tempArray;
	cout<<endl;
	}
	template<class T>
	bool SparseMatrix<T>::AddTo(const SparseMatrix& B)
	{
	if (rows!=B.rows||cols!=B.cols)
	{
	return false;
	}
	bool flag=false;
	int tempTerms=terms;
	for (int i=0;i<B.terms;i++)
	{
	flag=false;
	for (int j=0;j<tempTerms;j++)
	{
	if (data[j].col==B.data[i].col&&data[j].row==B.data[i].row)
	{
	data[j].val+=B.data[i].val;
	flag=true;
	}
	}
	if (flag==false)
	{
	data[++terms-1].col=B.data[i].col; //数组下标操作注意事项
	data[terms-1].row=B.data[i].row;
	data[terms-1].val=B.data[i].val;
	}
	}
	return true;
	}
	int main()
	{
	cout<<"此程序演示稀疏矩阵的普通转置和快速转置操作"<<endl;
	SparseMatrix<int> sm(50);
	SparseMatrix<int> sm1(50);
	SparseMatrix<int> sm2(50);
	sm.Input();
	cout<<"sm is"<<endl;
	sm.Output();
	sm.TransposeTo(sm1);
	cout<<"Transposition of sm is "<<endl;
	sm1.Output();
	sm.TransposeTo_Faster(sm2);
	cout<<"Transposition of sm is "<<endl;
	sm2.Output();
	SparseMatrix<int> sm3;
	cout<<"input a new matrix"<<endl;
	sm3.Input();
	cout<<"sm3 is"<<endl;
	sm3.Output();
	if(sm.AddTo(sm3))
	{
	cout<<"after adding sm3 ,sm is"<<endl;
	sm.Output();
	}
	else
	cout<<"the two matrix can't add"<<endl;
	cout<<"Good job!"<<endl;
	system("pause");
	return 0;
	}

view raw 2013100302.cpp hosted with ❤ by GitHub