Go语言-数据结构与算法

go语言之专业数据结构与算法

20.4 稀疏 sparsearray 数组

20.4.1 先看一个实际的需求

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

稀疏数组的处理方法是 :

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

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

20.4.4 应用实例

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

2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数

3) 整体思路分析

4) 代码实现

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. 转成稀疏数组。想-> 算法
	// 思路
	//(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 main

import (
	"errors"
	"fmt"
	"os"
)

//使用一个结构体管理队列
type Queue struct {
	maxSize int
	array   [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] = val
	return
}

//从队列中取出数据
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 string
	var val int
	for {
		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 main

import (
	"errors"
	"fmt"
	"os"
)

//使用一个结构体管理环形队列
type CircleQueue struct {
	maxSize int    // 4
	array   [5]int // 数组
	head    int    // 指向队列队首 0
	tail    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.maxSize
	return
}

//出队列
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.maxSize
	return
}

//显示队列
func (this *CircleQueue) ListQueue() {
	fmt.Println("环形队列情况如下：")
	//取出当前队列有多少个元素
	size := this.Size()
	if size == 0 {
		fmt.Println("队列为空")
	}
	//设计一个辅助的变量，指向 head
	tempHead := this.head
	for 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 string
	var val int
	for {
		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