数据结构实验报告4

r孑以小省堂计算机学院学生姓名（软学号件学院实）验成绩专业19计科班级2班实验日期年月曰实验报告课程名称数据结构与兜法任课教师实验名称稀疏矩阵基本操作实验序号实验地点S510实验台号指导教师

一、实验目的及要求实验目的批注[zl]:宋体，五号字体，行间距固定值20磅批注（z

211.深入了解数组的存储表示和实现.同上

2.掌握稀疏矩阵的特点（三元组存储方法）实验要求L课下完成实验程序的编写，实验室调试验证

3.实验完成后填写实验报告

二、实验内容（或实验原理、实验拓扑）

1.稀疏矩阵的存储及转置运算，完成教材实验题

6.LWindowsDEV-C++//求三元组元素}ifs!=0//产生一个三元组元素c.data[p].r=i;//三元组元素的行号c.data[p].c=j;//三元组元素的列号c.data[p].d=s://三元组元素的元素值P++;c.rows=a.rows;c.cols=b.cols:c.nums=p;//矩阵c的非零元素个数return true;

五、实验结果（包括设计效果、测试数据、运行结果等）

1.

6.1•»1i.H»-C批注h3］可以被取运行效果图.图片大小要适中,放置图片时，不要撑大表格.LM22SC«t2Wl0UMB2al«^*«MM*warthom^rwtQ«MMMI■PHMAMNM3M«♦叫CftfiO0，**G■°■■八©c.

4..gm31fak0M2SttMI・PffiMMtAMMrt»WSO=•CftfiO0H-I■S°・•.

六、实验小结（包括收获、心得体会、注意事项、存在问题及解决办法、建议等）通过这节的上机学习，理解了数组和一般线性表的异同，掌握稀疏矩阵的各种存储结构及其特点深入了解数组的存储表示和实现,掌握稀疏矩阵的特点（三元组存储方法）整体上实现程序的运行上掌握的还是不好，还需要继续努力，继续学习

七、附录包括作品、流程图、源程序及命令清单等^include stdio.h批注刈此处可以放置完成实验内容的核心代码，字1体用TimesNewRoman.行间拒20磅★includestdbool.h-define N4-define MAXSIZE100//矩阵中非零元素最多个数typedef intElemType;typedef structintr;//行号int c;//列号ElemType d;//元素值}TupNode;//三元组定义typedef struct{int rows;//行数值int cols;//列数值int nums;//非零元素个数TupNode data[MAX_SIZE];}TSMatrix//三元组顺序表定义/*产生稀疏矩阵A的三元组表示t*/static voidcreate_matrixTSMatrix t,ElemType A[N][N]int i,j;t.rows=N;//行数值t.cols=N;//列数值t.nums=0;//非零元素个数fori=0iN;i++forj=0;jN;j++ifA[i][j]!=0t.data[t.nums].r=i;//行号t.data[t.nums].c=j;//列号t.data[t.nums].d=A[i][j];//元素值t.nums++;//非零元素个数增1}}/*输出三元组表示t*/static voiddisp matrixTSMatrix tint i;if t.nums=0return;printf/，\t%d\t%d\t%d\nz，,t.rows,t.cols,t.nums;piintf*\t%d\t%d\t%d\nw,t.data[i].r,t.data[i].c,t.data[i].d;/*求三元组表示t的转置矩阵tb*//***转置矩阵*把矩阵A的行换成相应的列，得到的新矩阵称为A的转置矩阵*/static voidtran_matrixTSMatrix t,TSMatrix tbint p,v;int q=0;//q为tb.data的下标tb.rows=t.cols;//转置矩阵行数值tb.cols=t.rows;//转置矩阵列数值lb.nums=t.nums;//转置矩阵非零元素个数if t.nums!=0forv=0;vt.cols;v++//tb.data[q]中的记录以c域的次序排列for p=0;pt.nums;p++//p为t.data的下标if t.data[p].c=vtb.data[q].r=t.data[p].c;//转置矩阵的行号tb.datatq].c=t.data[p].r//转置矩阵的列号tb.datatq].d=t.data[p].d//转置矩阵的元素值q++；}}/*求c=a+b*/static boolmatrix_addTSMatrix a,TSMatrix b,TSMatrix c//弓I用类型形参cint i=0://a中非零元素个数索引int j=0;//b中非零元素个数索引int k=0;//c中非零元素个数ElemType v;if a.rows!=b.rows||a.cols!=b.cols//行数或列数不等时不能进行相加运算return false;//c的行列数与a的相同c.rows=a.rowsc.cols=a.cols;whileia.numsjb.nums//处理a和b中的元素假设a.nums=6,b.nums=4if a.data[i].r=b.data[j].r//a元素的行号等于b元素的行号if a.data[i].cb.data[j].c//a元素的列号小于b元素的列号//将a元素添加到c中c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++;else if a.data[i].cb.data[j].c//a元素的列号大于b元素的列号{//将b元素添加到c中c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++；}else//a元素的列号等于b元素的列号{v=a.data[i].d+b.data[j].d;ifv!=0//只将不为0的结果添加到c中{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;i++；j++；else if a.data[i].rb.data[j].r//a元素的行号小于b元素的行号

