稀疏数组

稀疏数组

什么是稀疏数组:

  • 举个例子:在一个比较大的二维数组中,里面有一些值,我想把这些值保存在电脑上(其中很多无用的0值那该如何保存),此时我可以用到今天所说的稀疏数组.
  • 在百度上找到的一个定义:如果一个数组(包括多维数组)中的大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组,节约空间。

那么应该如何来处理稀疏数组

  • 我使用稀疏数组的目的是为了节约空间,我们可以把一个多维数组的元素和行列,保存在一个比较小的数组内.
  • 这个数组只记录原数组有多少行和列和原数组有多少个不同的值

数组转换

稀疏数组的第二行参数解释:第一个11是整个二维数组的行,第二个11是整个二维数组的列,第三个4是整个二维数组有多少个作用值

而下面的数据的意思是:在第几行几列有一个多少的值,比如第三行就是在第1行3列有一个值是5

应用场景

稀疏数组应用的案例还是很多的,比如五子旗我们可以把棋盘看成一个很大的二维数组,上面的每一个棋子就是一个元素.当我们不想玩这个游戏的时候我们可以把这个游戏进度存档,方便下次接着玩,那么在这个存档的过程中,我们不可能把每个位置和这个位置上的元素存方到一个文件中,这时我可以使用稀疏数组来对这个庞大的二维数组进行压缩,然后存到文件中.当我要接着玩的时候就可以读取这个较小的文件,把里面的数据读出来进行还原.

代码讲解

我这个就写一个五子棋读存档的案例,不过不是真的五子棋,只是一个二维数组

生成原始二维数组

我在这里给这个数组起名字是oldArray,

int[][] oldArray = new int[11][11];
oldArray[1][3] = 5;
oldArray[4][6] = 7;
oldArray[6][4] = 10;
oldArray[4][4] = 20;

里面在初始化的时候我写上几个初始值

写完这些代码打印出来应该是这样的

原始二维数组

对二维数组压缩生成稀疏数组

第一步:计算有多少个作用值

对于这一部来说我应该分成多部写,先看下上面那个图片,在这个图片上的稀疏数组中有第二行有一个作用值,就是在这个数组中有多少个有意义的值, 我们首先要获取出这个值才能有下一部的动作

for (int i =0 ;i < 11; i++){
     for (int j =0 ;j<11;j++){
          if(oldArray[i][j] != 0){
             count++;
          }
     }
}

因为在这个数组中,我将没有意义的值都设置成了0,所以在这里我只要判断不等于0的值有多少个就有多少个作用值.

如果你是按照我的代码写的那么这些代码运行后打印的应该是4

第二步:创建稀疏数组

创建稀疏数组

int[][] newArray = new int[count+1][3];
newArray[0][0] = 11;
newArray[0][1] = 11;
newArray[0][2] = count;

这里在创建数组的时候行数要进行作用值的数+1的操作,因为这个稀疏数组的行数是作用值的个数,加一是因为在最上面还有一行是保存有多少行和列和作用值个数的一行,所以要加一

对稀疏数组赋值

int newArray_row = 0;
for (int i =0 ;i < 11; i++){
    for (int j =0 ;j<11;j++){
        if(oldArray[i][j] != 0){
            newArray_row++;
            newArray[newArray_row][0] = i;
            newArray[newArray_row][1] = j;
            newArray[newArray_row][2] = oldArray[i][j];
        }
    }
}

想必这块代码都是可以看懂的,说下newArray_row变量,在if块中赋值的操作的行是动态的,在程度的执行过程中我也不知道现在是第几行,所有我准备了一个变量用来存行数(也就是第几次循环)

第三步:将稀疏数组写到文件

因为我刚开始说做一个类似五子棋存档的程序,这里肯定会有将数组写到硬盘的代码

File arrayFile = new File("array.txt");
try {
    int writeCount = 0;
    FileWriter fileWriter = new FileWriter(arrayFile);
    fileWriter.write(newArray.length + "\t"+newArray[0].length + "\n");
    for (int[] row: newArray) {
        for (int item: row) {
            writeCount++;
            System.out.printf("写文本第%d次\n",writeCount);
            fileWriter.write(item + "\t");

        }
        fileWriter.write("\r\n");
        fileWriter.flush();
    }
    fileWriter.close();

} catch (IOException e) {
    e.printStackTrace();
}

这里的代码找几个重要的说一下

