搜索
数据结构课程设计报告题目：十字链表成为存储结构，实现稀疏矩阵的求和运算学生姓名:张旋班级:软件三班学号:201213040304指导教师:吴小平一、需求分析1.问题描述：要求：十字链表下的稀疏矩阵的加、转、乘的实现。2.基本功能实现十字链表下的转置，乘法，加法运算。3.输入输出（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（5）构造函数进行稀疏矩阵的转置，并输出结果。（6）退出系统。二、概要设计1.设计思路：本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘。首先要进行矩阵的初始化操作，定义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。2.数据结构设计：抽象数据类型稀疏矩阵的定义如下：ADTSparseMatrix{数据对象：D={aij|i=1,2,…,m;j=1,2,..,n;aij∈Elemset,m和n分别称为矩阵的行数和列数。}数据关系：R={Row,Col}Row={ai,j,ai,j+1|1=i=m,1=j=n-1}Col={ai,j,ai+1,j|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。}ADTSparseMatrix3.软件结构设计：（1）主程序模块：Voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）稀疏矩阵模块｛实现矩阵的相加boolAddSMatrix()；实现矩阵的相乘boolMultSMatrix()；实验矩阵的转置boolTransposeSMatrix()；｝（3）十字链表模块｛创建十字链表boolCreateSMatrix_OL(CrossList&M)；输出十字链表boolOutPutSMatrix_OL(CrossListT)；｝(4)主程序模块稀疏矩阵模块十字链表模块三、详细设计1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；typedefstruct{inti,j;inte;}Triple;//定义三元组的元素typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//定义普通三元组对象typedefstruct{Tripledata[MAXSIZE+2];intrpos[MAXROW+1];intmu,nu,tu;}RLSMatrix;//定义带链接信息的三元组对象typedefstructOLNode{//定义十字链表元素inti,j;inte;structOLNode*right,*down;//该非零元所在行表和列表的后继元素}OLNode,*OLink;//定义十字链表元素typedefstruct{//定义十字链表对象结构体OLink*rhead,*chead;intmu,nu,tu;//系数矩阵的行数，列数，和非零元素个数}CrossList;//定义十字链表对象结构体2．主函数intmain(){intt;cout.fill('*');coutsetw(80)'*';cout.fill('');coutsetw(50)***欢迎使用矩阵运算程序***endl;//输出头菜单cout.fill('*');coutsetw(80)'*';cout.fill('');cout请选择要进行的操作：endl;cout1:矩阵的转置。endl;cout2:矩阵的加法。endl;cout3:矩阵的乘法。endl;cout4:退出程序。endl;while(t){cout请输入您要进行的操作：endl;cint;switch(t){case1:TransposeSMatrix();//调用矩阵转置函数break;case2:AddSMatrix();//调用矩阵相加函数break;case3:MultSMatrix();//调用矩阵相乘函数break;case4:t=0;break;}}return0;}矩阵的转置函数boolTransposeSMatrix()//求矩阵的转置矩阵{TSMatrixM,T;//定义预转置的矩阵InPutTSMatrix(M,0);//输入矩阵intnum[MAXROW+1];intcpot[MAXROW+1];//构建辅助数组intq,p,t;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;if(T.tu){for(intcol=1;col=M.nu;col++)num[col]=0;for(t=1;t=M.tu;t++)++num[M.data[t].j];cpot[1]=1;for(inti=2;i=M.nu;i++)cpot[i]=cpot[i-1]+num[i-1];//求出每一列中非零元素在三元组中出现的位置for(p=1;p=M.tu;p++){intcol=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}cout输入矩阵的转置矩阵为endl;OutPutSMatrix(T);returntrue;}boolCount(RLSMatrix&T){intnum[MAXROW+1];for(introw=1;row=T.mu;row++)num[row]=0;for(intcol=1;col=T.tu;col++)++num[T.data[col].i];T.rpos[1]=1;for(inti=2;i=T.mu;i++)T.rpos[i]=T.rpos[i-1]+num[i-1];//求取每一行中非零元素在三元组中出现的位置returntrue;}矩阵的乘法函数boolMultSMatrix()//两个矩阵相乘{RLSMatrixM,N,Q;//构建三个带“链接信息”的三元组表示的数组InPutTSMatrix(M,1);//用普通三元组形式输入数组InPutTSMatrix(N,1);Count(M);Count(N);cout输入的两矩阵的乘矩阵为：endl;if(M.nu!=N.mu)returnfalse;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化intctemp[MAXROW+1];//辅助数组intarow,tp,p,brow,t,q,ccol;if(M.tu*N.tu)//Q是非零矩阵{for(arow=1;arow=M.mu;arow++){///memset(ctemp,0,N.nu);for(intx=1;x=N.nu;x++)//当前行各元素累加器清零ctemp[x]=0;Q.rpos[arow]=Q.tu+1;//当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1if(arowM.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];ptp;p++)//对当前行每个非零元素进行操作{brow=M.data[p].j;//在N中找到i值也操作元素的j值相等的行if(browN.mu)t=N.rpos[brow+1];elset=N.tu+1;for(q=N.rpos[brow];qt;q++)//对找出的行当每个非零元素进行操作{ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;//将乘得到对应值放在相应的元素累加器里面}}for(ccol=1;ccol=Q.nu;ccol++)//对已经求出的累加器中的值压缩到Q中if(ctemp[ccol]){if(++Q.tuMAXSIZE)returnfalse;Q.data[Q.tu].e=ctemp[ccol];Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;}}}OutPutSMatrix(Q);returntrue;}矩阵的加法函数boolAddSMatrix()//矩阵的加法{CrossListM,N;//创建两个十字链表对象，并初始化CreateSMatrix_OL(M);CreateSMatrix_OL(N);cout输入的两矩阵的和矩阵为：endl;OLinkpa,pb,pre,hl[MAXROW+1];//定义辅助指针，pa，pb分别为M,N当前比较的元素，pre为pa的前驱元素for(intx=1;x=M.nu;x++)hl[x]=M.chead[x];for(intk=1;k=M.mu;k++)//对M的每一行进行操作{pa=M.rhead[k];pb=N.rhead[k];pre=NULL;while(pb)//把N中此行的每个元素取出{OLinkp;if(!(p=(OLink)malloc(sizeof(OLNode))))exit(0);//开辟新节点，存储N中取出的元素p-e=pb-e;p-i=pb-i;p-j=pb-j;if(NULL==pa||pa-jpb-j)//当M此行已经检查完或者pb因该放在pa前面{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-jpb-j)//如果此时的pb元素因该放在pa后面，则取以后的pa再来比较{pre=pa;pa=pa-right;}elseif(pa-j==pb-j)//如果pa，pb位于同一个位置上，则将值相加{pa-e+=pb-e;if(!pa-e){//如果相加后的和为0，则删除此节点，同时改变此元素坐在行，列的前驱元素的相应值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;}}}}OutPutSMatrix_OL(M);returntrue;}创建十字链表boolCreateSMatrix_OL(CrossList&M)//创建十字链表{intx,y,m;cout请输入矩阵的行，列，及非零元素个数endl;cinM.muM.nuM.tu;i