稀疏矩阵的相加
题 目: 稀疏矩阵的相加
1、 问题描述
稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现两个矩阵相加运算。稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。
2、
2.1.存储结构设计
稀疏矩阵的行逻辑连接的顺序表存储结构表示如下:
#define MAXSIZE 20 /*非零元个数最大值*/
最大值*/#define MAXRC 10 /*各行第一个非零元总数
typedef struct{
,列下标*/ int i,j; /*行下标
int e; /*非零元值*/
}Triple;
typedef struct { /*行逻辑链接的顺序表*/
Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int rpos[MAXRC+1]; /*各行第一个非零元的位置表*/
int mu,nu,tu; /*阵的行数、列数和非零元个数*/
}TSMatrix;
2.2.主要算法设计
对2个矩阵相加的算法如下:
bool AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) /*求稀疏矩阵的和Q=M+N*/
{
int p=1,q=1,k=1;
if(M.tu==0&&N.tu==0) /*为空矩阵的情况*/
{
cout<<"该矩阵为空矩阵"<
N.data[q].i) /*M的行值比N的大取N的值*/
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
else /*M的行值和N一样大的情况*/
{
if(M.data[p].jN.data[q].j)/*M的列值比M的大取N的值*/
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
else /*M和N的列值相等*/
{
if(M.data[p].e+N.data[q].e!=0)/*相加结果不为0才取M值*/
{
Q.data[k].i=M.data[q].i;
Q.data[k].j=M.data[q].j;
Q.data[k].e=M.data[q].e+N.data[p].e;
k++;
}
p++;
q++;
}
}
}
while(q<=N.tu) /*再看N矩阵,直接取N值*/
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
if(M.mu>N.mu) Q.mu=M.mu;/*Q的行和列的值取M,N的最大值*/
else Q.mu=N.mu;
if(M.nu>N.nu) Q.nu=M.nu;
else Q.nu=N.nu;
Q.tu=k-1;
cout<<"相加成功"<报告
3.1调试过程
程序刚写完时有不少问题,像有些变量忘定义,符号错误等等,一些很低级的错误,主要是编程过程中不仔细造成的。改掉这些错误后,程序可以运行了,但用例子进行测试时又出现错误了,运行的结果不正确。就是矩阵相加的结果部分不正确,初步断定算法写的有问题,就对该部分进行调试,设置断点到矩阵相加函数,执行到断点,输入测试用例后,开始观察各变量的值是否正常。刚开始就发现执行顺序有问题,才发现自己误把矩阵的三元表存储当成是数组的形式了,数组是从0开始而三元组是从1开始的,初值设置有问题,于是都设为1,程序运行后与期待结果接近了.但发现程序对于两个矩阵取同一位置时的值相加是否为0的细节处理的不是很好,于是重新作处理,程序结果才显示正确。
3.2.对设计和编码的讨论和分析
这次设计主要包括以下几个部分:稀疏矩阵的存储结构、矩阵的创建、矩阵的输出、矩阵相加算法的实现、操作说明书的显示部分和主函数。其中稀疏矩阵的存储结构采用行逻辑连接的顺序表的形式。矩阵的创建部分是通过先设置一个初值,然后将后输入的值与前一个值进行比较来进行判断输入的值是否合法来对输入值进行筛选的,取符合要求的值建立矩阵。矩阵输出部分采用一行一行的输出方式,至到输出完为止。矩阵相加部分算法再上面已给出,也给了详细的说明这里就不多说了。说明书显示部分都是一些输出操作,主要是把该程序的操作发发提示给使用者,来方便使用者使用。主函数部分通过输入操作符对程序进行操作,这些操作都是通过调用各个函数来实现的。
4.源程序清单和运行结果
4.1程序代码如下:
#include
#include
using namespace std;
/*稀疏矩阵的三元组顺序表类型TSMatrix的定义*/ #define MAXSIZE 20 /*非零元个数最大值*/
#define MAXRC 10
typedef struct{
int i,j; /*行下标,列下标*/
int e; /*非零元值*/
}Triple;
typedef struct { /*行逻辑链接的顺序表*/
Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int rpos[MAXRC+1]; /*各行第一个非零元的位置表*/
int mu,nu,tu; /*阵的行数、列数和非零元个数*/ }TSMatrix;
bool CreateSMatrix(TSMatrix &M) /*创建一个稀疏矩阵*/ {int p=1,a,b,c;
cout<<"请输入矩阵的行列和非零元素个数"<>M.mu>>M.nu>>M.tu;
if(M.tu>MAXSIZE||M.tu<=0||M.tu>M.mu*M.nu)
{
cout<<"输入错误"<>a>>b>>c;
M.data[0].i=1;
M.data[0].j=1;
if(a<=M.mu&&b<=M.nu&&c!=0)
{
if(a>M.data[p-1].i||(a==M.data[p-1].i&&b>=M.data[p-1].j))/*行值比前一个大或行值等于前一个列值小于等于前一个元素*/
{
M.data[p].i=a;
M.data[p].j=b;
M.data[p].e=c;
p++;
cout<<"输入成功"<N.data[q].i)
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
else
{
if(M.data[p].jN.data[q].j)
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
else
{
if(M.data[p].e+N.data[q].e!=0)
{
Q.data[k].i=M.data[q].i;
Q.data[k].j=M.data[q].j;
Q.data[k].e=M.data[q].e+N.data[p].e;
k++;
}
p++;
q++;
}
}
}
while(q<=N.tu)
{
Q.data[k].i=N.data[q].i;
Q.data[k].j=N.data[q].j;
Q.data[k].e=N.data[q].e;
k++;
q++;
}
if(M.mu>N.mu) Q.mu=M.mu;
else Q.mu=N.mu;
if(M.nu>N.nu) Q.nu=M.nu;
else Q.nu=N.nu;
Q.tu=k-1;
cout<<"相加成功"<>select;
if(select==0)break;
switch(select)
{
case 1: CreateSMatrix(A);
break;
case 2: CreateSMatrix(B);
break;
case 3: PrintMatrix(A);
break;
case 4: PrintMatrix(B);
break;
case 5: AddSMatrix(A,B,C);
break;
case 6: PrintMatrix(C);
break;
default:cout<<"输入错误"<