Golang 稀疏数组

Jackey Golang 290 次浏览 , 没有评论

实际需求

编写的五子棋程序中,有存盘退出和续上盘的功能

如果按照原始的方式来存储二维数组,因为该二维数组很多值是默认值0,因此记录了很多没有意义的数据。

基本介绍

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

稀疏数组的处理方法是:

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

应用实例

使用稀疏数组来保留类似前面的二维数组(棋盘、地图等),把稀疏数组存盘,并且可以重新恢复原来的二维数组。

实现思路:

代码实现

package main

import (
  "bufio"
  "fmt"
  "io"
  "os"
  "strconv"
  "strings"
)

type ValNode struct {
  Row int
  Col int
  Val int
}

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

  // 输出查看原始的数组
  for _, v := range chessMap {
    for _, v2 := range v {
      fmt.Printf("%d\t", v2)
    }
    fmt.Println()
  }

  // 转成稀疏数组
  // 遍历chessMap ,如果发现有一个元素的值不为0,创建一个node结构体,将其放入到对应的切片即可
  var sparseArr []ValNode
  // 标准的一个稀疏数组应该还有一个记录元素的二维数组的规模(行、列、默认值)
  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 值节点
        valNode2 := ValNode{
          Row: i,
          Col: j,
          Val: v2,
        }
        sparseArr = append(sparseArr, valNode2)
      }
    }
  }

  // 输出稀疏数组
  fmt.Println("当前的稀疏数组是::::::")
  for i, valNode := range sparseArr {
    fmt.Printf("%d: %d %d %d\n", i, valNode.Row, valNode.Col, valNode.Val)
  }

  // 将稀疏数组存盘 /mnt/chessmap.data
  filePath := "/tmp/chessmap.data"
  file, _ := os.OpenFile(filePath, os.O_WRONLY|os.O_CREATE, 0666)
  defer file.Close()

  writer := bufio.NewWriter(file)
  for _, val := range sparseArr {
    writeString := fmt.Sprintf("%d %d %d\n", val.Row, val.Col, val.Val)
    writer.WriteString(writeString)
  }
  writer.Flush()

  // 打开文件 chessmap.data 恢复原始数组
  var fileConentArr []ValNode
  fileOpen, _ := os.Open(filePath)
  defer file.Close()
  reader := bufio.NewReader(fileOpen)
  for {
    str, err := reader.ReadString('\n')
    if err == io.EOF {
      break
    }
    strArr := strings.Split(str, " ")
    if len(strArr) == 3 {
      strArr[2] = strings.Replace(strArr[2], "\n", "", -1) // 将最后的换行符去掉
      row, _ := strconv.Atoi(strArr[0])
      col, _ := strconv.Atoi(strArr[1])
      val, _ := strconv.Atoi(strArr[2])
      valNode := ValNode{
        Row: row,
        Col: col,
        Val: val,
      }
      fileConentArr = append(fileConentArr, valNode)
    }
  }

  // 使用稀疏数组恢复数据
  var chessMap2 [11][11]int
  for i, valNode := range fileConentArr {
    if i != 0 { // 跳过第一行记录纸,因为第一行是记录的数组大小
      chessMap2[valNode.Row][valNode.Col] = valNode.Val
    }
  }

  // 查看恢复是否正确
  fmt.Println("恢复后的数据。。。。。")
  for _, v := range chessMap2 {
    for _, v2 := range v {
      fmt.Printf("%d\t", v2)
    }
    fmt.Println()
  }
}

输出结果:

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       
当前的稀疏数组是::::::
0: 11 11 0
1: 1 2 1
2: 2 3 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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Go