数据结构与算法之稀疏数组

温馨提示：

本文最后更新于 2023-3-1，已超过半年没有更新，若内容或图片失效，请留言反馈。

概念

当一个数组中存储了大量为0或者大量相同的数时, 为了缩小程序的规模, 我们可以使用稀疏数组来保存该数组。

处理方式是 通过记录数组一共有几行几列, 有多少个不同的值, 把具有不同值的元素的 行列值 记录在一个小规模数组(稀疏数组)中, 从而缩小程序的规模。

如果不太好理解，这里就举个最经典的五子棋场景。在编写一个五子棋的程序当中，要实现存盘退出和续上盘的功能。如下图所示: 存在一个棋盘, 退出保存的时候应该怎么存储呢? 使用一个二维数组, 1表示红棋, 2表示黑棋, 0表示没有下过的棋。因为该二维数组的大部分值都是默认的0, 因此记录了很多没有意义的数据, 这个时候就可以使用到 稀疏数组。

实现思路

步骤一

创建二维数组作为源数据, 我们看下源数据效果:

步骤二

遍历原始的二维数组, 将源数据中的有效数据转换为稀疏数组, 并把总行数、总列数和默认值也作为一个元素写入到稀疏数组第一个元素位置。可以看到, 实际有效数据有7个, 但是会产生8个元素, 用来记录总行总列。

步骤三

将稀疏数组复原为源数据, 先单独处理第一行, 创建原始的默认二维数组, 然后再读取稀疏数组中的其他行数据并赋值给二维数组即可。

废话不多说, 直接上代码(Go语言编写)

package main

import (
    "fmt"
)

/******* 稀疏数组 - 五子棋案例 *******/

const (
    ROW = 11
    COL = 11
)

var (
    classmap [ROW][COL]int
)

type nodeval struct {
    row int
    col int
    val interface{}
}

func main()  {
    // 输出原始数据
    originalData()

    // 转换为稀疏数组存档
    sparsearray := transformationSparseArrayStorage()

    // 转换为原始数据
    transformationOriginalData(sparsearray)
}

// 原始数据
func originalData()  {
    classmap[1][3] = 2
    classmap[2][3] = 1
    classmap[5][2] = 1
    classmap[6][8] = 2
    classmap[7][3] = 1
    classmap[4][5] = 1
    classmap[6][6] = 2

    // 查看数据
    for _, v := range classmap {
        for _, v1 := range v {
            fmt.Printf("%d\t", v1)
        }

        fmt.Println()   // 换行输出, 避免影响数据显示
    }

    // 输出:
    /**
        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       1       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       1       0       0       0       0       0
        0       0       1       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       2       0       2       0       0
        0       0       0       1       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
    */
}

// 转换为稀疏数组存档
func transformationSparseArrayStorage() []nodeval {
    // 转为稀疏数组 (这里使用切片实现)
    var sparsearray []nodeval
    // 创建数据模型
    sparsearray = append(sparsearray, nodeval{
        row: ROW,
        col: COL,
        val: 0,
    })
    // 存档
    for row, val := range classmap {
        for col, val1 := range val {
            if val1 == 0 {
                continue
            }

            // 加入到切片
            sparsearray = append(sparsearray, nodeval{
                row: row,
                col: col,
                val: val1,
            })
        }
    }

    fmt.Println(sparsearray)    // 此数据可存档入文件、缓存、数据库等, 输出: [{11 11 0} {1 3 2} {2 3 1} {4 5 1} {5 2 1} {6 6 2} {6 8 2} {7 3 1}]

    return sparsearray
}

// 转换为原始数据
func transformationOriginalData(sparsearray []nodeval) {
    var arr [][]int
    for key, nv := range sparsearray {
        var v int
        switch nv.val.(type) {
        case int:
            v = nv.val.(int)
        default:
        }

        if key == 0 {
            // 制作原始表格初始数据
            for i := 0; i < nv.row; i++ {
                var temp []int
                for j := 0; j < nv.col; j++ {
                    temp = append(temp, v)
                }

                arr = append(arr, temp)
            }

            // fmt.Println(arr)
            /**
                [
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                    [0 0 0 0 0 0 0 0 0 0 0]
                ]
            */
        } else {
            // 棋盘数组内容赋值
            arr[nv.row][nv.col] = v
        }
    }

    // 输出数据
    for _, v := range arr {
        for _, v1 := range v {
            fmt.Printf("%d\t", v1)
        }

        fmt.Println()   // 换行输出, 避免影响数据显示
    }
    /**
        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       1       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       1       0       0       0       0       0
        0       0       1       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       2       0       2       0       0
        0       0       0       1       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
        0       0       0       0       0       0       0       0       0       0       0
    */
}