1. 稀疏数组
稀疏数组（sparsearray）
基本介绍： 当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
本质上就是压缩数组。
稀疏数组的处理方法：
1. 记录数组一共有几行几列，有多少个不同的值。
2. 把具有不同值的元素的行列以及值，记录在一个小规模的数组中，从而缩小程序的规模。
1.1 实际问题（棋盘）
如下面的二维数组，我们可以假设成是一个棋盘，1代表白子，2代表黑子，现在我们要对其进行存盘以及续盘的操作，如果我们将整个数组都存起来，势必会造成内存的浪费，那么我们可以考虑使用稀疏数组来解决这个问题。
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1.1.1 存盘
func writeSparse() { // 定义一个结构体，用来存放稀疏矩阵的值 type ValNode struct{ row int // 所在行 col int // 所在列 val int // 值 } // 定义一个二维数组——棋盘 // 其他都为0 var chessMap [11][11]int chessMap[1][2] = 1 chessMap[2][3] = 2 // 定义一个切片 var sparseArr []ValNode // 11行 11列 默认值为0 valNode := ValNode{ row: 11, col: 11, val: 0, } sparseArr =append(sparseArr,valNode) // 遍历棋盘，寻找有棋子的地方 for i, v:= range chessMap{ for j, v2:=range v{ if v2 != 0{ // 拿到黑子和白子具体的位置 valNode := ValNode{ row: i, col: j, val: v2, } sparseArr =append(sparseArr,valNode) } } } // 存到文件中 便于续盘 filePath := "./数据结构/sparseArr.txt" file, err := os.OpenFile(filePath,os.O_WRONLY|os.O_CREATE,0666) // 第一个数字代表u(拥有者)权限， // 第二个数字代表g(群组)权限， // 第三个数字代表o(其他人)权限 // 每一个数字都是通过4（表示r）,2（表示w）,1（表示x）三个数字相加得到的 // rwx 对应4，2，1 // 那么只读的权限用4表示[r--]， // 读写用6（4+2）表示[rw-], // 读写加执行用7（4+2+1）表示[rwx]。 if err != nil{ fmt.Println("os.OpenFile err:",err) return } // 最终 关闭流 defer file.Close() // 创建写缓冲区 writer := bufio.NewWriter(file) // 取出棋子 for _, valNode:=range sparseArr{ str:=fmt.Sprint(valNode.row,valNode.col,valNode.val) // 写到缓存区中 _, err := writer.WriteString(str+"\n") if err != nil{ fmt.Println("writer.WriteString(str) err:",err) return } } // 刷新数据, 将缓冲区数据写入io writer writer.Flush() }
1.1.2 续盘
func readSparse() { type ValNode struct { row int col int val int } var sparseArr []ValNode filePath := "./数据结构/sparseArr.txt" file, err := os.Open(filePath) if err != nil { fmt.Println("os.Open(filePath) err:", err) return } defer file.Close() // 创建读缓冲区 reader := bufio.NewReader(file) // 读取信息 for{ // 读取delim之前的所有string数据 str,err := reader.ReadString('\n') if err==io.EOF { // io.EOF代表文件的末尾 break } fmt.Println(str) // 返回将字符串按照空白 //（unicode.IsSpace确定， 可以是一到多个连续的空白字符） // 分割的多个字符串。 // 如果字符串全部是空白或者是空字符串的话，会返回空切片。 arr := strings.Fields(str) valNode := ValNode{} for i, _ := range arr { in,err := strconv.Atoi(arr[i]) if err != nil { return } // arr 中 第一个位置是row 第二个位置是col 第三个位置是val switch i { case 0: valNode.row = in case 1: valNode.col = in case 2: valNode.val = in } } sparseArr = append(sparseArr,valNode) } // 棋盘 var chessMap [][]int //var chessMap [11][11]int for i, v := range sparseArr { if i == 0 { for a := 0; a < v.row; a++ { mm := make([]int, v.col) chessMap = append(chessMap, mm) } } else { chessMap[v.row][v.col] = v.val } } fmt.Println(chessMap) }
