还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》实验报告一.实验题目必做稀疏矩阵转置、加法行逻辑链接表选做稀疏矩阵乘法二.程序设计一需求分析
1.程序运行步骤
(1)开始;
(3)选择矩阵运算后,输入矩阵;
(4)对矩阵进行相应的运算;
(5)输出运算结果;
(6)结束
(二)概要设计程序模块及思想1.主函数主函数的主体是一个switch选择结构内部分为三种情况矩阵转置、矩阵加法和矩阵乘法
(1)矩阵转置运算
(1)输入矩阵;
(2)输出这个矩阵;
(3)转置这个矩阵;
(4)输出转置后的结果;
(5)结束
(2)矩阵加法运算
(1)输入矩阵A和矩阵B;
(2)输出这两个矩阵;
(3)将两个矩阵相加;
(4)输出相加后的结果;
(5)结束
(3)矩阵乘法运算
(1)输入矩阵A和矩阵B;
(2)输出这两个矩阵;
(3)将两个矩阵相加;
(4)输出相加后的结果;
(5)结束2.基本操作typedefstruct{intij;ElemTypee;}Triple;操作结果定义三元组typedefstruct{Tripledata[__XSIZE+1];intmunutucnum[__XSIZE+1]rnum[__XSIZE+1]cpot[__XSIZE+1]rpos[__XSIZE+1];//某一列非零元的个数,某一行非零元的个数,某一列第一个非零元在b.data中的位置,某一行非零元在b.data中的位置}T__atrix;操作结果定义稀疏矩阵intGet__atrixT__atrixt操作结果创建稀疏矩阵,以三元组表形式储存intTranspose__atrixT__atrixMT__atrixT操作结果转置矩阵intPrint__atrixT__atrixt操作结果输出矩阵intAdd__atrixT__atrixtT__atrixsT__atrixa操作结果矩阵相加
(三)详细设计1.结构体定义typedefstruct{intij;//行,列ElemTypee;//非零元素的值}Triple;操作结果定义三元组typedefstruct{Tripledata[__XSIZE+1];intmunutucnum[__XSIZE+1]rnum[__XSIZE+1]cpot[__XSIZE+1]rpos[__XSIZE+1];//行数,列数,非零元素个数,某一列非零元的个数,某一行非零元的个数,某一列第一个非零元在b.data中的位置,某一行非零元在b.data中的位置}T__atrix;操作结果定义稀疏矩阵
2.每个模块的分析
(1)主程序模块int__in{intk;T__atrixtsa;printf请输入需要执行的操作的序号(
1.矩阵转置
2.矩阵相加
3.矩阵乘法)\n;scanf%dk;switchk{case1:{Get__atrixt;//转置模块printf输入的矩阵为\n;Print__atrixt;Transpose__atrixts;printf转置后的矩阵为\n;Print__atrixs;}break;case2:{printf请依次输入两个矩阵\n;//加法模块Get__atrixt;printf\n\n;Get__atrixs;printf输入的两个矩阵分别为\n;printf矩阵a\n;Print__atrixt;printf矩阵b\n;Print__atrixs;ift.mu!=s.mu||t.nu!=s.nuprintfERROR;else{Add__atrixtsa;printf相加后的矩阵为\n;Print__atrixa;}}break;case3:{printf请依次输入两个矩阵\n;//乘法模块Get__atrixt;printf\n\n;Get__atrixs;printf输入的两个矩阵分别为\n;printf矩阵a\n;Print__atrixt;printf矩阵b\n;Print__atrixs;ift.nu!=s.muprintfERROR\n;else{Mult__atrixtsa;printf相乘后的矩阵为\n;Print__atrixa;}}break;return0;}}
(2)基本操作函数
(1)矩阵的创建intGet__atrixT__atrixt{//创建稀疏矩阵,以三元组表形式储存intik;t.cnum
[0]=0;t.cpot
[0]=1;t.rnum
[0]=0t.rpos
[0]=1;//第零列非零元的个数,第零行非零元的个数,第零列第一个非零元在b.data中的位置,第零行非零元在b.data中的位置等参数的初始值为零printf请输入矩阵的行数、列数以及非零元个数\n;scanf%d%d%dt.mut.nut.tu;printf请依次输入%d个非零元的行数、列数以及非零元的值\nt.tu;fori=1;i=t.tu;i++{scanf%d%d%dt.data[i].it.data[i].jt.data[i].e;//输入每个非零元素的行坐标,列坐标和值}fori=1;i=t.nu;i++{t.cpot[i]=t.cpot[i-1]+t.cnum[i-1];t.cnum[i]=0;//这一列非零元的个数初始值为零fork=1;k=t.tu;k++ift.data[k].j==it.cnum[i]+=1;//求这一列非零元的个数}fori=1;i=t.mu;i++{t.rpos[i]=t.rpos[i-1]+t.rnum[i-1];t.rnum[i]=0;//这一行非零元的个数初始值为零fork=1;k=t.tu;k++ift.data[k].i==it.rnum[i]+=1;//求这一行非零元的个数}returnOK;}
(2)矩阵的转置intTranspose__atrixT__atrixMT__atrixT{//转置矩阵T.mu=M.nu;//T的行数与M的列数相同T.nu=M.mu;//T的列数与M的列数相同T.tu=M.tu;intcolpq;ifT.tu{q=1;forcol=1;col=M.nu;++colforp=1;p=M.tu;++pifM.data[p].j==col{T.data[q].i=M.data[p].j;//将转置后的矩阵M的赋值给TT.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}returnOK;}
(3)矩阵的加法intAdd__atrixT__atrixtT__atrixsT__atrixa{//矩阵相加intikjq=1;a.mu=t.mu;a.nu=t.nu;a.tu=0;//ST矩阵的行列必须相同fori=1;i=t.mu;i++{k=t.rpos[i];j=s.rpos[i];ifi==t.mu{//如果i等于行数t.rpos[i+1]=t.rpos[i]+t.tu-k+1;//下一行第一个非零元在t.data中的位置等于总非零元的个数加一s.rpos[i+1]=s.rpos[i]+s.tu-j+1;//求下一行第一个非零元在s.data中的位置}whilekt.rpos[i+1]js.rpos[i+1]//当t与s还有非零元存在时{ift.data[k].j!=s.data[j].j//当T与S列行坐标不相等时{ift.data[k].js.data[j].j//当t的列坐标小于s的列坐标时{a.data[q].i=i;a.data[q].j=t.data[k].j;//a.data[q]赋值为t.data[k]a.data[q].e=t.data[k].e;q++;k++;a.tu++;}else{//a.data[q]赋值为s.data[q]a.data[q].i=i;a.data[q].j=s.data[j].j;a.data[q].e=s.data[j].e;q++;j++;a.tu++;}}else{//当T与S列行坐标相等时a.data[q].i=i;a.data[q].j=t.data[k].j;a.data[q].e=t.data[k].e+s.data[j].e;q++;k++;//相加j++;a.tu++;}}whilekt.rpos[i+1]//若仅有t还有非零元{a.data[q].i=i;a.data[q].j=t.data[k].j;//a.data[q]赋值为t.data[q]a.data[q].e=t.data[k].e;q++;k++;a.tu++;}whilejs.rpos[i+1]//若仅s还有非零元{a.data[q].i=i;a.data[q].j=s.data[j].j;//a.data[q]赋值为s.data[q]a.data[q].e=s.data[j].e;q++;j++;a.tu++;}}returnOK;}
(4)矩阵的乘法intMult__atrixT__atrixMT__atrixNT__atrixQ{intarowbrowccolctemp[__XSIZE+1]tptpqi;ifM.nu!=N.mureturnERROR;Q.mu=M.mu;Q.nu=N.nu;//确定矩阵的参数Q.tu=0;forarow=1;arow=M.mu;++arow{fori=1;i=N.nu;i++ctemp[i]=0;//累加器清零Q.rpos[arow]=Q.tu+1;//每一个Q.rpos[arow]赋相同的初值Q.tu+1ifarowM.mutp=M.rpos[arow+1];//定位驱动元素M.data[p]的范围M每一行在M.data[]中元素范围,//[M.rpos[arrow]M.rpos[arrow+1]]但是最后一行的范围[M.rpos[arrow],M.tu+1]M.tu与tu不同不是转置运算elsetp=M.tu+1;forp=M.rpos[arow];ptp;++p{//遍历M的一行元素,[M.rpos[arow],tp]驱动元素M.data[p]brow=M.data[p].j;ifbrowN.mut=N.rpos[brow+1];elset=N.tu+1;forq=N.rpos[brow];qt;++q{ccol=N.data[q].j;//相乘ctemp[ccol]+=M.data[p].e*N.data[q].e;}}forccol=1;ccol=Q.nu;++ccolifctemp[ccol]{//新的矩阵if++Q.tu__XSIZEreturnERROR;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}}}returnOK;}四程序使用说明及测试结果程序运行截图如下
1.矩阵转置
(2)矩阵加法
(3)矩阵乘法
(五)、实验总结实验心得
1.你在编程过程中花时多少?答从设计到编写,从调试到完成,直至最终完成实验报告一共用了约八个小时
2.多少时间在纸上设计?答两个小时
3.多少时间上机输入和调试?答四个多小时
4.多少时间在思考问题?答设计前就思考,直至完成报告,十个小时
5.遇到了哪些难题?又是怎么克服的?答答在做这项作业时我可以说自己遇到了无数难题,以为我的C语言成绩并不好,栈的熟悉度恐怕只有10%因此完成这项作业的过程可谓艰辛首先遇到的困难就是设计程序去年C语言学得很不扎实,我对三元组的结构都不甚了解,更别说运用与之相关的算法了在设计程序之前我花了很长时间复习书上与之相关的算法在周五下午数据结构的实验课上,我又将数据结构书上的算法仔细分析了一遍由于知识的匮乏,我只能先将书上的三元组稀疏矩阵有关的算法逐句逐句的分析, 然后在纸上设计相应的流程最后凭借自己的知识,并利用同学的帮助,磕磕绊绊地编写了程序接下来的困难,也就是最大,最麻烦,解决起来最耗费脑力,最枯燥乏味的问题——调试程序最初的程序编译之后,问题____,我根据系统的提示,首先补上了缺失的间隔符,又定义了遗漏的变量,再次编译,错误有所减少,但依然多,我又重新修改接下来的错误越来越“高级”,数据类型,返回类型,函数类型等有关我便循环往复,不厌其烦地修改,每当减少一个错误,我都会有几分高兴,而有的时候,修改后会产生更多的错误就这样一遍又一遍,终于系统显示没有错误和警告了我运行了程序当我按照自己的设想将输入数据时,敲下回车键后结果却令我傻了眼屏幕上没有任何显示,原来许多错误是编译器没有检测出来最终通过我的调试,修改和同学的帮助,终于完成了程序
6.你的收获有哪些?答首先,我对稀疏矩阵的知识有了更多了解破除了错误的认识其次,通过这次作业,我掌握了几种与稀疏矩阵有关的算法最后,我还温习了有关C语言的许多知识____【1】严蔚敏▪《数据结构▪第三章》清华大学出版社。