第20章 数据结构

20.1 数据结构(算法)的介绍

【点击观看视频】数据结构和算法的基本介绍

数据结构的介绍

1 ) 数据结构是一门研究算法的学科，只从有了编程语言也就有了数据结构.学好数据结构可以编写

出更加漂亮,更加有效率的代码。

2 ) 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.

3 ) 程序 = 数据结构 +算法

20.2 数据结构和算法的关系

• 算法是程序的灵魂，为什么有些网站能够在高并发，和海量吞吐情况下依然坚如磐石,大家可能会说: 网站使用了服务器群集技术、数据库读写分离和缓存技术(比如Redis等),那如果我再深入的问一句，这些优化技术又是怎样被那些天才的技术高手设计出来的呢?
• 大家请思考一个问题，是什么让不同的人写出的代码从功能看是一样的，但从效率上却有天壤之别, 拿在公司工作的实际经历来说, 我是做服务器的，环境是UNIX，功能是要支持上千万人同时在线， 并保证数据传输的稳定, 在服务器上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公 司的CTO对我的代码进行优化，再次上线，坚如磐石。那一瞬间,我认识到程序是有灵魂的，就是 算法。如果你不想永远都是代码工人,那就花时间来研究下算法吧!
• 本章着重讲解算法的基石-数据结构。

20.3 看几个实际编程中遇到的问题

20.4 稀疏SPARSEARRAY数组

【点击观看视频】数据结构和算法-稀疏数组介绍

【点击观看视频】数据结构和算法-原始数组转稀疏数组

【点击观看视频】数据结构和算法-稀疏数组转原始数组

20.4.1 先看一个实际的需求

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

• 分析按照原始的方式来的二维数组的问题

  因为该二维数组的很多值是默认值 0 , 因此记录了很多没有意义的数据

20.4.2 基本介绍

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:

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

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

20.4.3 稀疏数组举例说明

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()
	}
}

• 对老师的稀疏数组的改进

  1 ) 将构建的稀疏数组，存盘 chessmap.data

  2 ) 在恢复原始二维数组，要求从文件chessmap.data 读取。

20.5 队列(QUEUE)

20.5.1 队列的应用场景

20.5.2 队列介绍

• 队列是一个有序列表，可以用数组或是链表来实现。
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
• 示意图：(使用数组模拟队列示意图)

20.5.3 数组模拟队列

【点击观看视频】数据结构和算法-数组模拟队列分析

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下 其中maxSize是该队列的最大容量
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：

• 先完成一个非环形的队列(数组来实现)

• 当我们将数据存入队列时称为addqueue,addqueue的处理需要有两个步骤

  1)将尾指针往后移：rear+1，front == rear【空】

  2）若尾指引rear小于等于队列的最大下标MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == MaxSize - 1[队列满]

思路分析：

【点击观看视频】数据结构和算法-数组模拟队列实现

代码实现：

package main
import (
	"fmt"
	"os"
	"errors"
)

//使用一个结构体管理队列
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)
		}
	}
}

对上面代码的小结和说明：

1 ） 上面代码实现了基本队列结构，但是没有有效的利用数组空间

2 ） 请思考，如何使用数组 实现一个环形的队列

20.5.4 数组模拟环形队列

【点击观看视频】数据结构和算法-数组模拟环形队列

分析思路:

1 ) 什么时候表示队列满 (tail+ 1 )%maxSize =hed

2 ) tail==head 表示空

3 ) 初始化时， tail= 0 head= 0

4 ) 怎么统计该队列有多少个元素 (tail+maxSize-head)%maxSize

【点击观看视频】数据结构和算法-数组模拟环形队列实现

代码实现：

package main
import (
	"fmt"
	"errors"
	"os"
)

//使用一个结构体管理环形队列
type CircleQueue struct {
	maxSize int // 4
	array [5]int // 数组
	head  int //指向队列队首 0
	tail int  //指向队尾 0
}


//如队列 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)
		}
	}
}

20.6 链表

【点击观看视频】数据结构和算法-单链表的基本介绍

20.6.1 链表介绍

• 链表是有序的列表，但是它在内存中是存储如下

20.6.2 单链表的介绍

• 单链表的示意图：

• 说明：一般来说，为了比较好的对单链表进行增删改查的操作，我们都会给他设置一个头结点, 头结点的作用主要是用来标识链表头， 本身这个结点不存放数据。

20.6.3 单链表的应用实例

【点击观看视频】数据结构和算法-单链表的添加和显示

【点击观看视频】数据结构和算法-单链表有序插入

【点击观看视频】数据结构和算法-单链表的删除

• 案例的说明：

  使用带head头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作， 注: 删除和修改,查找可以考虑学员独立完成

• 第一种方法在添加英雄时，直接添加到链表的尾部

• 代码实现：

package main
import (
	"fmt"
)

//定义一个HeroNode
type HeroNode struct {
	no 		 int
	name 	 string
	nickname string
	next     *HeroNode //这个表示指向下一个结点
}

//给链表插入一个结点
//编写第一种插入方法，在单链表的最后加入.[简单]
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
	//思路
	//1. 先找到该链表的最后这个结点
	//2. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head
	for {
		if temp.next == nil { //表示找到最后
			break
		}
		temp = temp.next // 让temp不断的指向下一个结点
	}

	//3. 将newHeroNode加入到链表的最后
	temp.next = newHeroNode
}

