稀疏矩阵三元组实现矩阵转置算法实验报告

1实验三稀疏矩阵的三元组表示实现矩阵转置算法学院专业班学号姓名一．实习目的1.掌握稀疏矩阵的三元组顺序表存储表示；2.掌握稀疏矩阵三元组表示的传统转置算法的实现；3.掌握稀疏矩阵三元组表示的快速转置算法的实现；二．实习内容1.稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现传统转置算法，输出按通常的阵列形式输出。2.稀疏矩阵的按三元组形式输入，即按行序输入非零元的行号、列号、值，实现快速转置算法，输出按通常的阵列形式输出。三．实验步骤1.三元组的定义#defineMAX_SIZE100//非零元个数的最大值structTriple{inti,j;//行下标,列下标ElemTypee;//非零元素值};structTSMatrix{structTripledata[MAX_SIZE+1];//非零元三元组表，data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数};2.创建稀疏矩阵M（按三元组形式输入，即按行序输入非零元的行号、列号、值）3.编写三元组传统转置函数。4.编写三元组快速转置函数。4..主函数(1)程序代码#includestdio.h#includestdlib.h#defineMAX_SIZE100//非零元个数的最大值typedefintElemType;structTriple{inti,j;//行下标,列下标ElemTypee;//非零元素值};structTSMatrix2{structTripledata[MAX_SIZE+1];//非零元三元组表，data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数};intCreateSMatrix(TSMatrix&M){//创建稀疏矩阵Minti,m,n;ElemTypee;intk;printf(请输入矩阵的行数,列数,非零元素数：);scanf(%d,%d,%d,&M.mu,&M.nu,&M.tu);if(M.tuMAX_SIZE)return-1;M.data[0].i=0;//为以下比较顺序做准备for(i=1;i=M.tu;i++){do{printf(请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值:,i,M.mu,M.nu);scanf(%d,%d,%d,&m,&n,&e);//输入非零元的行号、列号、元素值k=0;if(m1||mM.mu||n1||nM.nu)//行或列超出范围k=1;if(mM.data[i-1].i||m==M.data[i-1].i&&n=M.data[i-1].j)//行或列的顺序有错k=1;}while(k);M.data[i].i=m;//将m,n,e填入MM.data[i].j=n;M.data[i].e=e;}return1;}voidPrintSMatrix(TSMatrixM){//按矩阵形式输出Minti,j,k=1;Triple*p=M.data;p++;//p指向第1个非零元素for(i=1;i=M.mu;i++)3{for(j=1;j=M.nu;j++)if(k=M.tu&&p-i==i&&p-j==j)//p指向非零元，且p所指元素为当前处理元素{printf(%3d,p-e);//输出p所指元素的值p++;//p指向下一个元素k++;//计数器+1}else//p所指元素不是当前处理元素printf(%3d,0);//输出0printf(\n);}}voidTransposeSMatrix(TSMatrixM,TSMatrix&T){//求稀疏矩阵M的转置矩阵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;}}}voidFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//快速求稀疏矩阵M的转置矩阵T。算法5.2改intp,q,t,k,col,*num,*cpot;num=(int*)malloc((M.nu+1)*sizeof(int));//存M每列(T每行)非零元素个数([0]不用)cpot=(int*)malloc((M.nu+1)*sizeof(int));//存T每行的下1个非零元素的存储位置([0]不用)T.mu=M.nu;//给T的行、列数与非零元素个数赋值T.nu=M.mu;4T.tu=M.tu;if(T.tu)//是非零矩阵{for(col=1;col=M.nu;++col)num[col]=0;//计数器初值设为0for(t=1;t=M.tu;++t)//求M中每一列含非零元素个数{k=M.data[t].j;++num[col];}cpot[1]=1;//T的第1行的第1个非零元在T.data中的序号为1for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求T的第col行的第1个非零元在T.data中的序号printf(num数组的值为：\n);for(col=1;col=M.nu;++col)printf(%4d,num[col]);printf(\n);printf(转置前cpot数组的值为：\n);for(col=1;col=M.nu;++col)printf(%4d,cpot[col]);printf(\n);for(p=1;p=M.tu;++p)//从M的第1个元素开始{col=M.data[p].j;//求得在M中的列数q=cpot[M.data[p].j];//q指示M当前的元素在T中的序号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];//T第col行的下1个非零元在T.data中的序号}}printf(转置后cpot数组的值为：\n);for(col=1;col=M.nu;++col)printf(%4d,cpot[col]);printf(\n);free(num);free(cpot);}voidmain(){TSMatrixA,T;printf(创建矩阵A:);CreateSMatrix(A);PrintSMatrix(A);5TransposeSMatrix(A,T);printf(传统矩阵转置程序执行后的矩阵t(A的转置):\n);PrintSMatrix(T);FastTransposeSMatrix(A,T);printf(快速矩阵转置程序执行后的矩阵t(A的转置):\n);PrintSMatrix(T);}（2）调试程序(3)运行程序（截图）四．实习小结自己写