数据结构实验二实验报告.docx

一题目:稀疏矩阵转置班级: 姓名: 学号: 完成日期:15.11.13一、题目要求:输出稀疏矩阵的转置矩阵。（行列均不大于20）要求为输入两个正整数n和m,为矩阵的行和列，然后输入矩阵三元组，（0,0,0）表示结束输入。二、概要设计1.需要的数据结构为：线性表。2.需要线性表的抽象数据类型： ADT SparseMatrix 数据对象：D=aij:|aijTermSet,i=1m,m0，j=1n,n0 m和n分别成为矩阵的行数和列数 数据关系：R=Row，Col Row =|1im，1jn-1 Col =|1im-1，1jn 基本操作： CreateSMtrix(& M) 操作结果：创建稀疏矩阵M。 DestroySMaix(&M) 初始条件：稀疏矩阵M已存在。 操作结果：销毁稀疏矩阵M。 PrintSMatrix(L) 初始条件：稀疏矩阵M已经存在。 操作结果：输出稀疏矩阵M。 CopySMatrix（M，&T） 初始条件：稀疏矩阵M已经存在。 操作结果：由稀疏矩阵M复制得到T。 TransposeSMatrix(M，&T) 初始条件：稀疏矩阵M已经存在。 操作结果：求稀疏矩阵M的转转矩阵T。 ADT SparseMatrix三、详细设计1.元素类型，结点类型 typedef struct int i,j,v;NODE;typedef struct int m,n,t; NODE dataMAX+1;MT;2.对抽象数据类型中的部分基本操作的伪码算法如下： /*三元组的转置*/ MT tran( MT a) /采用三元组存储表示，求稀疏矩阵a的转置矩阵b int p,q,col; MT b; b.m=a.n; b.n=a.m; b.t=a.t; if(a.t!=0) q=0; for(col=0;cola.n;col+)/先列 for(p=0;pa.t;p+) if(a.datap.j=col) b.dataq.i= a.datap.j; b.dataq.j= a.datap.i; b.dataq.v= a.datap.v; q+; return (b);/*主函数（包含输入输出函数）*/ int main() MT a,b; int i,r,c,t,n; scanf(%d,&r);/输入行数 scanf(%d,&c);/输入列数 t=0; a.m=r; a.n=c; for(i=0;i+) /输入初始矩阵a scanf(%d %d %d,&r,&c,&n); a.datai.i=r; a.datai.j=c; a.datai.v=n; t+; if(a.datai.i=0&a.datai.j=0&a.datai.v=0)break; /输入（0,0,0）结束 a.t=t; b=tran(a); for(i=0;it;i+) /输出转置后的矩阵 if(b.datai.i=0&b.datai.j=0&b.datai.v=0)continue; else printf(%d %d %dn,b.datai.i,b.datai.j,b.datai.v); return 0; 3.函数调用关系：MainMT tran四、调试分析与心得体会1.一开始我没有定义非零元素个数最大值，编译时出现error提示，如:编程sdfasdmain.cpp|10|error: MAX was not declared in this scope|等，经检查后发现错误，再开头加声明#deefine MAXSIZE 1000,最终解决错误。 2编译的时候错误一大堆,不过最关键的是转置函数的错误，再运行的结果中出现不了想要的结果，经过一一排除后，才发现只是一个赋值语句的顺序颠倒而已。编程就是这样，牵一发而动全身，一个字母就有可能导致全面崩盘。 3.特殊点的错误。一开始的程序中，对于以（0，0，t）类型的三元组不能有效识别并排序。例子如下图：最后才发现输出的部分并不是那么合理，因为我把结束标志当成一个矩阵元素对待，同样记录其中，固然再编写算法的时候取了巧，但是输出后却发生了错误。 4.不得不提其中出现的另一种问题，我在编程序的时候喜欢添加一些输出汉字来提示自己到的阶段，然而noj并不能很智能的处理多输出的格式问题。虽然有画蛇添足的嫌疑，但是希望以后的NOJ系统更智能化。 5.本次程序采用了数据抽象的程序设计方法，运用线性表的知识处理三元组数组类型的问题，并且将程序分为两部分，一部分为矩阵转置算法，另一部分为主函数，分而治之，容易调试，自己以后的编程中，会更偏向于这种分块的编程模式。五、用户操作说明 见三详细设计说明黑体字部分。 文字描述： 需要输入的数据有：矩阵的行与列 4 4 输入的矩阵： 1 1 1 2 1 2 3 2 3 结束的标志 0 0 0六、运行结果 如图：七、附录 源程序。#include#define MAX 10000typedef struct int i,j,v;NODE;typedef struct int m,n,t; NODE dataMAX+1;MT;MT tran( MT a) int p,q,col; MT b; b.m=a.n; b.n=a.m; b.t=a.t; if(a.t!=0) q=0; for(col=0;cola.n;col+) for(p=0;pa.t;p+) if(a.datap.j=col) b.dataq.i= a.datap.j; b.dataq.j= a.datap.i; b.dataq.v= a.datap.v; q+; return (b);int main() MT a,b; int i,r,c,t,n; scanf(%d,&r); scanf(%d,&c); t=0; a.m=r; a.n=c; for(i=0;i+) scanf(%d %d %d,&r,&c,&n); a.datai.i=r; a.datai.j=c; a.datai.v=n; t+; if(a.datai.i=0&a.datai.j=0&a.datai.v=0)break; a.t=t; b=tra