转载

稀疏数组

1、实际需求

编写的五子棋程序中,有存盘退出和续上盘的功能。

分析问题:因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据。

2、基本介绍

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:

1)记录数组-共有几行几列,有多少个不同的值

2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

稀疏数组举例说明

3、应用实例

1)使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)

2)把稀疏数组存盘,并且可以重新恢复原来的二维数组数

3)思路分析

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

  • 遍历原始的二维数组,得到有效数据的个数 sum
  • 根据sum就可以创建稀疏数组 sparsArr int[ sum + 1 ][3]
  • 将二维数组的有效数据存入到稀疏数组

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

  • 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的chessArr = int[11][11]
  • 再读取稀疏数组后面几行的内容,并赋给原始的二位数组即可

4)代码实现

public class SparseArray {
    public static void main(String[] args) throws IOException {
//        创建一个原始的二维数组
//        0表示没有棋子,1表示黑子,2表示蓝子
        int chessArr1[][]= new int[11][11];
        chessArr1[1][2]=1;
        chessArr1[2][3]=2;
        chessArr1[3][3]=2;
        System.out.println("-----------------初始化二维数组-----------------");
        for (int[] row:chessArr1) {
            for (int col:row) {
                System.out.printf("%d\t",col);
            }
            System.out.println();
        }
        System.out.println("-----------------将二维数组转稀疏数组-----------------");
//        1.先遍历二维数组,得到非零数据的个数
        int sum = 0;
        for (int i = 0; i <chessArr1.length ; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j]!=0)
                    sum++;
            }
        }
        System.out.println("非零数据个数="+sum);
//        2.创建对应的稀疏数组
        int sparseArr[][] = new int[sum+1][3];
//        给稀疏数组赋值
        sparseArr[0][0]=11;
        sparseArr[0][1]=11;
        sparseArr[0][2]=sum;
//        遍历二维数组,将非零的值存放
        int count = 0;
        for (int i = 0; i <chessArr1.length ; i++) {
            for (int j = 0; j < chessArr1.length; j++) {
                if (chessArr1[i][j]!=0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        System.out.println("-----------------将稀疏数组写入文件-----------------");
        File file = new File("d:/Spart.data");
        try {
            if (file.exists() == false) {//是否有指定文件,没有的话创建一个
                file.getParentFile().mkdir();
            }
            FileWriter fs = new FileWriter(file);
            for (int i = 0; i < sparseArr.length; i++) {
                for (int j = 0; j < 3; j++) {
                    fs.write(sparseArr[i][j] + "\t");
                }
                fs.write("\r");
            }
            fs.close();
        } catch (IOException e) {
            System.out.println("写入失败!");
        }

        System.out.println("-----------------开始读取文件-----------------");
//        获取行数
        BufferedReader in = new BufferedReader(new FileReader(file));
        String line;
        int row0 = 0;
        while ((line = in.readLine()) != null) {
            row0++;
        }

        int count1 = 0;
        String line1;
        int Spartarray[][] = new int[row0][3];
        BufferedReader in1 = new BufferedReader(new FileReader(file));
        while ((line1 = in1.readLine()) != null) {
            String[] temp = line1.split("\t");
            for (int m = 0; m < temp.length; m++) {
                Spartarray[count1][m] = Integer.parseInt(temp[m]);
            }
            count1++;
        }
        in.close();
        for (int i = 0; i < count1; i++) {
            System.out.printf("%d\t%d\t%d\t\n", Spartarray[i][0], Spartarray[i][1], Spartarray[i][2]);
        }
        System.out.println("-----------------读取文件结束-----------------");



        System.out.println("-----------------稀疏转换原始数组-----------------");
        System.out.println();
        for (int i = 0; i <Spartarray.length ; i++) {
            System.out.printf("%d\t%d\t%d\t\n",Spartarray[i][0],Spartarray[i][1],Spartarray[i][2]);
        }
//        先读取稀疏第一行数据,初始化数组
        int Spartarray2 [][]= new int[Spartarray[0][0]][Spartarray[0][1]];
//        读取后几行数据,并将其赋值给原始的数组
        for (int i = 1; i <Spartarray.length ; i++) {
            Spartarray2[Spartarray[i][0]][Spartarray[i][1]] =Spartarray[i][2];
        }
//      输出还原后的数组
        System.out.println("-----------------恢复后的数组-----------------");
        for (int row[]:Spartarray2) {
            for (int col: row) {
                System.out.printf("%d\t",col);
            }
            System.out.println();
        }
    }
}
  • 作者:管理员(联系作者)
  • 发表时间:2020-05-12 03:18
  • 版权声明:自由转载-非商用-非衍生-保持署名
  • 公众号转载:请在文末添加作者公众号二维码
  • 评论

    Gump 游客
    女大佬
    rpgdsk 游客
    韩顺平的数据结构吧
    管理员  @ rpgdsk
    站长
    是啊
    sss  @ 管理员 游客

    rpgdsk  @ 管理员 游客
    问一下,我的评论应该是parentComment(parentComment字段为null),你的回复是我的sonComment,parentComment应该就是我那条评论的comment_id;下面那位sss又回复了你,这条回复也是我的sonComment,parentComment也是我那条评论的comment_id,是这样吗?sss给你的回复,只需要记录parentComment就行了吗?还要不要记录你的comment_id?
    管理员  @ rpgdsk
    站长
    只记@的id
    rpgdsk  @ 管理员 游客
    还有一个问题,这个评论框和回复框不应该共用吧,我把回复做出来了,但是现在发现一个问题:点击任意回复按钮,此输入框记住父评论id,但是此时我突然不想回复了,想要发布一条新评论,那不就无法实现了吗?我的输入框始终会携带一条父评论id,我看知乎的微博的评论和回复都是分开的
    管理员  @ rpgdsk
    站长
    可以优化但没有时间
    管理员  @ rpgdsk
    站长
    semanticui好像有现成 的样式  改改就可以实现了
    王一嘉 游客
    6
    你明明 游客
    6525
    富强民主文明和谐 游客
    <script>
    alert('nbnb强大强大')
    </script>
    aha 游客
    nbnb