//给链表插入一个结点
//编写第2种插入方法，根据no 的编号从小到大插入..【实用】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
	//思路
	//1. 找到适当的结点
	//2. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head
	flag := true
	//让插入的结点的no，和temp的下一个结点的no比较
	for {
		if temp.next == nil {//说明到链表的最后
			break
		} else if temp.next.no >= newHeroNode.no {
			//说明newHeroNode 就应该插入到temp后面
			break 
		} else if temp.next.no == newHeroNode.no {
			//说明我们额链表中已经有这个no,就不然插入.
			flag = false
			break
		}
		temp = temp.next
	}

	if !flag {
		fmt.Println("对不起，已经存在no=", newHeroNode.no)
		return
	} else {
		newHeroNode.next = temp.next
		temp.next = newHeroNode
	}


}
//删除一个结点
func DelHerNode(head *HeroNode, id int) {
	temp := head
	flag := false
	//找到要删除结点的no，和temp的下一个结点的no比较
	for {
		if temp.next == nil {//说明到链表的最后
			break
		} else if temp.next.no == id {
			//说明我们找到了.
			flag = true
			break
		}
		temp = temp.next
	}
	if flag {//找到, 删除

		temp.next = temp.next.next
	} else {
		fmt.Println("sorry, 要删除的id不存在")
	}
}

//显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {

	//1. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head

	// 先判断该链表是不是一个空的链表
	if temp.next == nil {
		fmt.Println("空空如也。。。。")
		return 
	}
	//2. 遍历这个链表
	for {
		fmt.Printf("[%d , %s , %s]==>", temp.next.no, 
			temp.next.name, temp.next.nickname)
		//判断是否链表后
		temp = temp.next
		if temp.next == nil {
			break
		}
	}
}




func main() {

	//1. 先创建一个头结点, 
	head := &HeroNode{}

	//2. 创建一个新的HeroNode
	hero1 := &HeroNode{
		no : 1,
		name : "宋江",
		nickname : "及时雨",
	}

	hero2 := &HeroNode{
		no : 2,
		name : "卢俊义",
		nickname : "玉麒麟",
	}

	hero3 := &HeroNode{
		no : 3,
		name : "林冲",
		nickname : "豹子头",
	}

	// hero4 := &HeroNode{
	// 	no : 3,
	// 	name : "吴用",
	// 	nickname : "智多星",
	// }

	//3. 加入
	InsertHeroNode2(head, hero3)
	InsertHeroNode2(head, hero1)
	InsertHeroNode2(head, hero2)
	
	// 4. 显示
	ListHeroNode(head)

	// 5 删除
	fmt.Println()
	DelHerNode(head, 1)
	DelHerNode(head, 3)
	ListHeroNode(head)
}
	

• 删除结点：（代码DelHerNode方法）

20.6.4 双向链表的应用实例

【点击观看视频】数据结构和算法-双向链表介绍

【点击观看视频】数据结构和算法-双向链表创建和输出

【点击观看视频】数据结构和算法-双向链表的删除

使用带head头的双向链表实现- 水浒英雄排行榜管理

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，而需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除节点，总是找到temp的下一个节点来删除的（认真体会）

• 示意图

• 代码实现

package main
import (
	"fmt"
)

//定义一个HeroNode
type HeroNode struct {
	no 		 int
	name 	 string
	nickname string
	pre 	 *HeroNode //这个表示指向前一个结点
	next     *HeroNode //这个表示指向下一个结点
}

//给双向链表插入一个结点
//编写第一种插入方法，在单链表的最后加入.[简单]
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
	//思路
	//1. 先找到该链表的最后这个结点
	//2. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head
	for {
		if temp.next == nil { //表示找到最后
			break
		}
		temp = temp.next // 让temp不断的指向下一个结点
	}

	//3. 将newHeroNode加入到链表的最后
	temp.next = newHeroNode
	newHeroNode.pre = temp
}

//给双向链表插入一个结点
//编写第2种插入方法，根据no 的编号从小到大插入..【实用】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
	//思路
	//1. 找到适当的结点
	//2. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head
	flag := true
	//让插入的结点的no，和temp的下一个结点的no比较
	for {
		if temp.next == nil {//说明到链表的最后
			break
		} else if temp.next.no >= newHeroNode.no {
			//说明newHeroNode 就应该插入到temp后面
			break 
		} else if temp.next.no == newHeroNode.no {
			//说明我们额链表中已经有这个no,就不然插入.
			flag = false
			break
		}
		temp = temp.next
	}

	if !flag {
		fmt.Println("对不起，已经存在no=", newHeroNode.no)
		return
	} else {
		newHeroNode.next = temp.next //ok
		newHeroNode.pre = temp//ok
		if temp.next != nil {
			temp.next.pre = newHeroNode //ok
		}
		temp.next = newHeroNode //ok
	}


}
//删除一个结点[双向链表删除一个结点]
func DelHerNode(head *HeroNode, id int) {
	temp := head
	flag := false
	//找到要删除结点的no，和temp的下一个结点的no比较
	for {
		if temp.next == nil {//说明到链表的最后
			break
		} else if temp.next.no == id {
			//说明我们找到了.
			flag = true
			break
		}
		temp = temp.next
	}
	if flag {//找到, 删除
		temp.next = temp.next.next //ok
		if temp.next != nil {
			temp.next.pre = temp 
		}
	} else {
		fmt.Println("sorry, 要删除的id不存在")
	}
}

//显示链表的所有结点信息
//这里仍然使用单向的链表显示方式
func ListHeroNode(head *HeroNode) {

	//1. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head

	// 先判断该链表是不是一个空的链表
	if temp.next == nil {
		fmt.Println("空空如也。。。。")
		return 
	}
	//2. 遍历这个链表
	for {
		fmt.Printf("[%d , %s , %s]==>", temp.next.no, 
			temp.next.name, temp.next.nickname)
		//判断是否链表后
		temp = temp.next
		if temp.next == nil {
			break
		}
	}
}


