稀疏数组(go语言实现)

稀疏数组使用场景

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

稀疏数组处理方法

稀疏数组一般n行，3列，第一列表示原先二维数组的行，第二列表示原先二维数组的列，第三列表示值。
稀疏数组的第一行，一般用来表示原先二维数组的总行数以及总列数，值可以定义一个原先二维数组中不可能产生的值，比如-1,0。

简单的例子

原二维数组看做棋盘，白子为1，黑子为2。
稀疏数组第一行表示了”棋盘大小”为*77**，值为0，该值只是用于甄别其他有效值。
稀疏数组第二行至第四行表示了”棋盘”内白子黑子的分布，顺序为从上到下，从左到右。
可以将行和列看为x轴和y轴。

二维数组矩阵用稀疏数组表示(go语言思路)

每一个棋子有三个属性，x轴坐标，y轴坐标，颜色。一个棋子的属性可以用结构体来表示。
稀疏数组由于存在长度不确定性，所以使用切片的方式来表示。
稀疏数组的第一个元素围棋盘布局。

go代码对二维数组压缩保存为稀疏数组

package main

import "fmt"

func main() {
	// 定义一个7*7的二维数组, 将黑子白子进行赋值.
	var chessMap [7][7]int
	chessMap[1][1] = 1
	chessMap[2][2] = 2
	chessMap[2][4] = 1
	chessMap[5][3] = 2

	// 打印原始数据
	for _,v := range chessMap {
		for _,v2 := range v {
			fmt.Printf("%d\t",v2)
		}
		fmt.Printf("\n")
	}

	// 用稀疏数组表示
	/* 每一个棋子都有三个属性
		1. x轴位置
		2. y轴位置
		3. 棋子颜色
		这三个属性可以使用结构体来表示
		然后将结构体依次append进数组中, 就可以作为一个稀疏数组了.
	 */

	 // 定义一个存放棋子属性的结构体
	 type chess struct {
	 	axisX int
	 	axisY int
	 	value int
	 }

	 // 定义一个存放棋子结构体的切片
	 var chessSparseMap []chess

	 // chessSparseMap稀疏数组第一行定义x,y和value
	 firstLine := chess{
	 	axisX: 7,
	 	axisY: 7,
	 	value: 0,
	 }

	 chessSparseMap = append(chessSparseMap, firstLine)

	 // 对原始数据进行遍历, 然后将获取到有数值内容的值,存储到chess结构体中, 并且将该结构体append到chessSparseMap里面.
	for k,v := range chessMap {
		for k2,v2 := range v {
			if v2 != 0 {
				tmpChess := chess{
					axisX:k,
					axisY:k2,
					value:v2,
				}
				chessSparseMap = append(chessSparseMap, tmpChess)
			}
		}
	}
	fmt.Println("稀疏数组为")
	fmt.Println(chessSparseMap)

}


output:

0	0	0	0	0	0	0	
0	1	0	0	0	0	0	
0	0	2	0	1	0	0	
0	0	0	0	0	0	0	
0	0	0	0	0	0	0	
0	0	0	2	0	0	0	
0	0	0	0	0	0	0	
稀疏数组为
[{7 7 0} {1 1 1} {2 2 2} {2 4 1} {5 3 2}]

稀疏数组还原为二维数组

package main

import (
	"fmt"
	"os"
	"bufio"
	"io"
	"strings"
	"strconv"
)

func main() {
	// 定义单个棋子的属性, x, y, value
	type chess struct {
		axisX int
		axisY int
		value int
	}

	// 定义一个7*7数组
	var chessMap [7][7]int

	// 读取sparseMap文件
	file, err := os.Open("./learn-go/数据结构/1.稀疏数组/sparseMap")
	defer file.Close()
	if err != nil {
		fmt.Println("打开异常")
		return
	}

	reader := bufio.NewReader(file)
	for {
		content, err := reader.ReadString('\n')
		if err != nil {
			fmt.Println("内容读取完毕")
			break
		}

		if err == io.EOF {
			break
		}
		contentSlice := strings.Split(content," ")

		axisX, err := strconv.Atoi(contentSlice[0])
		if err != nil {
			fmt.Println("axisX转换出错")
			return
		}

		axisY, err := strconv.Atoi(contentSlice[1])
		if err != nil {
			fmt.Println("axisY转换出错")
			return
		}
		// strings.Split(contentSlice[2], "\r\n")[0] value结尾存在\n, 通过Split方法去除\r\n
		value, err := strconv.Atoi(strings.Split(contentSlice[2], "\r\n")[0])
		if err != nil {
			fmt.Println("value转换出错",err)
			return
		}

		if value != 0 {
			// axisX为x轴, axisY为y轴, value为棋子, 1 白子, 2 黑子
			chessMap[axisX][axisY] = value
		}
	}

	for _,v := range chessMap {
		for _, v2 :=range v{
			fmt.Printf("%d \t",v2)
		}
		fmt.Println()
	}
}

output:

0 	0 	0 	0 	0 	0 	0 	
0 	1 	0 	0 	0 	0 	0 	
0 	0 	2 	0 	1 	0 	0 	
0 	0 	0 	0 	0 	0 	0 	
0 	0 	0 	0 	0 	0 	0 	
0 	0 	0 	2 	0 	0 	0 	
0 	0 	0 	0 	0 	0 	0

sparseMap文件内容