编程实现稀疏矩阵转置、加法、减法的方法

0
作 者 ：Roam 日 期 : 2009-11-10 , , , , , , ,

稀疏矩阵的输入采用三元组形式  下面程序主要实现其矩阵的转置、加法和减法

至于稀疏矩阵的求逆自己还在学习中   其方法按照线性代数来说 先求其行列式判断是否可逆 再求其伴随矩阵

根据公式 A=1*（A*）/|A|   其中A*为伴随矩阵 ，|A|为矩阵的行列式

#include <iostream>
#define MAXSIZE 12500//假设非零元个数的最大值为12500
#define OK 1
#define ERROR 0
using namespace std;
typedef int ElemType;//定义ElemType的类型
typedef struct{
int i,j;//该非零元的行下表和列下表
ElemType e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];//非零元三元组表
int mu,nu,tu;//矩阵的行数、列数和非零元个数
}TSMatrix;
int CreateSMatrix(TSMatrix &M){
//采用三元组顺序表存储表示，创建稀疏矩阵M
cout<<”请输入稀疏矩阵的行数、列数和非零元个数：”<<endl;
cin>>M.mu>>M.nu>>M.tu;
if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu))
//判断行值、列值、元素个数是否合法
return ERROR;
for(int i=1;i<=M.tu;i++){//输入稀疏矩阵元素
cout<<”请输入元素坐标及大小：”<<endl;
cin>>M.data[i].i>>M.data[i].j>>M.data[i].e;
if((M.data[i].i<=0)||(M.data[i].j<=0)){
cout<<”输入错误，请重新输入”<<endl;
cin>>M.data[i].i>>M.data[i].j>>M.data[i].e;
}//if
}//for i
return OK;
}
int DestroySMatrix(TSMatrix &M){
//清除采用三元组顺序表存储表示的稀疏矩阵M
for(int i=1;i<=M.tu;i++){
M.data[i].i=0;
M.data[i].j=0;
M.data[i].e=0;
}//for i
M.mu=0;
M.nu=0;
M.tu=0;
return OK;
}
int PrintSMatrix(TSMatrix M){
//输出采用三元组顺序表存储表示的稀疏矩阵M
if((M.mu<=0)||(M.nu<=0)||(M.tu<=0))
return ERROR;
cout<<endl;
for(int row=1;row<=M.mu;row++){
for(int col=1;col<=M.nu;col++){
for(int i=1;i<=M.tu;i++){
if((M.data[i].i==row)&&(M.data[i].j==col)){
cout<<M.data[i].e<<” “;
goto loop;
}//if
}//for i
cout<<”0″<<” “;
loop:;
}//for col
cout<<endl;
}//for row
return OK;
}
int AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){
//求采用三元组顺序表存储表示的稀疏矩阵M和N的和，,结果赋给矩阵Q
if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(N.mu<=0)||(N.nu<=0)||(N.tu<=0))
return ERROR;
if(M.mu!=N.mu||M.nu!=N.nu)
return ERROR;
Q.mu=M.mu;
Q.nu=M.nu;
Q.tu=0;
int x=0,y=0;
for(int i=1;i<=Q.mu;i++){
for(int j=1;j<=Q.nu;j++){
for(int p=1;p<=M.tu;p++){
if((i==M.data[p].i)&&(j==M.data[p].j)){
x=M.data[p].e;
break;
}
else x=0;
}//for p
for(int q=1;q<=N.tu;q++){
if((i==N.data[q].i)&&(j==N.data[q].j)){
y=N.data[q].e;
break;
}
else y=0;
}//for q
if((x+y)!=0){
Q.data[Q.tu+1].i=i;
Q.data[Q.tu+1].j=j;
Q.data[Q.tu+1].e=x+y;
Q.tu++;
}//if
}//for j
}//for i
return OK;
}
int SubSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){
//求采用三元组顺序表存储表示的稀疏矩阵M和N的差,结果赋给矩阵Q
if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(N.mu<=0)||(N.nu<=0)||(N.tu<=0))
return ERROR;
if(M.mu!=N.mu||M.nu!=N.nu)
return ERROR;
Q.mu=M.mu;
Q.nu=M.nu;
Q.tu=0;
int x=0,y=0;
for(int i=1;i<=Q.mu;i++){
for(int j=1;j<=Q.nu;j++){
for(int p=1;p<=M.tu;p++){
if((i==M.data[p].i)&&(j==M.data[p].j)){
x=M.data[p].e;
break;
}
else x=0;
}//for p
for(int q=1;q<=N.tu;q++){
if((i==N.data[q].i)&&(j==N.data[q].j)){
y=N.data[q].e;
break;
}
else y=0;
}//for q
if((x-y)!=0){
Q.data[Q.tu+1].i=i;
Q.data[Q.tu+1].j=j;
Q.data[Q.tu+1].e=x-y;
Q.tu++;
}//if
}//for j
}//for i
return OK;
}
int FastTransposeSMatrix(TSMatrix M,TSMatrix &T){
//采用三元组顺序表存储表示，求稀疏矩阵M的转职矩阵T
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu){
int num[M.nu],cpot[M.nu];
for(int col=1;col<=M.nu;col++) num[col]=0;
for(int t=1;t<=M.tu;t++) num[M.data[t].j]++;//求M中每一列含有非零元个数
cpot[1]=1;//求第col列中第一个非零元在b.data中的序号
for(int col=2;col<=M.nu;col++) cpot[col]=cpot[col-1]+num[col-1];
for(int p=1,q=1,col;p<=M.tu;p++){
col=M.data[p].j;
q=cpot[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;
++cpot[col];
}//for p
}//if T.tu
return OK;
}
int main(){
system (“CLS”);
TSMatrix M,N,T,Q;//声明M、N、T、Q为稀疏矩阵
cout<<”1.矩阵加法运算\n2.矩阵减法运算\n3.矩阵转置运算\n4.退出\n请输入1~4:”;
int i;
while(cin>>i){
switch(i){
case 1: CreateSMatrix(M);//创建稀疏矩阵M
PrintSMatrix(M);//显示稀疏矩阵M
CreateSMatrix(N);//创建稀疏矩阵N
PrintSMatrix(N);//显示稀疏矩阵N
AddSMatrix(M,N,Q);//将稀疏矩阵M与N的和存入矩阵Q中
cout<<”加法结果：”;
PrintSMatrix(Q);//显示矩阵Q
break;
case 2: CreateSMatrix(M);//创建稀疏矩阵M
PrintSMatrix(M);//显示稀疏矩阵M
CreateSMatrix(N);//创建稀疏矩阵N
PrintSMatrix(N);//显示稀疏矩阵N
SubSMatrix(M,N,Q);//将稀疏矩阵M与N的差存入矩阵Q中
cout<<”减法结果：”;
PrintSMatrix(Q);//显示矩阵Q
break;
case 3: CreateSMatrix(M);//创建稀疏矩阵M
PrintSMatrix(M);//显示稀疏矩阵M
FastTransposeSMatrix(M,T);//将稀疏矩阵M转置，结果存入矩阵T中
cout<<”转置矩阵：”;
PrintSMatrix(T);//显示稀疏矩阵T
break;
case 4: return 0;
default: system (“CLS”);
cout<<”\n*输入错误，请重新输入*\n”<<endl;
break;
}
cout<<”1.矩阵加法运算\n2.矩阵减法运算\n3.矩阵转置运算\n4.退出\n请输入1~4:”;
}
}