func ListHeroNode2(head *HeroNode) {

	//1. 创建一个辅助结点[跑龙套, 帮忙]
	temp := head

	// 先判断该链表是不是一个空的链表
	if temp.next == nil {
		fmt.Println("空空如也。。。。")
		return 
	}

	//2. 让temp定位到双向链表的最后结点
	for {
		if temp.next == nil {
			break
		}
		temp = temp.next
	}


	//2. 遍历这个链表
	for {
		fmt.Printf("[%d , %s , %s]==>", temp.no, 
			temp.name, temp.nickname)
		//判断是否链表头
		temp = temp.pre
		if temp.pre == nil {
			break
		}
	}
}



func main() {

	//1. 先创建一个头结点, 
	head := &HeroNode{}

	//2. 创建一个新的HeroNode
	hero1 := &HeroNode{
		no : 1,
		name : "宋江",
		nickname : "及时雨",
	}

	hero2 := &HeroNode{
		no : 2,
		name : "卢俊义",
		nickname : "玉麒麟",
	}

	hero3 := &HeroNode{
		no : 3,
		name : "林冲",
		nickname : "豹子头",
	}

	
	InsertHeroNode(head, hero1)
	InsertHeroNode(head, hero2)
	InsertHeroNode(head, hero3)
	ListHeroNode(head)
	fmt.Println("逆序打印")
	ListHeroNode2(head)

}

20.6.5 单向环形链表的应用场景

20.6.6 环形单向链表介绍

【点击观看视频】数据结构和算法-环形链表创建和显示

20.6.7 环形的单向链表的案例

【点击观看视频】数据结构和算法-环形链表的删除

完成对单向环形链表的添加结点，删除结点和显示.

package main
import (
	"fmt"
)

//定义猫的结构体结点
type CatNode struct {
	no int //猫猫的编号
	name string
	next *CatNode
}

func InsertCatNode(head *CatNode, newCatNode *CatNode) {

	//判断是不是添加第一只猫
	if head.next == nil {
		head.no = newCatNode.no
		head.name = newCatNode.name
		head.next = head //构成一个环形
		fmt.Println(newCatNode, "加入到环形的链表")
		return 
	}
	
	//定义一个临时变量，帮忙,找到环形的最后结点
	temp := head
	for {
		if temp.next == head {
			break
		}
		temp = temp.next
	}
	//加入到链表中
	temp.next = newCatNode
	newCatNode.next = head

}

//输出这个环形的链表
func ListCircleLink(head *CatNode) {
	fmt.Println("环形链表的情况如下：")
	temp := head
	if temp.next == nil {
		fmt.Println("空空如也的环形链表...")
		return 
	} 
	for {
		fmt.Printf("猫的信息为=[id=%d name=%s] ->\n", temp.no, temp.name)
		if temp.next == head {
			break
		}
		temp = temp.next
	}
}

//删除一只猫
func DelCatNode(head *CatNode, id int) *CatNode {

	temp := head
	helper := head
	//空链表
	if temp.next == nil {
		fmt.Println("这是一个空的环形链表，不能删除")
		return head
	}
	
	//如果只有一个结点
	if temp.next == head { //只有一个结点
		if temp.no == id {
			temp.next = nil 
		}
		return head
	}

	//将helper 定位到链表最后
	for {
		if helper.next == head {
			break
		} 
		helper = helper.next
	}

	//如果有两个包含两个以上结点
	flag := true
	for {
		if temp.next == head { //如果到这来，说明我比较到最后一个【最后一个还没比较】
			break 
		} 
		if temp.no ==id {
			if temp == head { //说明删除的是头结点
				head = head.next
			}
			//恭喜找到., 我们也可以在直接删除
			helper.next = temp.next
			fmt.Printf("猫猫=%d\n", id)
			flag = false
			break
		}
		temp = temp.next //移动 【比较】
		helper = helper.next //移动 【一旦找到要删除的结点 helper】
	}
	//这里还有比较一次
	if flag { //如果flag 为真，则我们上面没有删除
		if temp.no == id {
			helper.next = temp.next
			fmt.Printf("猫猫=%d\n", id)
		}else {
			fmt.Printf("对不起，没有no=%d\n", id)
		}
	} 
	return head
}

func main() {

	//这里我们初始化一个环形链表的头结点
	head := &CatNode{}

	//创建一只猫
	cat1 := &CatNode{
		no : 1,
		name : "tom",
	}
	cat2 := &CatNode{
		no : 2,
		name : "tom2",
	}
	cat3 := &CatNode{
		no : 3,
		name : "tom3",
	}
	InsertCatNode(head, cat1)
	InsertCatNode(head, cat2)
	InsertCatNode(head, cat3)
	ListCircleLink(head)

	head = DelCatNode(head, 30)

	fmt.Println()	
	fmt.Println()	
	fmt.Println()	
	ListCircleLink(head)

}

【点击观看视频】数据结构和算法-链表作业布置

20.6.8 环形单向链表的应用实例

【点击观看视频】数据结构和算法-约瑟夫问题分析

Josephu 问题

Josephu 问题为：设编号为 1 ， 2 ，. n的n个人围坐一圈，约定编号为k（ 1 <=k<=n）的人从 1开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

【点击观看视频】数据结构和算法-约瑟夫问题解决(1)

【点击观看视频】数据结构和算法-约瑟夫问题解决(2)

提示

用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从 1 开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

• 示意图说明

• 走代码：

package main
import (
	"fmt"
)


//小孩的结构体
type Boy struct {
	No int // 编号
	Next *Boy // 指向下一个小孩的指针[默认值是nil]
}

// 编写一个函数，构成单向的环形链表
// num ：表示小孩的个数
// *Boy : 返回该环形的链表的第一个小孩的指针
func AddBoy(num int) *Boy {

	first := &Boy{} //空结点
	curBoy := &Boy{} //空结点

	//判断
	if num < 1 	{
		fmt.Println("num的值不对")
		return first
	}
	//循环的构建这个环形链表
	for i := 1; i <= num; i++ {
		boy := &Boy{
			No : i,
		}
		//分析构成循环链表，需要一个辅助指针[帮忙的]
		//1. 因为第一个小孩比较特殊
		if i == 1 { //第一个小孩
			first = boy //不要动
			curBoy = boy
			curBoy.Next = first // 
		} else {
			curBoy.Next = boy
			curBoy = boy
			curBoy.Next = first //构造环形链表
		}
	}
	return first

}

