go语言之专业数据结构与算法
20.4 稀疏 sparsearray 数组
20.4.1 先看一个实际的需求
编写的五子棋程序中，有存盘退出和续上盘的功能
稀疏数组的处理方法是 :
1) 记录数组一共有几行几列，有多少个不同的值
2) 思想：把具有不同值的元素的行列及值记录在一个小规模的数组中，从而 缩小程序 的规模
20.4.4 应用实例
1) 使用稀疏数组，来保留类似前面的二维数组 ( 棋盘、地图等等 )
2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3) 整体思路分析
4) 代码实现
package mainimport "fmt"type ValNode struct {row intcol intval int
}func main() {//1. 先创建一个原始数组var chessMap [11][11]intchessMap[1][2] = 1 // 黑子chessMap[2][3] = 2 // 蓝子//2. 输出看看原始的数组for _, v := range chessMap {for _, v2 := range v {fmt.Printf("%d\t", v2)}fmt.Println()}//3. 转成稀疏数组。想-> 算法// 思路//(1). 遍历 chessMap, 如果我们发现有一个元素的值不为 0，创建一个 node 结构体//(2). 将其放入到对应的切片即可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)}//将这个稀疏数组，存盘 d:/chessmap.data//如何恢复原始的数组//1. 打开这个 d:/chessmap.data => 恢复原始数组.//2. 这里使用稀疏数组恢复// 先创建一个原始数组var chessMap2 [11][11]int// 遍历 sparseArr [遍历文件每一行]for i, valNode := range sparseArr {if i != 0 {//跳过第一行记录值chessMap2[valNode.row][valNode.col] = valNode.val}}// 看看 chessMap2 是不是恢复fmt.Println("恢复后的原始数据......")for _, v := range chessMap2 {for _, v2 := range v {fmt.Printf("%d\t", v2)}fmt.Println()}
}
PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
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 %!d(MISSING)
1:1 2 1 %!d(MISSING)
2:2 3 2 %!d(MISSING)
恢复后的原始数据......
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 对老师的稀疏数组的改进
1) 将构建的稀疏数组，存盘 chessmap.data
2) 在恢复原始二维数组，要求从文件 chessmap.data 读取。
20.5 队列 (queue)
20.5.1 队列的应用场景
20.5.3 数组模拟队列
先完成一个非环形的队列 ( 数组来实现 )
思路分析：
代码实现：
package mainimport ("errors""fmt""os"
)//使用一个结构体管理队列
type Queue struct {maxSize intarray [5]int // 数组=>模拟队列front int // 表示指向队列首rear int // 表示指向队列的尾部
}//添加数据到队列
func (this *Queue) AddQueue(val int) (err error) {//先判断队列是否已满if this.rear == this.maxSize-1 { //重要重要的提示; rear 是队列尾部(含最后元素)return errors.New("queue full")}this.rear++ // rear 后移this.array[this.rear] = valreturn
}//从队列中取出数据
func (this *Queue) GetQueue() (val int, err error) {//先判断队列是否为空if this.rear == this.front { //队空return -1, errors.New("queue empty")}this.front++val = this.array[this.front]return val, err
}//显示队列, 找到队首，然后到遍历到队尾
func (this *Queue) ShowQueue() {fmt.Println("队列当前的情况是:")//this.front 不包含队首的元素for i := this.front + 1; i <= this.rear; i++ {fmt.Printf("array[%d]=%d\t", i, this.array[i])}fmt.Println()
}//编写一个主函数测试，测试
func main() {//先创建一个队列queue := &Queue{maxSize: 5, front: -1, rear: -1,}var key stringvar val intfor {fmt.Println("1. 输入 add 表示添加数据到队列")fmt.Println("2. 输入 get 表示从队列获取数据")fmt.Println("3. 输入 show 表示显示队列")fmt.Println("4. 输入 exit 表示退出")fmt.Scanln(&key)switch key {case "add":fmt.Println("输入你要入队列数")fmt.Scanln(&val)err := queue.AddQueue(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列ok")}case "get":val, err := queue.GetQueue()if err != nil {fmt.Println(err.Error())} else {fmt.Println("从队列中取出了一个数=", val)}case "show":queue.ShowQueue()case "exit":os.Exit(0)}}
}
PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
1
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
add
输入你要入队列数
1
加入队列ok
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
get
从队列中取出了一个数= 1
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
4. 输入 exit 表示退出程序
show
队列当前的情况是:1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
队列当前的情况是:
exit status 0xc000013a
PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
add
输入你要入队列数
1
加入队列ok
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
get
从队列中取出了一个数= 1
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
show
队列当前的情况是:1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出程序
exit
PS D:\Workspace\Go\src\projects\gin-demo> 对上面代码的小结和说明 ：
1 ） 上面代码实现了基本队列结构，但是 没有有效的利用数组 空间
2 ） 请思考，如何使用数组 实现一个环形的队列
20.5.4 数组模拟环形队列
分析思路 :
1) 什么时候表示队列满 (tail + 1) % maxSize hea d
2) tail == head 表示空
3) 初始化时， tail = 0 head = 0
4) 怎么统计该队列有多少个元素 (tail + maxSize - head ) % maxSize
代码实现 ：
package mainimport ("errors""fmt""os"
)//使用一个结构体管理环形队列
type CircleQueue struct {maxSize int // 4array [5]int // 数组head int // 指向队列队首 0tail int // 指向队尾
}//如队列 AddQueue(push) GetQueue(pop)
//入队列
func (this *CircleQueue) Push(val int) (err error) {if this.IsFull() {return errors.New("queue full")}//分析出 this.tail 在队列尾部，但是包含最后的元素this.array[this.tail] = val // 把值给尾部this.tail = (this.tail + 1) % this.maxSizereturn
}//出队列
func (this *CircleQueue) Pop() (val int, err error) {if this.IsEmpty() {return 0, errors.New("queue empty")}//取出,head 是指向队首，并且含队首元素val = this.array[this.head]this.head = (this.head + 1) % this.maxSizereturn
}//显示队列
func (this *CircleQueue) ListQueue() {fmt.Println("环形队列情况如下：")//取出当前队列有多少个元素size := this.Size()if size == 0 {fmt.Println("队列为空")}//设计一个辅助的变量，指向 headtempHead := this.headfor i := 0; i < size; i++ {fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])tempHead = (tempHead + 1) % this.maxSize}fmt.Println()
}//判断环形队列为满
func (this *CircleQueue) IsFull() bool {return (this.tail+1)%this.maxSize == this.head
}//判断环形队列是空
func (this *CircleQueue) IsEmpty() bool {return this.tail == this.head
}//取出环形队列有多少个元素
func (this *CircleQueue) Size() int {//这是一个关键的算法.return (this.tail + this.maxSize - this.head) % this.maxSize
}//编写一个主函数测试，测试
func main() {//先创建一个队列queue := &CircleQueue{maxSize: 5, head: 0, tail: 0,}var key stringvar val intfor {fmt.Println("1. 输入 add 表示添加数据到队列")fmt.Println("2. 输入 get 表示从队列获取数据")fmt.Println("3. 输入 show 表示显示队列")fmt.Println("4. 输入 exit 表示退出程序")fmt.Scanln(&key)switch key {case "add":fmt.Println("输入你要入队列数")fmt.Scanln(&val)err := queue.Push(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列ok")}case "get":val, err := queue.Pop()if err != nil {fmt.Println(err.Error())} else {fmt.Println("从队列中取出了一个数=", val)}case "show":queue.ListQueue()case "exit":os.Exit(0)}}
}
PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
add
输入你要入队列数
1
加入队列ok
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
add
输入你要入队列数
4
加入队列ok
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
add
输入你要入队列数
7
加入队列ok
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
show
环形队列情况如下：
arr[0]=1 arr[1]=4 arr[2]=7
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
get
从队列中取出了一个数= 1
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
get
从队列中取出了一个数= 4
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
get
从队列中取出了一个数= 7
1. 输入 add 表示添加数据到队列
2. 输入 get 表示从队列获取数据
3. 输入 show 表示显示队列
4. 输入 exit 表示退出
exit![[最大距离的最小值]路标设置](/images/no-images.jpg)
