go 实现稀疏数组

向右看齐 2021-07-24 23:03 395阅读 0赞

# 一 需求 #

## 1 编写的五子棋程序中，有存盘退出和续上盘的功能。 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 2 用元素二维数组存储的问题 ##

因为二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据。

# 二  点睛 #

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

稀疏数组的处理方式如下。

**1 记录数组一共有几行几列，有多少个不同的值。**

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

# 三 稀疏数组举例说明 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

# 四 分析 #

## 1 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)。 ##

## 2 将稀疏数组恢复成原来的二维数组数。 ##

## 3 整体思路 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2][]

# 五 代码 #

package main
    
    import (
       "fmt"
    )
    
    type ValNode struct {
       row int
       col int
       val int
    }
    
    func main() {
       // 1 先创建一个原始数组
       var chessMap [11][11]int
       chessMap[1][2] = 1 // 黑子
       chessMap[2][3] = 2 // 白子
       // 2 输出看看原始数组
       for _, v := range chessMap {
          for _, v2 := range v {
             fmt.Printf("%d\t", v2)
          }
          fmt.Println()
       }
       // 3 转成稀疏数组
       // 思路：
       // a 遍历 chessMap, 如果发现有一个元素的值不为0，创建一个 node 结构体
       // b 将其放入到对应的切片即可
       var sparseArr []ValNode
       // 标准的稀疏数组还有一个记录元素的二维数组的规模(行、列和默认值)。
       // 创建一个 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 值结点
                valNode := ValNode{
                   row: i,
                   col: j,
                   val: v2,
                }
                sparseArr = append(sparseArr, valNode)
             }
          }
       }
       // 输出稀疏数组
       fmt.Println(":::::当前的稀疏数组是:::::")
       for i, valNode := range sparseArr {
          fmt.Printf("%d: %d %d %d\n", i, valNode.row, valNode.col, valNode.val)
       }
       // 使用稀疏数组恢复成原始数组
       // 先创建一个原始数组
       var chessMap2 [11][11]int
       // 遍历 sparseArr
       for i, valNode := range sparseArr {
          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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/e304948f4f16445d9104daa5f739fb27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/8578f809ac30485cbececfa7aa9f2226.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2]: /images/20210724/a18a26ad03a6478b9eca7032b47d5e1a.png