数据结构稀疏矩阵的快速转置算法实现
数据结构稀疏矩阵的快速转置算法实现
代码如下：
#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");
CreatSMatrix(&a);//生成矩阵
printf("源矩阵:\n");
out_matrix(&a);//打印 矩阵
if (FastTransposeSMatrix(&a, &b)) /*若a不为零矩阵则转置a，存入b中*/
{
printf("在转置矩阵之后: \n");
out_matrix(&b);
}
else
{
printf("矩阵为零:\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;
}