Go语言实现稀疏数组：存储优化与五子棋存盘还原

package main

import (
	"fmt"
)

// ValNode 用于存储稀疏数组中的每一行数据
type ValNode struct {
	row int
	col int
	val int
}

func main() {
	// 1. 创建一个原始数组 (11x11 棋盘)
	var chessMap [11][11]int
	chessMap[1][2] = 1 // 1表示黑子
	chessMap[2][3] = 2 // 2表示蓝子

	// 2. 输出看看原始的数组
	fmt.Println("原始数组:")
	for _, v1 := range chessMap {
		for _, v2 := range v1 {
			fmt.Printf("%d\t", v2)
		}
		fmt.Println()
	}

	// 3. 转成稀疏数组
	var sparseArr []ValNode

	// 标准的一个稀疏数组应该还有一个记录元素的二维数组的规模（行和列）
	// 这里我们约定：sparseArr[0] 存放原始数组的总行数、总列数 和 有效元素个数
	// 但在本例简化逻辑中，我们先存放行和列，有效个数可以在遍历时统计，
	// 或者按照图示逻辑，先占位。这里采用更通用的做法：
	// 第一行记录: 行, 列, 有效值总数(稍后填入，此处先放0或临时计算)
	
	// 为了简单演示，我们假设已知有效个数为2，或者动态扩展。
	// 下面代码采用动态append的方式，最后再调整第一行或直接利用len()-1作为有效数
	
	valNode := ValNode{
		row: 11,
		col: 11,
		val: 0, // 暂存有效个数，实际应在遍历后修正，或放在独立变量
	}
	sparseArr = append(sparseArr, valNode)

	for i1, v1 := range chessMap {
		for i2, v2 := range v1 {
			if v2 != 0 {
				// 创建一个ValNode 值结点
				valNode = ValNode{
					row: i1,
					col: i2,
					val: v2,
				}
				sparseArr = append(sparseArr, valNode)
			}
		}
	}

	// 更新第一行，使其正确反映有效元素的数量
	// 此时 sparseArr 的长度减去头部的一个元素，即为有效元素个数
	if len(sparseArr) > 0 {
		sparseArr[0].val = len(sparseArr) - 1
	}

	// 输出稀疏数组
	fmt.Println("当前的稀疏数组是:::::")
	for i, node := range sparseArr {
		fmt.Printf("%d：%d %d %d \n", i, node.row, node.col, node.val)
	}

	// 4. 恢复原始数组
	// 思路：根据稀疏数组重建二维数组
	var chessMap2 [11][11]int

	// 跳过稀疏数组的第一行（元数据），从第二行开始读取有效数据
	for index, node := range sparseArr {
		if index == 0 {
			continue
		}
		chessMap2[node.row][node.col] = node.val
	}

	// 验证恢复结果
	fmt.Println("恢复后的数组:")
	for _, value1 := range chessMap2 {
		for _, value2 := range value1 {
			fmt.Printf("%d \t", value2)
		}
		fmt.Println()
	}
}