稀疏数组
与二维数组的比较
由于二维数组大多用于记录，因此大多数元素为0，浪费存储空间。若仅存储不同的部分和默认的值，则将会大幅减少硬盘空间使用量
基本介绍
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是
-
记录数组一共有几行几列,有多少个不同的值
-
把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
举例说明
应用实例
二维转稀疏
-
使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)
-
把稀疏数组存盘,并且可以重新恢复原来的二维数组
-
整体思路分析
-
代码实现
假设有一个棋盘如下
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
package main
import (
"fmt"
)
type ValNode struct {
row int
col int
val int
}
func main() {
// 1. 创建原始数组
var chessMap [11][11]int
chessMap[1][2] = 1 // 黑子
chessMap[2][3] = 2 // 白子
// 2. 输出原始数组
fmt.Println("原始的二维数组是：")
for _, v := range chessMap {
for _, v2 := range v {
fmt.Printf("%d\t", v2)
}
fmt.Println()
}
// 3. 转为稀疏数组（算法）
// 思路
// (1) 遍历chessMap，如果我们发现有一个元素的值不等于0，就创建一个ValNode结构体
// (2) 将其放入对应的切片中即可
var sparseArr []ValNode
// 标准的一个稀疏数组应该还有记录原始二维数组规模（行和列，默认值）
valNode := ValNode{
row: 11,
col: 11,
val: 0,
}
sparseArr = append(sparseArr, valNode)
for i, v := range chessMap {
for j, v2 := range v {
if v2 != 0 {
// 创建一个ValNode值结点
valNode = ValNode{
row: i,
col: j,
val: v2,
}
sparseArr = append(sparseArr, valNode)
}
}
}
// 输出稀疏数组
fmt.Println("当前的稀疏数组是：")
for i, valNode := range sparseArr {
fmt.Printf("%d: %d %d %d\n", i, valNode.row, valNode.col, valNode.val)
}
}
输出：
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 当前的稀疏数组是： 0: 11 11 0 1: 1 2 1 2: 2 3 2
这样我们就把原来11*11的二维数组转换成了3*3的稀疏数组，大幅减少了空间占用
将稀疏数组存盘并恢复
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)
type ValNode struct {
row int
col int
val int
}
func main() {
// ...
// 将这个稀疏数组存盘
filePath := "./chessMap.data"
file, err := os.OpenFile(filePath, os.O_CREATE|os.O_WRONLY, 0666)
if err != nil {
fmt.Println(err)
os.Exit(1)
}
writer := bufio.NewWriter(file)
for _, valNode := range sparseArr {
writer.WriteString(fmt.Sprintf("%d %d %d\n", valNode.row, valNode.col, valNode.val))
}
writer.Flush()
file.Close()
// 4. 读取存盘文件
// 创建一个新的二维数组
var chessMap2 [11][11]int
file, err = os.OpenFile(filePath, os.O_RDONLY, 0666)
if err != nil {
fmt.Println(err)
os.Exit(1)
}
reader := bufio.NewReader(file)
for {
b, _, err := reader.ReadLine()
if err == io.EOF {
break
}
str := string(b)
valNode := strings.Split(str, " ")
row, _ := strconv.Atoi(valNode[0])
col, _ := strconv.Atoi(valNode[1])
val, _ := strconv.Atoi(valNode[2])
if row < 11 && col < 11 { // 跳过第一行
chessMap2[row][col] = val
}
}
// 输出恢复的二维数组
fmt.Println("恢复的二维数组是：")
for _, v := range chessMap {
for _, v2 := range v {
fmt.Printf("%d\t", v2)
}
fmt.Println()
}
}
输出：
原始的二维数组是： 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 当前的稀疏数组是： 0: 11 11 0 1: 1 2 1 2: 2 3 2 恢复的二维数组是： 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
成功恢复！
This post belongs to Column 「算法专栏」 .
0
comments
latest
No comments yet.