（一）Java数据结构之稀疏数组

﹏ヽ暗。殇╰゛Y 2022-12-12 04:41 200阅读 0赞

**稀疏数组(sparse array)**是一种只为数组中的非零元素分配内存的特殊类型数组，分为三列：

1.  行下标
2.  列下标
3.  值

第一行为总行数、总列数、值的个数，其他行存储了非零元素的下标和值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70][]

根据上图我们可以写出如下代码实现稀疏数组：

package top.baikunlong.sparsearray;
    
    import java.io.*;
    
    /**
     * @author baikunlong
     * @date 2020/10/5 20:38
     * @apiNote
     */
    public class SparseArray {
        public static void main(String[] args) {
            //创建原数组
            int[][] originArray = new int[11][11];
            //赋值
            originArray[1][2] = 1;
            originArray[2][3] = 2;
            int length = originArray.length;
            System.out.println("原数组：");
            //打印一下原数组并得到原数组有效的个数
            int count = 0;
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    System.out.print(originArray[i][j] + "  ");
                    if (originArray[i][j] != 0) {
                        count++;
                    }
                }
                System.out.println();
            }
            System.out.println("有效值个数：" + count);
            //创建稀疏数组，因为第一行是用来存 行列数 和 值个数（文件读取恢复稀疏数组时会用到这个数） 的，所以要多一行
            int[][] sparseArray = new int[count + 1][3];
            sparseArray[0][0] = length;
            sparseArray[0][1] = length;
            sparseArray[0][2] = count;
            //给稀疏数组赋值，把原数组里非零的值存起来
            int rowIndex=1;//这里需要一个行下标记录下当前存储第几行，第一行已经存了行列数和值个数，所以从第二行开始存
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if (originArray[i][j] != 0) {
                        sparseArray[rowIndex][0]=i;
                        sparseArray[rowIndex][1]=j;
                        sparseArray[rowIndex][2]=originArray[i][j];
                        rowIndex++;
                    }
                }
            }
            System.out.println("稀疏数组：");
            for (int i = 0; i < sparseArray.length; i++) {
                for (int j = 0; j < sparseArray.length; j++) {
                    System.out.print(sparseArray[i][j]+"  ");
                }
                System.out.println();
            }
            //把稀疏矩阵存入文件SparseArray.data
            final String fileName = "SparseArray.data";
            File file = new File(fileName);
            try(FileOutputStream out = new FileOutputStream(file)) {
                int i = 0;
                for (; i < sparseArray.length-1; i++) {
                    out.write((sparseArray[i][0]+"  "+sparseArray[i][1]+"  "+sparseArray[i][2]+"\n").getBytes());
                }
                //最后行不用回车
                out.write((sparseArray[i][0]+"  "+sparseArray[i][1]+"  "+sparseArray[i][0]).getBytes());
            } catch (IOException e) {
                e.printStackTrace();
            }
            //==========================================================
            //到这里我们已经把原数组进行了压缩，使用稀疏数组进行存储，现在要开始读出来，并恢复成原数组
            try(BufferedReader reader = new BufferedReader(new FileReader(fileName))) {
                //读取第一行，用于创建稀疏数组
                String s = reader.readLine();
                String[] strings = s.split("  ");
                //注意，这里创建大小用到了第一行第三列那个 值个数 这个值，它加一就是行数了，列数固定还是三
                int[][] sparseArrayFromFile = new int[Integer.parseInt(strings[2])+1][3];
                //赋值第一行的数据，包含了行列式数和值个数
                sparseArrayFromFile[0][0]=Integer.parseInt(strings[0]);
                sparseArrayFromFile[0][1]=Integer.parseInt(strings[1]);
                sparseArrayFromFile[0][2]=Integer.parseInt(strings[2]);
                //开始读取下面的下标和值
                rowIndex=1;//行下标
                while ((s=reader.readLine())!=null){
                    strings = s.split("  ");
                    sparseArrayFromFile[rowIndex][0]=Integer.parseInt(strings[0]);
                    sparseArrayFromFile[rowIndex][1]=Integer.parseInt(strings[1]);
                    sparseArrayFromFile[rowIndex][2]=Integer.parseInt(strings[2]);
                    rowIndex++;
                }
                //打印文件读取出来的稀疏数组
                System.out.println("打印文件读取出来的稀疏数组：");
                for (int i = 0; i < sparseArrayFromFile.length; i++) {
                    for (int j = 0; j < sparseArrayFromFile.length; j++) {
                        System.out.print(sparseArrayFromFile[i][j]+"  ");
                    }
                    System.out.println();
                }
                //恢复原始数组
                int[][] recoveredArray = new int[sparseArrayFromFile[0][0]][sparseArrayFromFile[0][1]];
                for (int i = 1; i < sparseArrayFromFile.length; i++) {
                    recoveredArray[sparseArrayFromFile[i][0]][sparseArrayFromFile[i][1]]=sparseArrayFromFile[i][2];
                }
                //打印恢复的数组
                System.out.println("打印恢复的数组");
                for (int i = 0; i < recoveredArray.length; i++) {
                    for (int j = 0; j < recoveredArray.length; j++) {
                        System.out.print(recoveredArray[i][j]+"  ");
                    }
                    System.out.println();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70]: /images/20221123/1e1a5c969a224cf5b148a5965a215c43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70 1]: /images/20221123/19d96577e5ed450db0f0c9dc6d64b81e.png