课程设计模板

1、巢湖学院信息工程学院课程设计报告课程名称 数据结构 课题名称 稀疏矩阵的实现与应用 专业 网络工程 班级 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程序设计总结

2、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);

3、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)结束开始输出界面

4、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=<ai,j,ai,j+1> | 1<=i<=m,1<=j<=n-1Col=<ai,j,ai+1,j> | 1<=i<

5、;=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); 初始条件：

6、稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T。 ADT SparseMatrix3.2、算法的设计思想本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。3.3、稀疏矩阵各种运算的性质变换a)加法运算两个稀疏矩阵的加和矩阵仍然是稀疏矩阵b）乘法运算两个稀疏矩阵的乘积矩阵不是稀疏矩阵c）转置运算一个稀疏矩阵的转置矩阵仍然是稀疏矩阵4、调试与测试：4.1、调试方法与步骤：1.实际完成的情况说明（完成的功能，支持的数据类型等）； 完成了稀疏矩阵的建立

7、，初始化及输出值的操作。 实现三元组，十字链表下的稀疏矩阵的加法，乘法以及转置运算。2.程序的性能分析，包括时空分析；能应对一般小的错误输入，如果复杂则自动退出程序。3.上机过程中出现的问题及其解决方案； 1.起始有错误，设定的变量名相同。经检查，改正。 2.一些逻辑错误。经讨论改正。运行出现部分语法错误修正。4.程序中可以改进的地方说明； 程序在运行中一旦出现矩阵数据格式错误如输入汉字，则程序自动退出。需要重新启动。更新程序对更多错误输入情况的分析能力。5.程序中可以扩充的功能及设计实现假想。 对退出操作的扩充 在主菜单下，用户输入4回车选择退出程序是，询问是否真的退出系统，如果是，则即退出

8、系统，否则显示continue并且返回主菜单。为了方便由于误按导致程序退出。 在退出时可以增加一段感谢使用本程序的结束语。4.2、测试结果的分析与讨论：系统运行主界面输入需要执行的操作3矩阵的乘法5、时间复杂度的分析：a)加法运算由于两矩阵行列相等，故时间复杂度为O（行*列）b）乘法运算设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）c）转置运算时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu）6、源程序清单和执行结果#include<iostream>#include<iomanip >Using namespace

9、std;Const int MAXSIZE=100;/定义非零元素的对多个数Const int MAXROW=10; / 定义数组的行数的最大值#include<malloc.h>#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 data

10、MAXSIZE+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;/ 定义十字链表对象结构体Template&

11、lt;class P>Bool inputTSMatrix(P $ T,int y) / 输入矩阵，按三元组格式输入抽屉<<”输入矩阵的行，列和非零元素个数：”<<endi;cin>>T.mu>>T.nu>>T.tu;Cout<<”请输入非零元素的位置和值：”<<endi;for (int k=1;k<=T.tu;k+) Cin>>T.datak.i>>T.datak.j>>T.datak.e; Return true;Template <clasp>

12、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.width(4); Cout <<T.datak+.e; else Cout.width(4)； Cout <<”0”; Cout <<endi; Return true; / 输出矩阵，按标准格式输出Bool TransposeSMatrix() / 求矩阵的转置矩阵 TSMatrix

13、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;/求每一列中非零元素在三元组中出现的位

14、置 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

15、(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<<

16、;”输入的两矩阵的乘矩阵为：”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 =

17、 Q.tu = 1;/当前行的首个非零元素在三元组的位置委此前所有非零元素+1 If(arow<M.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p=M.ropsarow;p<tp;p+)/ 对当前行每个非零元素进行操作 brow = M.datap.j;/ 在N中找到i值也操作元素的j值相等的行 If (brow<N.mu) t=N.rposbrow + 1; else t = N.tu + 1; for (q = N.ropsbrow;q<t;q+)/ 对找出的行当每个非零元素进行操作 ccol = N.data

18、q.j; Ctempcool += M.datap.e * N.dataq.e;/ 将乘得到对应值放在相应的元素累加器里面 for (ccol = 1;ccol<=Q.nu; ccol+)/ 对已经求出的累加器中的值压缩到Q中 If (ctempccol) If (+Q.tu>MAXSIZE) 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 &

19、;M)/ 创建十字链表 Int x, y, m; cout<<”请输入矩阵的行，列，及非零元素个数”end； cin>>M.nu>>M.nu>>M.nu>>M.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;/初始化各行，列头指针，分

20、别为NULL for (x=0;x<=0;x<=M.nu;x+) M.cheradx = NULL; Cout<<”请按三元组的格式输入数组：”<<endl; for (int = 1;i<=M.tu;i+) Cin>>x>>y>>m;/按任意顺序输入非零元，(普通三元组形式输入)OLink p,q;If(!(p = (OLink) malloc(sizeof (OLNode) exit(0);/开辟新节点，用来存储输入的新元素p->i = x; P->i = y; P->e = m; If (M.

21、rheadx = NULL | M.rheadx->j>y) P->right = M.rheadx; M.rheadx = p; else for (q = M.rheadx;(q->right)&&(q->right->j<y);q = q->right);/ 查找节点在行表中的插入位置 p->right = q->right; q->right = p; / 完成行插入If (M.cheady = NULL | M.cheady->i>x) p->down = M.cheady; M.ch

22、eady = p;else p->down = M.cheady; M.cheady = p;else for ( q= M.cheady;(q->down)&&(q->down->i<x);q=q->down);/查找节点在列表中的插入位置 P->down = q->down; q->down = p;/ 完成列插入 return true; bool OutPutSMatrix_OL(CrossLisr T)/ 输出十字链表，用普通数组形式输出 for (int i = 1;i<=T.mu;i+) OLink p

23、= T.rheadi; for (int j =1;j<=T.nu;j+) If(p) && (j = p->j) cout<<setw(3)<<”0”; Cout<<endl; return true; bool AddSMatrix()/矩阵的加法CrossList M,N;/创建两个十字链接对象，并初始化CreateSMatrix_OL(M);CreateSMatrix_OL(N);Cout<<”输入的两矩阵的和矩阵为：”<<endl;OLink pa,pb,pre,hlMAXROW + 1;/定义辅

24、助指针，pa,pb分别为M,N当前比较的元素，pre为pa的前驱元素for (int x = 1;x<=M.nu;x+) hx = M.cheadx;for (int k = 1;k<=M.nu;k+)/对M的每一行进行操作 pa = M.rheadk; pb = N.rheadk; pre = NULL; while (pb)/把N中此行的每个元素取出 OLink p; If (!(p = (OLIink) malloc(sizeof (OLNode) exit(0); /开辟新节点，存储N中取出的元素 P->e = pb->e; P->j - pb->i

25、; P->j=pb->j; If(NULL = pa | pa->j>pb->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

26、 = pb->right;else If (NULL!= pa) && pa->j<pb->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->ringh

27、t; 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(*);cout<<setw(80)<<*;cout.fill(*);cout<<setw(50)<<*;cout.fill(*);cout<<setw(80)<<*;cout.fill(*);cout <<” 请选择要进行的操作：”<<endl;cout <<” 1：矩阵的置换。”<<endl;cout <<” 2：矩阵的加法。”<<endl;cout <<” 3：矩阵