稀疏矩阵计算器
实 习 报 告
目:编制一个稀疏矩阵运算器的程序
班级:计算机02,8, 姓名:陈 堪 学号:04 完成日期:2004.7.7 一、需求分析
1(稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算
可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算
的运算器。
2(以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现矩阵转置,求
逆,实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元
组表示,而运算结果的矩阵则以通常的阵列形式列出。
3(演示程序以用户和计算机的对话方式执行,数组的建立方式为边输入边建立。 4(由题目
可知:首先应输入矩阵的行数和列数,并判别给出的两个矩阵的
行、列数对于所要求作的运算是否相匹配。
5(程序可以对三元组的输入顺序不加以限制;根据对矩阵的行列,三元组作直
接插入排序,从而进行运算时,不会产生错误。
6(在用三元组表示稀疏矩阵时,相加、乘积和相减所得结果矩阵应该另生成;
矩阵求逆时,为了算法方便,使用二维数组存放。
7(程序在VC6.0环境下
。
程序执行的命令为:1) 稀疏矩阵转置; 2) 稀疏矩阵加法; 3) 稀疏矩
阵减法; 4) 稀疏矩阵乘法; 5) 稀疏矩阵求逆; 6)退出 8(测试数据:
10 0 0 0 0 0 10 0 0
0 0 0 + 0 0 -1 = 0 0 8
-1 0 0 1 0 -3 0 0 -3
10 0 0 0 10 0
0 9 - 0 -1 = 0 10
-1 0 1 -3 -2 3
4 -3 0 0 1 3 0 0 0 -6 0
0 0 0 8 0 × 4 2 0 = 8 0 0
0 0 1 0 0 0 1 0 0 1 0
0 0 0 0 70 1 0 0 0 0 0
0 0 0
1 0 1 -1 2 -1 -1
-1 1 1 = 3 -1 -2
2 1 1 -1 1 1
二、概要设计
1(抽象数据类型稀疏矩阵的定义如下:
ADT SparseMatrix{
数据对象:D={a|i=1,2,„,m; j=1,2,„,n; ij
a?ElemSet, m和n分别为矩阵的行数和列数} ij
数据关系:R={Row,Col }
Row={,a, a,| 1?i?m, 1?j?n-1} i,ji,j+1
Col = {,a, a,| 1?i?m-1, 1?j?n} i,ji+1,j
基本操作:
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<<"输入有误!!!!"<
>i1>>j1>>e;
if(i1>TM.mu||j1>TM.nu||e==0)
{cout<<"输入有误!!!!"<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].iA.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,原矩阵无逆矩阵!!"<>choice;
cout<清单:
稀疏矩阵计算器.cpp
八、参考资料
《数据结构》(C语言版)——清华大学出版社; 作者: 严蔚敏、吴伟民;
《数据结构题集》(C语言版)——清华大学出版社; 作者: 严蔚敏、吴伟民、米宁
《程序设计题典》(C语言版)——清华大学出版社; 作者: 李春葆