存储方式

  1. 普通存储

  2. 链式存储

    1. 普通链式存储
    2. 行式链式存储
    3. 十字链式存储

      基本介绍

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

  3. 记录数组一共有几行几列，有多少个不同的值

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

案例需求

image.png
问题： 存盘退出、续上盘
image.png
保存行和列：
image.png
image.png

代码

这里为了数据转化方便，我存放数据采用的是 map切片，
image.png
image.png

  1. // sparseArr 落盘数据
  2. 11    11    0
  3. 1    2    1
  4. 2    3    2
  6. // sparseArrObj 序列化后落盘数据
  7. [{"col":11,"row":11,"val":0},{"col":2,"row":1,"val":1},{"col":3,"row":2,"val":2}]

思考：

应不应该考虑写入文件的数据量大小？稀松数组

  1. chessMap     [[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 
  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]]
  3. sparseArr    [{11 11 0} {1 2 1} {2 3 2}]
  4. sparseArrObj [map[col:11 row:11 val:0] map[col:2 row:1 val:1] map[col:3 row:2 val:2]]
  1. // 稀疏数组 - 保留棋盘
  2. package main
  4. import (
  5.     "bufio"
  6.     "encoding/json"
  7.     "fmt"
  8.     "io"
  9.     "os"
  10. )
  12. type ValNode struct {
  13.     row int
  14.     col int
  15.     val int // int
  16. }
  18. func main() {
  19.     // 1. 原始数组, 二维数组
  20.     var chessMap [11][11]int
  21.     chessMap[1][2] = 1 // 1 - 黑子
  22.     chessMap[2][3] = 2 // 1 - 蓝子
  23.     chessMap[5][5] = 2 // 1 - 蓝子
  25.     // 2. 输出看看原始的数组
  26.     for _, v := range chessMap {
  27.         for _, v2 := range v {
  28.             fmt.Printf("%d \t", v2)
  29.         }
  30.         fmt.Println()
  31.     }
  33.     // 3. 转成新数组 - 稀疏数组
  34.     // 遍历数组，把值不为0的，创建一个 ValNode 结构体实例， 然后放入对应的切片
  36.     // 定义切片
  37.     var sparseArrObj []map[string]int
  39.     // 标准的稀疏数组，含有记录二维数组的规模
  40.     var obj map[string]int = make(map[string]int)
  41.     obj["row"] = 11
  42.     obj["col"] = 11
  43.     obj["val"] = 0
  44.     sparseArrObj = append(sparseArrObj, obj)
  45.     fmt.Println("sparseArrObj", sparseArrObj)
  47.     for row, v := range chessMap {
  48.         for col, v2 := range v {
  49.             if v2 != 0 {
  50.                 var obj map[string]int = make(map[string]int)
  51.                 obj["row"] = row
  52.                 obj["col"] = col
  53.                 obj["val"] = v2
  54.                 sparseArrObj = append(sparseArrObj, obj)
  55.             }
  56.         }
  57.     }
  59.     // 4. 输出稀疏数组
  60.     fmt.Println("map切片：")
  61.     for i, _map := range sparseArrObj {
  62.         fmt.Printf("%d: %d\t%d\t%d\n", i, _map["row"], _map["col"], _map["val"])
  63.     }
  65.     // 存盘退出 续上盘
  66.     // 5. 存盘 ： 稀松数组保存到文件 chessmap.data
  67.     fmt.Println("存盘数据, 'd:/chessmap.data'")
  68.     filepath := "d:/chessmap.data"
  69.     file, err := os.OpenFile(filepath, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0666)
  70.     if err != nil {
  71.         fmt.Println("打开文件失败")
  72.         return
  73.     }
  74.     defer func() {
  75.         err = file.Close()
  76.         if err != nil {
  77.             fmt.Println("关闭文件错误")
  78.         }
  79.     }()
  80.     // 写入数据, 带缓冲， writer.Flush()
  81.     writer := bufio.NewWriter(file)
  83.     // 5.1 序列化数据，存入文件，
  84.     data, err := json.Marshal(sparseArrObj)
  85.     if err != nil {
  86.         fmt.Println("序列化失败", err)
  87.         return
  88.     }
  89.     fmt.Println("sparseArrObj 序列化后： ", string(data))
  91.     writer.WriteString(string(data))
  92.     // 缓存落盘
  93.     writer.Flush()
  95.     // 6. 续上盘 ：读取 chessmap.data 文件，遍历每一行， 恢复数组
  96.     _file, err := os.OpenFile(filepath, os.O_RDWR|os.O_APPEND, 0666)
  97.     if err != nil {
  98.         fmt.Println("打开文件失败")
  99.         return
  100.     }
  102.     // 6.1 读取内容
  103.     fmt.Println("文件读取输出")
  104.     var oldData string
  105.     reader := bufio.NewReader(_file)
  106.     for {
  107.         // 读到一个换行就结束
  108.         oldData, err = reader.ReadString('\n')
  109.         // 输出内容
  110.         fmt.Println("oldData=", oldData)
  111.         if err == io.EOF {
  112.             // 读到一行末尾
  113.             break
  114.         }
  115.     }
  116.     // 6.2 反序列化
  117.     var _sparseArrObj []map[string]int
  118.     err = json.Unmarshal([]byte(oldData), &_sparseArrObj)
  119.     if err != nil {
  120.         fmt.Println("反序列化失败", err)
  121.         return
  122.     }
  123.     fmt.Println("反序列化结果： ", _sparseArrObj)
  125.     // 7. 还原原始数组, 这里写死数组元素的个数， 应该使用切片，
  126.     var newChessMap [11][11]int
  127.     for i, _map := range _sparseArrObj {
  128.         if i != 0 {
  129.             newChessMap[_map["row"]][_map["col"]] = _map["val"]
  130.         }
  131.     }
  132.     // 7.1 输出原始数组
  133.     fmt.Println("======================")
  134.     for _, v := range newChessMap {
  135.         for _, v2 := range v {
  136.             fmt.Printf("%d \t", v2)
  137.         }
  138.         fmt.Println()
  139.     }
  140.     fmt.Println("======================")
  142. }
  1. 0       0       0       0       0       0       0       0       0       0       0 
  2. 0       0       1       0       0       0       0       0       0       0       0 
  3. 0       0       0       2       0       0       0       0       0       0       0 
  4. 0       0       0       0       0       0       0       0       0       0       0 
  5. 0       0       0       0       0       0       0       0       0       0       0
  6. 0       0       0       0       0       2       0       0       0       0       0
  7. 0       0       0       0       0       0       0       0       0       0       0
  8. 0       0       0       0       0       0       0       0       0       0       0
  9. 0       0       0       0       0       0       0       0       0       0       0
  10. 0       0       0       0       0       0       0       0       0       0       0
  11. 0       0       0       0       0       0       0       0       0       0       0
  12. sparseArrObj [map[col:11 row:11 val:0]]
  13. map切片：
  14. 0: 11   11      0
  15. 1: 1    2       1
  16. 2: 2    3       2
  17. 3: 5    5       2
  18. 存盘数据, 'd:/chessmap.data'
  19. sparseArrObj 序列化后：  [{"col":11,"row":11,"val":0},{"col":2,"row":1,"val":1},{"col":3,"row":2,"val":2},{"col":5,"row":5,"val":2}]
  20. 文件读取输出
  21. oldData= [{"col":11,"row":11,"val":0},{"col":2,"row":1,"val":1},{"col":3,"row":2,"val":2},{"col":5,"row":5,"val":2}]
  22. 反序列化结果：  [map[col:11 row:11 val:0] map[col:2 row:1 val:1] map[col:3 row:2 val:2] map[col:5 row:5 val:2]]
  23. ======================
  24. 0       0       0       0       0       0       0       0       0       0       0
  25. 0       0       1       0       0       0       0       0       0       0       0
  26. 0       0       0       2       0       0       0       0       0       0       0
  27. 0       0       0       0       0       0       0       0       0       0       0
  28. 0       0       0       0       0       0       0       0       0       0       0
  29. 0       0       0       0       0       2       0       0       0       0       0
  30. 0       0       0       0       0       0       0       0       0       0       0
  31. 0       0       0       0       0       0       0       0       0       0       0
  32. 0       0       0       0       0       0       0       0       0       0       0
  33. 0       0       0       0       0       0       0       0       0       0       0
  34. 0       0       0       0       0       0       0       0       0       0       0
  35. ======================