数组和广义表 实验4

数组和广义表
班级：软件102 姓名： 学号： 完成日期：
2011.11.25
题目：数组转置
题目描述：存在稀疏矩阵A，编写程序将A转置为B。
基本要求：用三元组表示稀疏矩阵，应用算法5.2完成转置
一、 需求分析
功能：求一个用三元组表示的矩阵 的转置矩阵
输入：矩阵的行数、列数、非零元的个数、非零元对应的行下标和列下标
输出：转置后的矩阵

二、概要设计
有题目要求知，需要建立一个三元组的结构体，和转置的函数；
由此可以得到需要以下几个模块
模块：
1. 三元组表示的结构体
2. 快速转置的函数
大概算法：
模块2： 先求出每一列所含非零元的个数，然后找出每一列第一个
存储的位置依次进行转置
三、详细设计
1． 从键盘输入一个稀疏矩阵
printf("请输入要转置行列式的行和列的值：");
scanf("%d%d",&x,&y);
printf("请输入此稀疏矩阵的元素：\n");
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
scanf("%d",&A[i][j]);
2． 把输入的一个一维矩阵转换为一个三元组
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(A[i][j]!=0)
{
B.data[k].row=i;
B.data[k].col=j;
B.data[k].e=A[i][j];
k++;
}
B.m=x; //三元表的行数
B.n=y; //三元表的列数
B.len=k-1;
3．三元组的转置
void TransposeTSMatrix(TSMatrix *A,TSMatrix *B)
{
int i,j,k;
B->m=A->n;
B->n=A->m;
B->len=A->len;
if(B->len>0)
{
j=1;
for(k=1;k<=A->n;k++)
for(i=1;i<=A->len;i++)
if(A->data[i].col==k)
{
B->data[j].row=A->data[i].col;
B->data[j].col=A->data[i].row;
B->data[j].e=A->data[i].e;
j++;
}
}
}
4.三元组表的输出
for(i=1;i<=C.m;i++){
for(j=1;j<=C.n;j++){
if((C.data[p].row==i)&&(C.data[p].col==j)){
printf("%d ",C.data[p].e);
p++;
}
else printf("0 ");
}
printf("\n");
}

四、调试分析：
调试结果，检查出程序的错误地方。并且对程序不足的地方进行
一步步修改，因为哪怕程序是正确的，也可能存在太多问题。一
定要通过调试解决。

五、测试结果
1.第一组测试数据：

结果正确。
2.第二组测试数据：
结果正确
六、程序清单
#include
#define MAXSIZE 1000
typedef struct
{
int row,col;
int e;
}Triple;
typedef struct
{
int mu,nu,len;
Triple data[MAXSIZE+1];
}TSMatrix;
void TSTSMatrix(TSMatrix *A,TSMatrix *B)
{
int i,j,k;
B->mu=A->nu;
B->nu=A->mu;
B->len=A->len;
if(B->len>0)
{
j=1;
for(k=1;k<=A->nu;k++)
for(i=1;i<=A->len;i++)
if(A->data[i].col==k)
{
B->data[j].row=A->data[i].col;
B->data[j].col=A->data[i].row;
B->data[j].e=A->data[i].e;
j++;
}
}
}
int main()
{
int x,y,i,j;
int k=1,p=1;
TSMatrix B,C;
int A[100][100];
printf("请输入要转置行列式的行和列的值：");
scanf("%d%d",&x,&y);
printf("请输入此稀疏矩阵的元素：\n");
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
scanf("%d",&A[i][j]);
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(A[i][j]!=0)
{
B.data[k].row=i;
B.data[k].col=j;
B.data[k].e=A[i][j];
k++;
}
B.mu=x;
B.nu=y;
B.len=k-1;
TSTSMatrix(&B,&C);
printf("转置后的矩阵为：\n");
for(i=1;i<=C.mu;i++){
for(j=1;j<=C.nu;j++){
if((C.data[p].row==i)&&(C.data[p].col==j)){
printf("%d ",C.data[p].e);
p++;
}
else printf("0 ");
}
printf("\n");
}
return 0;
}