岁堤春晓

本来以为自己可以突破下 能够把逆矩阵完美的解答出来 可是经过一晚上的编写 始终没有取到其矩阵的精华 在网上找了半天 搜到这位朋友的稀疏矩阵计算器 基本上把大部分矩阵的算法都包含进来 下面分享下其内容

1．稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

2．以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

3．演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。

4．由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

5．程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。

6．在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。

7．程序在VC6.0环境下设计。

程序执行的命令为：1) 稀疏矩阵转置;     2) 稀疏矩阵加法;    3) 稀疏矩阵减法; 4) 稀疏矩阵乘法;     5) 稀疏矩阵求逆;     6)退出

二、概要设计

1．抽象数据类型稀疏矩阵的定义如下：

ADT SparseMatrix{

数据对象：D={a_ij|i=1,2,…,m; j=1,2,…,n;

a_ij∈ElemSet, m和n分别为矩阵的行数和列数}

数据关系：R={Row,Col }

Row={﹤a_i,j, a_i,j+1﹥|  1≤i≤m, 1≤j≤n-1}

Col = {﹤a_i,j, a_i+1,j﹥|  1≤i≤m-1, 1≤j≤n}

基本操作：

create(TSMatrix &TM)

操作结果：创建稀疏矩阵矩阵TM

LocateELem(TSMatrix M,int i,int j,int e)

初始条件：稀疏矩阵M存在

操作结果：稀疏矩阵中是否存在非零元素A[i][j]，若存在返回e

disp(TSMatrix TM)

初始条件：稀疏矩阵TM存在

操作结果：通常形式输出稀疏矩阵

InsertSortMatrix(TSMatrix &TM)

初始条件：稀疏矩阵TM存在

操作结果：根据对矩阵的行列，三元组TM作直接插入排序

TransposeSMatrix(TSMatrix M,TSMatrix &T)

初始条件：稀疏矩阵M和T存在

操作结果：求稀疏矩阵M转置的稀疏矩阵T

AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)

初始条件：稀疏矩阵A，B和C存在

操作结果：稀疏矩阵的加法运算:C=A+B

SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C)

初始条件：稀疏矩阵A，B和C存在

操作结果：稀疏矩阵的减法运算:C=A-B

MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)

初始条件：稀疏矩阵A，B和C存在

操作结果：稀疏矩阵的乘法运算:C=A×B

NiMatrix(TSMatrix &TM)

初始条件：稀疏矩阵TM存在

操作结果：稀疏矩阵求逆

}ADT SparseMatrix;

2. 主程序：

void main( )

{初始化；

do {

接受命令；

选择处理命令；

}while(命令！=“退出”)

}

3. 本程序有四个模块，调用关系如下：

主程序模块-》创建矩阵模块-》 矩阵运算模块 -》 矩阵输出模块

三、详细设计

1．三元组的类型

typedef int Status ;

typedef int ElemType;

typedef struct {

int    i,j; // 行下标,列下标

ElemType e; // 非零元素值

}Triple;

typedef struct  {

Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用

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

}TSMatrix;

2．基本操作设定为：

稀疏矩阵的基本操作设置如下：

void create(TSMatrix &TM);

//创建矩阵

void disp(TSMatrix TM);

//通常形式输出稀疏矩阵

Status LocateELem(TSMatrix M,int i,int j,int e);

//三元组表中是否存在非零元素A[i][j]，若存在返回e

void InsertSortMatrix(TSMatrix &TM);

//根据对矩阵的行列，三元组TM作直接插入排序

Status TransposeSMatrix(TSMatrix M,TSMatrix &T);

//矩阵转置的算法

Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);

//矩阵的加法运算:C=A+B

Status SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C);

//矩阵的减法运算:C=A-B

Status MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);

//矩阵的乘法运算:C=A×B

void NiMatrix(TSMatrix &TM);

//矩阵求逆

其中部分操作的算法如下:

void create(TSMatrix &TM)

//创建矩阵

{ int i,j,i1,j1,n,e;

cout<<”输入矩阵的行数、列数和非零元个数(mu,nu,tu):”;

cin>>i>>j>>n;

TM.mu=i;TM.nu=j;TM.tu=0;

if(TM.mu<1||TM.nu<1)

cout<<”输入有误!!!!”<<endl;

for(int k=1;k<=n;k++)

{ cout<<”非零的元素”<<k<<endl<<”坐标、值(i,j,e):”;

cin>>i1>>j1>>e;

if(i1>TM.mu||j1>TM.nu||e==0)

{cout<<”输入有误!!!!”<<endl; k–;}

else if(LocateELem(TM,i1,j1,e)==1)

{cout<<”元素已经存在!”<<endl; k–;;

}

else{

TM.data[k].i=i1;TM.data[k].j=j1;TM.data[k].e=e;TM.tu++;

}

}

InsertSortMatrix(TM); //直接插入排序

}

