数据结构-稀疏数组SparseArray

情景:当一个数组中大部分元素为0,或者为同一个值得数组时,可以用稀疏数组保存。

稀疏数组的处理方法:

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序规模
Sparse Array

应用实例:保存二维数组(棋盘、地图坐标)

一、二维数组转稀疏数组的思路

  1. 遍历原始的二维数组,得到有效数据的个数sum
  2. 根据sum创建稀疏数组SparseArray
  3. 将二维数组的有效数据存入到稀疏数组
  4. 将稀疏数组存盘

二、稀疏数组转原始二维数组的思路

  1. 先读取稀疏数组得第一行,根据第一行得数据创建原始二维数组
  2. 再读取稀疏数组后的几行数据,赋值给原始的二维数组即可

数组的行列数:

  1. 行数:array.length
  2. 列数:array[0].length
package com.joeaaa.sparsearray;

import java.io.*;

/*
* 二维数组与稀疏数组互转
* */
public class SparseArray {
    public static void main(String[] args) throws IOException {

        /*
        * 定义原始二维棋盘 5*6
        * */
        int originalChess[][] = new int [5][6];
        originalChess[1][2] = 1; // 第二行第三列=1
        originalChess[2][3] = 2; // 第三行第四列=2
        originalChess[4][5] = 6; // 第五航第六列=6
        System.out.println("Original Chess: ");
        for (int[] row : originalChess){
            for (int data: row){
                System.out.printf("%d\t" ,data);
            }
            System.out.println();
        }
        /*Original Chess:
            0	0	0	0	0	0
            0	0	1	0	0	0
            0	0	0	2	0	0
            0	0	0	0	0	0
            0	0	0	0	0	6
            */


        /*
        * 将二维数组转为稀疏数组
        * */
        // 1. 先遍历二维数组,得到非0得元素个数
        int nonZeroCount = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 6; j++) {
                if (originalChess[i][j] != 0){
                    nonZeroCount ++;
                }
            }
        }
        // 2. 创建对应的稀疏数组
        int SparseArray[][] = new int[nonZeroCount+1][3];  // 第一行记录数组行列、数,特征值个数;下面其余行为各个特征值的坐标+数据
        // 3. 给稀疏数组赋值
        SparseArray[0][0] = 5;
        SparseArray[0][1] = 6;
        SparseArray[0][2] = nonZeroCount;
        // 3. 遍历二维数组,将非0得值存放到稀疏数组
        int index = 0; // 第几个非0数据
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 6; j++) {
                if (originalChess[i][j] != 0){
                    index ++;
                    // 以下为稀疏数组的各个特征值坐标(第一行的后续)
                    SparseArray[index][0] = i;
                    SparseArray[index][1] = j;
                    SparseArray[index][2] = originalChess[i][j];
                }
            }
        }
        // 4. 稀疏数组输出
        System.out.println("SparseArray: ");
        for (int i = 0; i < SparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", SparseArray[i][0], SparseArray[i][1], SparseArray[i][2]);
        }
        System.out.println();
        /*SparseArray:
            5	6	3
            1	2	1
            2	3	2
            4	5	6
            */


        /*
        * 将稀疏数组SparseArray转化为二维数组
        * 1. 先读取稀疏数组第一行,得到二维数组得行数、列数
        * 2. 再读取稀疏数组非第一行数据,按坐标赋值给二维数组
        * */
        // 创建二维数组
        int[][] rebuildChess = new int[SparseArray[0][0]] [SparseArray[0][1]];
        // 赋值回去
        for (int i = 1; i < SparseArray.length ; i++) {
            rebuildChess[SparseArray[i][0]][SparseArray[i][1]] = SparseArray[i][2];
        }
        System.out.println("Rebuild Chess: ");
        for (int[] row : rebuildChess) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        /*Rebuild Chess:
            0	0	0	0	0	0
            0	0	1	0	0	0
            0	0	0	2	0	0
            0	0	0	0	0	0
            0	0	0	0	0	6
            */

        /*
        * 将结果保存到本地
        * */
        File file = new File("d:\\array.txt");  //存放数组数据的文件
        FileWriter out = new FileWriter(file);  //文件写入流
        
        //将数组中的数据写入到文件中。每行各数据之间TAB间隔
        for(int i = 0; i < rebuildChess.length; i++){ // 逐行读取, 行数:rebuildChess.length
            for(int j = 0; j < rebuildChess[0].length; j++){ // 列数:rebuildChess[0].length
                out.write(rebuildChess[i][j] +"\t");
            }
            out.write("\r\n");
        }
        out.close();
    }
}

MIT CLRS open courese-1/23

MIT CLRS open courese-1/23

Insertion-sort Algorit […]