数据结构课程设计：稀疏矩阵操作

一、需求分析
二、概要设计
三、详细设计：Cpp1.cpp
四、调试分析
五、用户手册及测试数据：执行Cpp1.exe
六、附录

[数据结构] 数据结构稀疏矩阵加法实验报告

一、需求分析
假设稀疏矩阵M和N均以三元组表作为存储结构，试写出矩阵相加的算法 ；
另设三元组表存放结果矩阵。
处理要求：
1．输入稀疏矩阵M和N。
2．检测M和N能否相加
3．矩阵相加运算
4．打印输出结果
矩阵相加测试实例：输入
M= ，N=

二、概要设计
1．稀疏矩阵三元数组定义如下：
ADT SparseMatrix {
数据对象：
m和n分别称为矩阵的行数和列数 }
数据关系：R={ Row, Col }

基本操作：
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
#include
#include
#include

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");
}