稀疏矩阵计算器
实 习 报 告
题目:编制一个稀疏矩阵运算器的程序
班级:计算机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<书
本有较详细的说明。给予本次作业一个较大的帮助。
2(整个程序主要运用了矩阵运算的
,利用创建矩阵,分析数据,行列是
否匹配,矩阵运算,矩阵输出。
3. 本次作业只有一个重要的算法,NiMatrix求逆,本来打算三元组形式进行
运算,但由于求矩阵的行列式值和求代数余子比较麻烦;后来把三元组形
式转换为一般矩阵形式计算。
4. 整个程序运行期间不是实行动态存储管理,故占用空间比较大;特别是执
行稀疏矩阵的求逆过程。
5. 主要算法的时空分析:
其中称疏矩阵转置时间复杂度为:O(n);加法,减法和乘法时间复杂度为:
O(m×n);但求逆的‘时间复杂度’比较复杂。
五、用户手册
1(本程序的运行环境为DOS操作系统,执行文件为:稀疏矩阵计算器.exe。 2(进入演示程序后即显示文本方式的用户界面:
作者班级、姓名、学号
功能选项
测
试
数
据
3(进入界面后可按用户需要选择功能选项,直接输入0-5其中一个数字。
4(例如加法:两个矩阵相加,按提示先输入矩阵A的行数、列数、非零个
数;再按提示输入各个非零元素的行、列、值,按回车。减法、乘法输
入与加法类似。
5(注意:输入数据必须按一定格式“行数,列数,非零个数” “行,列,
值”
六、测试结果
1(按题目测试要求输入:
例如:求逆阵
求逆阵功能
输入数据
结 果
2(程序在输入方面有一定测试,如果输入不合格,会显示错误信息。
3(经多组数据测试显示,程序运行结果符合题目要求。 七、附录
源程序文件清单:
稀疏矩阵计算器.cpp
八、参考资料
《数据结构》(C语言版)——清华大学出版社; 作者: 严蔚敏、吴伟民;
《数据结构题集》(C语言版)——清华大学出版社; 作者: 严蔚敏、吴伟民、米宁
《程序设计题典》(C语言版)——清华大学出版社; 作者: 李春葆