三元组存储稀疏矩阵实现逆置

cloud

发布日期: 2020-12-18 09:43:40 浏览量: 262
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验说明

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时,可以认为是稀疏矩阵)

矩阵压缩

存储矩阵的一般方法是采用二维数组,其优点是可以随机地访问每一个元素,因而能够较容易地实现矩阵的各种运算,如转置运算、加法运算、乘法运算等。

对于稀疏矩阵来说,采用二维数组的存储方法既浪费大量的存储单元用来存放零元素,又要在运算中花费大量的时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。

三、实验代码

  1. #include<stdio.h>
  2. #include<stdarg.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. #include<malloc.h>
  6. #define MAXSIZE 12500//假设非零元个数的最大值为12500
  7. #define MAX_ARRAY_DIM 8
  8. #define ElemType int
  9. #define OK 1
  10. typedef struct{
  11. ElemType *base;//数组元素基址 ,由InitArray分配
  12. int dim=2;//数组维数为二
  13. int *bounds;//数组维界基址,由InitArray分配
  14. int *constants; //数组映像函数常量基址,由InitArray分配
  15. }Array;
  16. typedef struct{
  17. int i,j;//该非零元的行下标和列下标
  18. ElemType e;
  19. }Triple;//三元组类型
  20. typedef struct{
  21. Triple data[MAXSIZE+1];//非零元三元组表,data[0]未用
  22. int mu,nu,tu;
  23. }TSMatrix;//稀疏矩阵类型
  24. int b[10][10]={0};
  25. int a[10][10]={
  26. 0,0,0,0,0,0,7,0,0,8,
  27. 5,0,0,0,0,0,0,0,0,3,
  28. 2,0,1,0,0,0,0,0,0,0,
  29. 0,0,4,0,0,0,0,0,0,0,
  30. 0,0,0,0,0,0,0,0,0,0,
  31. 0,0,0,0,0,0,0,0,0,0,
  32. 0,0,0,0,0,0,0,0,0,0,
  33. 0,0,0,0,0,0,0,0,0,0,
  34. 0,6,0,0,0,0,0,0,0,0,
  35. 0,0,0,0,0,0,0,0,0,0,
  36. };
  37. int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
  38. {//快速转置
  39. int col,num[100],cpot[100],p,q,t,i,j,m,n;
  40. for(i=0;i<10;i++){
  41. for(j=0;j<10;j++){
  42. if(a[i][j]!=0){
  43. M.data[M.tu].i=i;
  44. M.data[M.tu].j=j;
  45. M.data[M.tu].e=a[i][j];
  46. M.tu++;
  47. }
  48. }
  49. }
  50. T.mu=M.nu;
  51. T.nu=M.mu;
  52. T.tu=M.tu;//建立同样大小的矩阵
  53. if(T.tu){
  54. for(col=0;col<=M.nu;++col)
  55. num[col]=0;//使每一列的非零元个数清空为零相当于初始化
  56. for(t=0;t<M.tu;++t)
  57. ++num[M.data[t].j];
  58. //求M中每一列含非零元个数
  59. cpot[0]=0;
  60. //求第col列中第一个非零元在b.bata中的序号
  61. for(col=1;col<M.nu;++col)
  62. cpot[col]=cpot[col-1]+num[col-1];
  63. for(p=0;p<M.tu;++p){
  64. col=M.data[p].j;
  65. q=cpot[col];
  66. T.data[q].i=M.data[p].j;
  67. T.data[q].j=M.data[p].i;
  68. T.data[q].e=M.data[p].e;
  69. cpot[col]++;
  70. }
  71. }
  72. for(t=0;t<T.tu;t++){
  73. m=T.data[t].i;
  74. n=T.data[t].j;
  75. b[m][n]=T.data[t].e;
  76. //输出非零值在原矩阵中的位置及数值
  77. }
  78. for(i=0;i<T.mu;i++){
  79. for(j=0;j<T.nu;j++)
  80. printf("%d\ ",b[i][j]);
  81. printf("\n");
  82. }
  83. return 0;
  84. }
  85. int main()
  86. {
  87. 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");
  88. 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");
  89. TSMatrix M,T;
  90. int x,y;
  91. M.mu=10;
  92. M.nu=10;
  93. M.tu=0;
  94. printf("转置前:\n");
  95. for(x=0;x<M.mu;x++){
  96. for(y=0;y<M.nu;y++){
  97. printf("%d\ ",a[x][y]);
  98. }
  99. printf("\n");
  100. }
  101. printf("转置后:\n");
  102. FastTransposeSMatrix(M,T);
  103. return 0;
  104. }
上传的附件 cloud_download 三元组存储稀疏矩阵并实现逆置.docx ( 41.28kb, 1次下载 )

发送私信

8
文章数
0
评论数
最近文章
eject