Status LocateELem(TSMatrix M,int i,int j,int e)

//三元组表中是否存在非零元素A[i][j]，若存在返回e

{int k;

for(k=1;k<=M.tu;k++)

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

{e=M.data[k].e; return TRUE;}

return FALSE;

}

void InsertSortMatrix(TSMatrix &TM)

//根据对矩阵的行列，三元组TM作直接插入排序

{int i,j;

for(i=2;i<=TM.tu;i++) if(TM.data[i].i<TM.data[i-1].i||TM.data[i].i==TM.data[i-1].i

&&TM.data[i].j<TM.data[i-1].j)

{TM.data[0].i=TM.data[i].i;

TM.data[0].j=TM.data[i].j;

TM.data[0].e=TM.data[i].e;

for(j=i-1;TM.data[0].i<TM.data[j].i||TM.data[0].i==TM.data[j].i

&&TM.data[0].j<TM.data[j].j;–j)

{TM.data[j+1].i=TM.data[j].i;

TM.data[j+1].j=TM.data[j].j;

TM.data[j+1].e=TM.data[j].e;

}

TM.data[j+1].i=TM.data[0].i;

TM.data[j+1].j=TM.data[0].j;

TM.data[j+1].e=TM.data[0].e;

}

}

void disp(TSMatrix TM)

//通常形式输出稀疏矩阵

{ int i,j,k,flag=1;

for(i=1;i<=TM.mu;i++)

{ cout<<setw(6);

for(j=1;j<=TM.nu;j++)

{for(k=1;k<=TM.tu;k++)

if(i==TM.data[k].i&&j==TM.data[k].j)

{cout<<TM.data[k].e<<setw(6);flag=0;}

if(flag) cout<<”0″<<setw(6);

flag=1;

}

cout<<endl;

}

}

Status TransposeSMatrix(TSMatrix M,TSMatrix &T)

//矩阵转置的算法

{ int col,p,q;

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(M.tu)

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

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

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 OK;

}

Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)

///三元组表示的稀疏矩阵加法: C=A+B

{ int n=1,m=1,k=1;

ElemType  temp;

if(A.mu==B.mu&&A.nu==B.nu)

{while(m<=A.tu&&n<=B.tu)

//若A当前元素的行号等于B当前元素的行号，则比较其列号，将较小列的元素

//存入C中，如果列号也相等，则将对应的元素值相加后存入C中

if(A.data[m].i==B.data[n].i)

{ if(A.data[m].j<B.data[n].j)

{C.data[k].i=A.data[m].i; C.data[k].j=A.data[m].j;

C.data[k].e=A.data[m].e; k++;m++;

}

else if(A.data[m].j>B.data[n].j)

{C.data[k].i=B.data[n].i; C.data[k].j=B.data[n].j;

C.data[k].e=B.data[n].e; k++;n++;

}

else

{ temp=A.data[m].e+B.data[n].e;

if(temp!=0)//不为0才添加到C中

{C.data[k].i=A.data[m].i; C.data[k].j=A.data[m].j;

C.data[k].e=temp; k++;

}

m++;n++;

}

}

//若A当前元素的行号小于B当前元素的行号，则将A的元素存入C中

else if(A.data[m].i<B.data[n].i)

{C.data[k].i=A.data[m].i; C.data[k].j=A.data[m].j;

C.data[k].e=A.data[m].e; k++;m++;

}

//若A当前元素的行号大于B当前元素的行号，则将B的元素存入C中

else{C.data[k].i=B.data[n].i; C.data[k].j=B.data[n].j;

C.data[k].e=B.data[n].e; k++;n++;

}

//把剩余部分元素存入C中

if(m>A.tu&&n<=B.tu)

for( ;n<=B.tu;n++)

{C.data[k].i=B.data[n].i; C.data[k].j=B.data[n].j;

C.data[k].e=B.data[n].e; k++;

}

if(n>B.tu&&m<=A.tu)

for( ;m<=A.tu;m++)

{C.data[k].i=A.data[m].i; C.data[k].j=A.data[m].j;

C.data[k].e=A.data[m].e; k++;

}

C.mu=A.mu; C.nu=A.nu; C.tu=k-1; return OK;

}

else return ERROR;

}

