一、需求分析
二、概要设计
三、详细设计：Cpp1.cpp
四、调试分析
五、用户手册及测试数据：执行Cpp1.exe
六、附录
[数据结构] 数据结构稀疏矩阵加法实验报告
一、需求分析
假设稀疏矩阵M和N均以三元组表作为存储结构,试写出矩阵相加的算法 ；
另设三元组表存放结果矩阵.
处理要求：
1．输入稀疏矩阵M和N.
2．检测M和N能否相加
3．矩阵相加运算
4．打印输出结果
矩阵相加测试实例：输入
M= ,N=
二、概要设计
1．稀疏矩阵三元数组定义如下：
ADT SparseMatrix {
数据对象：
m和n分别称为矩阵的行数和列数 }
数据关系：R=
基本操作：
CreateSMatrix (&M) ;
操作结果：创建稀疏矩阵M.
AddSMatrix (M, N, &Q) ;
初始条件：稀疏矩阵M与N的行数列数相等.
操作结果：求得Q=M+N.
PrintSMatrix (M) ;
初始条件：稀疏矩阵M存在.
操作结果：输出稀疏矩阵M.
} ADT SparseMatrix
①．输入稀疏矩阵M和N.
CreateSMatrix_M (TSMatrix &M) //新建稀疏矩阵M
{ 输入矩阵M的行数,列数和非零元素个数
输入非零元素的行下标,列下标和值 }
// 稀疏矩阵相加,稀疏矩阵用数组来表示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
typedef struct
{
int row;
int col;
int val;
}Element; // 稀疏矩阵元素
#define DIM 10 // 稀疏矩阵维数
#define ARY1_LEN 10 // 稀疏矩阵1数组维数
#define ARY2_LEN 10 // 稀疏矩阵2数组维数
Element ary1[ARY1_LEN+1]; // 稀疏矩阵1数组
Element ary2[ARY2_LEN+1]; // 稀疏矩阵2数组
Element ary3[ARY1_LEN+ARY2_LEN+1]; // 稀疏矩阵之和数组
int cmp(const void *p1, const void *p2);
void matrix_add(Element ary1[], Element ary2[], Element ary3[]);
void print_matrix(Element ary1[], Element ary2[], Element ary3[]);
void main()
{
int i;
int j;
// 初始化稀疏矩阵1和2数组
srand(time(NULL));
for(i = 0; i < ARY1_LEN; i++)
{
ary1[i].row = i % DIM;
ary1[i].col = i % DIM;
ary1[i].val = rand() % 4 + 1;
}
ary1[i].row = -1;
ary1[i].col = -1;
ary1[i].val = 0;
for(i = 0; i < ARY2_LEN; i++)
{
ary2[i].row = i % DIM;
ary2[i].col = (ARY2_LEN - i - 1) % DIM;
ary2[i].val = rand() % 4 + 1;
}
ary2[i].row = -1;
ary2[i].col = -1;
ary2[i].val = 0;
// 将稀疏矩阵1和2相加,结果放到稀疏矩阵之和数组中
matrix_add(ary1, ary2, ary3);
// 打印稀疏矩阵相加的结果
print_matrix(ary1, ary2, ary3);
}
int cmp(const void *p1, const void *p2)
{
Element *pe1 = (Element *)p1;
Element *pe2 = (Element *)p2;
if (pe1->row == pe2->row)
{
return (pe1->col - pe2->col);
}
else
{
return (pe1->row - pe2->row);
}
}
void matrix_add(Element ary1[], Element ary2[], Element ary3[])
{
int i;
int j;
Element *pe;
// 将稀疏矩阵1和2按找行、列顺序由小到大来排序,排序算法在cmp()中定义.
qsort(ary1, ARY1_LEN, sizeof(Element), cmp);
qsort(ary2, ARY2_LEN, sizeof(Element), cmp);
// 先将稀疏矩阵1复制给稀疏矩阵之和数组
memcpy(ary3, ary1, sizeof(Element)*ARY1_LEN);
j = ARY1_LEN;
// 再将稀疏矩阵2的每个元素添加或累加到稀疏矩阵之和数组
for(i = 0; i < ARY2_LEN; i++)
{
pe = (Element *)bsearch(&ary2[i], ary1, ARY1_LEN, sizeof(Element), cmp);
if (pe != (Element *)NULL)
{
ary3[pe-ary1].val += ary2[i].val;
}
else
{
ary3[j++] = ary2[i];
}
}
ary3[j].row = -1;
ary3[j].col = -1;
ary3[j].val = 0;
// 最后将稀疏矩阵之和按找行、列顺序由小到大来排序,排序算法在cmp()中定义.
qsort(ary3, j, sizeof(Element), cmp);
}
void print_matrix(Element ary1[], Element ary2[], Element ary3[])
{
int i;
int j;
int k;
Element key;
Element *pe;
for(k = 0; k < ARY1_LEN+ARY2_LEN+1; k++)
{
if (ary3[k].row == -1)
{
break;
}
}
for(i = 0; i < DIM; i++)
{
for(j = 0; j < DIM; j++)
{
key.row = i;
key.col = j;
pe = (Element *)bsearch(&key, ary1, ARY1_LEN, sizeof(Element), cmp);
if (pe != (Element *)NULL)
{
printf(" %d", pe->val);
}
else
{
printf(" 0");
}
}
if (i == DIM / 2)
{
printf(" +");
}
else
{
printf(" ");
}
for(j = 0; j < DIM; j++)
{
key.row = i;
key.col = j;
pe = (Element *)bsearch(&key, ary2, ARY2_LEN, sizeof(Element), cmp);
if (pe != (Element *)NULL)
{
printf(" %d", pe->val);
}
else
{
printf(" 0");
}
}
if (i == DIM / 2)
{
printf(" =");
}
else
{
printf(" ");
}
for(j = 0; j < DIM; j++)
{
key.row = i;
key.col = j;
pe = (Element *)bsearch(&key, ary3, k, sizeof(Element), cmp);
if (pe != (Element *)NULL)
{
printf(" %d", pe->val);
}
else
{
printf(" 0");
}
}
printf("\n");
}
