Go稀疏数组实现与示例
Go语言中的稀疏数组稀疏数组(Sparse Array)是一种高效存储大量空白数据的数组结构。它在需要存储大量默认值(通常是0或空值)的情况下非常有用，因为它只存储非默认值的元素及其位置信息，从而大大减少内存使用。
概念
稀疏数组的核心思想是只记录以下信息：
[*]原始数组的行数和列数
[*]非默认值的元素数量
[*]每个非默认值的行索引、列索引和值
Go实现示例
下面是一个完整的Go稀疏数组实现示例：
package main
import "fmt"
// ValNode 定义一个三元组结构体，存储稀疏数组的非零值
type ValNode struct {
Row int // 行
Col int // 列
Val int // 值
}
func main() {
// 1. 先创建一个原始数组
var chessMap int
chessMap = 1 // 黑子
chessMap = 2 // 蓝子
// 2. 输出原始数组
fmt.Println("原始数组:")
for _, row := range chessMap {
for _, val := range row {
fmt.Printf("%d ", val)
}
fmt.Println()
}
// 3. 转为稀疏数组
var sparseArr []ValNode
// 首先记录数组的维度(11行11列)和非零值数量
defaultVal := 0
nonZeroCount := 0
for i, row := range chessMap {
for j, val := range row {
if val != defaultVal {
nonZeroCount++
node := ValNode{
Row: i,
Col: j,
Val: val,
}
sparseArr = append(sparseArr, node)
}
}
}
// 头部存储数组信息(行、列、默认值)
header := ValNode{
Row: len(chessMap),
Col: len(chessMap),
Val: defaultVal,
}
sparseArr = append([]ValNode{header}, sparseArr...)
// 4. 输出稀疏数组
fmt.Println("\n稀疏数组:")
for i, node := range sparseArr {
if i == 0 {
fmt.Printf("头部: %d 行 %d 列 默认值=%d\n", node.Row, node.Col, node.Val)
} else {
fmt.Printf("%d: %d %d %d\n", i, node.Row, node.Col, node.Val)
}
}
// 5. 将稀疏数组恢复为原始数组
var newChessMap int
for i, node := range sparseArr {
if i == 0 { // 跳过头部信息
continue
}
newChessMap = node.Val
}
// 6. 输出恢复后的数组
fmt.Println("\n恢复后的数组:")
for _, row := range newChessMap {
for _, val := range row {
fmt.Printf("%d ", val)
}
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
稀疏数组:
头部: 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应用场景
稀疏数组常用于：
[*]棋盘类游戏的数据存储（如五子棋）
[*]图像处理（存储大量空白像素的图像）
[*]大规模矩阵计算（很多元素为0的矩阵）
[*]数据库索引存储
这种数据结构在存储空间昂贵或数据传输受限的场景下特别有用。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 懂技术并乐意极积无私分享的人越来越少。珍惜
页:
[1]