温馨提示:
本文最后更新于
2023-3-1,已超过半年没有更新,若内容或图片失效,请留言反馈。
概念
当一个数组中存储了
大量为0或者大量相同的数
时, 为了缩小程序的规模, 我们可以使用稀疏数组来保存该数组。
处理方式是 通过记录数组一共有几行几列, 有多少个不同的值, 把具有不同值的元素的行列值
记录在一个小规模数组
(稀疏数组)中, 从而缩小程序的规模。
如果不太好理解,这里就举个最经典的五子棋场景。在编写一个五子棋的程序当中,要实现存盘退出和续上盘的功能。如下图所示: 存在一个棋盘, 退出保存的时候应该怎么存储呢? 使用一个二维数组, 1表示红棋, 2表示黑棋, 0表示没有下过的棋。 因为该二维数组的大部分值都是默认的0, 因此记录了很多没有意义的数据, 这个时候就可以使用到 稀疏数组
。
实现思路
步骤一
创建二维数组作为源数据, 我们看下源数据效果:
步骤二
遍历原始的二维数组, 将源数据中的有效数据转换为稀疏数组, 并把总行数、总列数和默认值也作为一个元素写入到稀疏数组第一个元素位置。可以看到, 实际有效数据有7个, 但是会产生8个元素, 用来记录总行总列。
步骤三
将稀疏数组复原为源数据, 先单独处理第一行, 创建原始的默认二维数组, 然后再读取稀疏数组中的其他行数据并赋值给二维数组即可。
废话不多说, 直接上代码(Go语言编写)
package main
import (
"fmt"
)
/******* 稀疏数组 - 五子棋案例 *******/
const (
ROW = 11
COL = 11
)
var (
classmap [ROW][COL]int
)
type nodeval struct {
row int
col int
val interface{}
}
func main() {
// 输出原始数据
originalData()
// 转换为稀疏数组存档
sparsearray := transformationSparseArrayStorage()
// 转换为原始数据
transformationOriginalData(sparsearray)
}
// 原始数据
func originalData() {
classmap[1][3] = 2
classmap[2][3] = 1
classmap[5][2] = 1
classmap[6][8] = 2
classmap[7][3] = 1
classmap[4][5] = 1
classmap[6][6] = 2
// 查看数据
for _, v := range classmap {
for _, v1 := range v {
fmt.Printf("%d\t", v1)
}
fmt.Println() // 换行输出, 避免影响数据显示
}
// 输出:
/**
0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 2 0 0
0 0 0 1 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
*/
}
// 转换为稀疏数组存档
func transformationSparseArrayStorage() []nodeval {
// 转为稀疏数组 (这里使用切片实现)
var sparsearray []nodeval
// 创建数据模型
sparsearray = append(sparsearray, nodeval{
row: ROW,
col: COL,
val: 0,
})
// 存档
for row, val := range classmap {
for col, val1 := range val {
if val1 == 0 {
continue
}
// 加入到切片
sparsearray = append(sparsearray, nodeval{
row: row,
col: col,
val: val1,
})
}
}
fmt.Println(sparsearray) // 此数据可存档入文件、缓存、数据库等, 输出: [{11 11 0} {1 3 2} {2 3 1} {4 5 1} {5 2 1} {6 6 2} {6 8 2} {7 3 1}]
return sparsearray
}
// 转换为原始数据
func transformationOriginalData(sparsearray []nodeval) {
var arr [][]int
for key, nv := range sparsearray {
var v int
switch nv.val.(type) {
case int:
v = nv.val.(int)
default:
}
if key == 0 {
// 制作原始表格初始数据
for i := 0; i < nv.row; i++ {
var temp []int
for j := 0; j < nv.col; j++ {
temp = append(temp, v)
}
arr = append(arr, temp)
}
// fmt.Println(arr)
/**
[
[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 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]
]
*/
} else {
// 棋盘数组内容赋值
arr[nv.row][nv.col] = v
}
}
// 输出数据
for _, v := range arr {
for _, v1 := range v {
fmt.Printf("%d\t", v1)
}
fmt.Println() // 换行输出, 避免影响数据显示
}
/**
0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 2 0 0
0 0 0 1 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
*/
}
评论一下?