//显示单向的环形链表[遍历]
func ShowBoy(first *Boy) {

	//处理一下如果环形链表为空
	if first.Next == nil {
		fmt.Println("链表为空，没有小孩...")
		return
	}

	//创建一个指针，帮助遍历.[说明至少有一个小孩]
	curBoy := first  
	for {
		fmt.Printf("小孩编号=%d ->", curBoy.No)
		//退出的条件?curBoy.Next == first
		if curBoy.Next == first {
			break
		}
		//curBoy移动到下一个
		curBoy = curBoy.Next
	}
}

/*
设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）
的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，
数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
*/

//分析思路
//1. 编写一个函数，PlayGame(first *Boy, startNo int, countNum int) 
//2. 最后我们使用一个算法，按照要求，在环形链表中留下最后一个人
func PlayGame(first *Boy, startNo int, countNum int) {

	//1. 空的链表我们单独的处理
	if first.Next == nil {
		fmt.Println("空的链表，没有小孩")
		return
	}
	//留一个，判断 startNO <= 小孩的总数
	//2. 需要定义辅助指针，帮助我们删除小孩
	tail := first 
	//3. 让tail执行环形链表的最后一个小孩,这个非常的重要
	//因为tail 在删除小孩时需要使用到.
	for {
		if tail.Next == first { //说明tail到了最后的小孩
			break
		}
		tail = tail.Next
	}
	//4. 让first 移动到 startNo [后面我们删除小孩，就以first为准]
	for i := 1; i <= startNo - 1; i++ {
		first = first.Next
		tail = tail.Next
	} 
	fmt.Println()
	//5. 开始数 countNum, 然后就删除first 指向的小孩
	for {
		//开始数countNum-1次
		for i := 1; i <= countNum -1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Printf("小孩编号为%d 出圈 \n", first.No)
		//删除first执行的小孩
		first = first.Next
		tail.Next = first
		//判断如果 tail == first, 圈子中只有一个小孩.
		if tail == first {
			break
		}
	}
	fmt.Printf("小孩小孩编号为%d 出圈 \n", first.No)

}

func main() {

	first := AddBoy(500)
	//显示
	ShowBoy(first)
	PlayGame(first, 20, 31)

}

20.7 排序

【点击观看视频】数据结构和算法-选择排序

20.7.1 排序的介绍

排序是将一组数据，依指定的顺序进行排列的过程, 常见的排序：

1 ) 冒泡排序

2 ) 选择排序

3 ) 插入排序

4 ) 快速排序

20.7.2 冒泡排序

20.7.3 选择排序基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。

20.7.4 选择排序思想:

选择排序（selectsorting）也是一种简单的排序方法。它的基本思想是：第一次从R[ 0 ]~R[n- 1 ]中选取最小值，与R[ 0 ]交换，第二次从R[ 1 ]~R[n- 1 ]中选取最小值，与R[ 1 ]交换，第三次从R[ 2 ]~R[n- 1 ]中选取最小值，与R[ 2 ]交换，.，第i次从R[i- 1 ]~R[n- 1 ]中选取最小值，与R[i- 1 ]交换，., 第n- 1 次从R[n- 2 ]~R[n- 1 ]中选取最小值，与R[n- 2 ]交换，总共通过n- 1 次，得到一个按排序码从小到大排列的有序序列。

20.7.5 选择排序的示意图

20.7.6 代码实现

package main
import (
	"fmt"
	"math/rand"
	"time"
)

//编写函数selectSort 完成排序

func SelectSort(arr *[80000]int) {

	//标准的访问方式
	//(*arr)[1] = 600 等价于 arr[1] = 900
	//arr[1] = 900
	//1. 先完成将第一个最大值和 arr[0] => 先易后难

	//1 假设  arr[0] 最大值

	for j := 0; j < len(arr) - 1; j++ {

		max := arr[j]
		maxIndex := j
		//2. 遍历后面 1---[len(arr) -1] 比较
		for i := j + 1; i < len(arr); i++ {
			if max < arr[i] { //找到真正的最大值
				max = arr[i]
				maxIndex = i
			}
		}
		//交换
		if maxIndex != j {
			arr[j], arr[maxIndex] = arr[maxIndex], arr[j]
		}

		//fmt.Printf("第%d次 %v\n  ", j+1 ,*arr)
	}
	

	/*
	max = arr[1]
	maxIndex = 1
	//2. 遍历后面 2---[len(arr) -1] 比较
	for i := 1 + 1; i < len(arr); i++ {
		if max < arr[i] { //找到真正的最大值
			max = arr[i]
			maxIndex = i
		}
	}
	//交换
	if maxIndex != 1 {
		arr[1], arr[maxIndex] = arr[maxIndex], arr[1]
	}

	fmt.Println("第2次 ", *arr)

	

	max = arr[2]
	maxIndex = 2
	//2. 遍历后面 3---[len(arr) -1] 比较
	for i := 2 + 1; i < len(arr); i++ {
		if max < arr[i] { //找到真正的最大值
			max = arr[i]
			maxIndex = i
		}
	}
	//交换
	if maxIndex != 2 {
		arr[2], arr[maxIndex] = arr[maxIndex], arr[2]
	}

	fmt.Println("第3次 ", *arr)

	max = arr[3]
	maxIndex = 3
	//2. 遍历后面 4---[len(arr) -1] 比较
	for i := 3 + 1; i < len(arr); i++ {
		if max < arr[i] { //找到真正的最大值
			max = arr[i]
			maxIndex = i
		}
	}
	//交换
	if maxIndex != 3 {
		arr[3], arr[maxIndex] = arr[maxIndex], arr[3]
	}

	fmt.Println("第4次 ", *arr)*/
}

