回顾数据结构（Java版）——稀疏矩阵压缩和解压

喜欢ヅ旅行 2023-06-05 05:51 9阅读 0赞

稀疏矩阵的压缩和解压缩

> 稀疏矩阵的压缩思路分析

1.  先统计在二维数组中有多少有效的的值统计出sum
2.  根据sum创建一个压缩数组
3.  然后遍历每一项有效值，并且将它记录在压缩数组中

> 稀疏矩阵的恢复

1.  根据压缩矩阵的行和列恢复原来的矩阵
2.  然后把其他有效值填进这个新建的矩阵

code

package com.wrial.sparse_matrix;
    /*
     * @Author  Wrial
     * @Date Created in 13:44 2019/10/6
     * @Description 将一个稀疏数组进行压缩和解压缩
     */
    
    public class SparseMatrix {
    
        public static void main(String[] args) {
    
            //1.创建一个原始的二维数组/矩阵
            int[][] matrix = new int[9][9];
            //2.填充一些值
            matrix[1][1] = 1;
            matrix[2][1] = 2;
            matrix[5][5] = 5;
            matrix[4][8] = 10;
            //输出一下当前矩阵
            System.out.println("原矩阵");
            output(matrix);
            //3.扫描数组的有效值
            int sum = 0;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (matrix[i][j] != 0) {
                        sum++;
                    }
                }
            }
            System.out.printf("sum = %d\n", sum);
            //4.根据sum创建出压缩数组  注意：不能是sum行而是sum+1行，因为第一行要记录总行数和列数
            int[][] sparseArray = new int[sum + 1][3];
            //5.将矩阵中的值填入压缩数组中
            sparseArray[0][0] = 9;
            sparseArray[0][1] = 9;
            sparseArray[0][2] = sum;
            int p = 0;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (matrix[i][j] != 0) {
                        ++p;
                        sparseArray[p][0] = i;
                        sparseArray[p][1] = j;
                        sparseArray[p][2] = matrix[i][j];
                    }
                }
            }
            System.out.println("压缩后");
            output(sparseArray);
    
            //6.压缩完成后进行解压缩，根据sparseArray[0][x]恢复原矩阵
            int[][] oldMatrix = new int[sparseArray[0][0]][sparseArray[0][1]];
            //7.给里面填值  根据sum作为终止
            for (int i = 1; i <= sparseArray[0][2]; i++) {
                oldMatrix[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
            }
    
            System.out.println("恢复后的矩阵");
            output(oldMatrix);
    
    
        }
    
        public static void output(int[][] matrix) {
            for (int[] ints : matrix) {
                for (int anInt : ints) {
                    System.out.printf("%d\t", anInt);
                }
                System.out.println();
            }
        }
    
    }

需要注意的点是压缩的稀疏数组的行数是sum+1行