fileWriter.write(newArray.length + "\t"+newArray[0].length + "\n");这行代码的意义是,在我读取文件的时候我要知道这个稀疏数组有多少行和多少列,所以这一行就是往文件写这个数组的行和列

下面的for循环的块中是通过foreach来进行遍历数组内容,将这些内容通过FileWriter的write方法写到文件

第四步:读取文件的内容

int[][] readArray_shishu = null;
try {
    int countReadFile = -1;
    BufferedReader br = new BufferedReader(new FileReader(arrayFile));
    String line = null;
    while ((line = br.readLine()) != null){

        readArray_shishu = splitLine(line,countReadFile,readArray_shishu);
        countReadFile++;
    }

    for (int[] row:
            readArray_shishu) {
        for (int r:
             row) {
            System.out.printf("%d\t",r);
        }
        System.out.println();
    }
} catch (FileNotFoundException e) {
    e.printStackTrace();
} catch (IOException e) {
    e.printStackTrace();
}
/**
 * 分割字符串,还原稀疏数组
 * @param line 读限文本的每一行
 * @param i 一个计数的变量,用于判断是不是读到的第一行,如果是取出数据生成数组
 */
public static int[][] splitLine(String line,int i,int[][] readArray_shishu){
    if(i == -1){
        String[] rowString = line.split("\t");
        readArray_shishu = new int[Integer.parseInt(rowString[0])][Integer.parseInt(rowString[1])];
    }else{
        String[] rowString = line.split("\t");
        readArray_shishu[i][0] = Integer.parseInt(rowString[0]);
        readArray_shishu[i][1] = Integer.parseInt(rowString[1]);
        readArray_shishu[i][2] = Integer.parseInt(rowString[2]);
    }
    return readArray_shishu;
}

这里因为在这里我是一行一行的读取文件,每次读取的数据都是一个字符串,在这里我要进行字符串的分割,所以我准备了一个splitLine用于分割字符串,

因为先读出的一行是代表的稀疏数组的行和列这一行我只用于初始化稀疏数组,所有这在读文件的时候准备一了个变量i,用于记录读文件的第几次,这个变量的初始值是-1,等于-1的时候就是读到的行和列,我就用于初始化数组,当不是-1就进行赋值.

这里每次赋值完成或者是初始化完成后,将这个数组返回,并用一个数组接收(可能这里看文字下是很好的理解,大家在看的时候结合着代码看),然后下一次赋值的时候再把这个数组传到splitLine方法.

注:在读取的数据我是保存在了String数组里面,所有使用的时候要进行使用Integer.parseInt()方法转换

第五步:还原二维数组

System.out.println("----------- 还原二维数组开始 -----------");
huanyuan_tow(readArray_shishu);
System.out.println("----------- 还原二维数组结束 -----------");
/**
 * 还原二维数组
 * @param readArray_shishu 这个参数是稀疏数组
 */
public static void huanyuan_tow(int[][] readArray_shishu){
    int[][] tow_array = new int[readArray_shishu[0][0]][readArray_shishu[0][1]];
    for (int i =1;i<=readArray_shishu[0][2];i++){
        tow_array[readArray_shishu[i][0]][readArray_shishu[i][1]] = readArray_shishu[i][2];
    }

    for (int[] t:
            tow_array) {
        for (int item:
             t) {
            System.out.printf("%d\t",item);
        }
        System.out.println();
    }
}

还原数组的时候因为稀疏数组的第一行保存的是二维数组的行和列,所有要使用稀疏数组的第一行的数据进行二维数组的初始化.int[][] tow_array = new int[readArray_shishu[0][0]][readArray_shishu[0][1]];

在对二维数组赋值的时候,要使用for循环,这个循环的条件就是稀疏数组中保存的作用值(稀疏数组第一行中最后一个值)int i =1;i<=readArray_shishu[0][2];i++.

for的循环体内就是对二维数组进行赋值的操作tow_array[readArray_shishu[i][0]][readArray_shishu[i][1]] = readArray_shishu[i][2];

readArray_shishu[i][0]代表的是这个值所在的行

readArray_shishu[i][1]代表的是这个值所在的列

readArray_shishu[i][2]代表的是值

所以通过上面的for就完成了二维数组的还原

结果

全部代码

