帮帮忙!!!如何用C语言实现稀疏矩阵的转置?

Question

如何用C语言实现稀疏矩阵的转置?请尽快回复,谢谢![]

Answer 1

（C语言）稀疏矩阵的快速转置算法/*矩阵的快速转置*/
#include <stdio.h>
#include <stdlib.h>
#include <process.h>
#define MAXSIZE 200 /*矩阵中最大非零元的个数*/
typedef struct triple
{
int i; /*行标,本程序中从1开始的*/
int j; /*列标，本程序中从1开始的*/
int e; /*非零元*/
}Triple; /*三元组定义*/
typedef struct tabletype
{
int mu; /*矩阵的行数*/
int nu; /*列数*/
int tu; /*非零元个数*/
Triple data[MAXSIZE]; /*非零元的三元组表,本程序中是从data[1]开始使用的*/
}Tabletype; /*三元组线性表*/
/*以下为函数声明，注意和书本上的参数类型不同，我用的形参全为指针*/
void CreatSMatrix(Tabletype *); /*生成矩阵*/
void DestroySMatrix(Tabletype *); /*销毁矩阵*/
void out_matrix(Tabletype *); /*打印 矩阵*/
int FastTransposeSMatrix(Tabletype *,Tabletype *); /*快速转置算法*/
int main( void ) /*主函数*/
{
char ch;
Tabletype a = {0,0,0,{0,0,0}}; /*初始化为0，便于输入数据时的无效检测*/
Tabletype b; /*声明矩阵b*/
while(1)
{
printf(" @@@@@@@@@@@@@@本程序的功能是实现稀疏矩阵的快速转置@@@@@@@@@@@@@@@\n");
printf(" @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");

CreatSMatrix(&a);
printf("The source Matrix:\n");
out_matrix(&a);

if(FastTransposeSMatrix(&a,&b)) /*若a不为零矩阵则转置a，存入b中*/
{ printf("After TransposeSMatrix: \n");
out_matrix(&b);
}
else
{
printf("The matrix is zeros:\n");
out_matrix(&a);
}
/*以下为程序控制*/
printf("Input 'q' to quit and 'c' run again:");
do{
if((ch = getchar()) == 'q' || ch == 'Q')
{
DestroySMatrix(&a);
DestroySMatrix(&b);
exit(0);
}
}while((ch!='C') && (ch!='c'));
system("cls");
}
return 1;
}

void CreatSMatrix(Tabletype *a)
{
int i;
printf("请输入矩阵的行数、列数和非零元个数，用空格间隔:");
scanf("%d%d%d",&(a->mu),&(a->nu),&(a->tu));
for(i=1;i<= a->tu;)
{
printf("请输入矩阵中第%d个非零元（按行标、列标、值的顺序，空格间隔）:",i);
scanf("%d%d%d",&(a->data[i].i),&(a->data[i].j),&(a->data[i].e));
if(a->data[i].i < 1 || a->data[i].i > a->mu || a->data[i].j < 1 || a->data[i].j > a->nu) /*下标越界*/
{
printf("注意：下标越界输入数据无效!\n请重新输入:行标范围：1--%d,列标范围1--%d!!!\n",a->mu,a->nu);
continue;
}
if( ((a->data[i].i) < (a->data[i-1].i)) ||
(((a->data[i].i) == (a->data[i-1].i)) && ((a->data[i].j) <= (a->data[i-1].j)))) /*非按行顺序输入*/
{
printf("注意：输入数据无效!\n请按照按行存储的顺序输入数据!!!\n");
continue;
}
i++;
}
}
void DestroySMatrix(Tabletype *a)
{ /* 销毁稀疏矩阵a*/
(*a).mu=0;
(*a).nu=0;
(*a).tu=0;
}
void out_matrix(Tabletype *a) /* 打印矩阵*/
{
int i,j,k = 1;
for(i = 1 ;i <= a->mu; i++)
{
for(j = 1; j<= a->nu; j++)
{ /*判断是否为非零元*/
if((a->data[k].i == i)&&(a->data[k].j == j))
{
printf("%4d",a->data[k].e);
k++;
}
else
printf("%4d",0);
}
printf("\n");
}
}
int FastTransposeSMatrix(Tabletype *a,Tabletype *b)
{
int p,q,col;
int *num;
int *cpot;
b->mu = a->nu; /*原矩阵的行数为新矩阵的列数，原列数为新行数，非零元个数不变*/
b->nu = a->mu;
b->tu = a->tu;
num=(int *)malloc((b->nu+1)*sizeof(int)); /* 生成两个辅助数组*/
cpot=(int *)malloc((b->nu+1)*sizeof(int));
if(b->tu) /*若a不为零矩阵*/
{
for(col = 0;col <a->nu;col++) /*初始化矩阵a的每列中非零元的个数均为0*/
num[col] = 0;
for(col = 0; col <=a->tu ; col++)/*统计每列中非零元的个数*/
num[a->data[col].j]++;
cpot[1] = 1; /*确定每列中第一个非零元的位置*/
for(col = 2;col <= a->nu; col++)
cpot[col] = num[col-1]+cpot[col-1];

for(p = 1; p <= a->tu; p++) /*p为a-data的下标*/
{
col = a->data[p].j; /*交换元素*/
q = cpot[col];
b->data[q].i = a->data[p].j;
b->data[q].j = a->data[p].i;
b->data[q].e = a->data[p].e;
q++;
cpot[col]++;
}
free(num); /*释放两个辅助数组*/
free(cpot);
return 1; /*转置成功*/
}
else /*a为零矩阵*/
return 0;