Status SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C)

/* 三元组表示的稀疏矩阵减法: C=A+B */

{

//稀疏矩阵减法的代码类似于加法

}

Status MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)

//矩阵乘法运算的算法

{ int i,j,k,sum,p=1;

for(i=1;i<=A.mu;i++)

for(j=1;j<=B.nu;j++)

{ sum=0;

for(k=1;k<=A.nu;k++)

sum+=value(A,i,k)*value(B,k,j);

if(sum!=0)

{ C.data[p].i=i; C.data[p].j=j; C.data[p].e=sum; p++; }

}

C.mu=A.mu; C.nu=B.nu; C.tu=p-1; return OK;

}

int JsMatrix(int s[][SIZENUM],int n)

//JsMatrix()函数用于计算行列式,通过递归算法实现

{

}

void N1Matrix(int s[][SIZENUM],float b[][SIZENUM],int n)

//N1Matrix()函数用于求原矩阵各元素对应的余子式，

//存放在数组b[n][n]中，定义为float型

{

}

void NiMatrix(TSMatrix &TM)

//矩阵求逆

{

k=JsMatrix(a,n); 矩阵的行列式的值

if(k==0) cout<<”行列式的值|A|=0,原矩阵无逆矩阵!!”<<endl;

else

{ N1Matrix(a, b,n);

//调用N1Matrix()函数，得到原矩阵各元素对应的”余子式”,存放在数组b[n][n]中

for(i=0;i<n;i++) //求代数余子式，此时b[n][n中存放的为原矩阵各元素对应的"代数余子式"

for(j=0;j<n;j++)

if((i+j)%2!=0 && b[i][j]!=0) b[i][j]=-b[i][j];

for(i=0;i<n;i++) //对b[N][N]转置,此时b[n][n]中存放的为原矩阵的伴随矩阵

for(j=i+1;j<n;j++)

{temp=b[i][j];

b[i][j]=b[j][i];

b[j][i]=temp;

}

print() ;// 打印伴随矩阵A*

for(i=0;i<n;i++)   //求逆矩阵，此时c[n][n]中存放的是原矩阵的逆矩阵

for(j=0;j<n;j++)

c[i][j]=b[i][j]/k;

print() ;// 打印逆矩阵

}//else

}

3.主函数

void main()

{inp: while(1)

{system(“cls”);

int choice;

cout<<endl<<” 请选择操作(0-5):”;

cin>>choice;

cout<<endl;

switch(choice)

{ case 1: cout<<”求转置矩阵”<<endl;

TransposeSMatrix(A,B);

case 2: cout<<”稀疏矩阵C=A+B”<<endl;

AddTSM(A,B,C);

case 3: cout<<”稀疏矩阵C=A-B”<<endl;

SubTSM(A,B,C);

case 4: cout<<”稀疏矩阵C=A×B”<<endl;

MultSMatrix(A,B,C);

case 5: cout<<”求稀疏矩阵逆阵”<<endl;

NiMatrix(A);

case 0:cout<<”谢谢使用!再见!”<<endl<<endl;

return ;

default:cout<<”错误命令!”<<endl;

cout<<”Press any key to continue!”<<endl;

getche();system(“cls”);goto inp;

}//switch

}//whlie(1)

三、调试分析

1．本次作业比较简单，其中矩阵加法在上机习题中曾经做过，稀疏矩阵在书本有较详细的说明。给予本次作业一个较大的帮助。

2．整个程序主要运用了矩阵运算的规则，利用创建矩阵，分析数据，行列是否匹配，矩阵运算，矩阵输出。

1. 本次作业只有一个重要的算法，NiMatrix求逆,本来打算三元组形式进行运算，但由于求矩阵的行列式值和求代数余子比较麻烦；后来把三元组形式转换为一般矩阵形式计算。
2. 整个程序运行期间不是实行动态存储管理，故占用空间比较大；特别是执行稀疏矩阵的求逆过程。
3. 主要算法的时空分析：

其中称疏矩阵转置时间复杂度为：O(n)；加法，减法和乘法时间复杂度为：O(m×n)；但求逆的‘时间复杂度’比较复杂。

上面内容基本给出了算法的描述 如果需要源代码或者实现的结果  可以发邮件

在此感谢陈堪同学的分享