稀疏数组

Anonymous 收录于 go

2023-09-19 2023-09-19 约 225 字预计阅读 2 分钟

概念

当一个数组大部分元素为0，或则为同一个值的数组时，可以使用稀疏数组来保存该数组。

处理方法

记录数组一共有几行几列，有多少个不同的值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

案例图

运用（五子棋存档）

实现

package main

import "fmt"

// main 五子棋棋盘存档-稀疏数组实现存储
func main() {
	// 先定义一个11*11的二维数组，0表示没有棋子，1-表示黑子，2表示白子
	var chessArr [11][11]int
	// 将第二行的第三列设置为黑子，第三行第五列设置为白子
	chessArr[1][2] = 1
	chessArr[2][3] = 2

	// 输出二维棋盘
	for i := 0; i < len(chessArr); i++ {
		for j := 0; j < len(chessArr[i]); j++ {
			fmt.Printf("%d\t", chessArr[i][j])
		}
		fmt.Println()
	}

	// 二维数组转稀疏数组
	// 1、先遍历棋盘，将有棋孽数组计数
	var count int
	for i := 0; i < len(chessArr); i++ {
		for j := 0; j < len(chessArr[i]); j++ {
			if chessArr[i][j] != 0 {
				count++
			}
		}
	}

	// 2. 创建一个稀疏数组（切片）
	var sparseArr = make([][3]int, count+1)
	// 3.将数据存入第一行
	sparseArr[0][0] = len(chessArr)    // 存储原始数组的行数
	sparseArr[0][1] = len(chessArr[0]) // 存储原始数组的列数
	sparseArr[0][2] = count            // 存储非零元素的个数

	// 4. 将数据存入第一行放入
	var row int
	for i := 0; i < len(chessArr); i++ {
		for j := 0; j < len(chessArr[i]); j++ {
			if chessArr[i][j] != 0 {
				row++
				sparseArr[row][0] = i
				sparseArr[row][1] = j
				sparseArr[row][2] = chessArr[i][j]
			}
		}
	}
	// 5. 输出稀疏数组sparseArr
	for i := 0; i < len(sparseArr); i++ {
		fmt.Println(sparseArr[i])
	}

	// 6.根据稀疏数组还原二维数组
	chessArr2 := make([][]int, sparseArr[0][0])
	for i := 0; i < sparseArr[0][0]; i++ {
		chessArr2[i] = make([]int, sparseArr[0][1])
	}
	for i := 1; i < len(sparseArr); i++ {
		chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]
	}
	for _, row := range chessArr2 {
		for _, value := range row {
			fmt.Printf("%d\t", value)
		}
		fmt.Println()
	}
}