中国石油大学数据结构上机实验

《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.4.24一、实验题目实验5稀疏矩阵的转置二、实验目的1.稀疏矩阵的压缩存储方法2.掌握稀疏矩阵的转置算法三、算法设计分析（一）实验内容1.从键盘输入数据，建立稀疏矩阵的三元组顺序存储2.实现稀疏矩阵的转置算法3.输出原矩阵及转置后的矩阵4．实现矩阵的快速转置算法（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：①创建稀疏矩阵函数②转置矩阵T函数③快速转置函数④输出函数⑤输出原矩阵和转置函数其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能Statusmain()（2）①创建稀疏矩阵函数StatusCreateSMatrix(TSMatrix&M){printf(请输入原矩阵：\n);printf(行数、列数：);scanf(%d%d,&M.mu,&M.nu);printf(元素总数：);scanf(%d,&M.tu);printf(输入各个对应压缩值：\n);for(inti=1;i=M.tu;++i)scanf(%d%d%d,&M.data[i].i,&M.data[i].j,&M.data[i].e);returnOK;}②转置矩阵T函数StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){intp,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col=M.nu;++col)for(p=1;p=M.tu;++p)if(M.data[p].j==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;++q;}}printf(\n\n稀疏矩阵M转置成功。\n\n);returnOK;}//TransposeSMatrix③快速转置函数StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){intcol,t,q;intnum[100],cpot[100];for(col=1;col=M.nu;++col)num[col]=0;for(t=1;t=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求cpot向量for(intp=1;p=M.tu;++p){col=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];}//for}//ifprintf(\n\n稀疏矩阵M快速转置成功。\n\n);returnOK;}④输出函数StatusOutputOSMatrix(TSMatrix&M){printf(\n\n原稀疏矩阵\n);printf(行数、列数、元素总数\n%d%d%d\n\n,M.mu,M.nu,M.tu);printf(值\n);for(intt=1;t=M.tu;++t)printf(%d%d%d\n,M.data[t].i,M.data[t].j,M.data[t].e);returnOK;}⑤输出原矩阵和转置函数StatusOutputTSMatrix(TSMatrix&M,TSMatrix&T){printf(\n\n原稀疏矩阵转置后的稀疏矩阵\n);printf(行数、列数、元素总数行数、列数、元素总数\n%d%d%d%d%d%d\n\n,M.mu,M.nu,M.tu,T.mu,T.nu,T.tu);printf(值值\n);for(intt=1;t=T.tu;++t)printf(%d%d%d%d%d%d\n,M.data[t].i,M.data[t].j,M.data[t].e,T.data[t].i,T.data[t].j,T.data[t].e);returnOK;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析矩阵的快速转置方法的原理是：如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中(上面那图是b.data)恰当位置。那么在对a.data中的三元组一次做转置时，便可直接放到b.data中恰当的位置上去。五、实验总结附录实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#defineMAXSIZE12500//假设非零元个数的最大值为12500#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//非零元对应的值}Triple;typedefstruct{Tripledata[MAXSIZE+1];//非零元三元组，data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数}TSMatrix;StatusCreateSMatrix(TSMatrix&M){//创建稀疏矩阵，从键盘输入数据，建立系数矩阵的三元组顺序存储printf(请输入原矩阵：\n);printf(行数、列数：);scanf(%d%d,&M.mu,&M.nu);printf(元素总数：);scanf(%d,&M.tu);printf(输入各个对应压缩值：\n);for(inti=1;i=M.tu;++i)//按照输入的元素总数，依次输入非零元的坐标以及值scanf(%d%d%d,&M.data[i].i,&M.data[i].j,&M.data[i].e);returnOK;}StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵Tintp,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col=M.nu;++col)for(p=1;p=M.tu;++p)if(M.data[p].j==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;++q;}}printf(\n\n稀疏矩阵M转置成功。\n\n);returnOK;}//TransposeSMatrixStatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T)//快速转置{//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){intcol,t,q;intnum[100],cpot[100];for(col=1;col=M.nu;++col)num[col]=0;//num数组的初始化for(t=1;t=M.tu;++t)++num[M.data[t].j];//求M中每一列含有的非零元个数cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求cpot向量for(intp=1;p=M.tu;++p){col=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];}//for}//ifprintf(\n\n稀疏矩阵M快速转置成功。\n\n);returnOK;}//FastTransposeSMatrixStatusOutputOSMatrix(TSMatrix&M){//输出原矩阵，为了输出美观，调整了间距printf(\n\n原稀疏矩阵\n);printf(行数、列数、元素总数\n%d%d%d\n\n,M.mu,M.nu,M.tu);printf(值\n);for(intt=1;t=M.tu;++t)printf(%d%d%d\n,M.data[t].i,M.data[t].j,M.data[t].e);returnOK;}StatusOutputTSMatrix(TSMatrix&M,TSMatrix&T){//输出原矩阵和转置矩阵，为了输出美观，调整了间距printf(\n\n原稀疏矩阵转置后的稀疏矩阵\n);printf(行数、列数、元素总数行数、列数、元素总数\n%d%d%d%d%d%d\n\n,M.mu,M.nu,M.tu,T.mu,T.nu,T.tu);printf(值值\n);for(intt=1;t=T.tu;++t)printf(%d%d%d%d%d%d\n,M.data[t].i,M.data[t].j,M.data[t].e,T.data[t].i,T.data[t].j,T.data[t].e);returnOK;}voidmainmenu()//输出菜单,供用户进行操作选择{printf(\n菜单);printf(\n****************************\n\n);printf(*1.创建稀疏矩阵*\n);printf(*2.稀疏矩阵转置*\n);printf(*3.稀疏矩阵快速转置*\n);printf(*4.输出原矩阵和转置矩阵*\n);printf(*0.退出*\n);printf(\n*****************************\n);}Statusmain()//主函数{TSMatrixM;TSMatrixT;intchoose;while(1){mainmenu();printf(\n请输入你的选择：);scanf(%d,&choose);switch(choose){case1://在此插入创建稀疏矩阵函数system(cls);CreateSMatrix(M);system(PAUSE);system(cls);break;case2://在此插入稀疏矩阵转置函数system(cls);TransposeSMatrix(M,T);system(PAUSE);system(cls);break;case3://在此调用稀疏矩阵快速转置函数system(cls);FastTransposeSMatrix(M,T);system(PAUSE);system(cls);break;case4://在此调用输出原稀疏矩阵以及转置矩阵函数system(cls);OutputTSMatrix(M,T);system(PAUSE);system(cls);break;case0://退出exit(0);break;default://输入非法，提示用户重新输入printf(\n输入错误，重新输入！\n);}}}