数据结构：稀疏数组

定义

稀疏固定有3列。

第一行为记录二维数组信息：第一行第一个元素为二维数组的行，第一行第二个元素为二维数组的列，第一行第三个元素为二维数组的非0个数。

第二行开始为二维数组的坐标信息，即：第一个元素记录第几行，第二个元素记录第几列，第三个元素记录数值为多少。

二维数组

0   10  0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   20  0   0   0   0   0   0   0   
0   0   0   0   30  0   0   0   0   0   0   
0   0   0   0   0   40  0   0   0   0   0   
0   0   0   0   0   0   50  0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   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  5   
0   1   10  
2   3   20  
3   4   30  
4   5   40  
5   6   50  

二维数组转稀疏数组

func main() {
    // Two-dimensional array
    var tda [11][11]int

    tda[0][1] = 10
    tda[2][3] = 20

    // 保存非0个数
    count := 0
    for _, arr := range tda {
        for _, value := range arr {
            fmt.Printf("%d\t", value)
            if value > 0 {
                count++
            }
        }
        fmt.Println()
    }

    fmt.Println("--------------------------")

    // 初始化稀疏数组
    var sparseArray = make([][3]int, count+1)

    sparseArray[0][0] = len(tda)
    sparseArray[0][1] = len(tda[0])
    sparseArray[0][2] = count

    // 记录稀疏数组行数
    index := 0
    for row, arr := range tda {
        for column, value := range arr {
            if value > 0 {
                index++ // 从第二行开始记录具体的非0值的坐标
                sparseArray[index][0] = row
                sparseArray[index][1] = column
                sparseArray[index][2] = value
            }
        }
    }

    // 打印稀疏数组
    for _, array := range sparseArray {
        for _, value := range array {
            fmt.Printf("%d\t", value)
        }
        fmt.Println()
    }

}

稀疏数组转二维数组

func main() {

    // 根据稀疏数组第一行第一个元素初始化二维数组的行
    // Golang无法使用 make([][sparseArray[0][1]]int, ...)
    tda2 := make([][]int, sparseArray[0][0])

    // 初始化二维数组
    for i := range tda2 {
        tda2[i] = make([]int, sparseArray[0][1])
    }

    for row, array := range sparseArray {
        // 第一行保存的是二维数组的行和列以及非0的个数，跳过
        if row > 0 {
            tda2[array[0]][array[1]] = array[2]
        }
    }

    // 打印输出
    for _, array := range tda2 {
        for _, value := range array {
            fmt.Printf("%d\t", value)
        }
        fmt.Println()
    }

}