go 算法与数据结构
数据结构
package main
import "fmt"
/*
稀疏数组
案例：五子棋存盘与复盘
节省存储空间
*/
type ValNode struct {
row int //行
col int //列
val int //值
}
//原始数组实现
func normalArray() {
var chessMap [][]int
chessMap[][] = //黑子
chessMap[][] = //白子
//输出
for _, v := range chessMap {
for _, v2 := range v {
fmt.Printf("%d ", v2)
}
fmt.Println()
}
}
//稀疏数组实现
func sparseArray() {
//数据源
var chessMap [][]int
chessMap[][] = //黑子
chessMap[][] = //白子
//切片
var sparseArr []ValNode
//创建一个ValNode节点
valNode := ValNode{
row: ,
col: ,
val: ,
}
//输入全局默认节点
sparseArr = append(sparseArr, valNode)
for i, v := range chessMap {
for j, v2 := range v {
//创建一个节点
if v2 != {
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)
}
var chessMap2 \[\]\[\]int
//稀疏数组恢复原始数组
for i, valNode := range sparseArr {
//跳过第一行默认记录值
if i != {
chessMap2\[valNode.row\]\[valNode.row\] = valNode.val
}
} //输出恢复后的数组
for _,v:=range chessMap2{
for _,v2:=range v{
fmt.Printf("%d ",v2)
}
fmt.Println()
}
}
func main() {
sparseArray()
}
使用数据模拟队列
package main
import (
"errors"
"fmt"
"os"
)
//使用结构体管理队列
type Queue struct {
maxSize int
array []int //数组=》模拟队列
front int //表示指向队首
rear int //表示指向队尾
}
//添加数据到队列
func (this *Queue) AddQueue(val int) (err error) {
//先判断队列是否已满
if this.rear == this.maxSize- { //重要提示，rear是队列尾部(含最后元素
return errors.New("queue full")
}
//元素从下标为1开始存入
this.rear++ //后移
//存入元素
this.array[this.rear] = val
return
}
//从队列中取出元素
func (this *Queue) GetQueue() (val int, err error) {
//先判断队列是否为空
if this.rear == this.front { //队列
return -, 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 + ; i <= this.rear; i++ {
fmt.Printf("array[%d]=%d\t", i, this.array[i])
}
}
func main(){
//创建一个队列
queue:=&Queue{
maxSize: ,
array: []int{},
front: -,
rear: -,
}
var key string
var val int
for{
fmt.Println("\n\n1.输入add表示添加数据到队列")
fmt.Println("2.输入get表示从队列获取数据")
fmt.Println("3.输入show表示显示队列")
fmt.Println("4.输入exit表示退出\n\n")
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.Print("加入队列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()
}
}
}
通过数组实现环形队列
package main
import (
"errors"
"fmt"
"os"
)
//数组模拟环形队列
/*
1.尾索引下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意
(tail+1)%maxSize==head满
2.tail==head [空]
*/
type CircleQueue struct {
maxSize int //
array []int //数组
head int //指向队首0
tail int //指向队尾0
}
//入队
func (this *CircleQueue) Push(val int) (err error) {
if this.IsFull() {
return errors.New("queue full")
}
//分析指出this.tail 在队列尾部，但是包含最后的元素
this.array[this.tail] = val //把值给队尾
//如果当前行满。回到行初开始(加1是因为下标从零开始)
this.tail = (this.tail + ) % this.maxSize
return
}
//出队
func (this *CircleQueue) Pop() (val int, err error) {
if this.IsEmpty() {
return , errors.New("queue empty")
}
//取出head指向队首，并且含队首元素
val = this.array[this.head]
//%如果满行回到行首
this.head = (this.head + ) % this.maxSize
return
}
//显示队列
func (this *CircleQueue) ListQueue() {
fmt.Println("环形队列情况如下")
//取出当前队列有多少个元素
size := this.Size()
if size == {
fmt.Println("队列为空")
}
//设计一个辅助便理那个指向head
tempHead := this.head
for i := ; i < size; i++ {
fmt.Printf("arr[%d]=%d\t", tempHead, this.array[tempHead])
tempHead = (tempHead + ) % this.maxSize
}
fmt.Println()
}
//判断队列为满
func (this *CircleQueue) IsFull() bool {
//队尾之前的长度%总长度=队首之后的长度
return (this.tail+)%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
}
/*
1.队尾在队首之后
this.tail% this.maxSize + this.maxSize% this.maxSize - this.head% this.maxSize
队尾之前的长度+1-队首之前的长度=总长度
*/
func main() {
cq := CircleQueue{
maxSize: ,
array: []int{},
head: ,
tail: ,
}
var key string
var val int
for {
fmt.Println("\n\n1.输入add表示添加数据到队列")
fmt.Println("2.输入get表示从队列获取数据")
fmt.Println("3.输入show表示显示队列")
fmt.Println("4.输入exit表示退出\n\n")
fmt.Scanln(&key)
switch key {
case "add":
fmt.Println("请输入入队的数:")
fmt.Scanln(&val)
err := cq.Push(val)
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println("入队成功")
}
case "get":
val, err := cq.Pop()
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Printf("出队成功:%d", val)
}
case "show":
cq.ListQueue()
case "exit":
os.Exit()
default:
fmt.Println("输入错误")
}
}
}
单向链表
package main
import "fmt"
/*
单向链表的应用
水浒英雄排行榜
*/
type HeroNode struct {
no int
name string
nickname string
next *HeroNode //表示指向下一个节点
}
//给链表插入一个节点
//编写第一个插入方法，在单链表最后加入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
temp := head
for {
if temp.next == nil { //表示找到最后
break
}
temp = temp.next //让temp不断指向下一个节点
}
//3.将newHeroNode加入到链表最后
temp.next = newHeroNode
}
//第二种插入方法，根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHreoNode *HeroNode) {
//1.找到适当的节点
temp := head
flag := true
//让插入的节点的no,和temp的下一个结点比较
for {
if temp.next == nil { //说明到了链表最后
break
} else if temp.next.no >= newHreoNode.no {
//说明newHeroNode就应该插入到temp后面
break
} else if temp.next.no == newHreoNode.no {
//说明链表中已经有这个no,就不插入
flag = false
break
}
//不断寻找下一个结点
temp = temp.next
}
if !flag {
fmt.Println("对不起，已经存在no=", newHreoNode.no)
return
} else {
newHreoNode.next = temp.next
temp.next = newHreoNode
} }
//显示所有链表节点信息
func ListNode(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 DelHeroNode(head *HeroNode, id int) {
temp := head
flag := false
//找到要删除的结点，和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 main() {
//1.先创建一个头结点
head := &HeroNode{}
//2.创建一个新的HeroNode
hero1 := &HeroNode{
no: ,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroNode{
no: ,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroNode{
no: ,
name: "林冲",
nickname: "豹子头",
}
hero4 := &HeroNode{
no: ,
name: "吴用",
nickname: "智多星",
}
InsertHeroNode(head, hero4)
InsertHeroNode(head, hero1)
InsertHeroNode(head, hero2)
InsertHeroNode(head, hero3)
ListNode(head)
//3.加入
//InsertHeroNode2(head, hero3)
//InsertHeroNode2(head, hero1)
//InsertHeroNode2(head, hero2)
//InsertHeroNode2(head, hero4)
////4.显示
//ListNode(head) }
双向链表
package main
import "fmt"
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
}
//给双向链表插入一个结点
//
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 {
flag = false
break
}
temp = temp.next
}
if !flag {
fmt.Println("对不起，已经存在no=", newHeroNode.no)
return
} else {
newHeroNode.next = temp.next
newHeroNode.pre = temp
if temp.next != nil { //不是最后一个才进行操作
temp.next.pre = newHeroNode
}
temp.next = newHeroNode
} }
//删除结点
func DelHeroNode(head *HeroNode, id int) {
temp := head
flag := true
//找到要删除的结点的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
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
}
//遍历链表
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
}
//遍历链表
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: ,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroNode{
no: ,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroNode{
no: ,
name: "林冲",
nickname: "豹子头",
}
hero4 := &HeroNode{
no: ,
name: "吴用",
nickname: "智多星",
}
InsertHeroNode(head, hero1)
InsertHeroNode(head, hero2)
InsertHeroNode(head, hero3)
InsertHeroNode(head, hero4)
ListHeroNode(head)
fmt.Println("\\n逆序打印")
ListHeroNode2(head)}
环形单向链表
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 //执行删除
fmt.Printf("删除猫猫=%d\n", id)
}
return head
}
//将helper定位到链表最后
for {
if helper.next == head {
break
}
helper = helper.next
}
//到这里为止helper为最后一个结点，temp为头结点，也就是说helper是temp前面一个结点。在循环中两者的关系始终相邻。
//head为头结点
//如果有两个包含两个以上的结点
flag := true
for {
//循环到结尾，跳出
if temp.next == head { //如果到这来，说明我们比较到最后一个\[最后一个还没比较\]
break
}
//找到结点
if temp.no == id {
//目标是头结点
if temp == head { //说明删除的是头结点
head = head.next //删除头结点
}
//目标是其他结点
//恭喜找到，我们也可以直接删除
helper.next = temp.next //执行删除，如果helper.no为2，temp.no为3，此时删除的是3
fmt.Printf("删除猫猫=%d\\n", id)
flag = false
break
}
//继续循环，类似i++,两个结点同步循环
temp = temp.next //移动
helper = helper.next //移动
}
//flag为true表示没找到
if flag {
fmt.Printf("对不起，没有no=%d\\n", id)
}
return head }
func main() {
//初始化一个环形链表的头节点
head := &CatNode{}
//创建一只猫
cat1 := &CatNode{
no: ,
name: "tom",
}
cat2 := &CatNode{
no: ,
name: "tom2",
}
cat3 := &CatNode{
no: ,
name: "tom3",
}
cat4 := &CatNode{
no: ,
name: "tom4",
}
InsertCatNode(head, cat1)
InsertCatNode(head, cat2)
InsertCatNode(head, cat3)
InsertCatNode(head, cat4)
ListCircleLink(head)
head = DelCatNode(head, )
fmt.Println()
fmt.Println()
fmt.Println()
fmt.Println()
ListCircleLink(head)}
环形单向链表应用
package main
import "fmt"
/*
环形单项链表的应用
问题为:设编号为1, 2，… n的n个人围坐一圈，约定编号为k (1<=k<=n) 的人从1
台报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，
直到所有人出列为止，由此产生个出队编号 的序列。
*/
//小孩的结构体
type Boy struct {
No int //编号
Next *Boy //指向下一个小孩的指针【默认值是nil】
}
//编写一个函数，构成单向的环形链表
//num:表示小孩的个数
//*Boy:返回该环形链表的第一个小孩的指针
func AddBoy(num int) *Boy {
first := &Boy{} //空结点
curBoy := &Boy{} //空结点
//判断
if num < {
fmt.Println("num的值不对")
return first
}
//循环的构建这个环形链表
for i := ; i <= num; i++ {
boy := &Boy{
No: i,
}
//分析构成循环链表，需要一个辅助指针
//1.因为第一个小孩比较特殊
if i == { //第一个小孩
first = boy //不要动
curBoy = boy //curBoy默认为第一个小孩
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.Println("小孩编号=%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 := ; i <= startNo-; i++ {
first = first.Next
tail = tail.Next
} //保持顺序推进到开始结点
fmt.Println()
//.开始数countNum,然后删除first指向的小孩
for {
//开始数countNum-1次
for i := ; i <= countNum-; i++ {
first = first.Next
tail = tail.Next
}
fmt.Printf("小孩编号为%d 出圈\n", first.No)
//删除first执行大小孩
first = first.Next //链接后面的新的，同时表示删除
//tail始终是first前面一个
tail.Next = first //把first前面的链接上
//判断如果tail==first，圈子中只有一个小孩
if tail == first {
break
}
}
fmt.Printf("小孩编号为%d出圈\n", first.No)
}
func main() {
first := AddBoy()
//显示
ShowBoy(first)
PlayGame(first, , )
}
算法
package main
import (
"fmt"
)
/*
选择排序
*/
func SelectSort(arr *[]int) {
for j := ; j < len(arr)-; j++ {
max := arr[j]
maxIndex := j
//每一次都找到全局最大值，放到前面
for i := j + ; 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+, *arr)
} }
/*
插入排序
*/
func InsertSort(arr *[]int) {
//完成第一次，给第二个元素找到合适的位置并插入
for i := ; i < len(arr); i++ {
insertVal := arr[i]
insertIndex := i - //下标
//如果后面的值大于前面的值，进行交换
//对i前面的数，从右向左，一次相邻作比较，大的放前面,同时数据后移
for insertIndex >= && arr[insertIndex] < insertVal {
fmt.Printf("arr[%v]=%v<%v\n", insertIndex, arr[insertIndex], insertVal)
arr[insertIndex+] = arr[insertIndex] //数据后移
insertIndex--
}
//插入
if insertIndex+ != i {
fmt.Printf("insertIndex=%v\n", insertIndex)
arr[insertIndex+] = insertVal
}
fmt.Printf("第%d次插入后 %v\n", i, *arr)
}
}
/*
快速排序法
*/
//说明
//1.left表示数组左边的下标
//2.right表示数组右边的下标
//3.array表示要排序的数组
func QuickSort(left int, right int, array *[]int) {
l := left
r := right
//pivot是中轴，支点
pivot := array[(left+right)/]
temp :=
//for循环的目标是将此pivot小的数放到左边
//比pivot大的数放到右边
for ; l < r; {
//从pivot的左边找到大于等于pivot的值
for ; array[l] < pivot; {
l++
}
//从pivot的upibian找到小于等于pivot的值
for ; array[r] > pivot; {
r--
}
//l<=r 表明本次分解任务完成，nreak
if l >= r {
break
}
//交换
temp = array[l]
array[l] = array[r]
array[r] = temp
//优化
if array[l] == pivot {
r--
}
if array[r] == pivot {
l++
}
}
//如果 lr,再移动下
if l == r {
l++
r--
}
//向左递归
if left < r {
QuickSort(left, r, array)
}
//向右递归
if right > l {
QuickSort(l, right, array)
}
}
func main() {
//arr:=[6]int{2,34,56,678,3,4}
//SelectSort(&arr)
//iarr := \[7\]int{2, 354, 67, 5, 687, 22, 343}
//InsertSort(&iarr)
arr:=\[\]int{-,,,,-,,,,-}
fmt.Println("初始",arr)
//调用快速排序
QuickSort(,len(arr)-,&arr)
fmt.Println("main..")
fmt.Println(arr) }
使用数组来模拟一个栈的使用
package main
import (
"errors"
"fmt"
)
//使用数组来模拟一个栈的使用
type Stack struct {
MaxTop int //表示我们栈最大可以存放的个数
Top int //表示栈顶，因为栈顶固定，因此直接使用Top
arr []int //数组模拟战
}
//入栈
func (this *Stack) Push(val int) (err error) {
//判断栈是否满了
if this.Top == this.MaxTop- {
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 == - {
fmt.Println("stack empty !")
return , errors.New("stack empty")
}
//先取值，再this.Top--
val = this.arr[this.Top]
this.Top--
return val, nil
}
//遍历栈，注意需要从栈顶开始遍历
func (this *Stack) List() {
//先判断栈是否为空
if this.Top == - {
fmt.Println("stack empty")
return
}
fmt.Println("栈的情况如下：")
for i := this.Top; i >= ; i-- {
fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
}
}
func main() {
stack := &Stack{
MaxTop : , // 表示最多存放5个数到栈中
Top : -, // 当栈顶为-1，表示栈为空,因为数组下标是从0开始
}
stack.Push()
stack.Push()
stack.Push()
stack.Push()
stack.List()
stack.Pop()
stack.List()
}
栈实现综合计算器
package main
import (
"errors"
"fmt"
"strconv"
)
//使用数组来模拟一个栈的使用
type Stack struct {
MaxTop int // 表示我们栈最大可以存放数个数
Top int // 表示栈顶, 因为栈顶固定，因此我们直接使用Top
arr []int // 数组模拟栈
}
//入栈
func (this *Stack) Push(val int) (err error) {
//先判断栈是否满了
if this.Top == this.MaxTop- {
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 == - {
fmt.Println("stack empty!")
return , errors.New("stack empty")
}
//先取值，再 this.Top--
val = this.arr\[this.Top\]
this.Top--
return val, nil}
//遍历栈，注意需要从栈顶开始遍历
func (this *Stack) List() {
//先判断栈是否为空
if this.Top == - {
fmt.Println("stack empty")
return
}
fmt.Println("栈的情况如下：")
for i := this.Top; i >= ; i-- {
fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
}
}
//判断一个字符是不是一个运算符[+, - , * , /]
func (this *Stack) IsOper(val int) bool {
if val == || val == || val == || val == {
return true
} else {
return false
} }
//运算的方法
func (this *Stack) Cal(num1 int, num2 int, oper int) int {
res :=
switch oper {
case :
res = num2 * num1
case :
res = num2 + num1
case :
res = num2 - num1
case :
res = num2 / num1
default:
fmt.Println("运算符错误.")
}
return res
}
//编写一个方法，返回某个运算符的优先级[程序员定义]
//[* / => 1 + - => 0]
func (this *Stack) Priority(oper int) int {
res :=
if oper == || oper == {
res =
} else if oper == || oper == {
res =
}
return res
}
func main() {
//数栈
numStack := &Stack{
MaxTop: ,
Top: -,
}
//符号栈
operStack := &Stack{
MaxTop: ,
Top: -,
}
exp := "30+3\*6-4-6"
//定义一个index ，帮助扫描exp
index :=
//为了配合运算，我们定义需要的变量
num1 :=
num2 :=
oper :=
result :=
keepNum := ""
for {
//这里我们需要增加一个逻辑，
//处理多位数的问题
ch := exp\[index : index+\] // 字符串.
//ch ==>"+" ===> 43
temp := int(\[\]byte(ch)\[\]) // 就是字符对应的ASCiI码
if operStack.IsOper(temp) { // 说明是符号
//如果operStack 是一个空栈， 直接入栈
if operStack.Top == - { //空栈
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()
//num1先出栈，num2后出栈，说明num2是先入栈的num2作为操作数，num1作为被操作数也就是，num2-num1,num2/num1
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)- {
val, \_ := strconv.ParseInt(keepNum, , )
numStack.Push(int(val))
} else {
//向index 后面测试看看是不是运算符 \[index\]
if operStack.IsOper(int(\[\]byte(exp\[index+ : index+\])\[\])) {
val, \_ := strconv.ParseInt(keepNum, , )
numStack.Push(int(val))
keepNum = ""
}
}
}
//继续扫描
//先判断index是否已经扫描到计算表达式的最后
if index+ == len(exp) {
break
}
index++
}
//如果扫描表达式 完毕，依次从符号栈取出符号，然后从数栈取出两个数，
//运算后的结果，入数栈，直到符号栈为空
for {
if operStack.Top == - {
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) }
迷宫找路
package main
import (
"fmt"
)
//编写一个函数，完成老鼠找路
//myMap *[8][7]int:地图，保证是同一个地图，使用引用
//i,j 表示对地图的哪个点进行测试
func SetWay(myMap *[][]int, i int, j int) bool {
//分析出什么情况下，就找到出路
//myMap\[6\]\[5\] == 2
if myMap\[\]\[\] == {
return true
} else {
//说明要继续找
if myMap\[i\]\[j\] == { //如果这个点是可以探测
//假设这个点是可以通, 但是需要探测 上下左右
//换一个策略 下右上左
myMap\[i\]\[j\] =
if SetWay(myMap, i+, j) { //下
return true
} else if SetWay(myMap, i, j+) { //右
return true
} else if SetWay(myMap, i-, j) { //上
return true
} else if SetWay(myMap, i, j-) { //左
return true
} else { // 死路
myMap\[i\]\[j\] =
return false
}
} else { // 说明这个点不能探测，为1，是强
return false
}
} }
func main() {
//先创建一个二维数组，模拟迷宫
//规则
//1. 如果元素的值为1 ，就是墙
//2. 如果元素的值为0, 是没有走过的点
//3. 如果元素的值为2, 是一个通路
//4. 如果元素的值为3， 是走过的点，但是走不通
var myMap [][]int
//先把地图的最上和最下设置为1
for i := ; i < ; i++ {
myMap\[\]\[i\] =
myMap\[\]\[i\] =
}
//先把地图的最左和最右设置为1
for i := ; i < ; i++ {
myMap\[i\]\[\] =
myMap\[i\]\[\] =
}
myMap\[\]\[\] =
myMap\[\]\[\] =
myMap\[\]\[\] =
myMap\[\]\[\] =
//输出地图
for i := ; i < ; i++ {
for j := ; j < ; j++ {
fmt.Print(myMap\[i\]\[j\], " ")
}
fmt.Println()
}
//使用测试
SetWay(&myMap, , )
fmt.Println("探测完毕....")
//输出地图
for i := ; i < ; i++ {
for j := ; j < ; j++ {
fmt.Print(myMap\[i\]\[j\], " ")
}
fmt.Println()
}}
雇员系统
package main
import (
"fmt"
"os"
)
/*
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别，年龄，住址..)，当输入该员工
的id时要求查找到该员工的所有信息.
➢要求:
1)不使用数据库尽量节省内存，速度越快越好=>哈希表(散列)
2)添加时，保证按照雇员的id从低到高插入
*/
//定义emp
type Emp struct {
Id int
Name string
Next *Emp
}
//方法待定..
func (this *Emp) ShowMe() {
fmt.Printf("链表%d 找到该雇员 %d\n", this.Id%, 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前面，且相邻
pre = cur //保证同步
cur = cur.Next //移动，此种方法会导致最后一个判断为nil,对应上面的cur!=nil判断
} else {
break
}
}
//退出时，我们看下是否将emp添加到链表最后
pre.Next = emp //存入pre后面
emp.Next = cur //后面连上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 []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 := ; i < len(this.LinkArr); i++ {
this.LinkArr[i].ShowLink(i)
}
}
//编写一个散列方法
func (this *HashTable) HashFun(id int) int {
return id % //得到一个值，就是对于的链表的下标
}
//编写一个方法，完成查找
func (this *HashTable) FindById(id int) *Emp {
//使用散列函数，确定将该雇员应该在哪个链表
linkNo := this.HashFun(id)
return this.LinkArr[linkNo].FindById(id)
}
func main() {
key := ""
id :=
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()
default:
fmt.Println("输入错误")
}
}}
前，中，后遍历
package main
import "fmt"
/*
二叉树三种遍历方式
*/
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//前序遍历【先输出root结点，然后再输出左子树，然后右子树】
func PreOrder(node *Hero) {
if node != nil {
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历【先输出root左子树，再输出root结点，最后输出root的有子树】
func InfixOrder(node *Hero) {
if node != nil {
InfixOrder(node.Left)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
InfixOrder(node.Right)
}
}
//后序遍历
func PostOrder(node *Hero) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
}
}
func main() {
//构建一个二叉树
root := &Hero{
No: ,
Name: "宋江",
}
left1 := &Hero{
No: ,
Name: "吴用",
}
node10 := &Hero{
No: ,
Name: "李逵",
}
node12 := &Hero{
No: ,
Name: "杨雄",
}
left1.Left = node10
left1.Right = node12
right1 := &Hero{
No: ,
Name: "卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No: ,
Name: "林冲",
}
right1.Right = right2
fmt.Println("前")
PreOrder(root)
fmt.Println("中")
InfixOrder(root)
fmt.Println("后")
PostOrder(root) }
。。。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章