稀疏矩阵的压缩与还原（Java实现）

亦凉 2024-04-17 17:04 12阅读 0赞

## 稀疏矩阵的压缩与还原（Java实现） ##

#### 1.稀疏矩阵的概念 ####

在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵，如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]

#### 2.稀疏矩阵的压缩 ####

如果要把一个含有如此多0元素的稀疏矩阵存储到计算机中，这些没有意义的0同样地会消耗掉计算机的内存，那么这势必造成计算机内存的浪费。那么，对于稀疏矩阵的存储，我们应该如何去处理呢？下面介绍一个例子：

**例：** 现在要模拟一个11\*11的五子棋棋盘的存档和续局。棋盘上有黑、白两种棋子，分别用1、2来表示，没有棋子的地方，则用0来表示。假设这个棋盘是只有3颗棋子，2颗白棋子，1颗黑棋子，则该棋盘抽象出来，就是一个稀疏矩阵，其中非0元素只有3个，分别是1，2，2。现在，不想下棋了，那么要保存这个棋盘，也就是保存这个稀疏矩阵。  
图解思路：  
棋盘上的状态如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]  
我们从图所得到的信息：棋盘矩阵是11 \* 11的，有3颗棋子  
黑子所在的位置是矩阵的第3行第3列,值是1  
白子所在的位置是矩阵的第6行第2列、第4行第5列，值都为2  
转化成数组的存储，就是：  
黑子所在的位置是矩阵的第2行第2列,值是1  
白子所在的位置是矩阵的第5行第1列、第3行第4列，值都为2（因为数组的下标是从0开始的）  
那么，我们可以将上面的信息抽象成一个新的二维数组：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]  
这样就实现了稀疏矩阵的压缩  
下面是代码实现：

