二、概要设计
三、详细设计：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 <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 = 0i <ARY1_LENi++)
{
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 = 0i <ARY2_LENi++)
{
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 = 0i <ARY2_LENi++)
{
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 = 0k <ARY1_LEN+ARY2_LEN+1k++)
{
if (ary3[k].row == -1)
{
break
}
}
for(i = 0i <DIMi++)
{
for(j = 0j <DIMj++)
{
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 = 0j <DIMj++)
{
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 = 0j <DIMj++)
{
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")
}
http://hi.baidu.com/alonso13/blog/item/5a454f29a2b513f899250ac6.html稀疏矩阵的定义及转置
#include <iostream>
using namespace std
const int maxNum=100
template <class T>
class Trituple
{
public:
int row
int col
T data
}
template <class T>
class SparseMatrix
{
friend istream&operator >>(istream&in,SparseMatrix<T>&m) //重载输入运算符
{
cout<<"请输入行数，列数以及非零元素个数：" //初始化稀疏矩阵的行、列以及非零元素的个数
in>>m.row>>m.col>>m.terms
if(m.terms>m.maxTerms)
{
cout<<"错误！非零元素溢出!"
}
else
{
for(int i=0i<m.termsi++)
{
cout<<"请输入第"<<i+1<<"个非零元素的行数，列数以及非零元素的值：" //通过初始化三元组来初始化矩阵
in>>m.t[i].row>>m.t[i].col>>m.t[i].data
while((m.t[i].row>=m.row)||(m.t[i].col>=m.col)) //矩阵元素下标检查
{
cout<<"错误！输入的矩阵元素下标越界！请从新输入："
in>>m.t[i].row>>m.t[i].col>>m.t[i].data
}
}
}
return in
}
friend ostream&operator <<(ostream&out,SparseMatrix<T>&m) //重载输出运算符
{
int i,j,k=0
out<<"行:"<<m.row<<" 列:"<<m.col<<" 非零元素个数:"<<m.terms<<endl
/*for(int i=0i<m.termsi++)
{
out<<"M["<<m.t[i].row<<"]["<<m.t[i].col<<"]="<<m.t[i].data<<endl//以 M[行][列] 的形式输出稀疏矩阵
}*/
for(i=0i<m.rowi++)
{
for(j=0j<m.colj++)
{
if((m.t[k].row==i)&&(m.t[k].col==j))
{
out<<m.t[k++].data<<" "
}
else
{
cout<<'0'<<" "
}
}
out<<endl
}
return out
}
private:
int row
int col
int terms
Trituple<T>*t //三元组数组
int maxTerms//最大元素数目
public:
SparseMatrix(int maxSize=maxNum) //构造函数
{
maxTerms=maxSize
row=col=terms=0
t=new Trituple<T>[maxSize]
}
~SparseMatrix()//析构函数
{
delete []t
}
/*SparseMatrix<T>transposedMatrix()//课本上的矩阵转置函数，逻辑正确，但是运行时内存报错
{
int *rowSize=new int[col] //存放转置矩阵各行中的非零元素个数
int *rowStart=new int[col] //存放转置矩阵各行中非零元素开始的存放位置
SparseMatrix<T>tp(maxTerms)//存放转置后的矩阵
tp.row=col
tp.col=row
tp.terms=terms
if(terms>0)
{
int i=0
int j=0
for(i=0i<coli++) //初始化rowSize
rowSize=0
for(i=0i<termsi++)
rowSize[t[i].col]++
rowStart[0]=0
for(i=1i<maxTermsi++) //初始化rowStart
rowStart[i]=rowSize[i]+rowStart[i-1]
//*****************************************
for(i=0i<coli++)
cout<<rowSize[i]<<" "
cout<<endl
for(i=0i<coli++)
cout<<rowStart[i]<<" "
cout<<endl
//******************************************
for(i=0i<termsi++)
{
j=rowStart[t[i].col] //j转置矩阵的三元组的行
//rowStart[t[i].col]++
tp.t[j].row=t[i].col
tp.t[j].col=t[i].row
tp.t[j].data=t[i].data
rowStart[t[i].col]++
}
}
delete []rowSize
delete []rowStart
return tp
}*/
void transposedMatrix(SparseMatrix &tp) //自己编写的转置矩阵函数
{
int i,j
if(terms>0)
{
int Row=0
tp.col=row//初始化转置矩阵的行、列以及非零元素个数
tp.row=col
tp.terms=terms
for(j=0j<colj++) //从第0列开始检查
{
for(i=0i<termsi++)
{
if(t[i].col==j) //检查原三元组的列，如果相同，则交换行、列赋值给转置矩阵
{
tp.t[Row].row=t[i].col
tp.t[Row].col=t[i].row
tp.t[Row].data=t[i].data
Row++
}
}
}
}
}
/*void displayTrituple() //输出三元组
{
for(int i=0i<termsi++)
{
cout<<t[i]
}
cout<<endl
}*/
}
//*******************************************SparseMatrixMain.cpp*************************************************
//#include "stdafx.h"
#include <iostream>
//#include "Trituple.h"
#include "SparseMatrix.h"
using namespace std
int _tmain(int argc, _TCHAR* argv[])
{
SparseMatrix<int>obj
SparseMatrix<int>obj1
cin>>obj
//obj.displayTrituple()//测试时使用的输出三元组的函数
cout<<"*********************初始矩阵**********************"<<endl
cout<<obj
obj.transposedMatrix(obj1) //调用自己编写的转置函数
//obj.transposedMatrix() //调用课本的转置函数
cout<<"*********************转置矩阵**********************"<<endl
cout<<obj1
//cout<<obj
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）