Go稀疏数组实现与示例

Go语言中的稀疏数组

稀疏数组(Sparse Array)是一种高效存储大量空白数据的数组结构。它在需要存储大量默认值(通常是0或空值)的情况下非常有用，因为它只存储非默认值的元素及其位置信息，从而大大减少内存使用。
概念

稀疏数组的核心思想是只记录以下信息：

• 原始数组的行数和列数
  
• 非默认值的元素数量
  
• 每个非默认值的行索引、列索引和值
  

Go实现示例

下面是一个完整的Go稀疏数组实现示例：

1. package main
3. import "fmt"
5. // ValNode 定义一个三元组结构体，存储稀疏数组的非零值
6. type ValNode struct {
7.         Row int // 行
8.         Col int // 列
9.         Val int // 值
10. }
12. func main() {
13.         // 1. 先创建一个原始数组
14.         var chessMap [11][11]int
15.         chessMap[1][2] = 1 // 黑子
16.         chessMap[2][3] = 2 // 蓝子
18.         // 2. 输出原始数组
19.         fmt.Println("原始数组:")
20.         for _, row := range chessMap {
21.                 for _, val := range row {
22.                         fmt.Printf("%d ", val)
23.                 }
24.                 fmt.Println()
25.         }
27.         // 3. 转为稀疏数组
28.         var sparseArr []ValNode
29.         // 首先记录数组的维度(11行11列)和非零值数量
30.         defaultVal := 0
31.         nonZeroCount := 0
32.         for i, row := range chessMap {
33.                 for j, val := range row {
34.                         if val != defaultVal {
35.                                 nonZeroCount++
36.                                 node := ValNode{
37.                                         Row: i,
38.                                         Col: j,
39.                                         Val: val,
40.                                 }
41.                                 sparseArr = append(sparseArr, node)
42.                         }
43.                 }
44.         }
45.        
46.         // 头部存储数组信息(行、列、默认值)
47.         header := ValNode{
48.                 Row: len(chessMap),
49.                 Col: len(chessMap[0]),
50.                 Val: defaultVal,
51.         }
52.         sparseArr = append([]ValNode{header}, sparseArr...)
54.         // 4. 输出稀疏数组
55.         fmt.Println("\n稀疏数组:")
56.         for i, node := range sparseArr {
57.                 if i == 0 {
58.                         fmt.Printf("头部: %d 行 %d 列 默认值=%d\n", node.Row, node.Col, node.Val)
59.                 } else {
60.                         fmt.Printf("%d: %d %d %d\n", i, node.Row, node.Col, node.Val)
61.                 }
62.         }
64.         // 5. 将稀疏数组恢复为原始数组
65.         var newChessMap [11][11]int
66.         for i, node := range sparseArr {
67.                 if i == 0 { // 跳过头部信息
68.                         continue
69.                 }
70.                 newChessMap[node.Row][node.Col] = node.Val
71.         }
73.         // 6. 输出恢复后的数组
74.         fmt.Println("\n恢复后的数组:")
75.         for _, row := range newChessMap {
76.                 for _, val := range row {
77.                         fmt.Printf("%d ", val)
78.                 }
79.                 fmt.Println()
80.         }
81. }

复制代码

输出示例

运行上述代码会得到类似以下输出：

1. 原始数组:
2. 0 0 0 0 0 0 0 0 0 0 0
3. 0 0 1 0 0 0 0 0 0 0 0
4. 0 0 0 2 0 0 0 0 0 0 0
5. 0 0 0 0 0 0 0 0 0 0 0
6. 0 0 0 0 0 0 0 0 0 0 0
7. 0 0 0 0 0 0 0 0 0 0 0
8. 0 0 0 0 0 0 0 0 0 0 0
9. 0 0 0 0 0 0 0 0 0 0 0
10. 0 0 0 0 0 0 0 0 0 0 0
11. 0 0 0 0 0 0 0 0 0 0 0
12. 0 0 0 0 0 0 0 0 0 0 0
14. 稀疏数组:
15. 头部: 11 行 11 列 默认值=0
16. 1: 1 2 1
17. 2: 2 3 2
19. 恢复后的数组:
20. 0 0 0 0 0 0 0 0 0 0 0
21. 0 0 1 0 0 0 0 0 0 0 0
22. 0 0 0 2 0 0 0 0 0 0 0
23. 0 0 0 0 0 0 0 0 0 0 0
24. 0 0 0 0 0 0 0 0 0 0 0
25. 0 0 0 0 0 0 0 0 0 0 0
26. 0 0 0 0 0 0 0 0 0 0 0
27. 0 0 0 0 0 0 0 0 0 0 0
28. 0 0 0 0 0 0 0 0 0 0 0
29. 0 0 0 0 0 0 0 0 0 0 0
30. 0 0 0 0 0 0 0 0 0 0 0

复制代码

应用场景

稀疏数组常用于：

• 棋盘类游戏的数据存储（如五子棋）
  
• 图像处理（存储大量空白像素的图像）
  
• 大规模矩阵计算（很多元素为0的矩阵）
  
• 数据库索引存储
  

这种数据结构在存储空间昂贵或数据传输受限的场景下特别有用。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！