#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>#define maxsize 12500
#define elemtype int
typedef int status
typedef struct
{
int i,j
elemtype e
}triple
typedef struct
{
triple data[maxsize+1]
int mu,nu,tu
}tsmatrix
tsmatrix creatematrix()
{
tsmatrix M
int n
printf("输入矩阵的行数,列数,个数:\n")
scanf("%d%d%d",&M.mu,&M.nu,&M.tu)
printf("输入非零元的值(行数、列数和值):\n")
for(n=0n<M.tun++)
scanf("%d%d%d",&M.data[n].i,&M.data[n].j,&M.data[n].e)
return M
}
tsmatrix transposesmtrix(tsmatrix M,tsmatrix T)
{
int q,col,p
T.mu=M.nu T.nu=M.mu T.tu=M.tu
if(T.tu)
{
q=0
for(col=0col<M.nucol++)
for(p=0p<M.tup++)
if(M.data[p].j==col)
{
T.data[q].i=M.data[p].j
T.data[q].j=M.data[p].i
T.data[q].e=M.data[p].e
++q
}
}
return T
}
void print(tsmatrix M)
{
int x,y,n,k
for(x=0x<M.mux++)
{
for(y=0y<M.nuy++)
{
k=0
for(n=0n<M.tun++)
if((M.data[n].i==x)&&(M.data[n].j==y))
{
printf("%3d",M.data[n].e)
k=1
}
if(k==0)
printf("%3d",k)
}
printf("\n")
}
}
void main()
{
tsmatrix M,T
M=creatematrix()
printf("M矩阵为:\n")
print(M)
T=transposesmtrix(M,T)
printf("转置后的矩阵为:\n")
print(T)
}
这是我写的,有矩阵的输出 和矩阵的转置,希望对你有用!
#include "stdio.h"#define MAXSIZE 100 //非零个数100
#define MAXROW 20 //最大行数20
#define MAXCOL 20 //最大列数20
typedef struct
{
int data[MAXSIZE+1][3]//非零元素的三元组表,data[0]未用
int m,n,len
}smat
void matadd(smat A,smat B,smat C)
{ //稀疏矩阵相加
int i=1,j=1,k=1,a[20][20]
while(i<=A.len||j<=B.len)
{
if(A.data[i][0]>B.data[j][0]||i>A.len) //当A的当前行号大于B的行号时,则将小的行号B加入C
{
C.data[k][0]=B.data[j][0]
C.data[k][1]=B.data[j][1]
C.data[k][2]=B.data[j][2]
k++ j++
}
else if(A.data[i][0]<B.data[j][0]||j>B.len) //当A的当前行号小于B的行号时,则将小的行号A加人C
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]
k++ i++
}
else//若A当前行号等于B当前行,则比较列号将较小的列项存入C,如果相等就相加存入C
{
if(A.data[i][1]>B.data[j][1])
{
C.data[k][0]=B.data[j][0]
C.data[k][1]=B.data[j][1]
C.data[k][2]=B.data[j][2]
k++ j++
}
else if(A.data[i][1]<B.data[j][1])
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]
k++ i++
}
else
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]+B.data[j][2]
k++ i++ j++
}
}
}
C.data[0][0]=A.m //将稀疏矩阵的行数放在C.data[0][0]
C.data[0][1]=A.n //将稀疏矩阵的列数放在C.data[0][1]
C.data[0][2]=k-1 //将稀疏矩阵的列数放在C.data[0][2]
i=1j=1k=1
for(i=1i<=C.data[0][0]i++)//初始化阵列式矩阵
{
for(j=1j<=C.data[0][1]j++)
{
a[i][j]=0
}
}
i=1j=1
for(k=1k<=C.data[0][2]k++)
{
i=C.data[k][0] //将行号赋值给i
j=C.data[k][1] //将列号赋值给j
a[i][j]=C.data[k][2] //将非零元素值赋值给a[i][j]
}
i=1
printf(" C=A+B的阵列式形式是:\n")
for(i=1i<=C.data[0][0]i++) //将运算结果以阵列式输出
{
printf("|")
for(j=1j<=C.data[0][1]j++)
{
printf("%4d",a[i][j])
}
printf("|")
printf("\n")
}
}
void matmul(smat A,smat B,smat C)
{ //两个矩阵相乘
int i=1,j=1,k,a[20][20],b[20][20],s[400],p=1,q=1,v=1,w
s[1]=0
for(i=1i<=A.mi++) // //初始化二维数值a[][]
{
for(j=1j<=A.nj++)
{
a[i][j]=0
}
}
for(k=1k<=A.lenk++)
{
i=A.data[k][0]//将A.data[k][0]行号赋值给i
j=A.data[k][1]//将A.data[k][1]列号赋值给j
a[i][j]=A.data[k][2] //将A.data[k][2]非零元素值赋值给a[i][j]
}
k=1
for(p=1p<=B.mp++)
{
for(q=1q<=B.nq++)
{
b[p][q]=0
}
}
for(k=1k<=B.lenk++)
{
p=B.data[k][0]
q=B.data[k][1]
b[p][q]=B.data[k][2]
}
i=1j=1k=1p=1q=1v=1
for(i=1i<=A.mi++) //两个稀疏矩阵相乘,结果放在s[v]里
{
for(q=1q<=B.nq++)
{
for(j=1,p=1j<=A.n,p<=B.mj++,p++)
{
s[v]=s[v]+a[i][j]*b[p][q]
}
v++
s[v]=0
}
v++
s[v]=0
}
w=v-1
v=1
k=1
printf(" C=A*B的阵列式形式是:\n")
for(v=1v<=wv++)//将运算结果以阵列式输出
{
printf("|")
for(k=1k<=B.nk++)
{
printf("%4d",s[v])
v++
}
printf("|")
printf("\n")
}
}
void matsub(smat A,smat B,smat C)
{ //两个稀疏矩阵相减
int i=1,j=1,k=1,a[20][20]
while(i<=A.len||j<=B.len)
{
if(A.data[i][0]>B.data[j][0]||i>A.len) // //当A的当前行号大于B的行数时,则将小的行号B加入C
{
C.data[k][0]=B.data[j][0]
C.data[k][1]=B.data[j][1]
if(B.data[j][2]>=0)
{
C.data[k][2]=B.data[j][2]
}
else
{
C.data[k][2]=-B.data[j][2]
}
k++ j++
}
else if(A.data[i][0]<B.data[j][0]||j>B.len) //当A的当前行号小于B的行数时,则将小的行号A加人C
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]
k++ i++
}
else //若A当前行号等于B当前行,则比较列号将较小的列项存入C,如果相等就相加存入C
{
if(A.data[i][1]>B.data[j][1])
{
C.data[k][0]=B.data[j][0]
C.data[k][1]=B.data[j][1]
if(B.data[j][2]>=0)
{
C.data[k][2]=B.data[j][2]
}
else
{
C.data[k][2]=-B.data[j][2]
}
k++ j++
}
else if(A.data[i][1]<B.data[j][1])
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]
k++ i++
}
else
{
C.data[k][0]=A.data[i][0]
C.data[k][1]=A.data[i][1]
C.data[k][2]=A.data[i][2]-B.data[j][2]
k++ i++ j++
}
}
}
C.data[0][0]=A.m
C.data[0][1]=A.n
C.data[0][2]=k-1
i=1j=1k=1
for(i=1i<=C.data[0][0]i++)
{
for(j=1j<=C.data[0][1]j++)
{
a[i][j]=0
}
}
i=1j=1
for(k=1k<=C.data[0][2]k++)
{
i=C.data[k][0]
j=C.data[k][1]
a[i][j]=C.data[k][2]
}
i=1
printf(" C=A-B的阵列式形式是:\n")
for(i=1i<=C.data[0][0]i++)
{
printf("|")
for(j=1j<=C.data[0][1]j++)
{
printf("%4d",a[i][j])
}
printf("|")
printf("\n")
}
}
void Initsmat(smat A)
{
int i=0,j=0
for(i=0i<=A.mi++)
{
for(j=0j<A.nj++)
{
A.data[i][j]=0
}
}
}
int main()
{
int e,m,n,p,k,a[20][20],b[20][20],i=1,j=1
smat A,B,C
Initsmat(A)
Initsmat(B)
Initsmat(C)
printf(" *************************************************************************\n")
printf("\n")
printf("稀疏矩阵运算器 \n")
printf("\n")
printf(" *************************************************************************\n")
loop1:
printf("\n")
printf(" 请输入第一个三元组A的信息(行数在1~20之间,列数在1~20之间,非零元个数在1~100之间)如果在输入过程想重新输入信息请按0:\n")
printf("请输入行数:")
scanf("%d",&A.m)
if(!(A.m<=20&&A.m>=1))
{
printf("你输入的行号超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
printf("请输入列数:")
scanf("%d",&A.n)
if(A.n>20||A.n<1)
{
printf("你输入的列号超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
printf("请输入三元组的非零个数:")
scanf("%d",&A.len)
if(A.len>100||A.len<1)
{
printf("你输入的非零元个数超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
for(i=1i<=A.leni++)
{
printf("请输入第%d个非零元素的行数:",i)
scanf("%d",&a[i][1])
if(a[i][1]>A.m||a[i][1]<1)
{
printf("输入错误,请重新输入:\n")
goto loop1
}
printf("请输入第%d个非零元素的列数:",i)
scanf("%d",&a[i][2])
if(a[i][2]>A.n||a[i][2]<1)
{
printf("输入错误,请重新输入:\n")
goto loop1
}
printf("请输入第%d个非零元素的数值:",i)
scanf("%d",&a[i][3])
}
Initsmat(A)
for(i=1,k=1i<=A.len,k<=A.leni++,k++)
{
A.data[k][0]=a[i][1]
if(A.data[k][0]>20||A.data[k][0]<1)
{
printf("你输入的行号超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
A.data[k][1]=a[i][2]
if(A.data[k][1]>20||A.data[k][1]<1||A.n>20||A.n<1)
{
printf("你输入的列号超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
A.data[k][2]=a[i][3]
if(A.data[k][2]>32767||A.data[k][2]<-32768)
{
printf("你输入的非零元数值超出范围,请重新输入第一个稀疏矩阵A三元组的信息:\n")
goto loop1
}
}
printf("\n")
printf("稀疏矩阵A的三元组是:\n")
printf("==================\n")
printf("行号 列号 数值\n")
printf("-------------------\n")
k=1
for(k=1k<=A.lenk++)
{
printf("\t%4d%4d%4d\n",A.data[k][0],A.data[k][1],A.data[k][2])
}
printf("==================\n")
goto loop2
loop2:
printf("\n")
printf("请输入第二个三元组B的信息\n")
printf("行数在1~20之间,列数在1~20之间,非零元个数在1~100之间\n")
printf("如果在输入过程想重新输入信息请按0:\n")
printf("请输入行数:")
scanf("%d",&B.m)
if(B.m>20||B.m<1)
{
printf("\n")
printf("你输入的行号超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
printf("请输入列数:")
scanf("%d",&B.n)
if(B.n>20||B.n<1)
{
printf("\n")
printf("你输入的列号超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
printf("请输入三元组的非零个数:")
scanf("%d",&B.len)
if(B.len>100||B.len<1)
{
printf("\n")
printf("你输入的非零元个数超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
i=1j=1k=1
for(i=1i<=A.leni++)
{
printf("请输入第%d个非零元素的行数:",i)
scanf("%d",&b[i][1])
if(b[i][1]>B.m||b[i][1]<1)
{
printf("输入错误,请重新输入:\n")
goto loop2
}
printf("请输入第%d个非零元素的列数:",i)
scanf("%d",&b[i][2])
if(b[i][2]>B.n||b[i][2]<1)
{
printf("输入错误,请重新输入:\n")
goto loop2
}
printf("请输入第%d个非零元素的数值:",i)
scanf("%d",&b[i][3])
}
Initsmat(B)
for(i=1,k=1i<=B.len,k<=B.leni++,k++)
{
B.data[k][0]=b[i][1]
if(B.data[k][0]>20||B.data[k][0]<1||B.m>20||B.m<1)
{
printf("\n")
printf("你输入的行号超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
B.data[k][1]=b[i][2]
if(B.data[k][1]>20||B.data[k][1]<1||B.n>20||B.n<1)
{
printf("\n")
printf("你输入的列号超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
B.data[k][2]=b[i][3]
if(B.data[k][2]>32767||B.data[k][2]<-32768)
{
printf("\n")
printf("你输入的非零元数值超出范围,请重新输入第二个矩阵B三元组的信息:\n")
goto loop2
}
}
printf("\n")
printf("矩阵B的三元组是:\n")
printf("==================\n")
printf("行号 列号 数值\n")
printf("-------------------\n")
k=1
B.data[0][2]=B.len
for(k=1k<=B.lenk++)
{
printf("\t%4d%4d%4d\n",B.data[k][0],B.data[k][1],B.data[k][2])
}
printf("==================\n")
goto loop3
loop3:
printf("\n")
printf("1.两个矩阵相加请选择.\n")
printf("2.两个矩阵相减请选择.\n")
printf("3.两个矩阵相剩请选择.\n")
printf("4.重新输入两个矩阵的三元组请选择\n")
printf("0.退出请选择.\n")
scanf("%d",&e)
if(e==1)
{
if(A.m!=B.m||A.n!=B.n)
{
printf("你输入的两个三元组不符合矩阵相加,请重新选择:\n")
goto loop3
}
matadd(A,B,C)
goto loop3
}
else if(e==2)
{
if(A.m!=B.m||A.n!=B.n)
{
printf("你输入的两个三元组不符合矩阵相减,请重新选择:\n")
goto loop3
}
matsub(A,B,C)
goto loop3
}
else if(e==3)
{
if(A.n!=B.m)
{
printf("你输入的两个三元组不符合矩阵相乘,请重新选择:\n")
goto loop3
}
matmul(A,B,C)
goto loop3
}
else if(e==4)
{
goto loop1
}
else if(e==0)
{
return 0
}
else
{
printf("你输入的选择无效,请重新选择:\n")
goto loop3
}
return 0
}