func main() {
	//定义一个数组 , 从大到小
	//arr := [6]int{10, 34, 19, 100, 80, 789}

	var arr [80000]int
	for i := 0; i < 80000; i++ {
		arr[i] = rand.Intn(900000)
	}

	//fmt.Println(arr)
	start := time.Now().Unix()
	SelectSort(&arr)
	end := time.Now().Unix()
	fmt.Printf("选择排序耗时=%d秒", end - start)
	fmt.Println("main函数")
	//fmt.Println(arr)
}

【点击观看视频】数据结构和算法-插入排序分析

20.7.7 插入排序法介绍:

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

20.7.8 插入排序法思想:

插入排序（InsertionSorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n- 1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

20.7.9 插入排序的示意图

20.7.10 插入排序法应用实例

【点击观看视频】数据结构和算法-插入排序实现

20.7.11 插入排序的代码实现

package main
import (
	"fmt"
	"math/rand"
	"time"
)

func InsertSort(arr *[80000]int) {

	//完成第一次，给第二个元素找到合适的位置并插入

	for i := 1; i < len(arr); i++ {

		insertVal := arr[i]
		insertIndex := i - 1 // 下标

		//从大到小
		for insertIndex >= 0 && arr[insertIndex] < insertVal {
			arr[insertIndex + 1] = arr[insertIndex] // 数据后移
			insertIndex-- 
		}
		//插入
		if insertIndex + 1 != i {
			arr[insertIndex + 1] = insertVal
		}
		//fmt.Printf("第%d次插入后 %v\n",i, *arr)
	}
	

	/*

	//完成第2次，给第3个元素找到合适的位置并插入
	insertVal = arr[2]
	insertIndex = 2 - 1 // 下标

	//从大到小
	for insertIndex >= 0 && arr[insertIndex] < insertVal {
		arr[insertIndex + 1] = arr[insertIndex] // 数据后移
		insertIndex-- 
	}
	//插入
	if insertIndex + 1 != 2 {
		arr[insertIndex + 1] = insertVal
	}
	fmt.Println("第2次插入后", *arr)

	//完成第3次，给第4个元素找到合适的位置并插入
	insertVal = arr[3]
	insertIndex = 3 - 1 // 下标

	//从大到小
	for insertIndex >= 0 && arr[insertIndex] < insertVal {
		arr[insertIndex + 1] = arr[insertIndex] // 数据后移
		insertIndex-- 
	}
	//插入
	if insertIndex + 1 != 3 {
		arr[insertIndex + 1] = insertVal
	}
	fmt.Println("第3次插入后", *arr)

	//完成第4次，给第5个元素找到合适的位置并插入
	insertVal = arr[4]
	insertIndex = 4 - 1 // 下标

	//从大到小
	for insertIndex >= 0 && arr[insertIndex] < insertVal {
		arr[insertIndex + 1] = arr[insertIndex] // 数据后移
		insertIndex-- 
	}
	//插入
	if insertIndex + 1 != 4 {
		arr[insertIndex + 1] = insertVal
	}
	fmt.Println("第4次插入后", *arr)*/
}
	

func main() {

	

	//arr := [7]int{23, 0, 12, 56,  34, -1, 55}

	var arr [80000]int
	for i := 0; i < 80000; i++ {
		arr[i] = rand.Intn(900000)
	}

	//fmt.Println(arr)
	start := time.Now().Unix()
	//fmt.Println("原始数组=", arr)
	InsertSort(&arr)
	end := time.Now().Unix()

	fmt.Println("main 函数")
	fmt.Printf("插入排序耗时%d秒", end-start)
	//fmt.Println(arr)
}

【点击观看视频】数据结构和算法-插入排序小结

20.7.12 快速排序法介绍

【点击观看视频】数据结构和算法-快速排序法

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

20.7.13 快速排序法示意图

20.7.14 快速排序法应用实例

20.7.15 快速排序法的代码实现

package main
import (
	"fmt"
	"math/rand"
	"time"
)

//快速排序
//说明
//1. left 表示 数组左边的下标
//2. right 表示数组右边的下标
//3  array 表示要排序的数组
func QuickSort(left int, right int, array *[8000000]int) {
	l := left
	r := right
	// pivot 是中轴， 支点
	pivot := array[(left + right) / 2]
	temp := 0

	//for 循环的目标是将比 pivot 小的数放到 左边
	//  比 pivot 大的数放到 右边
	for ; l < r; {
		//从  pivot 的左边找到大于等于pivot的值
		for ; array[l] < pivot; {
			l++
		}
		//从  pivot 的右边边找到小于等于pivot的值
		for ; array[r] > pivot; {
			r--
		}
		// 1 >= r 表明本次分解任务完成, break
		if l >= r { 
			break
		}
		//交换
		temp = array[l]
		array[l] = array[r]
		array[r] = temp
		//优化
		if array[l]== pivot  {
			r--
		}
		if array[r]== pivot {
			l++			
		}
	}
	// 如果  1== r, 再移动下
	if l == r {
		 l++
		 r--
	}
	// 向左递归
	if left < r {
		QuickSort(left, r, array)
	}
	// 向右递归
	if right > l {
		QuickSort(l, right, array)
	}
}


func main() {

	// arr := [9]int {-9,78,0,23,-567,70, 123, 90, -23}
	// fmt.Println("初始", arr)

	var arr [8000000]int
	for i := 0; i < 8000000; i++ {
		arr[i] = rand.Intn(900000)
	}

	//fmt.Println(arr)
	start := time.Now().Unix()
	//调用快速排序
	QuickSort(0, len(arr) - 1, &arr)
	end := time.Now().Unix()
	fmt.Println("main..")
	fmt.Printf("快速排序法耗时%d秒", end - start)
	//fmt.Println(arr)

}