#include <iostream>

#define MAXSIZE 12500//假设非零元个数的最大值为12500

#define OK 1

#define ERROR 0

using namespace std;

typedef int ElemType;//定义ElemType的类型

typedef struct{

int i,j;//该非零元的行下表和列下表

ElemType e;

}Triple;

typedef struct{

Triple data[MAXSIZE+1];//非零元三元组表

int mu,nu,tu;//矩阵的行数、列数和非零元个数

}TSMatrix;

int CreateSMatrix(TSMatrix &M){

//采用三元组顺序表存储表示，创建稀疏矩阵M

cout<<”请输入稀疏矩阵的行数、列数和非零元个数：”<<endl;

cin>>M.mu>>M.nu>>M.tu;

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu))

//判断行值、列值、元素个数是否合法

return ERROR;

for(int i=1;i<=M.tu;i++){//输入稀疏矩阵元素

cout<<”请输入元素坐标及大小：”<<endl;

cin>>M.data[i].i>>M.data[i].j>>M.data[i].e;

if((M.data[i].i<=0)||(M.data[i].j<=0)){

cout<<”输入错误，请重新输入”<<endl;

cin>>M.data[i].i>>M.data[i].j>>M.data[i].e;

}//if

}//for i

return OK;

}

int DestroySMatrix(TSMatrix &M){

//清除采用三元组顺序表存储表示的稀疏矩阵M

for(int i=1;i<=M.tu;i++){

M.data[i].i=0;

M.data[i].j=0;

M.data[i].e=0;

}//for i

M.mu=0;

M.nu=0;

M.tu=0;

return OK;

}

int PrintSMatrix(TSMatrix M){

//输出采用三元组顺序表存储表示的稀疏矩阵M

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0))

return ERROR;

cout<<endl;

for(int row=1;row<=M.mu;row++){

for(int col=1;col<=M.nu;col++){

for(int i=1;i<=M.tu;i++){

if((M.data[i].i==row)&&(M.data[i].j==col)){

cout<<M.data[i].e<<” “;

goto loop;

}//if

}//for i

cout<<”0″<<” “;

loop:;

}//for col

cout<<endl;

}//for row

return OK;

}

int AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){

//求采用三元组顺序表存储表示的稀疏矩阵M和N的和，,结果赋给矩阵Q

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(N.mu<=0)||(N.nu<=0)||(N.tu<=0))

return ERROR;

if(M.mu!=N.mu||M.nu!=N.nu)

return ERROR;

Q.mu=M.mu;

Q.nu=M.nu;

Q.tu=0;

int x=0,y=0;

for(int i=1;i<=Q.mu;i++){

for(int j=1;j<=Q.nu;j++){

for(int p=1;p<=M.tu;p++){

if((i==M.data[p].i)&&(j==M.data[p].j)){

x=M.data[p].e;

break;

}

else x=0;

}//for p

for(int q=1;q<=N.tu;q++){

if((i==N.data[q].i)&&(j==N.data[q].j)){

y=N.data[q].e;

break;

}

else y=0;

}//for q

if((x+y)!=0){

Q.data[Q.tu+1].i=i;

Q.data[Q.tu+1].j=j;

Q.data[Q.tu+1].e=x+y;

Q.tu++;

}//if

}//for j

}//for i

return OK;

}

int SubSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){

//求采用三元组顺序表存储表示的稀疏矩阵M和N的差,结果赋给矩阵Q

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(N.mu<=0)||(N.nu<=0)||(N.tu<=0))

return ERROR;

if(M.mu!=N.mu||M.nu!=N.nu)

return ERROR;

Q.mu=M.mu;

Q.nu=M.nu;

Q.tu=0;

int x=0,y=0;

for(int i=1;i<=Q.mu;i++){

for(int j=1;j<=Q.nu;j++){

for(int p=1;p<=M.tu;p++){

if((i==M.data[p].i)&&(j==M.data[p].j)){

x=M.data[p].e;

break;

}

else x=0;

}//for p

for(int q=1;q<=N.tu;q++){

if((i==N.data[q].i)&&(j==N.data[q].j)){

y=N.data[q].e;

break;

}

else y=0;

}//for q

if((x-y)!=0){

Q.data[Q.tu+1].i=i;

Q.data[Q.tu+1].j=j;

Q.data[Q.tu+1].e=x-y;

Q.tu++;

}//if

}//for j

}//for i

return OK;

}

int FastTransposeSMatrix(TSMatrix M,TSMatrix &T){

//采用三元组顺序表存储表示，求稀疏矩阵M的转职矩阵T

T.mu=M.nu;

T.nu=M.mu;

T.tu=M.tu;

if(T.tu){

int num[M.nu],cpot[M.nu];

for(int col=1;col<=M.nu;col++) num[col]=0;

for(int t=1;t<=M.tu;t++) num[M.data[t].j]++;//求M中每一列含有非零元个数

cpot[1]=1;//求第col列中第一个非零元在b.data中的序号

for(int col=2;col<=M.nu;col++) cpot[col]=cpot[col-1]+num[col-1];

for(int p=1,q=1,col;p<=M.tu;p++){

col=M.data[p].j;

q=cpot[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;

++cpot[col];

}//for p

}//if T.tu

return OK;

}

int main(){

system (“CLS”);

TSMatrix M,N,T,Q;//声明M、N、T、Q为稀疏矩阵

cout<<”1.矩阵加法运算\n2.矩阵减法运算\n3.矩阵转置运算\n4.退出\n请输入1~4:”;

int i;

while(cin>>i){

switch(i){

case 1: CreateSMatrix(M);//创建稀疏矩阵M

PrintSMatrix(M);//显示稀疏矩阵M

CreateSMatrix(N);//创建稀疏矩阵N

PrintSMatrix(N);//显示稀疏矩阵N

AddSMatrix(M,N,Q);//将稀疏矩阵M与N的和存入矩阵Q中

cout<<”加法结果：”;

PrintSMatrix(Q);//显示矩阵Q

break;

case 2: CreateSMatrix(M);//创建稀疏矩阵M

PrintSMatrix(M);//显示稀疏矩阵M

CreateSMatrix(N);//创建稀疏矩阵N

PrintSMatrix(N);//显示稀疏矩阵N

SubSMatrix(M,N,Q);//将稀疏矩阵M与N的差存入矩阵Q中

cout<<”减法结果：”;

PrintSMatrix(Q);//显示矩阵Q

break;

case 3: CreateSMatrix(M);//创建稀疏矩阵M

PrintSMatrix(M);//显示稀疏矩阵M

FastTransposeSMatrix(M,T);//将稀疏矩阵M转置，结果存入矩阵T中

cout<<”转置矩阵：”;

PrintSMatrix(T);//显示稀疏矩阵T

break;

case 4: return 0;

default: system (“CLS”);

cout<<”\n*输入错误，请重新输入*\n”<<endl;

break;

}

cout<<”1.矩阵加法运算\n2.矩阵减法运算\n3.矩阵转置运算\n4.退出\n请输入1~4:”;

}

}

  1. 留言得沙花