三元组压缩矩阵及解压

三元组压缩矩阵及解压

三元组:

  • 形如((x,y),z)的集合称为三元组(这就是说,三元组是这样的偶,其第一个射影亦是一个偶),常简记为(x,y,z).

  • 结构描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct node

{

int i,j; //定义三元组的行、列号

int v; //三元组的值

};

struct sparmatrix

{

int rows,cols; //稀疏矩阵的行、列数

int terms; //稀疏矩阵的非零元个数

struct node data[maxsize]; //存放稀疏矩阵的三元组表

};
  • 下面就是要把一个矩阵用三元组表示,思想就是利用三元组的关系把矩阵中的非零数据给记录下来,这样一来为0的部分就不占用内存,达到了压缩的目的。压缩记录的方法是,(x,y,z)中分别用x表示有效数据的行,y表示列。z就表示原矩阵x行y列的非零数据。

  • 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 2_7c.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
int main(int argc, char* argv[])
{
int n = 0; /*计算非零的数据个数 */
int i,j,k; /*遍历用的临时变量 */
/* 稀疏阵列的定义 */
int sparse[5][10] = {
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 9, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
0, 0, 0, 0, 3, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 6, 0, 0 };

/*----------------------压缩----------------------*/
//【1】计算非零的数据个数
for (i=0; i<5; i++)
for (j=0; j<10; j++)
{
if (sparse[i][j] != 0)
n += 1;
}
//【2】压缩阵列的声明和初始化
int (*compress)[3] = new int[n][3]; /*动态创建二维数组*/

k = 1; /* 设定变数初值 */
compress[0][0] = 5; /* 阵列sparse有5列 */
compress[0][1] = 10; /* 阵列sparse有10行 */
compress[0][2] = n; /* 阵列使用n个元素 */
//【3】进行压缩储存
for ( i = 0; i < 5; i++ ) /* 二维阵列的走访 */
for ( j = 0; j < 10; j++ )
if ( sparse[i][j] != 0 ) /* 元素有没有使用 */
{
compress[k][0] = i; /* 储存列数 */
compress[k][1] = j; /* 储存行数 */
/* 储存元素值 */
compress[k][2] = sparse[i][j];
k++; /* 下一列 */
}
//【4】压缩后的矩阵
printf("压缩后的矩阵:\n");
for ( i = 0; i < 6; i++ ) /* 压缩阵列的列印 */
{
for ( j = 0; j < 3; j++ )
printf("%2d ",compress[i][j]);
printf("\n"); /* 换行 */
}

/*------------------- 解压 ------------------*/
int array[5][10] = {0};
for (i=1; i<n; i++)
{
array[ compress[i][0] ][ compress[i][1] ] = compress[i][2];/* 有值的数据还原回去 */
}
/*输出解压后的数据*/
printf("解压后还原的矩阵:\n");
for (i=0; i<5; i++)
{
for (j=0; j<10; j++)
{
printf("%d\t",array[i][j]);
}
printf("\n");
}
return 0;
}
-------------本文结束感谢您的阅读-------------