import java.io.*;

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

        int count = 0;
        int[][] oldArray = new int[11][11];
        int[][] readArray_shishu = null;
        oldArray[1][3] = 5;
        oldArray[4][6] = 7;
        oldArray[6][4] = 10;
        oldArray[4][4] = 20;
        System.out.println("这个是原始的数组");
        System.out.println("------------------------------------------");
        for (int[] row: oldArray) {
            for (int item: row) {
                System.out.printf("%d\t",item);
            }
            System.out.println();
        }
        System.out.println("------------------------------------------");

        for (int i =0 ;i < 11; i++){
            for (int j =0 ;j<11;j++){
                if(oldArray[i][j] != 0){
                    count++;
                }
            }
        }
        System.out.printf("有%d个数字\n",count);
        System.out.println("压缩数组");
        int[][] newArray = new int[count+1][3];
        newArray[0][0] = 11;
        newArray[0][1] = 11;
        newArray[0][2] = count;

        int newArray_row = 0;
        for (int i =0 ;i < 11; i++){
            for (int j =0 ;j<11;j++){
                if(oldArray[i][j] != 0){
                    newArray_row++;
                    newArray[newArray_row][0] = i;
                    newArray[newArray_row][1] = j;
                    newArray[newArray_row][2] = oldArray[i][j];
                }
            }
        }

        System.out.println("----------- 打印稀疏数组开始 -----------");
        for (int[] row:
             newArray) {
            for (int item:
                 row) {
                System.out.printf("%d\t",item);
            }
            System.out.println();
        }
        System.out.println("----------- 打印稀疏数组完毕 -----------");
        System.out.println("----------- 写稀疏数组到文本开始 -----------");
        File arrayFile = new File("array.txt");
        try {
            int writeCount = 0;
            FileWriter fileWriter = new FileWriter(arrayFile);
            fileWriter.write(newArray.length + "\t"+newArray[0].length + "\n");
            for (int[] row: newArray) {
                for (int item: row) {
                    writeCount++;
                    System.out.printf("写文本第%d次\n",writeCount);
                    fileWriter.write(item + "\t");

                }
                fileWriter.write("\r\n");
                fileWriter.flush();
            }
            fileWriter.close();

        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("----------- 写稀疏数组到文本结束 -----------");

        System.out.println("----------- 读稀疏数组到文本开始 -----------");
        try {
            int countReadFile = -1;
            BufferedReader br = new BufferedReader(new FileReader(arrayFile));
            String line = null;
            while ((line = br.readLine()) != null){

                readArray_shishu = splitLine(line,countReadFile,readArray_shishu);
                countReadFile++;
            }

            for (int[] row:
                    readArray_shishu) {
                for (int r:
                     row) {
                    System.out.printf("%d\t",r);
                }
                System.out.println();
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("----------- 读稀疏数组到文本结束 -----------");

        System.out.println("----------- 还原二维数组开始 -----------");
        huanyuan_tow(readArray_shishu);
        System.out.println("----------- 还原二维数组结束 -----------");
    }

    /**
     * 分割字符串,还原稀疏数组
     * @param line 读限文本的每一行
     * @param i 一个计数的变量,用于判断是不是读到的第一行,如果是取出数据生成数组
     */
    public static int[][] splitLine(String line,int i,int[][] readArray_shishu){
        if(i == -1){
            String[] rowString = line.split("\t");
            readArray_shishu = new int[Integer.parseInt(rowString[0])][Integer.parseInt(rowString[1])];
        }else{
            String[] rowString = line.split("\t");
            readArray_shishu[i][0] = Integer.parseInt(rowString[0]);
            readArray_shishu[i][1] = Integer.parseInt(rowString[1]);
            readArray_shishu[i][2] = Integer.parseInt(rowString[2]);
        }
        return readArray_shishu;
    }

    /**
     * 还原二维数组
     * @param readArray_shishu 这个参数是稀疏数组
     */
    public static void huanyuan_tow(int[][] readArray_shishu){
        int[][] tow_array = new int[readArray_shishu[0][0]][readArray_shishu[0][1]];
        for (int i =1;i<=readArray_shishu[0][2];i++){
            tow_array[readArray_shishu[i][0]][readArray_shishu[i][1]] = readArray_shishu[i][2];
        }

        for (int[] t:
                tow_array) {
            for (int item:
                 t) {
                System.out.printf("%d\t",item);
            }
            System.out.println();
        }
    }
}
Last modification:October 13th, 2019 at 01:06 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment