第一章 稀疏数组

基本介绍

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

稀疏数组的处理方式是：

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

比如有下面这个数组：

我们可以看到该数组中有大量重复元素0，那么我们可以采用如下的方法进行存储。

我们重新定义一个n3的数组，其中n的看有多少值。第一行存储行数和列数以及默认值，如上是5行5列默认值是0，后续存储的就是具体的行列以及其对应的值。这样以来，我们就将55的数组压缩成了8*3。

继续看下面这个例子：

思路如下：

1. 遍历二维数组（棋盘），将有不为0的值保存到稀疏数组中
2. 遍历稀疏数组，将其保存到文件中
3. 从文件中读取将其恢复成二维数组（棋盘）

代码如下：
（1）存盘

package main
import (
    "fmt"
    "os"
)
type node struct {
    row int
    col int
    value int
}
func main(){
    // 创建原始数据
    var chess [11][11]int
    chess[1][2] = 1
    chess[2][3] = 2
    // 打印一下原棋盘
    for _, v :=range chess{
        for _,v2 := range v{
            fmt.Printf("%d ",v2)
        }
        fmt.Println()
    }
    // 将原始数据的行列以及默认值保存到第一个位置
    var ret []node
    n := node{
        row:   11,
        col:   11,
        value: 0,
    }
    ret = append(ret,n)
    // 遍历原始数组，将值不为0的存进去
    for i, v :=range chess{
        for j,v2 := range v{
            if v2 != 0{
                node := node{
                    row:   i,
                    col:   j,
                    value: v2,
                }
                ret = append(ret,node)
            }
        }
        fmt.Println()
    }
    // 将结果保存到文件中
    file, err := os.OpenFile("./chess.data", os.O_CREATE|os.O_APPEND|os.O_RDWR, 0644)
    if err != nil {
        fmt.Println("open file failed. err:",err)
        return
    }
    defer file.Close()
    for _,v := range ret{
        s := fmt.Sprintf("%d %d %d \n",v.row,v.col,v.value)
        _, err := file.WriteString(s)
        if err != nil {
            fmt.Println("write data failed.err:",err)
        }
    }
}

（2）恢复

package main
import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)
type node struct {
    row int
    col int
    value int
}
func  main()  {
    // 将结果保存到文件中
    file, err := os.Open("../digui/chess.data")
    if err != nil {
        fmt.Println("open file failed. err:",err)
        return
    }
    defer file.Close()
    reader := bufio.NewReader(file)
    count := 0
    var chessMap [11][11]int
    for{
        line ,err:= reader.ReadString('\n')
        if err == io.EOF{
            break
        }
        if err != nil {
            fmt.Println("read file failed. err:",err)
        }
        count ++
        if count != 1{
            line = strings.Trim(line,"\n")
            split := strings.Split(line, " ")
            i,_ := strconv.Atoi(split[0])
            j,_:=strconv.Atoi(split[1])
            value,_:=strconv.Atoi(split[2])
            chessMap[i][j] = value
        }
    }
    // 打印一下原棋盘
    for _, v :=range chessMap{
        for _,v2 := range v{
            fmt.Printf("%d ",v2)
        }
        fmt.Println()
    }
}