稀疏数组

• 先看一个实际的需求

编写的五子棋程序中，有存盘退出和续上盘的功能。

• 分析问题:

因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->稀疏数组

 

基本介绍

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

稀疏数组的处理方法是:

1. 记录数组一共有几行几列，有多少个不同的值
2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

• 稀疏数组举例说明

 

应用实例

1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3. 整体思路分析

1. 代码实现

package com.atguigu.chapter18

 

import scala.collection.mutable.ArrayBuffer

 

object SparseArr {

def main(args: Array[String]): Unit = {

val rowSize = 11

val colSize = 11

//演示一个稀疏数组的使用

val chessMap = Array.ofDim[Int](rowSize, colSize)

//初始化地图

chessMap(1)(2) = 1 // 1 表示黑子

chessMap(2)(3) = 2 // 2 表示白子

 

//输出原始的地图

for (item <- chessMap) {

for (item2 <- item) {

printf("%d ", item2)

}

println()

}

 

//将chessmap转成稀疏数组

// 思路 =》效果是达到对数据的压缩

// class Node (row, col, value)

// ArrayBuffer

 

val sparseArr = ArrayBuffer[Node]()

val node = new Node(rowSize, colSize, 0)

sparseArr.append(node)

for (i <- 0 until chessMap.length) {

for (j <- 0 until chessMap(i).length) {

 

//判断该值是否为0, 如果不为0,就保存

if (chessMap(i)(j) != 0) {

//构建一个 Node

val node = new Node(i, j, chessMap(i)(j))

sparseArr.append(node) //加入到稀疏数组

}

}

}

 

println("--------稀疏数组----------")

//输出稀疏数组

for (node <- sparseArr) {

printf("%d %d %d ", node.row, node.col, node.value)

}

 

//存盘

 

//读盘 -> 稀疏数组

 

//稀疏数组-> 原始数组

 

//读取稀疏数组的第一个节点

val newNode = sparseArr(0)

val rowSize2 = newNode.row

val colSize2 = newNode.col

 

val chessMap2 = Array.ofDim[Int](rowSize2, colSize2)

 

for (i <- 1 until sparseArr.length) {

val node = sparseArr(i)

chessMap2(node.row)(node.col) = node.value

}

 

println("-----------从稀疏数组恢复后的地图---------------")

 

for (item <- chessMap2) {

for (item2 <- item) {

printf("%d ", item2)

}

println()

}

}

}

 

class Node(val row: Int, val col: Int, val value: Int)

　　

课后练习

　　要求：

1. 在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data
2. 恢复原来的数组时，读取map.data 进行恢复