稀疏矩阵的应用

稀疏矩阵的应用数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:年级/专业/班:学生姓名:学号:开始时间:完成时间:课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总分（100）指导教师签名：年月日目录TOC\o"1-2"\h\z\u1需求分析 11.1任务与分析 11.2测试数据 12概要设计 12.1存储结构设计 12.2程序模块结构 22.3各功能模块 33详细设计 43.1结构体定义 43.2插入操作 44调试分析 165用户使用说明 166测试结果 166.1系统运行主界 166.2各子功能测试运行结果 17结论 20

摘要）本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘等操作，最后输出运算后的结果。考虑到难易程度，先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘等操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。关键词：程序设计；稀疏矩阵；三元组；十字链表引言1需求分析其目的是让我们在学习完C++、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。1.1任务与分析本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个稀疏矩阵A和B的和为矩阵C，并输出C；求出A的转置为矩阵D，输出D；求两个稀疏矩阵A和B的相乘为矩阵E，并输出E。1.2测试数据54511314723-131254-854101311422222312413434114264415122概要设计2.1存储结构设计三元组结构体定义:structelement{ inti,j; ElemTypeitem;};constintMaxTerm=100;structSparsematrix{ elementdata[MaxTerm]; intmu,nu,tu;//行数、列数、非零元个数};十字链表结构体定义:typedefstructMLnode{ inti;//结点的行下标 intj;//结点的列下标 ElemTypee;//非零元的值 structMLnode*right,*down;//该非零元所在行表和列表的后继元素}MLnode;2.2程序模块结构2.2.1结构体定义三元组结构体定义:structelement{ inti,j; ElemTypeitem;};constintMaxTerm=100;structSparsematrix{ elementdata[MaxTerm]; intmu,nu,tu;//行数、列数、非零元个数};十字链表结构体定义:typedefstructMLnode{ inti;//结点的行下标 intj;//结点的列下标 ElemTypee;//非零元的值 structMLnode*right,*down;//该非零元所在行表和列表的后继元素}MLnode;2.3各功能模块本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储结构下，由函数voidcreatT()实现，在十字链表存储结构下，由函数voidCreateL(Sparsematrix&X)依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的转置：此功能在三元组存储结构下，有两种方法：按行转置和按列转置，分别由函数voidzhuanzT(SparsematrixX,Sparsematrix&b)和sqmatrixtransmattwo()实现，在十字链表存储结构下，由函数voidzhuanzhi()实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。（2）稀疏矩阵的加法：此功能在三元组存储结构下，由函数voidaddT(Sparsematrixa,Sparsematrixb,Sparsematrix&c)实现，在十字链表存储结构下，由函数voidaddL(CrossList&a,CrossList&b)实现。当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（3）稀疏矩阵的乘法：此功能在三元组存储结构下，由函数voidcheng(sqmatrixa,sqmatrixb)实现。在十字链表存储结构下，由函数voidchengfa()实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。（4）退出：即退出稀疏矩阵的应用系统，由switch语句实现。当用户选择相应序号，则退出该稀疏矩阵的应用系统。3详细设计3.1结构体定义…三元组结构体定义:structelement{ inti,j; ElemTypeitem;};constintMaxTerm=100;structSparsematrix{ elementdata[MaxTerm]; intmu,nu,tu;//行数、列数、非零元个数};十字链表结构体定义:typedefstructMLnode{ inti;//结点的行下标 intj;//结点的列下标 ElemTypee;//非零元的值 structMLnode*right,*down;//该非零元所在行表和列表的后继元素}MLnode;3.2插入操作A.主程序模块设计： Sparsematrixs1,s2,s3; CrossListc1,c2;//两个链表储存的矩阵 intk; do{ cout<<endl; cout<<"***********稀疏矩阵应用**************"<<endl<<endl; cout<<"请你选择创建两个稀疏矩阵的方法"<<endl; cout<<"1、用三元组顺序表创建稀疏矩阵"<<endl; cout<<"2、用十字链表创建稀疏矩阵"<<endl; cout<<"3、退出程序"<<endl<<endl; cout<<"请选择："; cin>>k;cout<<endl; switch(k){ case1:{ createT(s1);//三元组顺序表创建矩阵 printT(s1); createT(s2); printT(s2); }break; case2:{ createL(c1);//十字链表创建矩阵 printL(c1); createL(c2); printL(c2);}break; } switch(k) { case1: cout<<"**********欢迎进入《三元组操作》矩阵系统**********"<<endl<<endl; cout<<"\n1、两矩阵求和"<<endl; cout<<"\n2、两矩阵相乘"<<endl; cout<<"\n3、矩阵按行转置"<<endl; cout<<"\n4、退出程序"<<endl<<endl; intkk=0; cout<<"请选择：";cin>>kk; switch(kk) { case1:{addT(s1,s2,s3);printT(s3);}break; case2:break; case3:{cout<<"转置第一个矩阵";Sparsematrixs4;zhuanzT(s1,s4);printT(s4);}break; case4:break; } }break; cout<<endl; case2:{ cout<<"**********欢迎进入《十字链表操作》矩阵系统**********"<<endl<<endl; cout<<"\n1、两矩阵求和"<<endl; cout<<"\n2、两矩阵相乘"<<endl; cout<<"\n3、矩阵按行转置"<<endl; cout<<"\n4、矩阵按列转置"<<endl; cout<<"\n5、退出程序"<<endl<<endl; intkk=0; cout<<"请选择：";cin>>kk; switch(kk){ case1:{addL(c1,c2);printL(c1); }break; case2:break; case3:break; case4:break; } cout<<endl; }break; } }while(k==1||k==2);cout<<endl;} B.稀疏矩阵操作各子函数的定义：(1)建立与初始化稀疏矩阵：采用三元组建立稀疏矩阵，输入非零元素的行号、列号和值，关键代码如下： cout<<"请输入稀疏矩阵的行数、列数、非零元值个数:"<<endl; cin>>X.mu>>X.nu>>X.tu; cout<<"行号i列号j非零元素值item"<<endl; for(intp=0;p<X.tu;p++) { intii,jj,element; cin>>ii>>jj>>element; X.data[p].i=ii; X.data[p].j=jj; X.data[p].item=element; }采用十字链表建立稀疏矩阵，输入非零元素的行号、列号和值，给新结点申请空间，按列循环链表和行循环链表形式插入到十字链表中关键代码如下：voidcreateL(CrossList&X){ inti,j,e,k; MLnode*p,*q; // if(X)deleteX; cout<<"请输入矩阵的行数、列数和非零元素个数："<<endl; cin>>X.m>>X.n>>X.t; X.rhead=(MLnode**)newMLnode[X.m+1];//按行数申请动态MLnode*类型的数组；并赋值全为空 for(k=1;k<=X.m;k++) X.rhead[k]=0; X.chead=(MLnode**)newMLnode[X.n+1];//按列数申请动态MLnode*类型的数组；并赋值全为空 for(k=1;k<=X.n;k++) X.chead[k]=0; intr=X.t; cout<<"请输入结点的行号、列号和非零元素值"<<endl; cin>>i>>j>>e; while(i) { --r; p=newMLnode; p->i=i;p->j=j;p->e=e; if(X.rhead[i]==0||X.rhead[i]->j>j)//若链表为空或者该行头头指针所在列大于输入的非零元所在列号小于号，前插，后移动头指针 { p->right=X.rhead[i];X.rhead[i]=p; } else//否则如果该行头指针所在列小于或等于输入的非零元所在列号，后插，不移动头指针 { for(q=X.rhead[i];(q->right)&&q->right->j<j;q=q->right);//寻找插入点 p->right=q->right;q->right=p; } if(X.chead[j]==0||X.chead[j]->i>i){p->down=X.chead[j];X.chead[j]=p;} else { for(q=X.chead[j];(q->down)&&q->down->i<i;q=q->down); p->down=q->down;q->down=p; } if(r==0)break; cin>>i>>j>>e; }}（2）输出稀疏矩阵：用三元组输出矩阵元素时，若稀疏矩阵所对应的元素在三元组中有该元素，则输出三元组中的这个元素的值，否则，输出零。其关键代码如下： if(data[p].i==i&&data[p].j==j){isfound=true;foundindex=p;} if(isfound==true)cout<<setw(5)<<data[foundindex].v; else cout<<setw(5)<<"0";}用十字链表输出矩阵元素时，若稀疏矩阵所对应的元素在十字链表中有该元素，则输出三元组中的这个元素的值，同时指针指向下一个结点，否则，输出零。其关键代码如下： for(intk=1;k<=X.m;k++) { p=X.rhead[k]; for(ints=1;s<=X.n;s++){ if((p)&&s==p->j) {cout<<setw(5)<<p->e;p=p->right;} else cout<<setw(5)<<"0"; } cout<<endl; }（3）实现矩阵的转置：用三元组和十字链表实现矩阵转置，都采用元素所对应的行号变为新矩阵的列号，所对应的列号变为新矩阵的行号，所对应的值不变，在这个过程中采用一个for循环使待转置的元素所对应的列号较小者先转置到新矩阵中，其关键代码如下：voidzhuanzT(SparsematrixX,Sparsematrix&b){ intk=1; for(inti=1;i<=X.mu;i++) { for(intj=1;j<=X.nu;j++) { boolisfound=false; intfoundindex; for(intp=0;p<X.tu;p++) { if(X.data[p].i==i&&X.data[p].j==j) { isfound=true;foundindex=p; break; } } if(isfound==true){ b.data[k].i=j;b.data[k].j=i;b.data[k].item=X.data[foundindex].item; ++k; } } b.mu=X.nu; b.nu=X.mu; b.tu=k; }}（4）实现两个矩阵的相加：采用三元组实现两矩阵相加时，先判断被加的两矩阵所对应的位置是否有非零元素，若没有或两矩阵元素相加为零，则新三元组表中不进行任何操作，若只有一个为非零元素，则新三元组表中对应位置元素值就为该非零元素的值，若两矩阵相同位置元素和k不为零，则新三元组表中对应应位置元素值就为k。其关键代码如下：//三元组顺序表矩阵的相加voidaddT(Sparsematrixa,Sparsematrixb,Sparsematrix&c){ inti=1,j=1,k=1; while(i<=a.tu&&j<b.tu) { if(a.data[i].i==b.data[j].i) { if(a.data[i].j==b.data[i].j) { c.data[k].i=a.data[i].i; c.data[k].j=a.data[i].j; c.data[k].item=a.data[i].item+b.data[j].item; j++;k++; } if(a.data[i].j<b.data[i].j) { c.data[k].i=a.data[i].i; c.data[k].j=a.data[i].j; c.data[k].item=a.data[i].item; i++;k++; } if(a.data[i].j>b.data[i].j) { c.data[k].i=b.data[j].i; c.data[k].j=b.data[j].j; c.data[k].item=b.data[j].item; j++;k++; } } elseif(a.data[i].i<b.data[j].i) { c.data[k].i=a.data[i].i; c.data[k].j=a.data[i].j; c.data[k].item=a.data[i].item; i++;k++; } elseif(a.data[i].i>b.data[j].i) { c.data[k].i=b.data[j].i; c.data[k].j=b.data[j].j; c.data[k].item=b.data[j].item; j++;k++; } } c.mu=a.mu; c.nu=a.nu; c.tu=k;}采用十字链表实现两矩阵相加时，和三元组实现两矩阵相加类似，不同点就是元素相加后转向被加的两个元素结点向下移动，新三元组的指针也向下移动其关键代码如下：voidaddL(CrossList&a,CrossList&b)//矩阵a与矩阵b相加，用b插入a{ intmax=a.n; MLnode**hl; hl=(MLnode**)newMLnode[max]; MLnode*pa,*pb,*pre,*insert,*keep; for(inti=1;i<=a.m;i++) { pa=a.rhead[i];//初始化指向首结点，以后逐个向后移动 pb=b.rhead[i]; pre=NULL; for(intj=1;j<max;j++)//n为矩阵列数,hl的作用是等同于pre指针，追踪竖向上新插入的结点 hl[j]=a.chead[j]; while(pb!=NULL) { if(pa==NULL||pa->j>pb->j)//横插 { insert=newMLnode; insert->i=pb->i; insert->j=pb->j; insert->e=pb->e; if(pre==NULL)a.rhead[i]=insert; elsepre->right=insert; insert->right=pa; pre=insert;//pre用于最终新插入的结点 if(a.chead[insert->j]==NULL||a.chead[insert->j]->i>insert->i)//竖插（拿新插入结点的所在列的头结点行数与新插入结点行数比较） { insert->down=a.chead[insert->j]; a.chead[insert->j]=insert; } else { insert->down=hl[insert->j]->down; hl[insert->j]->down=insert; } hl[insert->j]=insert; pb=pb->right; } elseif(pa->j==pb->j) { pa->e+=pb->e; if(pa->e==0)//如果相加不为0，不用操作，pa已经改动； { keep=pa; if(pre==NULL){a.rhead[i]=pa->right;}//pre不一定一定等于0当前一种情况的时候pre指向有可能改变 else{pre->right=pa->right;}//pre指向行首结点? pa=pa->right; deletekeep; } pb=pb->right; } else//pa->j<pb->j这种情况m不动，pa指向下一个结点让它和pb再比较 { pre=pa; pa=pa->right; } } } }（5）实现两个矩阵的相乘：三元组实现两矩阵相乘和三元组实现两矩阵相加类似，不同就是新矩阵非零元素所在行和列的值是两矩阵所对应行元素与所对应列元素相乘后相加，其主要代码如下：intctemp[max];t=0;m=a.m;n=a.n;if(a.t*b.t!=0){for(arow=1;arow<=a.m;arow++) {for(ii=1;ii<=a.n;ii++)ctemp[ii]=0;rpos[arow]=t;Mlim=arow<a.m?a.rpos[arow+1]:a.t+1;for(Mcol=a.rpos[arow];Mcol<Mlim;Mcol++){Mj=a.data[Mcol].j;Nlim=Mj<b.m?b.rpos[Mj+1]:b.t+1;for(Nrow=b.rpos[Mj];Nrow<Nlim;Nrow++)ctemp[b.data[Nrow].j]+=a.data[Mcol].v*b.data[Nrow].v; }十字链表实现矩阵相乘和十字链表实现矩阵相加类似，都要判断相乘后是否为零，在操作时要注意指针的指向。其关键代码如下：for(intx=1;x<=M.b;x++) hl[x]=M.chead[x];for(intk=1;k<=M.a;k++) {pa=M.rhead[k];pb=N.rhead[k];pre=NULL;while(pb) {OLinkp;p->e=pb->e;p->i=pb->i;p->j=pb->j;if(NULL==pa||pa->j>pb->j) {if(NULL==pre)M.rhead[p->i]=p;elsepre->right=p;p->right=pa;pre=p;if(NULL==M.chead[p->j]){M.chead[p->j]=p; p->down=NULL;}else {p->down=hl[p->j]->down;hl[p->j]->down=p;}hl[p->j]=p;pb=pb->right; }elseif((NULL!=pa)&&pa->j<pb->j) {pre=pa;pa=pa->right;}elseif(pa->j==pb->j){pa->e*=pb->e;if(!pa->e){if(NULL==pre)M.rhead[pa->i]=pa->right;elsepre->right=pa->right;p=pa;pa=pa->right;if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down;elsehl[p->j]->down=p->down;free(p);pb=pb->right;}else{pa=pa->right;pb=pb->right;}4调试分析用C++语言写代码实现所要求的功能过程中，用三元组实现矩阵相乘，有一定的难度，我通过多次调试，系统始终提示出错，通过参考网友的代码和同学的提示，原来两矩阵的第i行非零元素个数不一定等于另一矩阵的第i列非零元素个数，最后，我通过控制一矩阵的非零元素所在的i行、j列位置与另一个矩阵所对应的i列j行元素相乘，然后在相加。通过测试，功能能够实现了；在用十字链表实现各功能时，由于指针很多，写出的代码最初基本上都是指针指向出错，通过自己经验以及老