20.7.16 三种排序方法的速度的分析

【点击观看视频】数据结构和算法-排序的速度比较

20.8 栈

20.8.1 看一个实际需求

【点击观看视频】数据结构和算法-栈

20.8.2 栈的介绍

有些程序员也把栈称为堆栈, 即栈和堆栈是同一个概念

1. 栈的英文为(stack)
2. 栈是一个先入后出(FILO-FirstInLastOut)的有序列表。
3. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
4. 根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

20.8.3 栈的入栈和出栈的示意图

【点击观看视频】数据结构和算法-入栈操作和遍历

【点击观看视频】数据结构和算法-栈的出栈操作

20.8.4 栈的应用场景.

1 ) 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

2 ) 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

3 ) 表达式的转换与求值。

4 ) 二叉树的遍历。

5 ) 图形的深度优先(depth一first)搜索法。

20.8.5 栈的案例

• 代码实现

package main
import (
	"fmt"
	"errors"
)

//使用数组来模拟一个栈的使用
type Stack struct {
	MaxTop int  // 表示我们栈最大可以存放数个数
	Top int // 表示栈顶, 因为栈顶固定，因此我们直接使用Top
	arr [5]int // 数组模拟栈
}
//入栈
func (this *Stack) Push(val int) (err error) {

	//先判断栈是否满了
	if this.Top == this.MaxTop - 1 {
		fmt.Println("stack full")
		return errors.New("stack full")
	}
	this.Top++ 
	//放入数据
	this.arr[this.Top] = val
	return 
}

//出栈
func (this *Stack) Pop() (val int, err error) {
	//判断栈是否空
	if this.Top == -1 {
		fmt.Println("stack empty!")
		return 0, errors.New("stack empty")
	} 

	//先取值，再 this.Top--
	val =  this.arr[this.Top]
	this.Top--
	return val, nil

}
//遍历栈，注意需要从栈顶开始遍历
func (this *Stack) List() {
	//先判断栈是否为空
	if this.Top == -1 {
		fmt.Println("stack empty")
		return 
	}
	fmt.Println("栈的情况如下：")
	for i := this.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
	}

}

func main() {

	stack := &Stack{
		MaxTop : 5, // 表示最多存放5个数到栈中
		Top : -1, // 当栈顶为-1，表示栈为空
	}

	//入栈
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	stack.Push(4)
	stack.Push(5)

	//显示
	stack.List()
	val, _ := stack.Pop()
	fmt.Println("出栈val=", val) // 5
	//显示
	stack.List() // 

	fmt.Println()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()
	val, _ = stack.Pop()// 出错
	fmt.Println("出栈val=", val) // 5
	//显示
	stack.List() // 
}

20.8.6 栈实现综合计算器

【点击观看视频】数据结构和算法-栈的计算表达式(1)

【点击观看视频】数据结构和算法-栈的计算表达式(2)

【点击观看视频】数据结构和算法-栈的计算表达式(3)

【点击观看视频】数据结构和算法-栈的计算表达式(4)

• 分析了实现的思路

• 代码实现

package main
import (
	"fmt"
	"errors"
	"strconv"
)

//使用数组来模拟一个栈的使用
type Stack struct {
	MaxTop int  // 表示我们栈最大可以存放数个数
	Top int // 表示栈顶, 因为栈顶固定，因此我们直接使用Top
	arr [20]int // 数组模拟栈
}
//入栈
func (this *Stack) Push(val int) (err error) {

	//先判断栈是否满了
	if this.Top == this.MaxTop - 1 {
		fmt.Println("stack full")
		return errors.New("stack full")
	}
	this.Top++ 
	//放入数据
	this.arr[this.Top] = val
	return 
}

//出栈
func (this *Stack) Pop() (val int, err error) {
	//判断栈是否空
	if this.Top == -1 {
		fmt.Println("stack empty!")
		return 0, errors.New("stack empty")
	} 

	//先取值，再 this.Top--
	val =  this.arr[this.Top]
	this.Top--
	return val, nil

}
//遍历栈，注意需要从栈顶开始遍历
func (this *Stack) List() {
	//先判断栈是否为空
	if this.Top == -1 {
		fmt.Println("stack empty")
		return 
	}
	fmt.Println("栈的情况如下：")
	for i := this.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
	}

}
//判断一个字符是不是一个运算符[+, - , * , /]
func (this *Stack) IsOper(val int) bool {

	if val == 42 || val == 43 || val == 45 || val == 47 {
		return true
	} else {
		return false
	}
}

//运算的方法
func (this *Stack) Cal(num1 int, num2 int, oper int) int{
	res := 0
	switch oper {
		case 42 :
			res = num2 * num1
		case 43 :
			res = num2 + num1
		case 45 :
			res = num2 - num1
		case 47 :
			res = num2 / num1
		default :
			fmt.Println("运算符错误.")
	}
	return res
}

//编写一个方法，返回某个运算符的优先级[程序员定义]
//[* / => 1 + - => 0]
func (this *Stack) Priority(oper int) int {
	res := 0
	if oper == 42 || oper == 47 {
		res = 1
	} else if oper == 43 || oper == 45 {
		res = 0
	} 
	return res
} 

