《课程设计报告—稀疏矩阵的完全链表表示和运算》由会员分享，可在线阅读，更多相关《课程设计报告—稀疏矩阵的完全链表表示和运算（54页珍藏版）》请在金锄头文库上搜索。
1、WORD学院计算机科学与技术系课程设计报告2014 2015 学年第 2 学期课程 数据结构与算法课程设计名称稀疏矩阵的完全链表表示与其运算学生学号专业班级13软件工程（2）班 指导教师老师 20 15 年 1 月稀疏矩阵的完全链表表示与其运算问题描述稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行按列序）用right域起来。使得第二个表即列表，把所有结点按照列序（同一列按行序）用down起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结
2、点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。设计目的认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置实现提示链表上的操作。2、 数据结构的选择和概要设计（一）、问题分析1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提
3、供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。3、用单链表存储非零元素的结点信息，并且将之用矩阵的形式打印出来（二）、概要设计1、结构体的定义typedef int ElemType;struct OLNode int i,j; /非零元所在行、列 ElemType e;/非零元值 OLNode *right,*down;typedef OLNode *OLink;struct CrossList OLink *rhead,*chead;/行、列表头的头节点 int mu,nu,t
4、u;/矩阵的行、列和非零元个数;2、存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元的结点。3、主函数主函数包括相加、相减、相乘的各个子函数。4、菜单具有选择功能的用户友好、菜单式系统，可以选择相应的功能来处理输入的数据。三、详细设计和编码1. 设计表示（1）函数调用关系图主函数 1、相加 2、相减 3、相乘 非零元 OVERFLOW（2）算法思想稀疏矩阵的每个结点包含down，ri
5、ght，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行按列序）用right域起来。使得第二个表即列表，把所有结点按照列序（同一列按行序）用down起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。(3) 主要编码int Create(CrossList &M) int i,j,k,m,n,t; ElemType e; OLNode *p,*q; printf(请输入稀疏距阵的行数 列数 非零元的个数：); scanf(%d%d%d,&m
6、,&n,&t); M.mu=m; M.nu=n; M.tu=t; M.rhead=(OLink*)malloc(m+1)*sizeof(OLink); if(!M.rhead) exit(OVERFLOW); M.chead=(OLink*)malloc(n+1)*sizeof(OLink); if(!M.chead) exit(OVERFLOW); for(k=0;k!=m;k+)/初始化行头指针 M.rheadk=NULL; for(k=0;k!=n;k+)/初始化列头指针 M.cheadk=NULL; printf(请按任意次序输入%d个非零元的行 列 元素值:n,M.tu); for(
7、k=0;km|jn) printf(你输入的元素不在矩阵中 请检查重输:n); exit(OVERFLOW); else p=(OLNode*)malloc(sizeof(OLNode); if(!p) exit(OVERFLOW); p-i=i; p-j=j; p-e=e; if(M.rheadi=NULL|M.rheadi-jj)/p插入该行第一节点处 p-right=M.rheadi; M.rheadi=p; else/寻找行表插入位置 for(q=M.rheadi;q-right&q-right-jright); p-right=q-right;/完成行插入 q-right=p; if
8、(M.cheadj=NULL|M.cheadj-ii)/p插入该列第一节点处 p-down=M.cheadj; M.cheadj=p; else/寻找列表插入位置 for(q=M.cheadj;q-down&q-down-idown); p-down=q-down;/完成列插入 q-down=p; return OK;int Print(CrossList M) int i,j,k; OLink p; int array100100; for(i=0;i!=M.mu;i+) for(j=0;j!=M.nu;j+) arrayij=0;/初始化数组所需部分 for(k=0;k!=M.nu;k+)
9、 p=M.cheadk; while(p) arrayp-ip-j=p-e;/将非零元存入数组中 p=p-down; for(i=0;i!=M.mu;i+) for(j=0;j!=M.nu;j+) if(j=M.nu-1) coutarrayijendl; else coutarrayijjj)/矩阵M当情前结点的列小于矩阵N当前结点的列 p=(OLink)malloc(sizeof(OLNode);/生成Q的结点 if(!p) exit(OVERFLOW); Q.tu+; /非零元个数1 p-i=i; /赋值 p-j=pm-j; p-e=pm-e; p-right=NULL; pm=pm-r
10、ight; /pm右移 else if(pm-jpn-j) p=(OLink)malloc(sizeof(OLNode); if(!p) exit(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e=pn-e; p-right=NULL; pn=pn-right; else if(pm-e+pn-e)/M,N当前结点的列一样并且两元素之和非零 p=(OLink)malloc(sizeof(OLNode); if(!p) exit(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e=pm-e+pn-e; p-right=NULL; pm=pm-right;/pm右移 pn=pn-right;/pn右移 else/两元素相加为零 pm=pm-right; pn=pn-right; continue; if(Q.rheadi=NULL) Q.rheadi=pq=p; else pq-right=p;/完成行插入 pq=pq-right; if(Q.cheadp-j=NULL) Q.cheadp-j=colp-j=p; else co
