# 三元组存储稀疏矩阵实现逆置
## 一、实验说明
### 1.1 稀疏矩阵压缩存储
压缩存储值存储极少数的有效数据。使用{row，col，value}三元组(Trituple)存储 每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。
### 1.2 矩阵逆置
将原矩阵的行、列对换，也就是将[i][j]和[j][i]位置上的数据对换。
## 二、实验背景
### 2.1 三元组是什么？
三元组是用来存储稀疏矩阵的一种压缩方式。
### 2.2 那么为什么会用到三元组？
二维数组表示的稀疏矩阵有着大量0存在，而这些0造成了大量的内存浪费，是我们的忽略对象（实际应用加密解密中可以使用其他我们用不到的数来进行混淆）。
**稀疏矩阵**
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。
**特性**
- 稀疏矩阵其非零元素的个数远远小于零元素的个数，而且这些非零元素的分布也没有规律
- 稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n\*m的稀疏矩阵A中有t个非零元素，则稀疏因子δδ的计算公式如下：δ=tn∗mδ=tn∗m(当这个值小于等于0.05时，可以认为是稀疏矩阵)
**矩阵压缩**
存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。
对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。
## 三、实验代码
```c
# include<stdio.h>
# include<stdarg.h>
# include<stdlib.h>
# include<string.h>
# include<malloc.h>
# define MAXSIZE 12500//假设非零元个数的最大值为12500
# define MAX_ARRAY_DIM 8
# define ElemType int
# define OK 1
typedef struct{
ElemType *base;//数组元素基址 ，由InitArray分配
int dim=2;//数组维数为二
int *bounds;//数组维界基址，由InitArray分配
int *constants; //数组映像函数常量基址，由InitArray分配
}Array;
typedef struct{
int i,j;//该非零元的行下标和列下标
ElemType e;
}Triple;//三元组类型
typedef struct{
Triple data[MAXSIZE+1];//非零元三元组表，data[0]未用
int mu,nu,tu;
}TSMatrix;//稀疏矩阵类型
int b[10][10]={0};
int a[10][10]={
0,0,0,0,0,0,7,0,0,8,
5,0,0,0,0,0,0,0,0,3,
2,0,1,0,0,0,0,0,0,0,
0,0,4,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,6,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
};
int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{//快速转置
int col,num[100],cpot[100],p,q,t,i,j,m,n;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(a[i][j]!=0){
M.data[M.tu].i=i;
M.data[M.tu].j=j;
M.data[M.tu].e=a[i][j];
M.tu++;
}
}
}
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;//建立同样大小的矩阵
if(T.tu){
for(col=0;col<=M.nu;++col)
num[col]=0;//使每一列的非零元个数清空为零相当于初始化
for(t=0;t<M.tu;++t)
++num[M.data[t].j];
//求M中每一列含非零元个数
cpot[0]=0;
//求第col列中第一个非零元在b.bata中的序号
for(col=1;col<M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=0;p<M.tu;++p){
col=M.data[p].j;
q=cpot[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;
cpot[col]++;
}
}
for(t=0;t<T.tu;t++){
m=T.data[t].i;
n=T.data[t].j;
b[m][n]=T.data[t].e;
//输出非零值在原矩阵中的位置及数值
}
for(i=0;i<T.mu;i++){
for(j=0;j<T.nu;j++)
printf("%d\ ",b[i][j]);
printf("\n");
}
return 0;
}
int main()
{
printf("矩阵转置前：<0,6,7>,<0,9,8>,<1,0,5>,<1,9,3>,<2,0,2>,<2,2,1>,<3,2,4>,<8,1,6>\n");
printf("矩阵转置后：<0,1,5>,<0,2,2>,<1,8,6>,<2,2,1>,<2,3,4>,<6,0,7>,<9,0,8>,<9,1,3>\n");
TSMatrix M,T;
int x,y;
M.mu=10;
M.nu=10;
M.tu=0;
printf("转置前：\n");
for(x=0;x<M.mu;x++){
for(y=0;y<M.nu;y++){
printf("%d\ ",a[x][y]);
}
printf("\n");
}
printf("转置后：\n");
FastTransposeSMatrix(M,T);
return 0;
}
```
