《数据结构课程设计之稀疏矩阵实现与应用》由会员分享，可在线阅读，更多相关《数据结构课程设计之稀疏矩阵实现与应用（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告题目：十字链表成为存储结构，实现稀疏矩阵的求和运算学生姓名:张旋班级:软件三班 学号:201213040304指导教师: 吴小平 一、需求分析 1.问题描述：要求：十字链表下的稀疏矩阵的加、转、乘的实现。 2.基本功能 实现十字链表下的转置，乘法，加法运算。 3.输入输出 （1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（5）构造函数进行稀疏矩阵的转置，并输出结果。（6）退出系统。二、 概要设计1.设计思路：本实验要求在三元组，十字链表下实
2、现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。 2.数据结构设计：抽象数据类型稀疏矩阵的定义如下：ADT SparseMatrix 数据对象：D=aij | i=1,2,m; j=1,2,.,n;aijElemset, m和n分别称为矩阵的行数和列数。数据关系：R=Row,ColRow= | 1=i=m, 1=j=n-1 Col= | 1=i=m-1, 1=j=n基本操作：CreateSMatrix(&M)； 操作结果：创建稀疏矩阵M。DestroySMatrix(&M)；
3、初始条件：稀疏矩阵M存在。 操作结果：销毁稀疏矩阵M。PrintSMatrix(M)； 初始条件：稀疏矩阵M存在。 操作结果：输出稀疏矩阵M。AddSMatrix(M，N，&Q)； 初始条件：稀疏矩阵M与N的行数和列数对应相等 操作结果：求稀疏矩阵的和Q=M+N。MultSMatrix(M，N，Q)； 初始条件：稀疏矩阵M的列数等于N的行数。 操作结果：求稀疏矩阵乘积Q=M*N。 TransposeSMatrix(M，T)； 初始条件：稀疏矩阵M存在。 操作结果：求稀疏矩阵M的转置矩阵T。 ADT SparseMatrix 3.软件结构设计：（1）主程序模块：Void main（）初始化；do
4、 接受命令；处理命令；while（“命令”=“退出”）；（2）稀疏矩阵模块实现矩阵的相加bool AddSMatrix()；实现矩阵的相乘bool MultSMatrix()；实验矩阵的转置bool TransposeSMatrix()；（3）十字链表模块 创建十字链表bool CreateSMatrix_OL(CrossList & M)； 输出十字链表bool OutPutSMatrix_OL(CrossList T)；(4) 主程序模块 稀疏矩阵模块 十字链表模块三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；typedef struct int i, j
5、; int e; Triple; / 定义三元组的元素typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 定义普通三元组对象typedef struct Triple dataMAXSIZE + 2; int rposMAXROW + 1; int mu, nu, tu; RLSMatrix; / 定义带链接信息的三元组对象typedef struct OLNode / 定义十字链表元素 int i, j; int e; struct OLNode *right, *down; / 该非零元所在行表和列表的后继元
6、素 OLNode, *OLink; / 定义十字链表元素typedef struct / 定义十字链表对象结构体 OLink *rhead, *chead; int mu, nu, tu; / 系数矩阵的行数，列数，和非零元素个数 CrossList; / 定义十字链表对象结构体2主函数int main() int t; cout.fill(*); cout setw(80) *; cout.fill( ); cout setw(50) *欢迎使用矩阵运算程序* endl; /输出头菜单 cout.fill(*); cout setw(80) *; cout.fill( ); cout 请选择
7、要进行的操作： endl; cout 1:矩阵的转置。 endl; cout 2:矩阵的加法。 endl; cout 3:矩阵的乘法。 endl; cout 4:退出程序。 endl;while(t)cout请输入您要进行的操作：t;switch(t)case 1:TransposeSMatrix(); /调用矩阵转置函数break;case 2:AddSMatrix(); /调用矩阵相加函数break;case 3: MultSMatrix(); /调用矩阵相乘函数break;case 4:t=0;break;return 0;矩阵的转置函数bool TransposeSMatrix() /
8、 求矩阵的转置矩阵 TSMatrix M, T; /定义预转置的矩阵 InPutTSMatrix(M, 0); /输入矩阵 int numMAXROW + 1; int cpotMAXROW + 1; / 构建辅助数组 int q, p, t; T.tu = M.tu; T.mu = M.nu; T.nu = M.mu; if (T.tu) for (int col = 1; col = M.nu; col+) numcol = 0; for (t = 1; t = M.tu; t+) +numM.datat.j; cpot1 = 1; for (int i = 2; i = M.nu; i+
9、) cpoti = cpoti - 1 + numi - 1; / 求出每一列中非零元素在三元组中出现的位置 for (p = 1; p = M.tu; p+) int col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol; cout 输入矩阵的转置矩阵为 endl; OutPutSMatrix(T); return true;bool Count(RLSMatrix &T) int numMAXROW + 1; for (int r
10、ow = 1; row = T.mu; row+) numrow = 0; for (int col = 1; col = T.tu; col+) +numT.datacol.i; T.rpos1 = 1; for (int i = 2; i = T.mu; i+) T.rposi = T.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元组中出现的位置 return true;矩阵的乘法函数bool MultSMatrix() / 两个矩阵相乘 RLSMatrix M, N, Q; / 构建三个带“链接信息”的三元组表示的数组 InPutTSMatrix(M, 1);
11、 / 用普通三元组形式输入数组 InPutTSMatrix(N, 1); Count(M); Count(N); cout 输入的两矩阵的乘矩阵为： endl; if (M.nu != N.mu) return false; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q初始化 int ctempMAXROW + 1; / 辅助数组 int arow, tp, p, brow, t, q, ccol; if (M.tu * N.tu) / Q是非零矩阵 for (arow = 1; arow = M.mu; arow+) /memset(ctemp,0,N.nu); for (int x = 1; x = N.nu; x+) / 当前行各元素累加器清零 ctempx = 0; Q.rposarow = Q.tu + 1; / 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1 if (arow M.mu) tp = M.rposarow + 1;
