阅读 20

数据结构复习1-稀疏数组

【转载请注明出处:From李诗雨—blog.csdn.net/cjm24848365…

不诗意的女程序猿不是好厨师~

1.一些基础点

1.1数据结构:包括线性结构和非线性结构。

1.2线性结构

  • 特点是数据元素之间存在一对一的线性关系.
  • 线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。 顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
  • 线性结构常见的有:数组、队列、链表和栈。

1.3非线性结构

  • 非线性结构包括:二维数组,多维数组,广义表,树结构,图结构

2.稀疏数组

2.1实际使用场景

在这里插入图片描述
举个栗子来说: 我们都玩过五子棋游戏,那么如果让我们自己撸起袖子来写一个,你会怎么做呢?用什么来表示棋盘棋子?黑棋白棋如何表示?如果下到一半累了不想玩了需要保存棋局该怎么做?打了局王者乏了又想来继续下五子棋,又该如何复局呢?
数组1
现在我们来分析一下,我们可以用一个11*11的二维数组来模拟棋局,二维数组的值来代表棋子,如果是1就表示是黑子,如果是2就表示是蓝子。 如果要实现保存棋盘的功能,就要把这个二维数组保存起来。 但是我们看现在这个二维数组有很多的0值,直接保存起来感觉很浪费。那有没有什么办法可以简化这个二维数组呢?
数组2
我们可以把它优化成如上图所示的二维数组, 第一行用来表示原有数组有几行几列吗,多少个不同的值。 从第二行开始每一行表示 行、列的位置 和对应的值。

所以数组2可以得到的信息是: 原有数组有11行11列有2个不同的值,其中在(1,2)位置的值是1,(2,3)位置的值是2。 看,其实就是对原有数组的另一种表示。而且我们把1111的规模编程了33的规模,是不是大大的做到了简化。

好的,不知不觉中我们就引入了稀疏数组,其实啊,简化后的数组就是一个稀疏数组。下面我们来看看什么是稀疏数组。

2.1稀疏数组的小结

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

稀疏数组的处理方法是: 记录数组一共有几行几列,有多少个不同的值。 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模。

3.学以致用,撸代码

在这里插入图片描述
现在让我们按下面的要求来撸一段代码,练习一下:

3.0利用稀疏数组完成棋局的保存棋局的恢复功能。

分析: 先将如图所示的棋局,用1111的二维数组表示出来,然后把它转化为对应的稀疏数组,存储到本地文件中,这样就完成“棋局的保存”功能。 我们将文件中的内容读取出来,转化为稀疏数组,然后在转化为对应的1111的二维数组,这样就完成了“复盘”功能。

光说不练假把式,具体代码如下:

3.1用11*11的二维数组展示棋局。

/**
         * 创建一个11*11的二维数组 ,来模拟五子棋棋盘
         * 其中值1代表黑棋,棋2代表蓝棋
         */
        int[][] gobangArray = new int[11][11];
        gobangArray[1][2] = 1;
        gobangArray[2][3] = 2;

        System.out.println("原始棋局:");
        for (int[] row : gobangArray) {
            for (int element : row) {
                System.out.printf("%d\t", element);
            }
            System.out.println();
        }
复制代码

打印结果如下:

在这里插入图片描述

3.2 将 原始数组 转化为 稀疏数组

具体思路: a. 遍历 原始的二维数组,得到有效数据的个数 sum b. 根据sum 创建 稀疏数组 sparseArray int[sum + 1] [3] c. 将二维数组的有效数据数据存入到 稀疏数组

  /**
         * 遍历原始棋局,得到棋子总数
         */
        int sum = 0;
        for (int[] row : gobangArray) {
            for (int element : row) {
                if (element != 0) sum++;
            }
        }

        /**
         * 创建稀疏数组 int[sum+1][3]
         * 第一行存原始棋局的行数,列数 和 棋子数
         * 后面的每一行:第一列 存棋子的所在行下标,第二列 存棋子的所在列下标,第三列 存值
         */
        int[][] sparseArray = new int[sum + 1][3];
        sparseArray[0][0] = 11;
        sparseArray[0][1] = 11;
        sparseArray[0][2] = sum;
        int sparseRow = 1;
        for (int row = 0; row < 11; row++) {
            for (int column = 0; column < 11; column++) {
                if (gobangArray[row][column] != 0) {
                    sparseArray[sparseRow][0] = row;
                    sparseArray[sparseRow][1] = column;
                    sparseArray[sparseRow][2] = gobangArray[row][column];
                    sparseRow++;
                }
            }
        }

        /**
         * 验证一下
         */
        System.out.println();
        System.out.println("稀疏数组为:");
        for (int[] row : sparseArray) {
            for (int element : row) {
                System.out.printf("%d\t", element);
            }
            System.out.println();
        }

复制代码

打印结果如下:

