稀疏矩阵的相加
题 目: 稀疏矩阵的相加
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<<"相加成功"<
#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<<"输入错误"<体会
这次实验使我对稀疏矩阵这部分内容的了解和认识有所加深,包括稀疏矩阵的存储结构、创建过、输出和矩阵相加的实现等等。这次实验使我对数据结构和算法的认识进一步加深,为以后的程序设计积累了宝贵的经验。
这次设计虽然达到了实验的要求,但仍存在一些问题,程序功能不是很健全,对一些特殊的操作是否会使程序出错,对于出错程序是否能处理等等。这些问题都有待解决。算法方面也有待改进,我觉得程序若采用十字链表的存储形式来对矩阵相加的算法进行实现会使算法更简洁些,程序中可以不用通过比较行标和列标而只通过比较指针的就可实现对矩阵相加的相应情况的处理。