题目：假设稀疏矩阵A采用三元组表表示，编写程序实现该矩阵的快速转置 要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组
表，由程序将其转换成矩阵形式后输出。
二、概要设计
⒈ 为实现上述算法，需要线性表的抽象数据类型：
ADT SparseMatrix {
数据对象：D={aij:|aij∈TermSet,i=1„m,m≥0，j=1„n,n≥0
m和n分别成为矩阵的行数和列数 }
数据关系：R={Row，Col}
Row ={|1≤i≤m，1≤j≤n-1 }
Col ={|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。
}ADT SparseMatrix
2. 本程序有三个模块：
⑴ 主程序模块
main(){
初始化；
{
接受命令；
显示结果；
｝
｝
⑵ 矩阵压缩存储单元模块：实现链表抽象数据类型操作，即函数的定义模块；
三、详细设计
⒈元素类型，结点类型
typedef struct {
int i,j;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];
int mu,nu,tu;
} Tsmatrix;
2.对抽象数据类型中的部分基本操作的伪码算法如下：
Tsmatrix * creatarray(Tsmatrix *M)
{ int m,n,p=1;
int c;
printf("please input the array A:\n");
for(m=1;m
for(n=1;n
{ scanf("%d",&c);
if(c!=0)
{ M->data[p].e=c;
M->data[p].i=m;
M->data[p].j=n;
p++;
}
}
M->tu=p; M->mu=a; M->nu=b;
printf("yuan lai san yuan zu de biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);
printf("\n");
return M;
}
/*三元组快速转置*/
Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T)
{ int p,col,q,t,m;
int num[100];
int cpot[100];
T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;
if(T->tu!=0)
{
for(col=1;colnu;col++) num[col]=0;
for(t=1;ttu;t++) ++num[M->data[t].j];
cpot[1]=1;
for(col=2;colnu;col++) cpot[col]=cpot[col-1]+num[col-1];
for(p=1;ptu;++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];
}
}
printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);
printf("\n");
return T;
}
/*输出三元组函数*/
void print(Tsmatrix *T,int x,int y)
{ int m,n,p=1;
int d;
for(m=1;m
{ printf("\n");
for(n=1;n
{ if(T->data[p].i==m&&T->data[p].j==n)
{ d=T->data[p].e;
p++;
}
else d=0;
printf("%6d",d);
}
}
}
}3.主函数和其他函数的伪码算法
void main()
{ Tsmatrix *M,*T;
M=(Tsmatrix *)malloc(sizeof(Tsmatrix));
T=(Tsmatrix *)malloc(sizeof(Tsmatrix));
printf("please input array's row and col:\n");
scanf("%d%d",&a,&b); /*输入行列数*/
M=creatarray(M); /*创建稀疏矩阵*/
printf("you had creat the array:\n");
print(M,a,b); /*输出创建好的三元组*/
T=fasttrans(M,T); /*将三元组转置*/
printf("the trans array is:\n");
print(T,b,a);
getch();
}
4 函数调用关系
四、调试分析
⒈在定义变量的时候，我运用动了整型的全局变量a和b。初步编程完后，编译出现如下的
警告提示：可能在“a”定义以前使用了它在creatarray函数中。通过检查发现我在creatarray函数中又定义了一个局部变量a，导致有如上的警告提示。最后将局部变量a改为c就可以了。
⒉ 编译时的错误一大堆，但是致命的是在关键的函数快速转置有错误，在运行的结果中不
是自己想要的结果。在一一排除的情况下，数组转换三元组是正确的只是fasttrans函数算法有错，如出现下图的错误：
最后发现原来的该函数的代码的算法少了几条语句。
3．因为要将稀疏矩阵M和稀疏矩阵T分别调用函数print，所以设计print函数的时候发现形参不仅仅要稀疏矩阵而且还应该有盖稀疏矩阵的行列数才能正确的输出稀疏矩阵，最后定义为 print(Tsmatrix *T,int x,int y)才实现了输出。
4. 算法的时空分析
各操作的算法时间复杂度比较合理
Creatarray，print为O(a*b) 其中a和b分别表示稀疏矩阵的行列数
fasttrans为O(tu) 其中tu表示稀疏矩阵中的非零个数
5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使
调试也较顺利，各模块有较好的可重用性。
五、用户手册
⒈ 本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为
Exp2Prb5.c；
⒉ 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS
环境中，用户根据需求键入相应的数据，可以看到相应的结果。
六、测试结果
所以在TC2.0中运行得到的结果如下图所示：
（1）我输入的稀疏矩阵为：
（2）回车显示的结果是：
七、附录：源程序
#include
#define MAXSIZE 100
typedef struct {
int i,j;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];
int mu,nu,tu;
} Tsmatrix;
int a,b; /*定义全局变量数组的行数a和列数b*/
/*用数组创建三元组*/
Tsmatrix * creatarray(Tsmatrix *M)
{ int m,n,p=1;
int c;
printf("please input the array A:\n");
for(m=1;m
for(n=1;n
{ scanf("%d",&c);
if(c!=0)
{ M->data[p].e=c;
M->data[p].i=m;
M->data[p].j=n;
p++;
}
}
M->tu=p; M->mu=a; M->nu=b;
printf("yuan lai san yuan zu de biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e); printf("\n");
return M;
}
/*三元组快速转置*/
Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T)
{ int p,col,q,t,m;
int num[100];
int cpot[100];
T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;
if(T->tu!=0)
{
for(col=1;colnu;col++) num[col]=0;
for(t=1;ttu;t++) ++num[M->data[t].j];
cpot[1]=1;
for(col=2;colnu;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;ptu;++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];
}
}
printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n"); for(m=1;mtu;m++)
printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e); printf("\n");
return T;
}
/*输出三元组函数*/
void print(Tsmatrix *T,int x,int y)
{ int m,n,p=1;
int d;
for(m=1;m
{ printf("\n");
for(n=1;n
{ if(T->data[p].i==m&&T->data[p].j==n) { d=T->data[p].e;
p++;
}
else d=0;
printf("%6d",d);
}
}
}
void main()
{ Tsmatrix *M,*T;
M=(Tsmatrix *)malloc(sizeof(Tsmatrix)); T=(Tsmatrix *)malloc(sizeof(Tsmatrix));
printf("please input array's row and col:\n"); scanf("%d%d",&a,&b); /*输入行列数*/ M=creatarray(M);
printf("you had creat the array:\n");
print(M,a,b);
T=fasttrans(M,T);
printf("the trans array is:\n");
print(T,b,a);
getch();
}
题目：假设稀疏矩阵A采用三元组表表示，编写程序实现该矩阵的快速转置 要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组
表，由程序将其转换成矩阵形式后输出。
二、概要设计
⒈ 为实现上述算法，需要线性表的抽象数据类型：
ADT SparseMatrix {
数据对象：D={aij:|aij∈TermSet,i=1„m,m≥0，j=1„n,n≥0
m和n分别成为矩阵的行数和列数 }
数据关系：R={Row，Col}
Row ={|1≤i≤m，1≤j≤n-1 }
Col ={|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。
}ADT SparseMatrix
2. 本程序有三个模块：
⑴ 主程序模块
main(){
初始化；
{
接受命令；
显示结果；
｝
｝
⑵ 矩阵压缩存储单元模块：实现链表抽象数据类型操作，即函数的定义模块；
三、详细设计
⒈元素类型，结点类型
typedef struct {
int i,j;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];
int mu,nu,tu;
} Tsmatrix;
2.对抽象数据类型中的部分基本操作的伪码算法如下：
Tsmatrix * creatarray(Tsmatrix *M)
{ int m,n,p=1;
int c;
printf("please input the array A:\n");
for(m=1;m
for(n=1;n
{ scanf("%d",&c);
if(c!=0)
{ M->data[p].e=c;
M->data[p].i=m;
M->data[p].j=n;
p++;
}
}
M->tu=p; M->mu=a; M->nu=b;
printf("yuan lai san yuan zu de biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);
printf("\n");
return M;
}
/*三元组快速转置*/
Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T)
{ int p,col,q,t,m;
int num[100];
int cpot[100];
T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;
if(T->tu!=0)
{
for(col=1;colnu;col++) num[col]=0;
for(t=1;ttu;t++) ++num[M->data[t].j];
cpot[1]=1;
for(col=2;colnu;col++) cpot[col]=cpot[col-1]+num[col-1];
for(p=1;ptu;++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];
}
}
printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);
printf("\n");
return T;
}
/*输出三元组函数*/
void print(Tsmatrix *T,int x,int y)
{ int m,n,p=1;
int d;
for(m=1;m
{ printf("\n");
for(n=1;n
{ if(T->data[p].i==m&&T->data[p].j==n)
{ d=T->data[p].e;
p++;
}
else d=0;
printf("%6d",d);
}
}
}
}3.主函数和其他函数的伪码算法
void main()
{ Tsmatrix *M,*T;
M=(Tsmatrix *)malloc(sizeof(Tsmatrix));
T=(Tsmatrix *)malloc(sizeof(Tsmatrix));
printf("please input array's row and col:\n");
scanf("%d%d",&a,&b); /*输入行列数*/
M=creatarray(M); /*创建稀疏矩阵*/
printf("you had creat the array:\n");
print(M,a,b); /*输出创建好的三元组*/
T=fasttrans(M,T); /*将三元组转置*/
printf("the trans array is:\n");
print(T,b,a);
getch();
}
4 函数调用关系
四、调试分析
⒈在定义变量的时候，我运用动了整型的全局变量a和b。初步编程完后，编译出现如下的
警告提示：可能在“a”定义以前使用了它在creatarray函数中。通过检查发现我在creatarray函数中又定义了一个局部变量a，导致有如上的警告提示。最后将局部变量a改为c就可以了。
⒉ 编译时的错误一大堆，但是致命的是在关键的函数快速转置有错误，在运行的结果中不
是自己想要的结果。在一一排除的情况下，数组转换三元组是正确的只是fasttrans函数算法有错，如出现下图的错误：
最后发现原来的该函数的代码的算法少了几条语句。
3．因为要将稀疏矩阵M和稀疏矩阵T分别调用函数print，所以设计print函数的时候发现形参不仅仅要稀疏矩阵而且还应该有盖稀疏矩阵的行列数才能正确的输出稀疏矩阵，最后定义为 print(Tsmatrix *T,int x,int y)才实现了输出。
4. 算法的时空分析
各操作的算法时间复杂度比较合理
Creatarray，print为O(a*b) 其中a和b分别表示稀疏矩阵的行列数
fasttrans为O(tu) 其中tu表示稀疏矩阵中的非零个数
5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使
调试也较顺利，各模块有较好的可重用性。
五、用户手册
⒈ 本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为
Exp2Prb5.c；
⒉ 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS
环境中，用户根据需求键入相应的数据，可以看到相应的结果。
六、测试结果
所以在TC2.0中运行得到的结果如下图所示：
（1）我输入的稀疏矩阵为：
（2）回车显示的结果是：
七、附录：源程序
#include
#define MAXSIZE 100
typedef struct {
int i,j;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];
int mu,nu,tu;
} Tsmatrix;
int a,b; /*定义全局变量数组的行数a和列数b*/
/*用数组创建三元组*/
Tsmatrix * creatarray(Tsmatrix *M)
{ int m,n,p=1;
int c;
printf("please input the array A:\n");
for(m=1;m
for(n=1;n
{ scanf("%d",&c);
if(c!=0)
{ M->data[p].e=c;
M->data[p].i=m;
M->data[p].j=n;
p++;
}
}
M->tu=p; M->mu=a; M->nu=b;
printf("yuan lai san yuan zu de biao shi wei :\n\n");
for(m=1;mtu;m++)
printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e); printf("\n");
return M;
}
/*三元组快速转置*/
Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T)
{ int p,col,q,t,m;
int num[100];
int cpot[100];
T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;
if(T->tu!=0)
{
for(col=1;colnu;col++) num[col]=0;
for(t=1;ttu;t++) ++num[M->data[t].j];
cpot[1]=1;
for(col=2;colnu;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;ptu;++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];
}
}
printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n"); for(m=1;mtu;m++)
printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e); printf("\n");
return T;
}
/*输出三元组函数*/
void print(Tsmatrix *T,int x,int y)
{ int m,n,p=1;
int d;
for(m=1;m
{ printf("\n");
for(n=1;n
{ if(T->data[p].i==m&&T->data[p].j==n) { d=T->data[p].e;
p++;
}
else d=0;
printf("%6d",d);
}
}
}
void main()
{ Tsmatrix *M,*T;
M=(Tsmatrix *)malloc(sizeof(Tsmatrix)); T=(Tsmatrix *)malloc(sizeof(Tsmatrix));
printf("please input array's row and col:\n"); scanf("%d%d",&a,&b); /*输入行列数*/ M=creatarray(M);
printf("you had creat the array:\n");
print(M,a,b);
T=fasttrans(M,T);
printf("the trans array is:\n");
print(T,b,a);
getch();
}