func main() {

	//数栈
	numStack := &Stack{
		MaxTop : 20,
		Top : -1,
	}
	//符号栈
	operStack := &Stack{
		MaxTop : 20,
		Top : -1,
	}

	exp := "30+30*6-4-6"
	//定义一个index ，帮助扫描exp
	index := 0
	//为了配合运算，我们定义需要的变量
	num1 := 0
	num2 := 0
	oper := 0
	result := 0
	keepNum := "" 

	for {
		//这里我们需要增加一个逻辑，
		//处理多位数的问题
		ch := exp[index:index+1] // 字符串.
		//ch ==>"+" ===> 43
		temp := int([]byte(ch)[0]) // 就是字符对应的ASCiI码
		if operStack.IsOper(temp) { // 说明是符号

			//如果operStack  是一个空栈， 直接入栈
			if operStack.Top == -1 { //空栈
				operStack.Push(temp)
			}else {
				//如果发现opertStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级
				//，就从符号栈pop出，并从数栈也pop 两个数，进行运算，运算后的结果再重新入栈
				//到数栈， 当前符号再入符号栈
				if operStack.Priority(operStack.arr[operStack.Top]) >= 
					operStack.Priority(temp) {
						num1, _ = numStack.Pop()
						num2, _ = numStack.Pop()
						oper, _ = operStack.Pop()
						result = operStack.Cal(num1,num2, oper)
						//将计算结果重新入数栈
						numStack.Push(result)
						//当前的符号压入符号栈
						operStack.Push(temp)

				}else {
					operStack.Push(temp)
				}

			}


		} else { //说明是数
			
			//处理多位数的思路
			//1.定义一个变量 keepNum string, 做拼接
			keepNum += ch 
			//2.每次要向index的后面字符测试一下，看看是不是运算符，然后处理
			//如果已经到表达最后，直接将 keepNum
			if index == len(exp) - 1 { 
				val, _ := strconv.ParseInt(keepNum, 10, 64)
				numStack.Push(int(val))
			} else {
				//向index 后面测试看看是不是运算符 [index]
				if operStack.IsOper(int([]byte(exp[index+1:index+2])[0])) {
					val, _ := strconv.ParseInt(keepNum, 10, 64)
					numStack.Push(int(val))
					keepNum = ""
				}
			}
		}

		//继续扫描
		//先判断index是否已经扫描到计算表达式的最后
		if index + 1 == len(exp) {
			break
		}
		index++

	}

	//如果扫描表达式 完毕，依次从符号栈取出符号，然后从数栈取出两个数，
	//运算后的结果，入数栈，直到符号栈为空
	for {
		if operStack.Top == -1 {
			break //退出条件
		}
		num1, _ = numStack.Pop()
		num2, _ = numStack.Pop()
		oper, _ = operStack.Pop()
		result = operStack.Cal(num1,num2, oper)
		//将计算结果重新入数栈
		numStack.Push(result)
		
	}

	//如果我们的算法没有问题，表达式也是正确的，则结果就是numStack最后数
	res, _ := numStack.Pop()
	fmt.Printf("表达式%s = %v", exp, res)
}

20.9 递归

【点击观看视频】数据结构和算法-递归机制剖析

20.9.1 递归的一个应用场景迷宫问题

20.9.2 递归的概念

【点击观看视频】数据结构和算法-递归相关说明

简单的说: 第归就是函数/方法自己调用自己,每次调用时传入不同的变量.第归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

20.9.3 递归快速入门

我列举两个小案例,来帮助大家理解递归，递归在讲函数时已经讲过(当时讲的相对比较简单)，这里在给大家回顾一下递归调用机制

1 ) 打印问题

2 ) 阶乘问题

3 ) 快速入门的示意图

20.9.4 递归用于解决什么样的问题

1 ） 各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)

2 ） 将用栈解决的问题-->第归代码比较简洁

20.9.5 递归需要遵守的重要原则

1 ) 执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)

2 ) 函数的局部变量是独立的，不会相互影响, 如果希望各个函数栈使用同一个数据，使用引用传递

3 ) 递归必须向退出递归的条件逼近【程序员自己必须分析】，否则就是无限递归，死龟了:)

4 ) 当一个函数执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁

20.9.6 举一个比较综合的案例,迷宫问题

【点击观看视频】数据结构和算法-迷宫回溯问题(1)

【点击观看视频】数据结构和算法-迷宫回溯问题(2)

• 走代码：

package main
import (
	"fmt"
)

//编写一个函数，完成老鼠找路
//myMap *[8][7]int:地图，保证是同一个地图，使用引用
//i,j 表示对地图的哪个点进行测试
func SetWay(myMap *[8][7]int, i int, j int) bool {

	//分析出什么情况下，就找到出路 
	//myMap[6][5] == 2
	if myMap[6][5] == 2 {
		return true
	} else {
		//说明要继续找
		if myMap[i][j] == 0 { //如果这个点是可以探测

			//假设这个点是可以通, 但是需要探测 上下左右
			//换一个策略 下右上左
			myMap[i][j] = 2
			if SetWay(myMap, i + 1, j) { //下
				return true 
			} else if SetWay(myMap, i , j + 1) { //右
				return true
			} else if SetWay(myMap, i - 1, j) { //上
				return true
			} else if SetWay(myMap, i , j - 1) { //左
				return true
			} else { // 死路
				myMap[i][j] = 3
				return false
			}

		} else { // 说明这个点不能探测，为1，是强
			return false
		}

	}
}

func main() {
	//先创建一个二维数组，模拟迷宫
	//规则
	//1. 如果元素的值为1 ，就是墙
	//2. 如果元素的值为0, 是没有走过的点
	//3. 如果元素的值为2, 是一个通路
	//4. 如果元素的值为3， 是走过的点，但是走不通
	var myMap [8][7]int

	//先把地图的最上和最下设置为1
	for i := 0 ; i < 7 ; i++ {
		myMap[0][i] = 1
		myMap[7][i] = 1
	}

	//先把地图的最左和最右设置为1
	for i := 0 ; i < 8 ; i++ {
		myMap[i][0] = 1
		myMap[i][6] = 1
	}

	myMap[3][1] = 1
	myMap[3][2] = 1
	myMap[1][2] = 1
	myMap[2][2] = 1

	//输出地图
	for i := 0; i < 8; i++ {
		for j := 0; j < 7; j++ {
			fmt.Print(myMap[i][j], " ")
		}
		fmt.Println()
	}

	//使用测试
	SetWay(&myMap, 1, 1)
	fmt.Println("探测完毕....")
	//输出地图
	for i := 0; i < 8; i++ {
		for j := 0; j < 7; j++ {
			fmt.Print(myMap[i][j], " ")
		}
		fmt.Println()
	}

}

