#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=1j<=colsj++)
{
for (int k=0k<termsk++)
{
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=0j<colsj++)
{
num[j]=0
}
for (int k=0k<termsk++)
{
num[data[k].col-1]++
}
//求出B中每一行的起始下标cpot[]
cpot[0]=0
for (int j=1j<colsj++)
{
cpot[j]=cpot[j-1]+num[j-1]
}
//执行转置 *** 作
for (int p,k=0k<termsk++)
{
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=0i<rowsi++)
{
for (int j=0j<colsj++)
{
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=0i1<rowsi1++)
{
tempArray[i1]=new int[cols]
}
for (int j=0j<rowsj++)
{
for (int k=0k<colsk++)
{
tempArray[j][k]=0
}
}
for (int i=0i<termsi++)
{
tempArray[data[i].row-1][data[i].col-1]=data[i].val
}
for (int j=0j<rowsj++)
{
for (int k=0k<colsk++)
{
cout<<setw(4)<<tempArray[j][k]
}
cout<<endl
}
for (int l=0l<rowsl++)
{
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=0i<B.termsi++)
{
flag=false
for (int j=0j<tempTermsj++)
{
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
}
#include <stdio.h>#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std
#define Max 12500
#define Elemtype int
typedef struct {
int i ,j
Elemtype e
}Triple
typedef struct {
Triple data[Max+1]
int mu,nu,tu
}Tsmatrix
int Createsmatrix(Tsmatrix &M)
{ int n
cout<<"请输入稀疏矩阵的元素个数n"<<endl
cin>>n
M.tu=n
cout<<"请输入稀疏矩阵的行数,列数:"<<endl
cin>>M.mu>>M.nu
int i
for(i=1i<=ni++){
cout<<"请输入稀疏矩阵的行下标和列下标,及数据"<<endl
cin>>M.data[i].i>>M.data[i].j>>M.data[i].e
}
return 1
}
int Transpose(Tsmatrix M , Tsmatrix &T)
{
T.mu=M.nuT.nu=M.mu T.tu=M.tu
if(T.tu){
int col , p , q=1
for(col=1col<=M.nu++col)
for(p=1p<=M.tu++p)
if (M.data[p].j==col){
T.data[q].i=M.data[p].jT.data[q].j=M.data[p].i
T.data[q].e=M.data[p].e ++q}
}
return 1
}
int Print(Tsmatrix M)
{
int iint p=1
{
for (i=1i<=M.mu*M.nui++)
if(i==((M.data[p].i-1)*M.nu+M.data[p].j))
{
if(M.data[p].j==M.nu)
{ cout<<M.data[p].e<<endlp++}
else
{ cout<<M.data[p].e<<" "p++}
}
else if(i%M.nu==0) cout<<"0"<<endl
else cout<<"0 "
}
cout<<"\n"<<endl
return 1
}
int Addsmatrix(Tsmatrix a, Tsmatrix b, Tsmatrix &c)
{
int s=1,t=1,k=1Elemtype temp
if(a.mu!=b.mu||a.nu!=b.nu) return 0
if(a.tu == 0) {c=breturn 1}
if(b.tu==0) {c=areturn 1}
if(a.tu==0 &&b.tu==0) { c=areturn 1}
while(!(s>a.tu &&t>b.tu))
{
if(a.data[s].i>b.data[t].i)
{
c.data[k]=b.data[t]
k++ t++
}
if(a.data[s].i<b.data[t].i)
{
c.data[k]=a.data[s]
k++ s++
}
if(a.data[s].i==b.data[t].i)
{
if(a.data[s].j>b.data[t].j)
{
c.data[k]=b.data[t]
k++t++
}
if(a.data[s].j<b.data[t].j)
{
c.data[k]=a.data[s]
k++s++
}
if(a.data[s].j==b.data[t].j)
{
temp=a.data[s].e+b.data[t].e
if(temp==0){s++t++}
else
{ c.data[k].e=tempc.data[k].i=a.data[s].ic.data[k].j=a.data[s].j
s++t++k++
}
}
}//if
if(s>a.tu&&t<=b.tu)
{
while(t<=b.tu)
{
c.data[k]=b.data[t]
k++t++
}
}
if(t>b.tu&&s<=a.tu)
{
while(s<=a.tu)
{
c.data[k]=a.data[s]
k++s++
}
}
}//while
c.tu=k-1c.mu=a.muc.nu=a.nu
}
return 1int main()
{
Tsmatrix a,b,c
Createsmatrix( a)
Createsmatrix( b)
Print(a)
Print(b)
Addsmatrix(a,b,c)
Print(c)
return 1
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)