数据结构和算法-01

稀疏数组

简介

当一个数组中的元素大部分为0(或者其他相同类型的值)，或者同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

案例

需求

example

代码实现

原始数组转稀疏数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


package main

import (
	"bufio"
	"encoding/json"
	"fmt"
	"os"
)

type NodeValue struct {
	Row    int
	Column int
	Value  int
}

func NewNodeValue(row int, col int, val int) *NodeValue {
	return &NodeValue{
		Row:    row,
		Column: col,
		Value:  val,
	}
}

func main() {
	// 创建一个原始数组
	var chessMap [11][11]int
	chessMap[1][2] = 1 // 黑子
	chessMap[2][3] = 2 // 白子

	// 查看原始数组
	for _, v1 := range chessMap {
		for _, v2 := range v1 {
			fmt.Printf("%v ", v2)
		}
		fmt.Println()
	}

	// 转换成稀疏数组
	// 思路：
	// 	1. 创建一个代表数组中特殊值的结构体，每发现一个，即创建对应位置的结构体
	//  2. 将结构体放入到切片中组成新的数组
	var sparseArr []NodeValue

	// 加入用于恢复原始数组的相关数据
	sparseArr = append(sparseArr, *NewNodeValue(11, 11, 0))
	for r, v1 := range chessMap {
		for c, v2 := range v1 {
			if v2 != 0 {
				mem := NewNodeValue(r, c, v2)
				sparseArr = append(sparseArr, *mem)
			}
		}
	}
	fmt.Println(sparseArr)

	// 将稀疏数组存盘（这种数据可以存放在客户端本地，方便读取）
	filepath := "path/to/chessMap.data"
	file, _ := os.OpenFile(filepath, os.O_CREATE|os.O_WRONLY, 0666)
	data, _ := json.Marshal(&sparseArr)

	writer := bufio.NewWriter(file)
	writer.Write(data)

	writer.Flush()
	
	file.Close()
}

稀疏数组转原始数组

代码接上面的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


	// 恢复成原始数组
	var recoverArr []NodeValue
	data, _ = os.ReadFile(filepath)
	json.Unmarshal(data, &recoverArr)

	var chessMap2 [11][11]int
	for i := 1; i < len(recoverArr); i++ {
		chessMap2[recoverArr[i].Row][recoverArr[i].Column] = recoverArr[i].Value
	}
	for _, v1 := range chessMap2 {
		for _, v2 := range v1 {
			fmt.Printf("%v ", v2)
		}
		fmt.Println()
	}