课程设计报告—稀疏矩阵的完全链表表示及其运算

合肥学院计算机科学与技术系课程设计报告2014～2015学年第2学期课程数据结构与算法课程设计名称稀疏矩阵的完全链表表示及其运算学生姓名学号专业班级13软件工程（2）班指导教师陈老师2015年1月稀疏矩阵的完全链表表示及其运算【问题描述】稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。【设计目的】认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构【基本要求】建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的内容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置【实现提示]链表上的操作。二、数据结构的选择和概要设计（一）、问题分析1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。3、用单链表存储非零元素的结点信息，并且将之用矩阵的形式打印出来（二）、概要设计1、结构体的定义typedefintElemType;structOLNode{inti,j;//非零元所在行、列ElemTypee;//非零元值OLNode*right,*down;};typedefOLNode*OLink;structCrossList{OLink*rhead,*chead;//行、列表头的头节点intmu,nu,tu;//矩阵的行、列和非零元个数};2、存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元的结点。3、主函数主函数包括相加、相减、相乘的各个子函数。4、菜单具有选择功能的用户友好、菜单式系统，可以选择相应的功能来处理输入的数据。三、详细设计和编码1.设计表示（1）函数调用关系图1、相加2、相减3、相乘非零元OVERFLOW（2）算法思想稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。(3)主要编码intCreate(CrossList&M){inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(请输入稀疏距阵的行数列数非零元的个数：);scanf(%d%d%d,&m,&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.rhead[k]=NULL;for(k=0;k!=n;k++)//初始化列头指针M.chead[k]=NULL;printf(请按任意次序输入%d个非零元的行列元素值:\n,M.tu);for(k=0;kt;k++){scanf(%d%d%d,&i,&j,&e);if(im||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.rhead[i]==NULL||M.rhead[i]-jj)//p插入该行第一节点处{p-right=M.rhead[i];M.rhead[i]=p;}else//寻找行表插入位置{for(q=M.rhead[i];q-right&&q-right-jj;q=q-right);p-right=q-right;//完成行插入q-right=p;}if(M.chead[j]==NULL||M.chead[j]-ii)//p插入该列第一节点处{p-down=M.chead[j];M.chead[j]=p;}else//寻找列表插入位置{for(q=M.chead[j];q-down&&q-down-ii;q=q-down);p-down=q-down;//完成列插入q-down=p;}}}returnOK;}intPrint(CrossListM){inti,j,k;OLinkp;intarray[100][100];for(i=0;i!=M.mu;i++){for(j=0;j!=M.nu;j++){array[i][j]=0;//初始化数组所需部分}}for(k=0;k!=M.nu;k++){p=M.chead[k];while(p){array[p-i][p-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)coutarray[i][j]endl;elsecoutarray[i][j];//以矩阵的显示方式显示稀疏矩阵}}returnOK;}intAdd(CrossListM,CrossListN,CrossList&Q){inti,k;OLinkp,pq,pm,pn;OLink*col;Q.mu=M.mu;//初始化QQ.nu=M.nu;Q.tu=0;Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink));if(!Q.rhead)exit(OVERFLOW);Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink));if(!Q.chead)exit(OVERFLOW);for(k=0;k!=Q.mu;k++)//初始化行Q.rhead[k]=NULL;for(k=0;k!=Q.nu;k++)//初始化列Q.chead[k]=NULL;col=(OLink*)malloc((Q.nu+1)*sizeof(OLink));//生成指向列的最后节点的数组if(!col)exit(OVERFLOW);for(k=0;k!=Q.nu;k++)//赋初始值col[k]=NULL;for(i=0;i!=M.mu;i++)//按行序相加{pm=M.rhead[i];pn=N.rhead[i];while(pm&&pn){if(pm-jpn-j)//矩阵M当情前结点的列小于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode));//生成Q的结点if(!p)exit(OVERFLOW);Q.tu++;//非零元个数＋1p-i=i;//赋值p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;//pm右移}elseif(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;}elseif(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.rhead[i]==NULL)Q.rhead[i]=pq=p;else{pq-right=p;//完成行插入pq=pq-right;}if(Q.chead[p-j]==NULL)Q.chead[p-j]=col[p-j]=p;else{col[p-j]-down=p;//完成列插入col[p-j]=col[p-j]-down;}}while(pm)//将矩阵M该行的剩余元素插入矩阵Q{p=(OLink)malloc(sizeof(OLNode));if(!p)exit(OVERFLOW);Q.tu++;p-i=i;p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;if(Q.rhead[i]==NULL)Q.rhead[i]=pq=p;else{pq-right=p;pq=pq-right;}if(Q.chead[p-j]==NULL)Q.chead[p-j]=col[p-j]=p;else{col[p-j]-down=p;col[p-j]=col[p-j]-down;}}while(pn)//将矩阵N该行的剩余元素插入矩阵Q{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;if(Q.rhead[i]==NULL)Q.rhead[i]=pq=p;else{pq-right=p;pq=pq-right;}if(Q.chead[p-j]==NULL)Q.chead[p-j]=col[p-j]=p;else{col[p-j]-down=p;col[p-j]=col[p-j]-down;}}}for(k=0;k!=Q.nu;k++)if(col[k])col[k]-down=NULL;free(col);returnOK;}CrossListNegative(CrossListM){OLinkp;for(intj=0;j!=M.mu;j++){p=M.rhead[j];while(p){p-e=-p-e;//将非零元的值反号p=p-right;}}return(M);}intMult(CrossListM,CrossListN,CrossList&Q){inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu){printf(你输入的两个距阵不能进行此操作\n);exit(OVERFLOW);}else{Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink));if(!Q.rhead)exit(OVE