Go数据结构与算法
稀疏 sparsearray 数组
先看一个实际的需求
编写的五子棋程序中，有存盘退出和续上盘的功能
分析按照原始的方式来的二维数组的问题
因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据
基本介绍
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
- 记录数组一共有几行几列，有多少个不同的值
- 思想：把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
稀疏数组举例说明
应用实例
- 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
- 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
- 整体思路分析
- 代码实现
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)
type ValNode struct {
row int
col int
val int
}
func main() {
var chessMap[11][11]int
chessMap[1][2] = 1
chessMap[2][3] = 2
for _, v := range chessMap {
for _, v2 := range v {
fmt.Printf("%d\t",v2)
}
fmt.Println()
}
var sparseArr []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{
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)
}
//将这个稀疏数组，存盘 e:/chessmap.data
filePath := "e:/chessmap.data"
file, err := os.OpenFile(filePath, os.O_WRONLY|os.O_CREATE, 0666)
if err != nil {
fmt.Println(err)
return
}
defer file.Close()
writer := bufio.NewWriter(file)
for _, valNode := range sparseArr {
str :=fmt.Sprintf("%d %d %d\n",valNode.row,valNode.col ,valNode.val)
writer.WriteString(str)
}
writer.Flush()
//如何恢复原始的数组
//1. 打开这个 d:/chessmap.data => 恢复原始数组.
f, err := os.Open(filePath)
if err != nil {
fmt.Println("open file err=",err)
}
defer f.Close()
reader := bufio.NewReader(f)
var sparseArr2 []string
for {
str ,err := reader.ReadString('\n')
if err == io.EOF {
break
}
sparseArr2 = append(sparseArr2, str)
fmt.Print(str)
}
fmt.Println("文件读取结束..")
var chessMap2 [11][11]int
for i, valNode := range sparseArr2 {
if i != 0 {
s := strings.Trim(valNode,"\n")
str := strings.Split(s, " ")
fmt.Println(str)
val0, _ := strconv.Atoi(str[0])
val1, _ := strconv.Atoi(str[1])
val2, _ := strconv.Atoi(str[2])
chessMap2[val0][val1] = val2
}
}
fmt.Println("恢复后的原始数据....")
for _, v := range chessMap2 {
for _, v2 := range v {
fmt.Printf("%d\t",v2)
}
fmt.Println()
}
}
对老师的稀疏数组的改进
-
将构建的稀疏数组，存盘 chessmap.data （完成）
-
在恢复原始二维数组，要求从文件 chessmap.data 读取。（完成）
队列(queue)
队列的应用场景
银行排队的案例
队列介绍
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
示意图：(使用数组模拟队列示意图)
数组模拟队列
先完成一个非环形的队列(数组来实现)
思路分析：
代码实现：
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） 请思考，如何使用数组 实现一个环形的队列
数组模拟环形队列
分析思路:
-
什么时候表示队列满 (tail + 1) % maxSize = head
-
tail == head 表示空
-
初始化时， tail = 0 head = 0a
-
怎么统计该队列有多少个元素 (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)
}
}
}
链表
链表介绍
链表是有序的列表，但是它在内存中是存储如下
单链表的介绍
单链表的示意图：
说明：一般来说，为了比较好的对单链表进行增删改查的操作，我们都会给他设置一个头结点, 头结点的作用主要是用来标识链表头， 本身这个结点不存放数据。
单链表的应用实例
案例的说明：
使用带 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 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)
InsertHeroNode2(head, hero4)
// 4. 显示
ListHeroNode(head)
}
删除结点：
双向链表的应用实例
示意图
代码实现
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)
}
排序
排序的介绍
排序是将一组数据，依指定的顺序进行排列的过程, 常见的排序：
-
冒泡排序
-
选择排序
-
插入排序
-
快速排序
冒泡排序
选择排序基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的
选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 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 次，得到一个按排序码从小到大排列的有序 序列。
选择排序的示意图
代码实现
插入排序法介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序法思想
插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
插入排序的示意图
插入排序法应用实例
插入排序的代码实现
快速排序法介绍
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序法示意图
快速排序法应用实例
快速排序法的代码实现
package main
import "fmt"
//快速排序
//说明
//1. left 表示 数组左边的下标
//2. right 表示数组右边的下标
//3 array 表示要排序的数组
func QuickSort(left int,right int,array *[9]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++
}
}
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)
// 调用快速排序
QuickSort(0,len(arr)-1,&arr)
fmt.Println("main...")
fmt.Println(arr)
}
栈
栈的介绍
有些程序员也把栈称为堆栈, 即栈和堆栈是同一个概念
-
栈的英文为(stack)
-
栈是一个**先入后出(FILO-First In Last Out)**的有序列表。
-
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
-
根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
栈的入栈和出栈的示意图
栈的应用场景
-
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
-
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
-
表达式的转换与求值。
-
二叉树的遍历。
-
图形的深度优先(depth 一 first)搜索法。
栈的案例
代码实现
package main
import (
"errors"
"fmt"
)
type Stack struct {
MaxTop int // 最多存放几个
Top int // Top从-1开始 , 下标0，1，2，3，4存放值
arr [5]int // 最多存5个
}
func (s *Stack) Push(val int) (err error) {
if s.Top == s.MaxTop - 1 { // 当Top = 4时，说明下标为4了，栈已满
fmt.Println("stack full")
return errors.New("stack full")
}
s.Top++
s.arr[s.Top] = val
return
}
func (s *Stack) Pop() (val int,err error) {
if s.Top == -1 {
fmt.Println("stack empty")
return 0,errors.New("stack empty")
}
val = s.arr[s.Top]
s.Top--
return val, nil
}
func (s *Stack) List() {
if s.Top == -1 {
fmt.Println("stack empty")
return
}
fmt.Println("栈的情况如下")
for i := s.Top; i >= 0 ; i-- {
fmt.Printf("arr[%d]=%d\n",i,s.arr[i])
}
}
func main(){
s := Stack{
MaxTop: 5,
Top: -1,
arr: [5]int{},
}
s.Push(3)
s.Push(4)
s.Push(5)
s.Push(6)
s.Push(7)
s.Push(10) // stack full
val, err := s.Pop()
if err != nil {
fmt.Println(err)
return
}
fmt.Println(val) // 7
s.List()
}
栈实现综合计算器
分析了实现的思路
package main
import (
"errors"
"fmt"
"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)
}
递归
递归的一个应用场景[迷宫问题]
递归的概念
简单的说: 第归就是函数/方法自己调用自己,每次调用时传入不同的变量.第归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
递归快速入门
我列举两个小案例,来帮助大家理解递归，递归在讲函数时已经讲过(当时讲的相对比较简单)，这里在给大家回顾一下递归调用机制
-
打印问题
-
阶乘问题
-
快速入门的示意图
递归用于解决什么样的问题
1） 各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)
2） 将用栈解决的问题-->第归代码比较简洁
递归需要遵守的重要原则
-
执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)
-
函数的局部变量是独立的，不会相互影响, 如果希望各个函数栈使用同一个数据，使用引用传递
-
递归必须向退出递归的条件逼近【程序员自己必须分析】，否则就是无限递归，死龟了:)
-
当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁
举一个比较综合的案例,迷宫问题
走代码：
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()
}
}
课后思考题：
思考: 如何求出最短路径?
哈希表(散列)
实际的需求
google 公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查找到该员工的 所有信息.
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
哈希表的基本介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
使用 hashtable 来实现一个雇员的管理系统[增删改查]
思路分析
-
使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
-
思路分析并画出示意图
- 代码实现[增删改查(显示所有员工，按 id 查询)]
package main
import (
"fmt"
)
//定义 emp
type Emp struct {
Id int
Name string
Next *Emp
}
//方法待定..
//定义 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() //换行处理
}
//定义 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 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 "exit":
default:
fmt.Println("输入错误")
}
}
}
评论