还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构课程设计《数据结构》课程设计
1.题目稀疏矩阵应用(限1人完成)要求实现三元组,十字链表下的稀疏矩阵的加、转、乘的实现
(1)稀疏矩阵的存储
(2)稀疏矩阵加法
(3)矩阵乘法
(4)矩阵转置
2.算法思想描述
1.算法概述首先用两个结构体来定义十字链表元素typedefstructOLNode{intij;inte;structOLNode*right*down;}OLNode*OLink;OLNode结构为链表结点,ije分别表示稀疏矩阵中元素的行,列和值typedefstruct{intmunutu;//行数mu,列数nu,非零元素的个数tuOLink*rhead*chead;}CrossList;CrossList结构用于连接起各个结点,munutu分别表示整个矩阵的行数列数和非零元素的个数整个程序包含Create__atix_OL(用于创建十字链表),__atrix_ADD(十字链表相加),Show__trix十字链表显示,Mult__atrix_OL(十字链表相乘),Turn__atrix_OL(十字链表转置),Destroy__atrix_OL(十字链表销毁)六个函数Create__atix_OL的功能如下首先输入稀疏矩阵的行数,列数,非零元素的个数,为*rhead和*chead分配内存空间,并将十字链表中节点初始化为NULL然后依次输入非零元素的行,列,值,以000为结尾结束链表的连接和while循环__atrix_ADD的功能如下在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵,连接结束后__atrix_ADD函数以循环的方式比较非零元素是否为同一行列,如果是则两值相加,如果不是则把第二个元素加入链表中Show__trix的功能如下逐一输出链表的行,列,值三个元素知道达到表尾的NULLMult__atrix_OL的功能如下与相加类似,在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵,连接结束后Mult__atrix_OL函数以循环的方式比较非零元素是否为同一行列,如果是则两值相乘,如果不是则修改原来的元素值为0Turn__atrix_OL的功能如下逐一查找十字链表中各个元素,将他们的ij值对调已达到转置的目的.
2.算法具体分析
(1)、输入需要执行的操作1为创建稀疏矩阵,调用Create__atix_OL函数,输入稀疏矩阵的行数列数和非零元素的个数(如221,中间以空格分开)Create__atix_OL函数会将各个元素的信息保存在十字链表的结点中并连接起来2为退出程序
(2)、选择接下来要执行的操作1为稀疏矩阵转置调用Turn__atrix_OL函数逐一查找十字链表中各个元素,将他们的ij值对调已达到转置的目的2为稀疏矩阵相加,调用__atrix_ADD函数创建另一个稀疏矩阵并且将两矩阵中的非零元素相加3为稀疏矩阵相乘,调用Mult__atrix_OL函数创建另一个稀疏矩阵并且将两矩阵中的同行列的非零元素项相乘,其余项修改为04为退出
(3)、程序显示操作结果,运行正常,结果正确
三、程序结构
四、实验结果与分析上述程序在VisualC++
6.0环境下加以实现,经过多次的测试,程序运行正确例如输入1,再输入221接着输入非零元素为第2行第1列值为9
(219).运行结果如图2,图中创建十字链表成功可以选择后续操作稀疏矩阵转置,稀疏矩阵相加,稀疏矩阵相乘图2选择稀疏矩阵相加实验,输入2,再输入222创建另一个稀疏矩阵,接着输入119和211两个非零元素,__atrix_ADD函数会将两个矩阵的非零元素相比较,在同行列的值相加,不在同行列的为十字链表添加结点,计算结果如图3,可以看到第一行第一列的元素9被加入到链表中,而第2行第1列的两个元素9和1相加得到10,程序运行成功图3五.体会通过这次课程设计,我有很深的体会,具体如下
1.十字链表的建立,和使用有了更深层次的理解
2.各种循环语句的使用和switch语句的应用比较熟悉了
3.把各个功能写在不同的函数体里,分工明确,条理清晰,这样不但语句简洁,而且十分明了
4.从用户角度出发来编写程序,使结果尽量简洁明了附代码#includestdio.h#includestdlib.h#include__lloc.h#define__XSIZE100intnum
[100];typedefstructOLNode{intij;inte;structOLNode*right*down;}OLNode*OLink;typedefstruct{intmunutu;//行数mu,列数nu,非零元素的个数tuOLink*rhead*chead;}CrossList;intCreate__atix_OLCrossListM{intije;OLinkq;OLinkp;printf请输入稀疏矩阵的行数,列数,非零元素的个数:;scanf%d%d%dM.muM.nuM.tu;M.rhead=OLink*__llocM.mu+1*sizeofOLNode;M.chead=OLink*__llocM.nu+1*sizeofOLNode;fori=1;i=M.mu;i++M.rhead[i]=NULL;fori=1;i=M.nu;i++M.chead[i]=NULL;printf请输入元素的行列值最后输入000为结束\n;scanf%d%d%dije;whilei!=0{p=OLink__llocsizeofOLNode;p-i=i;p-j=j;p-e=e;ifM.rhead[i]==NULL||M.rhead[i]-jj{p-right=M.rhead[i];M.rhead[i]=p;}else{q=M.rhead[i];whileq-rightq-right-jjq=q-right;p-right=q-right;q-right=p;}ifM.chead[j]==NULL||M.chead[j]-ii{p-down=M.chead[j];M.chead[j]=p;}else{q=M.chead[j];whileq-downq-down-iiq=q-down;p-down=q-down;q-down=p;}scanf%d%d%dije;}return1;}//创建十字链表intCompareinta1intb1inta2intb2{ifa1a2return1;elseifa1a2return-1;elseifb1b2return1;ifb1b2return-1;elsereturn0;}int__atrix_ADDCrossList*ACrossList*B{OLNode*pa*pb*pre*p*cp
[100];intijt;t=A-tu+B-tu;forj=1;j=A-nu;j++cp[j]=A-chead[j];fori=1;i=A-mu;i++{pa=A-rhead[i];pb=B-rhead[i];pre=NULL;whilepb{ifpa==NULL||pa-jpb-j{p=OLink__llocsizeofOLNode;if!preA-rhead[i]=p;elsepre-right=p;p-right=pa;pre=p;p-i=i;p-j=pb-j;p-e=pb-e;if!A-chead[p-j]{A-chead[p-j]=cp[p-j]=p;p-down=NULL;}else{cp[p-j]-down=p;cp[p-j]=p;}pb=pb-right;}elseifpa-jpb-j{pre=pa;pa=pa-right;}elseifpa-e+pb-e{t--;pa-e+=pb-e;pre=pa;pa=pa-right;pb=pb-right;}else{t=t-2;if!preA-rhead[i]=pa-right;elsepre-right=pa-right;p=pa;pa=pa-right;ifA-chead[p-j]==pA-chead[p-j]=cp[p-j]=p-down;elsecp[p-j]-down=p-down;freep;pb=pb-right;}}}A-mu=A-muB-muA-mu:B-mu;A-nu=A-nuB-nuA-nu:B-nu;return1;}//十字链表相加intShow__trixCrossList*A{intcol;OLinkp;forcol=1;col=A-mu;col++ifA-rhead[col]{p=A-rhead[col];whilep{printf%3d%3d%3d\np-ip-jp-e;p=p-right;}}return1;}//十字链表显示intMult__atrix_OLCrossListMCrossListNCrossListQ{intije;//中间变量OLinkp0q0pplpla;//中间变量//检查稀疏矩阵M的列数和N的行数是否对应相等ifM.nu!=N.mu{printf稀疏矩阵A的列数和B的行数不相等,不能相乘\n;return0;}Q.mu=M.muQ.nu=N.nuQ.tu=0;if!Q.rhead=OLink*__llocQ.mu+1*sizeofOLinkexit-2;if!Q.chead=OLink*__llocQ.nu+1*sizeofOLinkexit-2;fori=1;i=Q.mu;i++Q.rhead[i]=NULL;fori=1;i=Q.nu;i++Q.chead[i]=NULL;//相乘fori=1;i=Q.mu;i++forj=1;j=Q.nu;j++{p0=M.rhead[i]q0=N.chead[j]e=0;whilep0q0//M第i行和N第j列有元素{ifp0-jq0-iq0=q0-down;//M的列大于N的行,则N的列指针后移elseifp0-jq0-ip0=p0-right;//M的列小于N的行,则M的行指针右移else{//M的行等于N的列e+=p0-e*q0-e;//乘积累加q0=q0-downp0=p0-right;//__指针}}ife//乘积不为0{if!p=OLink__llocsizeofOLNodeexit-2;Q.tu++;//非零元素增加p-i=ip-j=jp-e=ep-right=NULLp-down=NULL;//赋值,指针后移//将p插入十字链表//行插入ifQ.rhead[i]==NULL//若p为该行的第1个结点Q.rhead[i]=pl=p;//p插在该行的表头且pl指向p该行的最后一个结点elsepl-right=ppl=p;//插在pl所指结点之后,pl右移//列插入ifQ.chead[j]==NULL//若p为该列的第一个结点Q.chead[j]=p;//该列的表头指向pelse{//插在列表尾pla=Q.chead[j];//pla指向j行的第1个结点whilepla-downpla=pla-down;//pla指向j行最后一个结点pla-down=p;}}}return1;}//十字链表相乘voidTurn__atrix_OLCrossListM{intcolrow;OLinkpq;forcol=1;col=M.mu;col++{q=p=M.rhead[col];whileq{row=p-i;p-i=p-j;p-j=row;q=p-right;p-right=p-down;p-down=q;}}}//十字链表转置intDestroy__atrix_OLCrossListM{inti;//中间变量OLinkpq;//中间变量if!M.rhead||!M.cheadreturn1;//M不存在else{//M存在ifM.chead//所有列链表头指针置为空fori=1;i=M.nu;i++M.chead[i]=NULL;ifM.rhead//按行释放节点fori=1;i=M.mu;i++{p=M.rhead[i];whilep{q=pp=p-right;freeq;}}//释放行和列链表头指针指向基址freeM.rhead;freeM.chead;//返回return1;}}//十字链表销毁void__in{intni;//T__atrixMTS;CrossListMMTTSS;printf请你选择操作:\n1:用十字建表创建稀疏矩阵\n2:退出\n1|2:;scanf%dn;switchn{case1:{Create__atix_OLMM;printf已经选择十字链表创建稀疏矩阵,请选择操作\n1稀疏矩阵转置\n2稀疏矩阵相加\n3稀疏矩阵相乘\n4退出\n1|2|3|4:;scanf%di;switchi{case1:Turn__atrix_OLMM;Show__trixMM;break;case2:printf请你输入另一个稀疏矩阵:;Create__atix_OLTT;__atrix_ADDMMTT;Show__trixMM;break;case3:printf请你输入另一个稀疏矩阵:;Create__atix_OLTT;Mult__atrix_OLMMTTSS;Show__trixSS;break;case4:exit0;}};break;case2:exit0;default:printferorr;}}__in函数退出Create__atix_OL函数exit函数Turn__atrix_OL函数Switch()函数Switch()函数Show__trix函数Create__atix_OL;函数__atrix_ADD;函数Show__trix函数Create__atix_OL函数Mult__atrix_OL函数Show__trix函数。