• 课后思考题：思考 : 如何求出最短路径?

20.10 哈希表(散列)

【点击观看视频】数据结构和算法-哈希表(散列)1

【点击观看视频】数据结构和算法-哈希表(散列)2

【点击观看视频】数据结构和算法-哈希表(散列)3

【点击观看视频】数据结构和算法-哈希表(散列)4

20.10.1 实际的需求

google公司的一个上机题:

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址),当输入该员工的id时,要求查找到该员工的 所有信息.

要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

20.10.2 哈希表的基本介绍

散列表（Hashtable，也叫哈希表），是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

20.10.3 使用hashtable来实现一个雇员的管理系统[增删改查]

• 应用实例google公司的一个上机题:

  有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址),当输入该员工的id时,要求查找到该员工的 所有信息.

• 要求:

  1 ) 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

  2 ) 添加时，保证按照雇员的id从低到高插入

• 思路分析

  1 ) 使用链表来实现哈希表, 该链表不带表头

  [即: 链表的第一个结点就存放雇员信息]

  2 ) 思路分析并画出示意图

  

  3 ) 代码实现[增删改查(显示所有员工，按 id 查询)]

package main
import (
	"fmt"
	"os"
)

//定义emp
type Emp struct {
	Id int
	Name string
	Next *Emp
}
//方法待定..
func (this *Emp) ShowMe() {
	fmt.Printf("链表%d 找到该雇员 %d\n", this.Id % 7, this.Id)
}

//定义EmpLink
//我们这里的EmpLink 不带表头,即第一个结点就存放雇员
type EmpLink struct {
	Head *Emp 
}
//方法待定..
//1. 添加员工的方法, 保证添加时，编号从小到大
func (this *EmpLink) Insert(emp *Emp) {

	cur := this.Head // 这是辅助指针
	var pre *Emp = nil // 这是一个辅助指针 pre 在cur前面
	//如果当前的EmpLink就是一个空链表
	if cur == nil {
		this.Head = emp //完成
		return 
	}
	//如果不是一个空链表,给emp找到对应的位置并插入
	//思路是 让 cur 和 emp 比较，然后让pre 保持在 cur 前面
	for {
		if cur != nil {
			//比较
			if cur.Id > emp.Id {
				//找到位置
				break
			}
			pre = cur //保证同步
			cur = cur.Next
		}else {
			break
		}
	} 
	//退出时，我们看下是否将emp添加到链表最后
	pre.Next = emp
	emp.Next = cur
	
}
//显示链表的信息
func (this *EmpLink) ShowLink(no int) {
	if this.Head == nil {
		fmt.Printf("链表%d 为空\n", no)
		return 
	}

	//变量当前的链表，并显示数据
	cur := this.Head // 辅助的指针
	for {
		if cur != nil {
			fmt.Printf("链表%d 雇员id=%d 名字=%s ->", no, cur.Id, cur.Name)
			cur = cur.Next
		} else {
			break
		}
	}
	fmt.Println() //换行处理
}

//根据id查找对应的雇员，如果没有就返回nil
func (this *EmpLink) FindById(id int)  *Emp {
	cur := this.Head
	for {
		if cur != nil && cur.Id == id {
			return cur
		} else if cur == nil {
			break
		}
		cur = cur.Next
	}
	return nil
}

//定义hashtable ,含有一个链表数组
type HashTable struct {
	LinkArr [7]EmpLink
}

//给HashTable 编写Insert 雇员的方法.
func (this *HashTable) Insert(emp *Emp) {
	//使用散列函数，确定将该雇员添加到哪个链表
	linkNo := this.HashFun(emp.Id)
	//使用对应的链表添加
	this.LinkArr[linkNo].Insert(emp) //
}

//编写方法，显示hashtable的所有雇员
func (this *HashTable) ShowAll() {
	for i := 0; i < len(this.LinkArr); i++ {
		this.LinkArr[i].ShowLink(i)
	}
}

//编写一个散列方法
func (this *HashTable) HashFun(id int) int {
	return id % 7 //得到一个值，就是对于的链表的下标
}
//编写一个方法，完成查找
func (this *HashTable) FindById(id int) *Emp {
	//使用散列函数，确定将该雇员应该在哪个链表
	linkNo := this.HashFun(id)
	return this.LinkArr[linkNo].FindById(id)
}


func main() {

	key := ""
	id := 0
	name := ""
	var hashtable HashTable
	for {
		fmt.Println("===============雇员系统菜单============")
		fmt.Println("input 表示添加雇员")
		fmt.Println("show  表示显示雇员")
		fmt.Println("find  表示查找雇员")
		fmt.Println("exit  表示退出系统")
		fmt.Println("请输入你的选择")
		fmt.Scanln(&key)
		switch key {
			case "input":
				fmt.Println("输入雇员id")
				fmt.Scanln(&id)
				fmt.Println("输入雇员name")
				fmt.Scanln(&name)
				emp := &Emp{
					Id : id,
					Name : name,
				}
				hashtable.Insert(emp)
			case "show":
				hashtable.ShowAll()
			case "find":
				fmt.Println("请输入id号:")
				fmt.Scanln(&id)
				emp := hashtable.FindById(id)
				if emp == nil {
					fmt.Printf("id=%d 的雇员不存在\n", id)
				} else {
					//编写一个方法，显示雇员信息
					emp.ShowMe()
				}

			case "exit":
				os.Exit(0)
			default :
				fmt.Println("输入错误")
		}
	}

}

【点击观看视频】数据结构和算法-二叉树三种遍历方式