稀疏矩阵C 语言实现.doc

#include<iostream>
#include<iomanip>
usingnamespacestd;

template<classT>
//三元组
structTrituple
{
introw;
intcol;
Tval;
};
//稀疏矩阵声明
template<classT>
classSparseMatrix
{
public:
SparseMatrix(intmaxt=100);
~SparseMatrix();
boolTransposeTo(SparseMatrix&);
boolAddTo(constSparseMatrix&);
boolTransposeTo_Faster(SparseMatrix&);
voidInput();
voidOutput();
private:
Trituple<T>*data;
introws,cols,terms;
intmaxterms;
};
template<classT>
SparseMatrix<T>::SparseMatrix(intmaxt)
{
maxterms=maxt;
data=newTrituple<T>[maxterms];
terms=rows=cols=0;
}
template<classT>
SparseMatrix<T>::~SparseMatrix()
{
if(data!=NULL)
{
delete[]data;
}
}
//普通转置
template<classT>
boolSparseMatrix<T>::TransposeTo(SparseMatrix&B)
{
if(terms>B.maxterms)
{
returnfalse;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if(terms>0)
{
intp=0;
for(intj=1;j<=cols;j++)
{
for(intk=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++;
}
}
}
}
returntrue;
}
//快速转置
template<classT>
boolSparseMatrix<T>::TransposeTo_Faster(SparseMatrix&B)
{
if(terms>B.maxterms)
{
returnfalse;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if(terms>0)
{
int*num,*cpot;
num=newint[cols];
cpot=newint[cols];
for(intj=0;j<cols;j++)
{
num[j]=0;
}
for(intk=0;k<terms;k++)
{
num[data[k].col-1]++;
}
//求出B中每一行的起始下标cpot[]
cpot[0]=0;
for(intj=1;j<cols;j++)
{
cpot[j]=cpot[j-1]+num[j-1];
}
//执行转置操作
for(intp,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;
}
returntrue;
}
template<classT>
voidSparseMatrix<T>::Input()
{
cout<<"intputthematrix'row:";
introw1;
cin>>row1;
cout<<"intputthematrix'col:";
intcol1;
cin>>col1;
cout<<"input"<<row1<<"*"<<col1<<"matrix"<<endl;
intnumber;
rows=row1;
cols=col1;
for(inti=0;i<rows;i++)
{
for(intj=0;j<cols