《数据结构课程设计稀疏矩阵实现与应用.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计稀疏矩阵实现与应用.doc（22页珍藏版）》请在三一办公上搜索。
1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 稀疏矩阵实现与应用 专业 计算机科学与技术 班级 学号姓名 联系方式 指导教师20 11 年 12 月 25 日目 录1、数据结构课程设计任务书1.1、题目-1.2、要求-2、总体设计 -2.1、功能模块设计-12.2、所有功能模块的流程图-23、详细设计-33.1、程序中所采用的数据结构及存储结构的说明-103.2、算法的设计思想-103.3、稀疏矩阵各种运算的性质变换-104、调试与测试：-104.1、调试方法与步骤： -104.2、测试结果的分析与讨论：-115、时间复杂度的分析：-126、源程序清单和执行结果-
2、127、C程序设计总结-208、致谢-209、参考文献-201、数据结构课程设计任务书1.1、题目 实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。1.2、要求 (1).设计函数建立稀疏矩阵，初始化值； (2).设计函数输出稀疏矩阵的值； (3).构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵； (4).构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵； (5).构造函数进行稀疏矩阵的转置，并输出结果； (6).退出系统。2、总体设计2.1、功能模块设计输入矩阵1矩阵相加输入矩阵2计算结果矩阵相减输入矩阵1输入矩阵2计算结果矩阵转置输入矩阵计算结果退出2.2、所有功能模块的流程图3、详细
3、设计1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；typedef struct int i, j; 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,
4、 j; int e; struct OLNode *right, *down; / 该非零元所在行表和列表的后继元素 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; /输出
5、头菜单 cout.fill(*); cout setw(80) *; cout.fill( ); cout 请选择要进行的操作： 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;c
6、ase 4:t=0;break;return 0;矩阵的转置函数bool TransposeSMatrix() / 求矩阵的转置矩阵 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
7、+) +numM.datat.j; cpot1 = 1; for (int i = 2; i = M.nu; i+) 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 tr
8、ue;bool Count(RLSMatrix &T) int numMAXROW + 1; for (int row = 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() / 两个矩阵相乘 RLSMa
9、trix M, N, Q; / 构建三个带“链接信息”的三元组表示的数组 InPutTSMatrix(M, 1); / 用普通三元组形式输入数组 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是非零矩
10、阵 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; else tp = M.tu + 1; for (p = M.rposarow; p tp; p+) / 对当前行每个非零元素进行操作 brow = M.datap.j; / 在N中找
11、到i值也操作元素的j值相等的行 if (brow N.mu) t = N.rposbrow + 1; else t = N.tu + 1; 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 =
12、ccol; OutPutSMatrix(Q); return true;矩阵的加法函数bool AddSMatrix() /矩阵的加法 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
13、; k e = pb-e; p-i = pb-i; p-j = pb-j; if (NULL = pa | pa-j pb-j) / 当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 i
14、f (NULL != pa) & pa-j j) / 如果此时的pb元素因该放在pa后面，则取以后的pa再来比较 pre = pa; pa = 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
15、.cheadp-j = p) M.cheadp-j = hlp-j = p-down; / 修改列前驱元素值 else hlp-j-down = p-down; free(p); pb = pb-right; else pa = pa-right; pb = pb-right; OutPutSMatrix_OL(M); return true;创建十字链表bool CreateSMatrix_OL(CrossList & M)/ 创建十字链表 int x, y, m; cout 请输入矩阵的行，列，及非零元素个数 M.mu M.nu M.tu; if (!(M.rhead = (OLink*)
16、 malloc(M.mu + 1) * sizeof (OLink) exit(0); if (!(M.chead = (OLink*) malloc(M.nu + 1) * sizeof (OLink) exit(0); for (x = 0; x = M.mu; x+) M.rheadx = NULL; / 初始化各行，列头指针，分别为NULL for (x = 0; x = M.nu; x+) M.cheadx = NULL; cout 请按三元组的格式输入数组： endl; for (int i = 1; i x y m; / 按任意顺序输入非零元，（普通三元组形式输入） OLink
17、p, q; if (!(p = (OLink) malloc(sizeof (OLNode) exit(0); / 开辟新节点，用来存储输入的新元素p-i = x; p-j = y; p-e = m; if (M.rheadx = NULL | M.rheadx-j y) p-right = M.rheadx; M.rheadx = p; else for (q = M.rheadx; (q-right) & (q-right-j right); / 查找节点在行表中的插入位置 p-right = q-right; q-right = p; / 完成行插入 if (M.cheady = NUL
18、L | M.cheady-i x) p-down = M.cheady; M.cheady = p; else for (q = M.cheady; (q-down) & (q-down-i down); / 查找节点在列表中的插入位置 p-down = q-down; q-down = p; / 完成列插入 return true;十字链表的输出bool OutPutSMatrix_OL(CrossList T)/ 输出十字链表，用普通数组形式输出 for (int i = 1; i = T.mu; i+) OLink p = T.rheadi; for (int j = 1; j j) c
19、out setw(3) e; p = p-right; else cout setw(3) 0; cout endl; return true;3.1、程序中所采用的数据结构的说明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存在。 操作结果：
20、销毁稀疏矩阵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 SparseMatrix3.2、算法的设计思想本实验要求在三元组，十字链表下实现稀疏 矩阵的加、转、乘。首先要进行矩阵的初始化操作，定
21、义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。3.3、稀疏矩阵各种运算的性质变换a)加法运算两个稀疏矩阵的加和矩阵仍然是稀疏矩阵b）乘法运算两个稀疏矩阵的乘积矩阵不是稀疏矩阵c）转置运算一个稀疏矩阵的转置矩阵仍然是稀疏矩阵4、调试与测试：4.1、调试方法与步骤：1. 实际完成的情况说明（完成的功能，支持的数据类型等）； 完成了稀疏矩阵的建立，初始化及输出值的操作。 实现三元组，十字链表下的稀疏矩阵的加法，乘法以及转置运算。2.程序的性能分析，包括时空分析；能应对一般小的错误输入，如果复杂则自动退出程序。3.上机过程中出现的问题及
22、其解决方案； 1.起始有错误,设定的变量名相同。经检查，改正。2一些逻辑错误。经讨论改正。运行出现部分语法错误修正4.程序中可以改进的地方说明；程序在运行中一旦出现矩阵数据格式错误如输入汉字，则程序自动退出。需要重新启动。更新程序对更多错误输入情况的分析能力。5.程序中可以扩充的功能及设计实现假想。对退出操作的扩充在主菜单下，用户输入4回车选择退出程序是，询问是否真的退出系统，如果是，则即退出系统，否则显示continue并且返回主菜单。为了方便由于误按导致程序退出。在退出时可以增加一段感谢使用本程序的结束语。4.2、测试结果的分析与讨论：系统运行主界面输入需要执行的操作1矩阵的转置输入需要执
23、行的操作2矩阵的加法输入需要执行的操作3矩阵的乘法输入错误操作时需要重新选择退出操作5、时间复杂度的分析：a)加法运算由于两矩阵行列相等，故时间复杂度为O（行*列）b）乘法运算设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）c）转置运算时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu）6、 源程序清单和执行结果#include #include using namespace std;const int MAXSIZE = 100; / 定义非零元素的对多个数const int MAXROW = 10; / 定义数组的行数的最大值 typede
24、f struct int i, j; 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;
25、/ 该非零元所在行表和列表的后继元素 OLNode, *OLink; / 定义十字链表元素typedef struct / 定义十字链表对象结构体 OLink *rhead, *chead; int mu, nu, tu; / 系数矩阵的行数，列数，和非零元素个数 CrossList; / 定义十字链表对象结构体template bool InPutTSMatrix(P & T, int y) /输入矩阵，按三元组格式输入 cout 输入矩阵的行，列和非零元素个数: T.mu T.nu T.tu; cout 请输出非零元素的位置和值: endl; for (int k = 1; k T.dat
26、ak.i T.datak.j T.datak.e; return true;template bool OutPutSMatrix(P T) int m, n, k = 1; for (m = 0; m T.mu; m+) for (n = 0; n T.nu; n+) if (T.datak.i - 1) = m & (T.datak.j - 1) = n) cout.width(4); cout T.datak+.e; else cout.width(4); cout 0; cout endl; return true;/ 输出矩阵，按标准格式输出bool TransposeSMatrix
27、() / 求矩阵的转置矩阵 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
28、; i+) 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 row = 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