import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    public class SparseArray {
    
        public static void main(String[] args) throws IOException {
            //创建一个原始的二维数组11*11
            //0：表示无棋子，1表示黑子，2表示白子
            int[][] chessArr1=new int[11][11];
            chessArr1[2][2]=1;
            chessArr1[5][1]=2;
            chessArr1[3][4]=2;
    
            //输出原始的二维数组
            System.out.println("原始的二维数组：");
            for (int[] row:chessArr1){
                for (int data:row){
                    System.out.printf("%d\t",data);
                }
                System.out.println();//每打印一行就换一行
            }
            //将二维数组 转 稀疏数组
            //1.先遍历二维数组，得到非0数据的个数
            int count=0;
            for(int[] row:chessArr1){
                for (int data:row){
                    if (data!=0){
                        count++;
                    }
                }
            }
            System.out.println("非0的元素个数为："+count);
            //2.创建稀疏数组
            int[][] sparseArr=new int[count+1][3];
            //3.给稀疏数组赋值
            sparseArr[0][0]=11;
            sparseArr[0][1]=11;
            sparseArr[0][2]=count;
            //4.遍历二维数组，将非0的值存放到sparseArr中
            int row=1;//用于记录是第几个非0数据
            for (int i = 0; i < 11; i++) {
                for (int j = 0; j < 11; j++) {
                    if (chessArr1[i][j]!=0){
                        sparseArr[row][0]=i;
                        sparseArr[row][1]=j;
                        sparseArr[row][2]=chessArr1[i][j];
                        row++;
                    }
                }
            }
            //6.输出稀疏数组
            System.out.println("得到的稀疏数组为：");
            for (int[] row1:sparseArr){
                for (int data:row1){
                    System.out.printf("%d\t",data);
                }
                System.out.println();
            }
            //7.将稀疏数组写入到文件中
            FileWriter writer=null;
            try {
                writer=new FileWriter(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt"));
                int count1=0;//用于控制换行
                for (int i = 0; i < sparseArr.length; i++) {
                    for (int j = 0; j < sparseArr[i].length; j++) {
                        writer.write(sparseArr[i][j]+"\t");
                        count1++;
                        if (count1%3==0){
                            writer.write("\n");
                        }
                    }
                }
            } catch (IOException e) {
                e.printStackTrace();
            }finally {
                if (writer!=null) {
                    writer.close();
                }
    
            }

输出结果如下：  
控制台输出结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 3]  
由于需求是棋盘存档，显然要把压缩后的数组保存到文件中，那么上面代码得到的data.txt文件内容如下：  
![在这里插入图片描述][20190829095239564.png]  
棋盘存档成功！

#### 3.稀疏矩阵的还原 ####

还原的话就很简单了，利用压缩后的数组的第0行信息来构建新的二维数组（11 \* 11），然后读取第一行以后的信息，把非0元素的行、列和值对应地赋值到新二维数组就可以了。  
整个需求的完整代码实现如下：

package cn.Day01.demo2;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.io.IOException;
    
    public class SparseArray {
    
                public static void main(String[] args) throws IOException {
                    //创建一个原始的二维数组11*11
                    //0：表示无棋子，1表示黑子，2表示白子
                    int[][] chessArr1=new int[11][11];
                    chessArr1[2][2]=1;
                    chessArr1[5][1]=2;
                    chessArr1[3][4]=2;
    
                    //输出原始的二维数组
                    System.out.println("原始的二维数组：");
                    for (int[] row:chessArr1){
                        for (int data:row){
                            System.out.printf("%d\t",data);
                        }
                        System.out.println();//每打印一行就换一行
                    }
                    //将二维数组 转 稀疏数组
                    //1.先遍历二维数组，得到非0数据的个数
                    int count=0;
                    for(int[] row:chessArr1){
                        for (int data:row){
                            if (data!=0){
                                count++;
                            }
                        }
                    }
                    System.out.println("非0的元素个数为："+count);
                    //2.创建稀疏数组
                    int[][] sparseArr=new int[count+1][3];
                    //3.给稀疏数组赋值
                    sparseArr[0][0]=11;
                    sparseArr[0][1]=11;
                    sparseArr[0][2]=count;
                    //4.遍历二维数组，将非0的值存放到sparseArr中
                    int row=1;//用于记录是第几个非0数据
                    for (int i = 0; i < 11; i++) {
                        for (int j = 0; j < 11; j++) {
                            if (chessArr1[i][j]!=0){
                                sparseArr[row][0]=i;
                                sparseArr[row][1]=j;
                                sparseArr[row][2]=chessArr1[i][j];
                                row++;
                            }
                        }
                    }
                    //6.输出稀疏数组
                    System.out.println("得到的稀疏数组为：");
                    for (int[] row1:sparseArr){
                        for (int data:row1){
                            System.out.printf("%d\t",data);
                        }
                        System.out.println();
                    }
                    //7.将稀疏数组写入到文件中
                    FileWriter writer=null;
                    try {
                        writer=new FileWriter(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt"));
                        int count1=0;//用于控制换行
                        for (int i = 0; i < sparseArr.length; i++) {
                            for (int j = 0; j < sparseArr[i].length; j++) {
                                writer.write(sparseArr[i][j]+"\t");
                                count1++;
                                if (count1%3==0){
                                    writer.write("\n");
                                }
                            }
                        }
                    } catch (IOException e) {
                        e.printStackTrace();
                    }finally {
                        if (writer!=null) {
                            writer.close();
                        }
    
                    }
            //根据稀疏矩阵来还原二维数组
            //0.将稀疏数组从文件中读取出来:
            /**
             *
             */
            FileReader reader=new FileReader(new File("E:\\Java项目\\Java数据结构\\src\\cn\\Day01\\Files\\data.txt"));
            BufferedReader bfreader=new BufferedReader(reader);
            String temp;
            String[] temps=null;
            int lineArr=0;
            while ((temp= bfreader.readLine())!=null){
                temps=temp.split("\t");
                for (int i=0;i<temps.length;i++){
                    sparseArr[lineArr][i]=Integer.parseInt(temps[i]);
                }
                lineArr++;
            }
            System.out.println("还原后的稀疏矩阵为：");
            for (int i = 0; i < sparseArr.length; i++) {
                for (int j = 0; j < sparseArr[i].length; j++) {
                    System.out.printf("%d\t",sparseArr[i][j]);
                }
                System.out.println();
            }
    
    
            //1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
    
            int[][] chessArr2=new int[sparseArr[0][0]][sparseArr[0][1]];
            //2.遍历稀疏矩阵，给二维数组赋值
            for(int i=1;i<sparseArr.length;i++){
                    chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
            }
            //3.输出原二维数组
            System.out.println("还原后的数组为：");
            for (int i = 0; i < chessArr2.length; i++) {
                for (int j = 0; j < chessArr2[i].length; j++) {
                    System.out.printf("%d\t",chessArr2[i][j]);
                }
                System.out.println();
    
            }
    
        }
    }

#### 4.总结 ####

目前在跟着尚硅谷的韩顺平老师学习图解数据结构和算法（Java版），刚学完第一个知识点，受益匪浅，故作此篇，与各位学习交流！  
2019/8/29

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2f8fb30fca9146739a2e8747c5326c35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/06494345207c4c0cae7c977c05450059.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e3ebbe33ce114c6289f9ebe734100376.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/71c7ac14dda241149d23f31bdd40e5cc.png
[20190829095239564.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ae5a56fa7ceb439591682d0fee7d94e3.png