开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-原始数组转稀疏数组(一)】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/627/detail/9829
数据结构和算法-原始数组转稀疏数组(一)
内容简介:
一、应用实例
二、代码实现
一、应用实例
看一个具体的案例,第一步使用稀疏数组来保存类似前面的二维数组,比如棋盘或者地图等等,第二步把稀疏数组存盘,把它存在文件里去,并且可以重新恢复原来的二维数组,
整体的思路分析如图所示:
这是一个二维数组,11乘11的,那么要把它做成一个稀疏数组的话,思路是这样的:
比如这是一个稀疏数组,就记录了1和2,比如1是一行,二列是一个1,然后2是第二行第三列,就记录下来了,当然了要做一个标准的稀疏数组,它应该还要记录这个值,就是它一共有11行11列,然后其他值应该是零,标志性输出稀疏数组,它首先进入一共有11行有11列,默认值为零,把它记录下来,但是,对于这个 Go 语言而言,这个11如果把它重新恢复成二维数组的话,这个11意义不是特别大,因为有个问题,就是它在进行定义一个数组的时候,必须把那个写死,所以要恢复的话,可能得想办法把它做成一个切片性质的,那就意义不大了,所以说,如果是公务员,这两个值就是行和列有多少个,意义不是特别大,但是也可以把它记录下来,按照一个标准的稀疏数组应该把它记录下来,这样子现在就来把它完成了。
二、代码实现
(1)二维数组代码实现
首先打开 VSCode ,然后新建一个章节称之为 chapter20 ,在其内新建一个文件夹称为 sparsearry ,再在其内新建一个文件称为 main.go ,并输入以下代码:
package main
import (
“
fmt
”
)
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()
}
}
先看原始数组长什么样子,打开 D 盘,找到刚才写的这段代码所在的目录 chapter20 ,然后取出数组,接下来运行一下上述代码,结果如下:
(2)转换成稀疏数组
可以看到当前这个二维数组,长得就跟我们想的很像,有一个1有一个2,那么这个时候发现这样不合理,因为如果原先按照这个方式去存盘,它一共有11乘以11个数据,规模比较大,那现在要把它转成稀疏数组,怎么把它转成一个稀疏数组?
显然,事先并不知道它有多少个有效数据,那在 go 语言里面,只能使用切片,因为并不知道它有一个1和2,如果用切片应该怎么保存比较好?
最好的一种设计方式就是直接用一个结构体就可以了,需注意,结构体仍然是可以做成一个数组的,因为在一个切片里面放有多个结构体实例,它就是一个结构体的一种切片,那切片的本质还是一个数组,所以这个是没有问题的,这个就叫大家去想怎么做,这个就叫算法,这个算法好像很神秘的样子,算法可以说是无处不在,比如说将来在实现购物编程的时候,别人让你去把近十天前十个浏览的商品给我拍到上面去,你写一段代码,这个也叫算法,只是有些算法,它是一些常规算法,即都认同的一种算法,比如说语音识别算法、比如像人工智能的图像识别、语音识别、图像识别,还有文字识别,那些是比较有名的算法,都认同的有些算法是在工作实际开发中去解决一个小问题,设计的一个解决方案,也叫算法,那么算法怎么做?
//思路
//(1).遍历 chessMap ,如果我们发现有一个元素的值不为0,创建一个 node 结构体
//(2).将其放入到对应的切片即可
这时的问题在于结构体要怎么设计?显然这个结构体,至少应该有三个字段,一个是行,一个是列,输入以下代码:
type ValNode struct {
row int
col int
val int
}
(3)切片代码实现
结构体设计就好了,定好了过后,个切片就可以把它定下来,现在先做一个切片,输入以下代码:
var sparseArr []ValNode
for i, v := range chessMap {
for j, v2 := range v {
if v2 != 0 {
//创建一个 ValNode 值结点
valNode = ValNode[
row : i,
col : j,
val : v2,
}
}
}
}