【数据结构与算法】稀疏数组 sparsearray

【数据结构与算法】稀疏数组 sparsearray

文章目录

​​一、实际应用​​

​​♦ 场景​​​​♦ 分析问题​​

​​二、稀疏数组介绍​​

​​♦ 定义​​​​♦ 稀疏数组的处理方法​​

​​三、应用实例​​

​​♦ 需求分析​​​​♦ 代码实现​​

​​▶创建原始二维数组​​​​▶创建稀疏数组​​​​▶稀疏数组还原成二维数组​​

一、实际应用

♦ 场景

♦ 分析问题

我们将棋盘看成是一个二维的数组，利用数字来代表其中的棋子。因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据 -> 可以利用稀疏数组压缩实现。

​​返回顶部​​

二、稀疏数组介绍

♦ 定义

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

♦ 稀疏数组的处理方法

​​返回顶部​​

三、应用实例

♦ 需求分析

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

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

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

先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的​​chessArr2 = int [11][11]​​在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.

​​返回顶部​​

♦ 代码实现

▶创建原始二维数组

public class SparseArray { public static void main(String[] args) { // 1.创建一个原始的二维数组 11*11 // 0:表示没有棋子；1表示黑子；2表示白子 int[][] chessArr = new int[11][11]; // 2.放置棋子 chessArr[1][2] = 1; chessArr[2][3] = 2; // 遍历输出二维数组 for (int[] row:chessArr){ // 换行 System.out.println(); for (int column:row){ System.out.printf("%d\t",column); } } }}棋盘输出：0 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0

​​返回顶部​​

▶创建稀疏数组

// 4.统计非0值个数 int sum = 0; for (int i=0;i

​​返回顶部​​

▶稀疏数组还原成二维数组

// 8.还原二维数组 // 8.1创建一个原始数组大小的新数组 int row = parseArray[0][0]; int columns = parseArray[0][1]; int[][] chessArray1 = new int[row][columns]; // 8.2将稀疏数组存储的数据还原到新的稀疏数组 for (int i = 1; i < parseArray.length; i++) { // 从稀疏数组中获取二维数组非0值对应的行、列 int pre_row = parseArray[i][0]; int pre_columns = parseArray[i][1]; // 从稀疏数组中获取非0值赋给二维数组 chessArray1[pre_row][pre_columns] = parseArray[i][2]; } // 8.3遍历输出二维数组 for (int[] pre_row : chessArray1) { // 换行 System.out.println(); for (int column : pre_row) { System.out.printf("%d\t", column); } }还原二维数组：0 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0

​​返回顶部​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。