数据结构 - -稀疏矩阵运算器课程设计

数据结构----稀疏矩阵运算器课程设计

目 录

稀疏矩阵运算器设计 ............................................................................................ I 摘 要 ................................................................................................................... II

第一章 需求分析 .......................................................................................... 1 第二章 概要设计 .......................................................................................... 2 第三章 设计步骤 .......................................................................................... 6 3.1 函数说明 ....................................................................................... 6 3.2 设计步骤 ....................................................................................... 7 第四章 设计理论分析方法 ........................................................................ 20 4.1 算法一：矩阵转置 ..................................................................... 20 4.2 算法二：矩阵加法 ..................................................................... 20 4.3 算法三：矩阵乘法 ..................................................................... 21 第五章 程序调试 ........................................................................................ 23 第六章 心得体会 ........................................................................................ 25 参考文献 .................................................................................................... 26

第一章 需求分析

1． 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

2． 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 3． 演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。

4． 由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

5． 程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。

6． 在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。 7． 程序在VC6.0环境下设计。

程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出 的工作。

第二章 概要设计

1． 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{

数据对象：D={aij|i=1,2,?,m; j=1,2,?,n;

aij∈ElemSet, m和n分别为矩阵的行数和列数}

数据关系：R={Row,Col }

Row={﹤ai,j, ai,j+1﹥| 1≤i≤m, 1≤j≤n-1} Col = {﹤ai,j, ai+1,j﹥| 1≤i≤m-1, 1≤j≤n} 基本操作：

create(TSMatrix &TM)

操作结果：创建稀疏矩阵矩阵TM

LocateELem(TSMatrix M,int i,int j,int e)

初始条件：稀疏矩阵M存在

操作结果：稀疏矩阵中是否存在非零元素A[i][j]，若存在返回e

disp(TSMatrix TM)

初始条件：稀疏矩阵TM存在 操作结果：通常形式输出稀疏矩阵 InsertSortMatrix(TSMatrix &TM)

初始条件：稀疏矩阵TM存在

操作结果：根据对矩阵的行列，三元组TM作直接插入排序 TransposeSMatrix(TSMatrix M,TSMatrix &T) 初始条件：稀疏矩阵M和T存在

操作结果：求稀疏矩阵M转置的稀疏矩阵T AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在

操作结果：稀疏矩阵的加法运算:C=A+B

SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的减法运算:C=A-B MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的乘法运算:C=A×B NiMatrix(TSMatrix &TM) 初始条件：稀疏矩阵TM存在 操作结果：稀疏矩阵求逆 }ADT SparseMatrix;

2. 主程序： void main( ) {初始化；

do {

接受命令；

选择处理命令； }while(命令！=“退出”) }

3. 本程序有四个模块，调用关系如下：

4 本程序的流程图

主程序模块 矩阵输入模块 矩阵运算模块 矩阵输出模块 图2.1

}

int shuru[100][100]={0}; for(k=1;k<=B.t;k++) {

shuru[B.data[k].j][B.data[k].i]=B.data[k].v; }

