一、稀疏数组
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
1、记录数组一共有几行几列，有多少个不同的值
2、思想:把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
package main
import "fmt"
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 ", v2)
}
fmt.Println()
}
//转成稀疏数组:遍历chessMap, 如果发现有一个元素的值不为0，创建一个node结构体,将其放入到对应的切片即可
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
", i, valNode.row, valNode.col, valNode.val)
}
//将这个稀疏数组存盘
//恢复这个稀疏数组
//创建一个原始数组
var chessMap2 [11][11]int
for i, valNode := range sparseArr {
//跳过第一行记录值
if i != 0 {
chessMap2[valNode.row][valNode.col] = valNode.val
}
}
fmt.Println("恢复后的原始数据")
for _, v := range chessMap2 {
for _, v2 := range v {
fmt.Printf("%d ", v2)
}
fmt.Println()
}
}
二、队列
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出
1、数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明中应该有maxSize变量表示队列的最大容量。
队列的输出、输入是分别从前后端来处理，需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。
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 {
return errors.New("queue full")
}
this.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("队列当前元素是：")
for i := this.front + 1; i <= this.rear; i++ {
fmt.Printf("array[%d]=%d ", 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("加入队列成功")
}
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)
}
}
}
2、数组模拟环形队列
package main
import (
"errors"
"fmt"
"os"
)
type CircleQueue struct {
maxSize int //队列的容量
array [5]int //数组模拟队列
head int //表示指向队列首部
tail int //表示指向队列的尾部
}
//添加数据到队列
func (this *CircleQueue) Push(val int) (err error) {
//判断队列是否已满
if this.IsFull() {
return errors.New("queue full")
}
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")
}
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("队列为空")
}
tempHead := this.head
for i := 0; i < size; i++ {
fmt.Printf("array[%d]=%d ", 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("加入队列成功")
}
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)
}
}
}
三、链表
1、单链表
package main
import "fmt"
type HeroNode struct {
no int
name string
nickname string
next *HeroNode
}
//在单链表的最后插入节点
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
tmp := head
for {
if tmp.next == nil {
break
}
tmp = tmp.next
}
tmp.next = newHeroNode
}
//根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
tmp := head
flag := true
for {
if tmp.next == nil {
break
} else if tmp.next.no >= newHeroNode.no {
break
} else if tmp.next.no == newHeroNode.no {
flag = false
break
}
tmp = tmp.next
}
if !flag {
fmt.Println("no已存在", newHeroNode.no)
return
} else {
newHeroNode.next = tmp.next
tmp.next = newHeroNode
}
}
func ListHeroNode(head *HeroNode) {
tmp := head
if tmp.next == nil {
fmt.Println("链表为空")
return
}
for {
fmt.Printf("[%d,%s,%s]-->", tmp.next.no, tmp.next.name, tmp.next.nickname)
tmp = tmp.next
if tmp.next == nil {
break
}
}
}
func DelHeroNode(head *HeroNode, id int) {
tmp := head
flag := false
for {
if tmp.next == nil {
break
} else if tmp.next.no == id {
flag = true
break
}
tmp = tmp.next
}
if flag {
tmp.next = tmp.next.next
} else {
fmt.Println("sorry,要删除的ID不存在")
}
}
func main() {
head := &HeroNode{}
hero1 := &HeroNode{
no: 1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroNode{
no: 2,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroNode{
no: 3,
name: "林冲",
nickname: "豹子头",
}
hero4 := &HeroNode{
no: 4,
name: "吴用",
nickname: "智多星",
}
InsertHeroNode2(head, hero3)
InsertHeroNode2(head, hero1)
InsertHeroNode2(head, hero2)
InsertHeroNode2(head, hero4)
ListHeroNode(head)
DelHeroNode(head, 3)
ListHeroNode(head)
}
2、双链表
package main
import "fmt"
type HeroDoubleNode struct {
no int
name string
nickname string
pre *HeroDoubleNode
next *HeroDoubleNode
}
//在单链表的最后插入节点
func InsertNode(head *HeroDoubleNode, newHeroNode *HeroDoubleNode) {
tmp := head
for {
if tmp.next == nil {
break
}
tmp = tmp.next
}
tmp.next = newHeroNode
newHeroNode.pre = tmp
}
//根据no的编号从小到大插入
func InsertNode2(head *HeroDoubleNode, newHeroNode *HeroDoubleNode) {
tmp := head
flag := true
for {
if tmp.next == nil {
break
} else if tmp.next.no >= newHeroNode.no {
break
} else if tmp.next.no == newHeroNode.no {
flag = false
break
}
tmp = tmp.next
}
if !flag {
fmt.Println("该编号的节点已经存在")
return
} else {
newHeroNode.next = tmp.next
newHeroNode.pre = tmp
if tmp.next != nil {
tmp.next.pre = newHeroNode
}
tmp.next = newHeroNode
}
}
//删除一个节点
func DelHeroDoubleNode(head *HeroDoubleNode, id int) {
tmp := head
flag := false
for {
if tmp.next == nil {
break
} else if tmp.next.no == id {
flag = true
break
}
tmp = tmp.next
}
if flag {
tmp.next = tmp.next.next
if tmp.next != nil {
tmp.next.pre = tmp
} else {
fmt.Println("sorry,要删除的ID不存在")
}
}
}
//显示链表的所有节点信息
func ListHeroDoubleNode(head *HeroDoubleNode) {
tmp := head
if tmp.next == nil {
fmt.Println("链表为空")
return
}
for {
fmt.Printf("[%d,%s,%s]-->", tmp.next.no, tmp.next.name, tmp.next.nickname)
tmp = tmp.next
if tmp.next == nil {
break
}
}
}
func ListHeroDoubleNodeReverse(head *HeroDoubleNode) {
tmp := head
if tmp.next == nil {
fmt.Println("链表为空")
return
}
for {
if tmp.next == nil {
break
}
tmp = tmp.next
}
for {
fmt.Printf("[%d,%s,%s]-->", tmp.no, tmp.name, tmp.nickname)
tmp = tmp.pre
if tmp.pre == nil {
break
}
}
}
func main() {
head := &HeroDoubleNode{}
hero1 := &HeroDoubleNode{
no: 1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroDoubleNode{
no: 2,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroDoubleNode{
no: 3,
name: "林冲",
nickname: "豹子头",
}
InsertNode(head, hero1)
InsertNode(head, hero2)
InsertNode(head, hero3)
ListHeroDoubleNode(head)
fmt.Println("
逆序打印")
ListHeroDoubleNodeReverse(head)
}
3、单向环形链表添加节点、删除节点和显示节点
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
}
tmp := head
for {
if tmp.next == head {
break
}
tmp = tmp.next
}
tmp.next = newCatNode
newCatNode.next = head
}
func ListCircleLink(head *CatNode) {
fmt.Println("环形链表的节点如下:")
tmp := head
if tmp.next == nil {
fmt.Println("链表为空")
return
}
for {
fmt.Printf("[id=%d name=%s] -> ", tmp.no, tmp.name)
if tmp.next == head {
break
}
tmp = tmp.next
}
}
func DelCatNode(head *CatNode, id int) *CatNode {
tmp := head
helper := head
if tmp.next == nil {
fmt.Println("链表为空")
return head
}
//只有一个节点
if tmp.next == head {
if tmp.no == id {
tmp.next = nil
}
return head
}
for {
if helper.next == head {
break
}
helper = helper.next
}
flag := true
for {
if tmp.next == head {
break
}
if tmp.no == id {
if tmp == head {
head = head.next
}
helper.next = tmp.next
fmt.Printf("抓到的人为%d
", id)
flag = false
break
}
tmp = tmp.next
helper = helper.next
}
if flag {
if tmp.no == id {
helper.next = tmp.next
fmt.Printf("抓到的人为%d
", id)
} else {
fmt.Printf("没有找到%d
", 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)
}
4、约瑟夫环问题
package main
import "fmt"
type Boy struct {
No int
Next *Boy
}
//构成单向的环形链表,num:表示小孩的个数,返回该环形的链表的第一个小孩的指针
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,
}
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)
if curBoy.Next == first {
break
}
curBoy = curBoy.Next
}
}
func PlayGame(first *Boy, startNo int, countNum int) {
if first.Next == nil {
fmt.Println("链表为空，没有小孩")
return
}
tail := first
for {
if tail.Next == first {
break
}
tail = tail.Next
}
for i := 1; i <= startNo-1; i++ {
first = first.Next
tail = tail.Next
}
fmt.Println()
for {
for i := 1; i <= countNum-1; i++ {
first = first.Next
tail = tail.Next
}
fmt.Printf("小孩编号为%d出圈
", first.No)
first = first.Next
tail.Next = first
if tail == first {
break
}
}
fmt.Printf("最后剩下的小孩是%d
", first.No)
}
func main() {
first := AddBoy(500)
ShowBoy(first)
PlayGame(first, 20, 31)
}
四、栈
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
package main
import (
"errors"
"fmt"
"strconv"
)
type Stack struct {
MaxTop int //表示栈的最大容量
Top int //表示栈顶，栈顶是固定的
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")
}
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
", 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 = num1 * num2
case 43:
res = num1 + num2
case 45:
res = num2 - num1
case 47:
res = num2 / num1
default:
fmt.Println("运算符错误")
}
return res
}
//返回某个运算符的优先级
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 := 0
num1 := 0
num2 := 0
oper := 0
result := 0
keepNum := ""
for {
ch := exp[index : index+1]
tmp := int([]byte(ch)[0])
if operStack.IsOper(tmp) {
if operStack.Top == -1 {
operStack.Push(tmp)
} else {
//如果发现opertStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级就从符号栈pop出，
//并从数栈也pop两个数进行运算，运算后的结果再重新入栈到数栈,当前符号再入符号栈
if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(tmp) {
num1, _ = numStack.Pop()
num2, _ = numStack.Pop()
oper, _ = operStack.Pop()
result = operStack.Cal(num1, num2, oper)
numStack.Push(result)
operStack.Push(tmp)
} else {
operStack.Push(tmp)
}
}
} else {
keepNum += ch
//如果已经到表达最后，直接将keepNum入栈
if index == len(exp)-1 {
val, _ := strconv.ParseInt(keepNum, 10, 64)
numStack.Push(int(val))
} else {
//向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)
}
res, _ := numStack.Pop()
fmt.Printf("表达式%s = %v", exp, res)
}
五、递归
package main
import "fmt"
func SetWay(myMap *[8][7]int, i int, j int) bool {
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是墙,如果元素的值为0是没有走过的点,如果元素的值为2是一个通路,如果元素的值为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()
}
}
六、哈希表
散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
使用hashtable来实现一个雇员的管理系统[增删改查]。使用链表来实现哈希表, 该链表不带表头，即链表的第一个结点就存放雇员信息。
package main
import "fmt"
type Emp struct {
Id int
Name string
Next *Emp
}
type EmpLink struct {
Head *Emp
}
//添加员工
func (this *EmpLink) Insert(emp *Emp) {
cur := this.Head
var pre *Emp = nil
if cur == nil {
this.Head = emp
return
}
for {
if cur != nil {
if cur.Id > emp.Id {
//找到位置
break
}
pre = cur
cur = cur.Next
} else {
break
}
}
pre.Next = emp
emp.Next = cur
}
func (this *EmpLink) ShowLink(no int) {
if this.Head == nil {
fmt.Printf("链表%d为空
", 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()
}
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("输入错误")
}
}
}