数据结构-实验6-稀疏矩阵

《算法设计与分析》实验报告-1-1、实验目的（1)掌握稀疏矩阵三元组表的存储方法；（2)掌握稀疏矩阵三元组表的创建、显示、转置和查找算法。2、实验内容（1)编写稀疏矩阵三元组表的存储程序；（2)编写稀疏矩阵三元组表的创建、显示、转置和查找程序。3、实验要求（1)用C（C++）语言完成算法设计和程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜单的输出，设计另外五个函数来求分别实现新建，转置，查找，显示，最后，串接函数，并调试程序，在调试的时候，我先进行新建操作，输入数据之后，然后开始转置操作，再进行查找其中的非零元素，多次调试后，发现没有问题，得出实验结果，并截图。⑵源代码#includestdio.h#includeiomanip.h#includestdlib.h#includestring.h#defineSMAX100//三元组非零元素的最大个数typedefstructSPNode//定义三元组{inti,j,v;//三元组非零元素的行、列和值};typedefstructsparmatrix//定义稀疏矩阵{introws,cols,terms;//稀疏矩阵行、列和非零元素的个数SPNodedata[SMAX];//三元组表};sparmatrixCreateSparmatrix()//创建稀疏矩阵{sparmatrixA;printf(\n\t\t请输入稀疏矩阵的行数,列数和非零元个数(用逗号隔开):);《算法设计与分析》实验报告-2-scanf(%d,%d,%d,&A.rows,&A.cols,&A.terms);for(intn=0;n=A.terms-1;n++){printf(\n\t\t输入非零元值(格式:行号,列号,值):);scanf(%d,%d,%d,&A.data[n].i,&A.data[n].j,&A.data[n].v);}returnA;}sparmatrixTrans(sparmatrixA)//转置稀疏矩阵{sparmatrixB;B.rows=A.cols;B.cols=A.rows;B.terms=A.terms;for(intn=0;n=A.terms-1;n++){B.data[n].i=A.data[n].j;B.data[n].j=A.data[n].i;B.data[n].v=A.data[n].v;}returnB;}voidShowSparmatrix(sparmatrixA)//显示稀疏矩阵{intk;printf(\n\t\t);for(intx=0;x=A.rows-1;x++){for(inty=0;y=A.cols-1;y++){k=0;for(intn=0;n=A.terms-1;n++){if((A.data[n].i==x)&&(A.data[n].j==y)){printf(%8d,A.data[n].v);k=1;}}if(k==0)printf(%8d,k);}printf(\n\t\t);《算法设计与分析》实验报告-3-}}voidSearchSparmatrix(sparmatrixA,ints)//查找稀疏矩阵中非零元素{intn,t;t=A.terms;for(n=0;nt;n++){if(A.data[n].v==s){printf(\n\t\t行列值\n);printf(\n\t\t元素位置:%2d%2d%2d\n,A.data[n].i,A.data[n].j,A.data[n].v);n=-1;break;}}if(n!=-1)printf(\n\t\t矩阵中无此元素!\n);}voidmain()//稀疏矩阵的三元组存储{intch=1,choice,s;structsparmatrixA,B;A.terms=0;B.terms=0;while(ch){printf(\n);printf(\n\t\t稀疏矩阵的三元组存储\n);printf(\n\t\t******************************************);printf(\n\t\t*1-----新建*);printf(\n\t\t*2-----转置*);printf(\n\t\t*3-----查找*);printf(\n\t\t*4-----显示*);printf(\n\t\t*0-----返回*);《算法设计与分析》实验报告-4-printf(\n\t\t******************************************);printf(\n\n\t\t请输入菜单号(0--4):);scanf(%d,&choice);switch(choice){case1:A=CreateSparmatrix();break;case2:if(A.terms==0)printf(\n\t\t三元组为空!\n);else{B=Trans(A);printf(\n\t\t转置后的稀疏矩阵:\n);ShowSparmatrix(B);}break;case3:if(A.terms==0)printf(\n\t\t三元组为空!\n);else{printf(\n\t\t输入要查找的非零元素:);scanf(%d,&s);SearchSparmatrix(A,s);}break;case4:ShowSparmatrix(A);break;case0:ch=0;break;default:system(cls);printf(\n\t\t输入错误!请重新输入!\n);《算法设计与分析》实验报告-5-break;}if(choice==1||choice==2||choice==3||choice==4){printf(\n\t\t);system(pause);system(cls);}elsesystem(cls);}}5、测试数据与实验结果（可以抓图粘贴）（1）菜单显示：（2）新建：（3）转置：（4）查找：《算法设计与分析》实验报告-6-（5）显示：6、结果分析与实验体会本次实验是书中的范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。在实验的过程中，我加深了对稀疏矩阵各种操作的理解，因为稀疏矩阵非零元素较少，为了节省空间可以只存储非零元素的值，并记下它所在的行和列的信息，这样就可以方便找出相应的元素，在做矩阵转置的时候，尤其要注意，算法不能只是进行简单的行列互换，转化之后，行的下标不是从小到大排列的，所以必须再对行的下标进行排序才行。若把具有同一行号的非零元素用一个链表连接起来，则稀疏矩阵中的若干行组成若干个单向链表，合起来就成为带行指针的单向链表了。所以掌握稀疏矩阵的各种操作算法很有必要。