浅谈Java数据结构之稀疏数组知识总结

稀疏数组

• 当一个数组中的元素大多为0或者相同元素的时候，可以用稀疏数组来压缩
• 稀疏数组只记录 行row 列col 值value

将下列的二维数组转为稀疏数组,如下两图所示

1.实现二维数组转为稀疏数组的步骤：

• 遍历数组，得到数组中 不为0的个数，并记录为sum，作为稀疏数组第0行的 value
• 遍历数组，将数组中不为0的数的行和列和值分别写入稀疏数组的 row col val 中

代码实现：

public class SparseArray {
    public static void main(String[] args) {

        // 创建一个原始二维数组
        // 0表示没有棋子，1，2各表示一种棋
        int chessArr[][] = new int[8][8];
        chessArr[1][1] = 1;
        chessArr[2][2] = 2;

        // 遍历原始数组，获得不等于 0 的个数,并输出原始数组
        int sum = 0;
        System.out.println("原始数组：");
        for (int[] ints : chessArr) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
                if (anInt != 0){
                    sum++;
                }
            }
            System.out.println();
        }
        System.out.println(sum);

        // 创建稀疏数组并赋值
        int sparseArray[][] = new int[sum+1][3];
        int row = chessArr.length; // 原数组的行数
        int col = chessArr[0].length; // 原数组的列数
        sparseArray[0][0] = row;
        sparseArray[0][1] = col;
        sparseArray[0][2] = sum;

        // 遍历原始数组并赋值给稀疏数组
        int count = 0; // count 为计数器
        for (int i = 0;i < row;i++) {
            for (int j = 0;j < col;j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = chessArr[i][j];
                }
            }
        }

        // 输出得到的稀疏数组
        System.out.println("稀疏数组为：");
        for (int i = 0 ;i < sparseArray.length;i++) {
            System.out.println(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]);
        }

    }
}

2.实现二维数组转稀疏数组的步骤

• 根据稀疏数组的第一行创建新的二维数组
• 遍历稀疏数组，将row col val 赋给新的二维数组

代码实现：

public class SparseArray {
    public static void main(String[] args) {

		...... // 接上一段代码

        // 输出得到的稀疏数组
        System.out.println("稀疏数组为：");
        for (int i = 0 ;i < sparseArray.length;i++) {
            System.out.println(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]);
        }

        // 创建新的二维数组
        int newChessArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1 ;i < sparseArray.length;i++) {
            newChessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        // 输出新的二维数组
        System.out.println("恢复后的二维数组是：");
        for (int[] ints : newChessArray) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
}

3.将稀疏数组写入磁盘

public static void main(String[] args) {
    ........
	// 将稀疏数组存入磁盘
    FileOutputStream fw = null;
    try {
        fw = new FileOutputStream("sparseArray.txt");
        // 遍历写入磁盘
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < 3; j++) {
                fw.write(sparseArray[i][j]);
            }
        }
        fw.flush();
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if (fw != null){
            fw.close();
        }
    }
}

4.从磁盘读取稀疏数组

public static void main(String[] args) {
    .......
    // 从磁盘读取稀疏数组
    FileInputStream fi = null;
    int newSparseArray[][] = new int[sum+1][3];  // sum 指前面二维数组有值的个数
    try {
        fi = new FileInputStream("sparseArray.txt");
        for (int i = 0;i < newSparseArray.length;i++) {
            for (int j = 0;j < 3;j++){
                newSparseArray[i][j] = fi.read();
            }
        }
    } catch (FileNotFoundException e){
        e.printStackTrace();
    } finally {
        if (fi != null){
            fi.close();
        }
    }
}

到此这篇关于浅谈Java数据结构之稀疏数组知识总结的文章就介绍到这了,更多相关Java稀疏数组内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！