数据结构课程设计之稀疏矩阵实现与应用.doc
《数据结构课程设计之稀疏矩阵实现与应用.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计之稀疏矩阵实现与应用.doc(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构课程设计报告题目:十字链表成为存储结构,实现稀疏矩阵的求和运算学生姓名:张旋班级:软件三班 学号:4指导教师: 吴小平 一、需求分析 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); 初始条件:稀疏矩阵M存
3、在。 操作结果:销毁稀疏矩阵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; int e; Tr
5、iple; / 定义三元组的元素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; / 该非零元所在行表和列表的后继元素 OLNode, *
6、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 请选择要进行的操作: end
7、l; 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() / 求矩阵的转置矩阵 T
8、SMatrix 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+) cpoti = c
9、poti - 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 row = 1; row
10、 = 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
12、 x = 1; x = N.nu; x+) / 当前行各元素累加器清零 ctempx = 0; Q.rposarow = Q.tu + 1; / 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1 if (arow M.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p = M.rposarow; p tp; p+) / 对当前行每个非零元素进行操作 brow = M.datap.j; / 在N中找到i值也操作元素的j值相等的行 if (brow N.mu) t = N.rposbrow + 1; else t = N.tu + 1
13、; for (q = N.rposbrow; q t; q+) / 对找出的行当每个非零元素进行操作 ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e; / 将乘得到对应值放在相应的元素累加器里面 for (ccol = 1; ccol MAXSIZE) return false; Q.dataQ.tu.e = ctempccol; Q.dataQ.tu.i = arow; Q.dataQ.tu.j = ccol; OutPutSMatrix(Q); return true;矩阵的加法函数bool AddSMatrix() /矩阵的加法
14、CrossList M, N; / 创建两个十字链表对象,并初始化 CreateSMatrix_OL(M); CreateSMatrix_OL(N); cout 输入的两矩阵的和矩阵为: endl; OLink pa, pb, pre, hlMAXROW + 1; /定义辅助指针,pa,pb分别为M,N当前比较的元素,pre为pa的前驱元素 for (int x = 1; x = M.nu; x+) hlx = M.cheadx; for (int k = 1; k e = pb-e; p-i = pb-i; p-j = pb-j; if (NULL = pa | pa-j pb-j) / 当
15、M此行已经检查完或者pb因该放在pa前面 if (NULL = pre) M.rheadp-i = p; else pre-right = p; p-right = pa; pre = p; if (NULL = M.cheadp-j) / 进行列插入 M.cheadp-j = p; p-down = NULL; else p-down = hlp-j-down; hlp-j-down = p; hlp-j = p; pb = pb-right; else if (NULL != pa) & pa-j j) / 如果此时的pb元素因该放在pa后面,则取以后的pa再来比较 pre = pa; p
16、a = pa-right; else if (pa-j = pb-j) / 如果pa,pb位于同一个位置上,则将值相加 pa-e += pb-e; if (!pa-e) / 如果相加后的和为0,则删除此节点,同时改变此元素坐在行,列的前驱元素的相应值 if (NULL = pre) / 修改行前驱元素值 M.rheadpa-i = pa-right; else pre-right = pa-right; p = pa; pa = pa-right; if (M.cheadp-j = p) M.cheadp-j = hlp-j = p-down; / 修改列前驱元素值 else hlp-j-do
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 稀疏 矩阵 实现 应用
限制150内