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

一题目:稀疏矩阵转置

班级:姓名:学号:完成日期:15.11.13

一、题目要求:
输出稀疏矩阵的转置矩阵。（行列均不大于20）要求为输入两个正整数n和m,为矩阵的行和列，然后输入矩阵三元组，（0,0,0）表示结束输入。

二、概要设计
1.需要的数据结构为：线性表。
2.需要线性表的抽象数据类型：
ADTSparseMatrix{
数据对象：D={aij:|aij∈TermSet,i=1…m,m≥0，j=1…n,n≥0
m和n分别成为矩阵的行数和列数}
数据关系：R={Row，Col}
Row={<ai，j,ai，j+1>|1≤i≤m，1≤j≤n-1}
Col={<ai，j,ai+1，j>|1≤i≤m-1，1≤j≤n}
基本操作：
CreateSMtrix(&M)
操作结果：创建稀疏矩阵M。DestroySMaix(&M)
初始条件：稀疏矩阵M已存在。
操作结果：销毁稀疏矩阵M。
PrintSMatrix(L)
初始条件：稀疏矩阵M已经存在。
操作结果：输出稀疏矩阵M。CopySMatrix（M，&T）
初始条件：稀疏矩阵M已经存在。操作结果：由稀疏矩阵M复制得到T。
TransposeSMatrix(M，&T)
初始条件：稀疏矩阵M已经存在。
操作结果：求稀疏矩阵M的转转矩阵T。
}ADTSparseMatrix
三、详细设计
1.元素类型，结点类型
typedefstruct{
inti,j,v;
}NODE;
typedefstruct{
intm,n,t;
NODEdata[MAX+1];
}MT;
2.对抽象数据类型中的部分基本操作的伪码算法如下：
/*三元组的转置*/
MTtran(MTa)
{//采用三元组存储表示，求稀疏矩阵a的转置矩阵b
intp,q,col;
MTb;
b.m=a.n;
b.n=a.m;
b.t=a.t;
if(a.t!=0)
{
q=0;
for(col=0;col<a.n;col++)//先列
for(p=0;p<a.t;p++)
if(a.data[p].j==col)
{
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
q++;
}
}
return(b);
}
/*主函数（包含输入输出函数）*/
intmain()
{MTa,b;
inti,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.data[i].i=r;
a.data[i].j=c;
a.data[i].v=n;
t++;
if(a.data[i].i==0&&a.data[i].j==0&&a.data[i].v==0)break;//输入（0,0,0）结束
}

a.t=t;
b=tran(a);

for(i=0;i<t;i++)//输出转置后的矩阵
{if(b.data[i].i==0&&b.data[i].j==0&&b.data[i].v==0)continue;
else
printf("%d%d%d\n",b.data[i].i,b.data[i].j,b.data[i].v);
}
return0;
}
3.函数调用关系：
Main
↓
MTtran
四、调试分析与心得体会
1.一开始我没有定义非零元素个数最大值，编译时出现error提示，如:\编程\sdfasd\main.cpp|10|error:'MAX'wasnotdeclaredinthisscope|等，经检查后发现错误，再开头加声明#deefineMAXSIZE1000,最终解决错误。
2．编译的时候错误一大堆,不过最关键的是转置函数的错误，再运行的结果中出现不了想要的结果，经过一一排除后，才发现只是一个赋值语句的顺序颠倒而已。编程就是这样，牵一发而动全身，一个字母就有可能导致全面崩盘。
3.特殊点的错误。一开始的程序中，对于以（0，0，t）类型的三元组不能有效识别并排序。例子如下图：

最后才发现输出的部分并不是那么合理，因为我把结束标志当成一个矩阵元素对待，同样记录其中，固然再编写算法的时候取了巧，但是输出后却发生了错误。
4.不得不提其中出现的另一种问题，我在编程序的时候喜欢添加一些输出汉字来提示自己到的阶段，然而noj并不能很智能的处理多输出的格式问题。虽然有画蛇添足的嫌疑，但是希望以后的NOJ系统更智能化。
5.本次程序采用了数据抽象的程序设计方法，运用线性表的知识处理三元组数组类型的问题，并且将程序