稀疏矩阵的压缩存储
目录
稀疏矩阵的定义
稀疏矩阵的转置
代码实现
运行结果
稀疏矩阵的定义
假设在 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;
}
运行结果