cout<<\输入为：\ for(k=1;k<=B.m;k++) {

for(int l=1;l<=B.n;l++) cout<

int result[100][100]={0};

for(k=1;k<=B.t;k++) {

result[B.data[k].i][B.data[k].j]=B.data[k].v; }

cout<<\结果为：\ for(k=1;k<=B.n;k++) {

for(int l=1;l<=B.m;l++)

cout<

以上主要设计思想：通过三元组输入一个矩阵A，为了找到A的每一列中所有非零元素，需要对其三元组表A.data从第一行起整个扫描一遍，由于A.data是以A的行序为主序来存放每个非零元的，由此得到的恰是B.data的应有的顺序。

加法矩阵：

void tripletable::add( ) //矩阵的加法 { int k;

tripletable A,B;

cout<<\输入稀疏矩阵A的行数，列数和非零元个数：\ cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) {

printf(\输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; }

cout<<\输入稀疏矩阵B的行数，列数和非零元个数：\ cin>>B.m>>B.n>>B.t;

for(k=1;k<=B.t;k++) {

printf(\输入第%d个非0元素的行数，列数和值:\ cin>>B.data[k].i>>B.data[k].j>>B.data[k].v; }

if(A.m!=B.m||A.n!=B.n) {

cout<<\输入错误：A与B的行数或列数不相同，请重新输入\ return; }

int a[100][100]={0}; for(k=1;k<=A.t;k++) {

a[A.data[k].i][A.data[k].j]=A.data[k].v; }

cout<<\输入为：\ for(k=1;k<=A.m;k++) {

for(int l=1;l<=A.n;l++) cout<

int b[100][100]={0}; for(k=1;k<=B.t;k++) {

b[B.data[k].i][B.data[k].j]=B.data[k].v; }

cout<<\输入为：\ for(k=1;k<=B.m;k++) {

for(int l=1;l<=B.n;l++) cout<

int c[100][100]={0}; for(k=1;k<=A.m;k++) {

for(int l=1;l<=A.n;l++) {

c[k][l]=a[k][l]+b[k][l]; } }

cout<<\加法结果C为：\ for(k=1;k<=A.m;k++) {

for(int l=1;l<=A.n;l++) cout<

以上主要设计思想：此功能由函数add( )实现，当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相加的规则，如果符合，进行加法。否则重新输入第二个矩阵来保证两个矩阵可以相加。最后输出结果。 乘法矩阵：

void tripletable::multi() //矩阵的乘法 { int k;

tripletable A,B,C;

cout<<\输入稀疏矩阵A的行数，列数和非零元个数：\ cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) {

printf(\输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } int row=1;

for(k=1;k<=A.t;k++) {

while(row<=A.data[k].i) {

A.rpos[row++]=k; } }

while(row<=A.m)A.rpos[row++]=A.t+1;

cout<<\输入稀疏矩阵B的行数，列数和非零元个数：\ cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k++) {

printf(\输入第%d个非0元素的行数，列数和值:\ cin>>B.data[k].i>>B.data[k].j>>B.data[k].v; } row=1;

for(k=1;k<=B.t;k++) {

while(row<=B.data[k].i) {

B.rpos[row++]=k; }

}

while(row<=B.m)B.rpos[row++]=B.t+1; if(A.n!=B.m) {

cout<<\输入错误：A的列数不等于B的行数，请重新输入\ return; }

C.m=A.m;C.n=B.n;C.t=0; int arow,p,q,ccol,t,tp; if(A.t*B.t!=0) {

for(arow=1;arow<=A.m;++arow) {

int ctemp[maxsize]={0}; C.rpos[arow]=C.t+1;

if(arow

for(p=A.rpos[arow];p

int brow=A.data[p].j;

if(brow

for(q=B.rpos[brow];q

ccol=B.data[q].j;

ctemp[ccol]+=A.data[p].v*B.data[q].v; } }

for(ccol=1;ccol<=C.n;++ccol) {

if(ctemp[ccol]) {

if(++C.t>maxsize)return; C.data[C.t].i=arow; C.data[C.t].j=ccol; C.data[C.t].v=ctemp[ccol]; } } } }

int a[100][100]={0}; for(k=1;k<=A.t;k++) {

a[A.data[k].i][A.data[k].j]=A.data[k].v; }

cout<<\输入为：\ cout<

for(k=1;k<=A.m;k++) {

for(int l=1;l<=A.n;l++) cout<

int b[100][100]={0}; for(k=1;k<=B.t;k++) {

b[B.data[k].i][B.data[k].j]=B.data[k].v; }

cout<<\输入为：\ for(k=1;k<=B.m;k++) {

for(int l=1;l<=B.n;l++) cout<

int c[100][100]={0}; for(k=1;k<=C.t;k++) {

c[C.data[k].i][C.data[k].j]=C.data[k].v; }

cout<<\乘法结果C为：\ for(k=1;k<=C.m;k++) {

for(int l=1;l<=C.n;l++) cout<

以上主要设计思想为：此功能由函数multi( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后检测两者是否可以相乘，如果不能，则重新初始化第二个矩阵。先对矩阵B进行逐行处理，先求得累计求和的中间结果（C的每一行），然后再压缩存储到c.data中去，最后得到结果。

第四章 设计理论分析方法

4.1 算法一：矩阵转置

转置运算时一种最简单的矩阵运算，对于一个m*n的矩阵M，他的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i），1<=i<=n,1<=j<=m。

显然，一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。(1)将矩阵的行列值相互交换;(2)将每个三元组中的i和j相互调换；（3）重排三元组之间的次序便可实现矩阵的转置。

一般矩阵转置算法为 for(col=1;col<=nu;++col) for(row=1;row<=mu;++row) T[col][row]=M[row][col];

按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。在此，需要附设num和cpot两个向量。Num[col]表示矩阵M中

第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。 cpot[1]=1

cpot[col]=cpot[col-1]+num[col-1] 2<=col<=a.nu 这就是快速转置。

4.2 算法二：矩阵加法

稀疏矩阵使用三元组存储，则运算时只需考虑非零元的值即可。两个矩阵相加

首先必须保证M.mu=N.mu&&M.nu=N.nu即同行同列的矩阵才能相加。

for(k=1;k<=M.tu;k++) for(i=1;i<=N.tu;i++)

if(M.data[k].i == N.data[i].i && M.data[k].j == N.data[i].j)

Q.data[count].e = M.data[k].e + N.data[i].e; flag[i] = true;

如果非零元位置一样就直接相加 if(i>N.tu)

Q.data[count].e = M.data[k].e;

如果没有找到与M非零元位置一样的元素就直接把M中的非零元赋值给矩阵Q。

for(k=1;k<=N.tu;k++) if(!flag[k])

Q.data[count].e = N.data[k].e;

如果N中的元素没有被查找，则直接把N中的非零元赋值给矩阵Q。

4.3 算法三：矩阵乘法

矩阵乘法采用“带行链接信息”的三元组存储。经典算法如下： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j) {Q[i][j]=0;

for（k=1;k<=n1;++k） Q[i][j]+=M[j][k]*N[k][j]; }

稀疏矩阵相乘前提：M.nu=N.mu 大致步骤描述如下： Q初始化； If(Q是非零矩阵) {//逐行求积

for(arow=1;arrow<=M.mu;++arow) {//处理M的每一行 ctemp[ ]=0;//累加器清零

计算Q中第arow行的积并存入ctemp[ ]中； 将ctemp[ ]中非零元压缩存储到Q.data; } }

第五章 程序调试

整个程序主要运用了矩阵运算的规则，利用创建三元组表，分析数据，行列是否匹配，稀疏矩阵的转置，稀疏矩阵的相加，稀疏矩阵的相乘。 （1）稀疏矩阵的转置

图 5.1 （2）稀疏矩阵的加法

图 5.2

（3）稀疏矩阵的乘法：

图 5.3

第六章 心得体会

通过此次课程设计，使我更加扎实的掌握了有关稀疏矩阵方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。 过而能改，善莫大焉。在课程设计过程中，不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师和同学的指导下，终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！

参考文献

[1]谭浩强著.C程序设计（第三版）[M].北京：清华大学出版社，2009.5 [2]严蔚敏、吴伟民 主编《数据结构 （C语言版）》[M]. 清华大学出版社 2004.11

[3]．李建学 等 编著《数据结构课程设计案例精编（用C/C++描述）》[M]，清华大学出版社 2007.2

[4].殷人昆 主编《数据结构:用面向对象方法与C++语言描述》[M]， 清华大学出版社 2007.6

本文来源：https://www.bwwdw.com/article/gz35.html