目录
稀疏矩阵的定义
稀疏矩阵的转置
代码实现
运行结果
稀疏矩阵的定义
假设在 m * n 的矩阵中，有 t 个元素不为零，且 t<<m*n，则称此矩阵为稀疏矩阵。按照常规的存储方法，稀疏矩阵很浪费内存空间，所以采取只存储非零元素的方式。但对于这类矩阵，通常零元素分布没有规律，为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列。对于稀疏矩阵，压缩存储的方式有很多种，如三元组顺序表，十字链表等。
稀疏矩阵的转置
【问题描述】
实现稀疏矩阵的三元组表存储和转置运算。
【输入形式】
输入一个整型的6阶稀疏矩阵。
【输出形式】
输出稀疏矩阵的三元组表形式，输出转置后的三元组表形式。
【样例输入】
10 0 0 0 0 0
0 -20 0 0 40 0
0 0 30 0 0 0
0 0 0 0 0 0
0 0 0 50 0 0
0 0 -60 0 0 70
【样例输出】
M
6 6 7
0 0 10
1 1 -20
1 4 40
2 2 30
4 3 50
5 2 -60
5 5 70
T
6 6 7
0 0 10
1 1 -20
2 2 30
2 5 -60
3 4 50
4 1 40
5 5 70
【样例说明】
M表示转置前矩阵，T表示转置后矩阵。6 6 7表示稀疏矩阵的mu,nu,tu，后面若干行为非零元素。（同行数据之间以空格分隔）
【评分标准】
采用三元组表结构存储矩阵。转置算法使用一般转置或快速转置算法均可。
代码实现
算法实现基本步骤如下：
（1）M的行、列转换为T的列、行。
（2）按照M的列序来转置，找到M的每一列的非零元素，行列交换后顺序存储到T的三元组种。
#include<stdio.h>
#define MAXSIZE 12500
typedef int ElemType;
typedef struct
{int i,j;ElemType e;
}Triple;
typedef struct
{Triple data[MAXSIZE+1];int mu,nu,tu;}TSMatrix;
void InitSMatrix(TSMatrix *t)
{t->mu = 6;t->nu = 6;t->tu = 0;
}
void CreatSMatrix(TSMatrix *t)
{int x,q=1;int a = 0 , b = -1;while(a < 6){scanf("%d",&x);b ++ ;if(x != 0) {t->tu ++;t->data[q].i = a;t->data[q].j = b;t->data[q].e = x;q ++ ;}if(b == 5){printf("\n");a ++;b = -1; }}
}
void TransposeSMatrix(TSMatrix *M, TSMatrix *T)
{int p,q,col; T->mu = M->nu;T->nu = M->mu;T->tu = M->tu; if(T->tu){q=1;for(col=0;col<=M->nu-1;++col){ for(p=1;p<=M->tu;++p) if(M->data[p].j==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;++q;}}}
}
void Print(TSMatrix *t)
{printf("%d %d %d\n",t->mu,t->nu,t->tu);int q;for(q=1 ; q <= t->tu ; q++){printf("%d %d %d\n",t->data[q].i,t->data[q].j,t->data[q].e);}
}int main()
{TSMatrix M,T;InitSMatrix(&M);CreatSMatrix(&M);TransposeSMatrix(&M,&T); printf("M\n");Print(&M);printf("T\n");Print(&T);return 0;
}
运行结果
