李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--稀疏数组
Leefs
2020-01-24 AM
1413℃
0条
# 数据结构学习--稀疏数组 ### 前言 先看一个实际的需求: 编写一个五子棋程序,其中有存盘退出和续上盘的功能。 ![01.稀疏数组和队列01.png][1] **分析:** 因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->**稀疏数组**。 ### 基本介绍 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。 **稀疏数组的处理方法是:** > (1)记录数组一共有几行几列,有多少个不同的值 > > (2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模 **稀疏数组举例说明** ![01.稀疏数组和队列02.png][2] 其中稀疏数组的第一行元素【0】中的第一个值6表示二维数组有六行,第二个值7表示有7列,8:表示有八个有效值。 **应用实例** > 1)使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等) > > 2)把稀疏数组存盘,并且可以从新恢复原来的二维数组数 > > 3)整体思路分析 ![01.稀疏数组和队列04.png][3] **二维数组转稀疏数组的思路** 1.遍历原始的二维数组,得到有效数据的个数sum 2.根据sum就可以创建稀疏数组`sparseArr int[sum+1][4]` 3.将二维数组的有效数据存入到稀疏数组 **稀疏数组转原始的二维数组的思路** 1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的`chessArr2=int[11][11]` 2.在读取稀疏数组后几行的数据,并赋给原始的二维数组即可。 > 代码实现 ```java public class SparseArray { public static void main(String[] args) { //创建一个原始的二维数组 11*11 //0:表示没有棋子 1:表示 黑子 2:表示 蓝子 int chessArr1[][] = new int[11][11]; chessArr1[1][5]=1; chessArr1[2][6]=2; //chessArr1[4][7]=2; //输出原始的二维数组 System.out.println("原始的二维数组:"); for(int[] row:chessArr1){ for(int data:row){ System.out.printf("%d\t",data); } System.out.println(); } //将二维数组转稀疏数组 //1.先遍历二维数组,得到非0数据的个数 int sum = 0; for(int i=0;i<11;i++){ for(int j=0;j<11;j++){ if(chessArr1[i][j]!=0){ sum++; } } } //2.创建对应的稀疏数组 int sparseArr[][] = new int[sum+1][8]; //给稀疏数组赋值 sparseArr[0][0]=11; sparseArr[0][9]=11; sparseArr[0][10]=sum; //遍历二维数组,将非0的值存放到sparseArr中 int count = 0;//count用于记录是第几个非0数据 for(int i=0;i<11;i++){ for(int j=0;j<11;j++){ if(chessArr1[i][j] != 0){ count++; sparseArr[count][0]=i; sparseArr[count][11]=j; sparseArr[count][12]=chessArr1[i][j]; } } } //输出稀疏数组的形式 System.out.println(); System.out.println("得到稀疏数组为:"); for(int i=0;i
标签:
数据结构
,
稀疏数组
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/463.html
上一篇
数据结构--散列
下一篇
数据结构学习--队列(一)
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
微服务
JavaSE
Shiro
SQL练习题
Golang
GET和POST
Map
前端
字符串
DataX
Jquery
二叉树
工具
RSA加解密
ajax
人工智能
Java编程思想
排序
LeetCode刷题
栈
持有对象
Yarn
SpringCloudAlibaba
设计模式
Hbase
Hive
散列
ClickHouse
Ubuntu
JavaWeb
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