四、实验设计方案包括实验步骤、设计思想、算法描述或开发流程等定义一个三元组typedef structintr;//行号int c;//列号ElcmTypc d;//元素值}TupNode;//三元组定义typedef structintrows;//行数值int cols;//列数值int nums;//非零元素个数TupNode data[MAX_SIZE];}TSMatrix;//三元组顺序表定义算法思路过程/*产生稀疏矩阵的三元组表示t*/static voidcreate_matrixTSMatrix t,ElemType A[N][N]int i,j;t.rows=N;//行数值t.cols=N;//列数值t.nums=0;//非零元素个数c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].dk++;i++；}else//a元素的行号大于b元素的行号//将b元素添加到c中c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++；c.nums=k;}return true;}/*返回三元组t表示的A[i][j]值*/static intget_va1ueTSMatrix t,int i,int jwhilekt.numst.data[k].r!=i||t.data[k].c!=jk++;ifkt.numsreturn t.data[k].cl;elsereturn0;}/*求c=a*b*/static boolmatrix mu1TSMatrix a,TSMatrix b,TSMatrix c//弓|用类型形参cint i;int j;int k;int p=0;//矩阵c的非零元素个数ElemType s;if a.cols!=b.rows//a的列数不等于b的行数时不能进行乘法运算return false;for i=0ia.rowsi++//矩阵c的行数{forj=0;jb.cols;j++//矩阵c的列数s=0;fork=0;ka.cols;k++s=s+get_valuea,i,k*get_valueb,k,j;//求三元组元素}ifs!=0//产生一个三元组元素c.datatp].r=i://三元组元素的行号c.data[p].c=j://三元组元素的列号c.data[p].d=s;//三元组元素的元素值P++;}c.rows=a.rowsc.cols=b.cols;c.nums=p;//矩阵c的非零元素个数return true;}int mainvoidElemTypcal[N][N]={1,0,3,0,0,1,0,0,0,0,1,0,{0,0,1,1};ElemType bl[N][N]={{3,0,0,0,0,4,0,0,0,0,1,0,[0,0,0,2；TSMatrix a,b,c;create matrixa,al;create_matrixb,bl;printf*a的三元组八的;disp_matrixa;printf Cb的三元组:\n;disp matrixb;printf Ca转置为c\n*tran_matrixa,c;printf*c的三元组八的;disp matrixc;printfc=a+b\n;matrix_adda,b,c;printf*c的三元组:\n;disp_matrixc;printf*c=a*b\nw;matrix_mul a,b,c;printf*c的三元组:\n;disp matrixc;return0;fori=0;iN;i++forj=0;jN;j++ifA[i][j]!=0t.data[t.nuras],r=i;//行号t.data[t.nums].c=j;〃列号t.data[t.nums].d=A[i][j];//元素值t.nums++;//非零元素个数增1}/*输出三元组表示t*/static voiddisp_matrixTSMatrix tint i;if t.nums=0return;printf/，\l%d\t%d\t%d\n*,t.rows,t.cols,t.nums;fori=0it.nums:i++printf z，\t%d\t%d\t%d\nw,t.data[i].r,t.data[i].c,t.dalati].d;/*求三元组表示t的转置矩阵tb*//***转置矩阵*把矩阵A的行换成相应的列，得到的新矩阵称为A的转置矩阵*/static voidtran_matrixTSMatrixt,TSMatrix tbint p,v;int q=0;//q为tb.data的下标tb.rows=t.cols;//转置矩阵行数值tb.cols=t.rows;//转置矩阵列数值tb.nums=t.nums;//转置矩阵非零元素个数if t.nums!=0forv=0;vt.cols;v++//tb.dala[q]中的记录以c域的次序排列forp=0;pt.nums;p++//p为t.data的下标if t.data[p].c==vtb.data[q].r=t.data[p].c://转置矩阵的行tb.data[q].c=t.data[p].r://转置矩阵的列号tb.data[q].d=t.data[p].d;//转置矩阵的元素值q++；}/*—求c=a+b*/static boolmatrix_aldTSMatrix a,TSMatrix b,TSMatrix c//弓I用类型形参cint i=0;//a中非零元素个数索引int j=0;//b中非零元素个数索引int k=0;//c中非零元素个数ElemType v;if a.rows!=b.rows11a.cols!=b.cols//行数或列数不等时不能进行相加运算return false;//c的行列数与a的相同c.rows=a.rows;c.cols=a.cols;whileia.numsjb.nums//处理a和b中的元素假设a.nums=6,b.nums=4{if a.data[i].r==b.data[j].r//a元素的行号等于b元素的行号ifa.data[i].cb.data[j].c//a元素的列号小于b元素的列号{//将a元素添加到c中c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k],d=a.data[i],d;k++;i++；}else ifa.data[i].cb.datatj].c//a元素的列号大于b元素的列号{//将b元素添加到c中c.data[k].r=b.data[j].r;c.data[k].c=b.data[j],c;c.data[k].d=b.datatj].d;k++;j++；}else//a元素的列号等于b元素的列号v=a.data[i].d+b.data[j].d;ifv!=0//只将不为0的结果添加到c中c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;i++；j++；}else ifa.data[i],rb.data[j].r//a元素的行号小于b元素的行号I//将a元素添加到c中c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;k++;i++；else//a元素的行号大于b元素的行号I//将b元素添加到c中c.dala[k].r=b.data[j].r c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++；c.nums=k;return true;}/*-—返回三元组t表示的A[i][j]值*/static intget_va1ueTSMatrix t,inti,int j{int k=0;whilekt.numst.data[k].r!=i||t.data[k].c!=j k++;ifkt.numsreturn t.data[k].d;elsereturn0;/*求c=a*b*/static boolmatrix_mulTSMatrix a,TSMatrix b,TSMatrix c//弓|用类型形参cint i;int j;int k;intp=0;//矩阵c的非零元素个数ElemType s;ifa.cols!=b.rows//a的列数不等于b的行数时不能进行乘法运算return false;fori=0;ia.rows;i++//矩阵c的行数forj=0;jb.cols;j++//矩阵c的列数s=0;fork=0;ka.cols;k++s=s+gct valuea,i,k*get valueb,k,j。