+稀疏数组【黑马java培训】

更新时间:2019年07月26日 11时15分24秒来源:黑马程序员论坛

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));
        }
    }
}

推荐了解热门学科

java培训	Python人工智能	Web前端培训	PHP培训
区块链培训	影视制作培训	C++培训	产品经理培训
UI设计培训	新媒体培训	产品经理培训	Linux运维
大数据培训	智能机器人软件开发

传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。

黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会）	零起点打开Java世界的大门
C++\| 匠心之作从0到1入门学编程	PHP\|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript	软件测试入门到精通

全国中心

+稀疏数组【黑马java培训】

相关阅读