课程设计模板.doc

巢湖学院信息工程学院课程设计报告课程名称 数据结构 课题名称 稀疏矩阵的实现与应用 专业 网络工程 班级 16网工二班 学号 姓名 联系方式 指导教师刘波20 16 年 6 月 13 日目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、稀疏矩阵各种运算的性质变换4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：4.3、测试过程中遇到的主要问题及采取的解决措施：5、时间复杂度的分析：6、源程序清单和执行结果7、C程序设计总结8、致谢9、参考文献1、数据结构课程设计任务书1.1、题目实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。1.2、要求（1）设计函数建立稀疏矩阵，初始化值；（2）设计函数输出稀疏矩阵的值；（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵；（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵；（5）构造函数进行稀疏矩阵的转置，并输出结果；（6）退出系统。2、总体设计2.1、功能模块设计：输入矩阵1矩阵相加输入矩阵2计算结果矩阵相减输入矩阵1输入矩阵2计算结果矩阵转置输入矩阵计算结果退出2.2、所有功能模块的流程图开始Crosslist M,N;CreateSMatrix_OL(M);CreateSMatrix_OL(N);对应位置相加输出结果结束开始RLSMatrix m,N,Q;InPutTSMatrix(M,I);INPutTSMatrix(N,I);Int ctempMAXROW+1;Int arrow,tp,p,brow,t,q,cool;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;实现矩阵的相乘结束开始TSMatrix M,T;InPutTSMatrix(M,O);Int numMAXROW+1;Int cpotMAXROW+1;T.tu=M.tu;T.mu=M.nu;T.nu=M.muT.tu是实现转置OUtPutSMatrix(T)结束开始输出界面Int I;输入 iiTransposeSMatrix();AddSMatrix();MultSMatrix();结束3、详细设计1、定义程序中所有用到的数据及其数据结构，及其基本操作的实现；3.1、程序中所采用的数据结构及存储结构的说明ADT SparseMatrix数据对象：D=aij | i=1,2,.,m;j=1,2,n; AijElemset,m和n分别称为矩阵的行数和列数。数据关系：R=Row,Col Row= | 1=i=m,1=j=n-1Col= | 1=i=m-1,1=j=n基本操作： CreateSMatrix($M); 操作结果：创建稀疏矩阵M. DestroySMatrix($M); 初始条件：稀疏矩阵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 SparseMatrix3.2、算法的设计思想本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。3.3、稀疏矩阵各种运算的性质变换a)加法运算两个稀疏矩阵的加和矩阵仍然是稀疏矩阵b）乘法运算两个稀疏矩阵的乘积矩阵不是稀疏矩阵c）转置运算一个稀疏矩阵的转置矩阵仍然是稀疏矩阵4、调试与测试：4.1、调试方法与步骤：1.实际完成的情况说明（完成的功能，支持的数据类型等）； 完成了稀疏矩阵的建立，初始化及输出值的操作。 实现三元组，十字链表下的稀疏矩阵的加法，乘法以及转置运算。2.程序的性能分析，包括时空分析；能应对一般小的错误输入，如果复杂则自动退出程序。3.上机过程中出现的问题及其解决方案； 1.起始有错误，设定的变量名相同。经检查，改正。 2.一些逻辑错误。经讨论改正。运行出现部分语法错误修正。4.程序中可以改进的地方说明； 程序在运行中一旦出现矩阵数据格式错误如输入汉字，则程序自动退出。需要重新启动。更新程序对更多错误输入情况的分析能力。5.程序中可以扩充的功能及设计实现假想。 对退出操作的扩充 在主菜单下，用户输入4回车选择退出程序是，询问是否真的退出系统，如果是，则即退出系统，否则显示continue并且返回主菜单。为了方便由于误按导致程序退出。 在退出时可以增加一段感谢使用本程序的结束语。4.2、测试结果的分析与讨论：系统运行主界面输入需要执行的操作3矩阵的乘法5、时间复杂度的分析：a)加法运算由于两矩阵行列相等，故时间复杂度为O（行*列）b）乘法运算设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）c）转置运算时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu）6、源程序清单和执行结果#include#includeUsing namespace std;Const int MAXSIZE=100;/定义非零元素的对多个数Const int MAXROW=10; / 定义数组的行数的最大值#include#define MAXSIZE 100 /*假设非零元个数的最大值为20*/typedef struct int i,j; int e;Triple; / 定义三元组的元素typedef structTriple dataMAXSIZE+1; /*非零元三元组表,data0未用*/ 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,*OLink;/ 定义十字链表元素Typedef struct / 定义十字链表对象结构体 OLink *rhead,*chead; Int mu,nu,tu;/ 系数矩阵的行数，列数，和非零元素个数CrossList;/ 定义十字链表对象结构体TemplateBool inputTSMatrix(P $ T,int y) / 输入矩阵，按三元组格式输入抽屉”输入矩阵的行，列和非零元素个数：”T.muT.nuT.tu;Cout”请输入非零元素的位置和值：”endi;for (int k=1;kT.datak.iT.datak.jT.datak.e; Return true;Template Bool OutPutSMatrix(P T) Int m,n,k=1; For(m=0;mT.mu;m+) For (n=0;nT.nu;n+) If(T.datak.i-1)=m$ (T.datak.j-1)=n)cout.width(4); Cout.width(4); Cout T.datak+.e; else Cout.width(4)； Cout ”0”; Cout endi; Return true; / 输出矩阵，按标准格式输出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+)+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 cool - 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+numi-1;/求每一行中非零元素在三元组中出现的位置 return true;bool MultSMatrix() /两个矩阵相乘 RLSMatrix M,N,Q;/ 构建三个带”链接信息”的三元组表示的数组 InPutTSMatrix(M,1);/ 用普通三元组形式输入数组 InPutTSMatrix(M,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 ctempMAXROE + 1;/ 辅助数组 Int arow,tp,p,brow,t,q,cool; If (M.tu * N.t.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(arowM.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p=M.ropsarow;ptp;p+)/ 对当前行每个非零元素进行操作 brow = M.datap.j;/ 在N中找到i值也操作元素的j值相等的行 If (browN.mu) t=N.rposbrow + 1; else t = N.tu + 1; for (q = N.ropsbrow;qt;q+)/ 对找出的行当每个非零元素进行操作 ccol = N.dataq.j; Ctempcool += M.datap.e * N.dataq.e;/ 将乘得到对应值放在相应的元素累加器里面 for (ccol = 1;ccolMAXSIZE) return false; Q.dataQ.tu.e = ctempccol; Q.dataQ.tu.i = arow; Q.dataQ.tu.j=ccol; OutPutSMatrix(Q); return true;bool CreateSMatrix_OL(CrossList &M)/ 创建十字链表 Int x, y, m; coutM.nuM.nuM.nuM.tu; If (!(M.rthead = (OLink*)malloc(M.mu + 1)*sizeof (OLink) exit(0); If (!(M.cthead = (OLink*)malloc(M.mu + 1)*sizeof (OLink) exit(0); for (x=0;x=M.nu;x+) M.rheradx = NULL;/初始化各行，列头指针，分别为NULL for (x=0;x=0;x=M.nu;x+) M.cheradx = NULL; Cout”请按三元组的格式输入数组：”endl; for (int = 1;ixym;/按任意顺序输入非零元，(普通三元组形式输入)OLink p,q;If(!(p = (OLink) malloc(sizeof (OLNode) exit(0);/开辟新节点，用来存储输入的新元素p-i = x; P-i = y; P-e = m; If (M.rheadx = NULL | M.rheadx-jy) P-right = M.rheadx; M.rheadx = p; else for (q = M.rheadx;(q-right)&(q-right-jright);/ 查找节点在行表中的插入位置 p-right = q-right; q-right = p; / 完成行插入If (M.cheady = NULL | M.cheady-ix) p-down = M.cheady; M.cheady = p;else p-down = M.cheady; M.cheady = p;else for ( q= M.cheady;(q-down)&(q-down-idown);/查找节点在列表中的插入位置 P-down = q-down; q-down = p;/ 完成列插入 return true; bool OutPutSMatrix_OL(CrossLisr T)/ 输出十字链表，用普通数组形式输出 for (int i = 1;i=T.mu;i+) OLink p = T.rheadi; for (int j =1;jj) coutsetw(3)”0”; Coutendl; 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+) hx = M.cheadx;for (int k = 1;ke = pb-e; P-j - pb-i; P-j=pb-j; If(NULL = pa | pa-jpb-j)/ 当M此行已经检查完成或者pb因该放在pa前面 If (NULL = pre) M.rheadp-j = p; else pre-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-jj)/如果此时的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-ringht; else pre-right = pa-right; p = pa; pa = pa-right; if (M.cheadp-j =p) M.cheadp-j = hlp-j = hlp-j = p-down;/修改列前驱元素值 else pa = pb-right; pb = pa-right; outPutSMatrix_OL(M);return true;Int main() Int t;cout.fill(*);coutsetw(80)*;cout.fill(*);coutsetw(50)*;cout.fill(*);coutsetw(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: TransposeSMatri