在这里插入图片描述

3.3 将稀疏数组保存到本地的txt文件中

 //将稀疏数组存入到文件中
        File file = new File("e:\\array.txt");  //存放数组数据的文件
        try {
            FileWriter out = new FileWriter(file);  //文件写入流
            //将数组中的数据写入到文件中。每行各数据之间用TAB间隔
            for(int i=0;i<sparseArray.length;i++){
                for(int j=0;j<3;j++){
                    out.write(sparseArray[i][j]+"\t");
                }
                out.write("\r\n");
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("存入文件时出现异常:"+e.getMessage().toString());
        }

复制代码

此时在本地的e盘下我们会发现多了一个array.txt文件,打开这个文件,发现存储正确。

在这里插入图片描述
哈哈,到此模拟 棋局的保存 功能就完成了。

3.4 从本地txt文件中读取数据,并转化为对应的稀疏数组。

 /**
         * 从txt文件中读取数据
         */
        File txtFile = new File("e:\\array.txt");
        int[][] txtSparseArr = new int[3][3];
        try {
            String line;//存放每行的数据
            int row = 0;//记录行数
            if (txtFile.exists()) {
                BufferedReader in = new BufferedReader(new FileReader(txtFile));
                while ((line = in.readLine()) != null) {
                    String[] temp = line.split("\t");
                    for (int j = 0; j < temp.length; j++) {
                        txtSparseArr[row][j] = Integer.parseInt(temp[j]);
                    }
                    row++;
                }
            } else {
                System.out.println("没有找到文件");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }

        /**
         * 验证一下
         */
        System.out.println();
        System.out.println("txt中得到的稀疏数组:");
        for (int[] lineData : txtSparseArr) {
            for (int ele : lineData) {
                System.out.printf("%d\t", ele);
            }
            System.out.println();
        }

复制代码

打印结果如下:

在这里插入图片描述

3.5 将稀疏数组恢复为原始数组

具体思路: a. 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 int[][] gobangArray2 = new int[11][11]。 b. 在读取稀疏数组后几行的数据,并赋给 原始的二维数组 即可。

 /**
         * 根据稀疏数组恢复棋局
         * 遍历稀疏数组的每行,给新棋局进行赋值
         */
        int row1 = txtSparseArr[0][0];
        int column1 = txtSparseArr[0][1];
        int[][] gobangArray2 = new int[row1][column1];
        for (int i = 1; i < txtSparseArr.length; i++) {//需从第二行开始
            int row2 = txtSparseArr[i][0];
            int column2 = txtSparseArr[i][1];
            int value = txtSparseArr[i][2];
            gobangArray2[row2][column2] = value;
        }

        System.out.println();
        System.out.println("复局后的新棋盘");
        for (int[] row : gobangArray2) {
            for (int element : row) {
                System.out.printf("%d\t", element);
            }
            System.out.println();
        }

复制代码

打印结果如下:

在这里插入图片描述
这样 “恢复棋局” 功能也实现了。

思考:如果不知道txt中二维数组的行、列数呢?该如何处理?

我的想法是把txt中的每行数据都装进一个ArrayList中,这样ArrayList.size就是行数,每个行的内容进行拆分后形成的数组的长度就是列数。这样就可以创建稀疏数组了,然后遍历,把数据放入稀疏数组中。这样也可以把txt文件转换为二维数组了。 这个只是自己笨拙的思考,如果大佬有好的方法,希望可以告诉我一下哈。

 File file5 = new File("e:\\array.txt");
        ArrayList<String> txtData = new ArrayList<>();
        try {
            String line;
            if (file5.exists()) {
                BufferedReader in = new BufferedReader(new FileReader(file5));
                while ((line = in.readLine()) != null) {
                    txtData.add(line);
                }
            } else {
                System.out.println("没有找到文件");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }

        if (txtData != null && txtData.size() > 0) {
            String[] firstLine = txtData.get(0).split("\t");
            int rows = txtData.size();//得到行数
            int columns = firstLine.length;//得到列数
            int[][] sparseArray3 = new int[rows][columns];
            for (int i = 0; i < txtData.size(); i++) {
                String[] oneLine = txtData.get(i).split("\t");
                //如果数组 sparseArray3 和 onLine 中的元素类型相同,则只要写此行就可以了
//                sparseArray3[i] = oneLine;
                for (int j = 0; j < oneLine.length; j++) {
                    sparseArray3[i][j] = Integer.parseInt(oneLine[j]);
                }
            }

            System.out.println();
            System.out.println("新方式得到的稀疏数组222:");
            for (int[] lineData : sparseArray3) {
                for (int ele : lineData) {
                    System.out.printf("%d\t", ele);
                }
                System.out.println();
            }
        }
复制代码

打印结果如下:

在这里插入图片描述

关注下面的标签,发现更多相似文章
评论