存储方式

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