A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

1. 数据结构【逻辑层面】
  • 数据结构包括:线性结构 和 非线性结构
A. 线性结构
  • 线性结构作为做最常用的数据结构,其特点是数据元素之间存在一对一的先行关系
  • 线性结构有两种不同的存储结构,即【顺序存储】和【链式存储】
    • 顺序存储的线性表成为顺序表,顺序表钟的存储元素是连续的
    • 链式存储的线性表成为链表,链表钟的存储元素不一定是连续的,元素节点钟存放数据元素以及相邻元素的地址信息
  • 线性结构常见的有:数组,队列,链表,栈
B. 非线性结构
  • 非线性结构包括:二维数组,多为数组,广义表,树结构,图结构
2. 稀疏数组(SparseArray)的应用场景
  • 编写五子棋的程序中,有【存盘退出】和【继续上盘】的功能
    • 我们使用二维数组记录棋盘

[AppleScript] 纯文本查看 复制代码
0  0  0  0  0  0  0  0  0  0  0
0  1  0  0  0  0  0  0  0  0  0
0  0  2  0  0  0  0  0  0  0  0
0  0  0  0  1  0  0  0  0  0  0
0  0  0  0  0  0  0  2  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0

  • 因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据
    • 我们使用【稀疏数组】来存储

A. 稀疏数组基本介绍
  • 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组
  • 稀疏数组的处理方法:
    • 记录数组一共有几行几列,有多少个不同的值
    • 吧具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
      • 小规模的数组 --> 稀疏数组


[AppleScript] 纯文本查看 复制代码
[6 X 7 = 42]              
0  0  0  22 0  0  15      
0  11 0  0  0  17 0       
0  0  0  -6 0  0  0       
0  0  0  0  0  39 0       
91 0  0  0  0  0  0       
0  0  28 0  0  0  0 

[AppleScript] 纯文本查看 复制代码
[9 * 3 = 27]
   | 行 | 列 | 值 |
   |row |col |val |
---|----|----|----|
[0]| 6  | 7  | 8  | # 第一行第一列记录着【行】【列】【一共有多少个值】
---|----|----|----|
[1]| 0  | 3  | 22 | # 第0行第3列的值为22
[2]| 0  | 6  | 15 | # 第0行第6列的值为15
[3]| 1  | 1  | 11 | # 第1行第1列的值为11
[4]| 1  | 5  | 17 | # .....
[5]| 2  | 3  | -6 |
[6]| 3  | 5  | 39 |
[7]| 4  | 0  | 91 |
[8]| 5  | 2  | 28 |

  • 由 6 X 7 的数组转成 9 X 3 的稀疏数组
B. 应用实例
  • 使用稀疏数组,来保留类似前面的二位数组(棋盘,地图等)
  • 把稀疏数组存盘,并且可以重新恢复原来的二位数组
C. 代码实现
  • 二维数组 -> 稀疏数组 -> 二维数组
[AppleScript] 纯文本查看 复制代码
"二维数组 -> 稀疏数组 -> 二维数组"
public class SparseArray {
    public static void main(String[] args) {
        "创建一个原始的二维数组 【11 X 11】"
        "0 表示没有棋子,1表示黑子,2表示蓝子"
        int[][] chessArray = new int[11][11];
        chessArray[1][2] = 1; // 1 个黑子
        chessArray[2][3] = 2; // 1 个蓝子
        "打印棋盘"
        for (int[] arr : chessArray) {
            System.out.println(Arrays.toString(arr));
        }
        "转稀疏数组"
        System.err.println("---------------------------------");
        "遍历二维数组获取非零个数"
        int totalCount = 0;
        for (int[] arr : chessArray) {
            for (int ele : arr) if (ele != 0) totalCount++;
        }
        "创建稀疏数组"
        int[][] sparseArray = new int[totalCount + 1][3];
        sparseArray[0][0] = chessArray.length;      // 行
        sparseArray[0][1] = chessArray[0].length;   // 多少列
        sparseArray[0][2] = totalCount;             // 有多少个元素

        int count = 1;
        outer:
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray[i].length; j++) {
                if (chessArray[i][j] != 0) {
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = chessArray[i][j];
                    if (++count == totalCount + 1) {
                        System.err.println("all element had put into sparseArray");
                        break outer;
                    }
                }
            }
        }
        "打印稀疏数组"
        for (int[] arr : sparseArray) {
            System.out.println(Arrays.toString(arr));
        }

        System.err.println("---------------------------------");
        int[][] resultArr = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            int row = sparseArray[i][0];
            int col = sparseArray[i][1];
            int val = sparseArray[i][2];
            resultArr[row][col] = val;
        }
        for (int[] arr : resultArr) {
            System.out.println(Arrays.toString(arr));
        }
    }
}




0 个回复

您需要登录后才可以回帖 登录 | 加入黑马