一、稀疏数组
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:1、记录数组一共有几行几列，有多少个不同的值2、思想:把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模package mainimport "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\t", 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\n", 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\t", v2) } fmt.Println() }} 二、队列
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出1、数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明中应该有maxSize变量表示队列的最大容量。
队列的输出、输入是分别从前后端来处理，需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。package mainimport ( "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\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("加入队列成功") } 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 mainimport ( "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\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("加入队列成功") } 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 mainimport "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 mainimport "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("\n逆序打印") ListHeroDoubleNodeReverse(head)} 3、单向环形链表添加节点、删除节点和显示节点
package mainimport "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] ->\t", 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\n", id) flag = false break } tmp = tmp.next helper = helper.next } if flag { if tmp.no == id { helper.next = tmp.next fmt.Printf("抓到的人为%d\n", id) } else { fmt.Printf("没有找到%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)} 4、约瑟夫环问题
package mainimport "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出圈\n", first.No) first = first.Next tail.Next = first if tail == first { break } } fmt.Printf("最后剩下的小孩是%d\n", first.No)}func main() { first := AddBoy(500) ShowBoy(first) PlayGame(first, 20, 31)} 四、栈
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。package mainimport ( "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\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 = 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 mainimport "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 mainimport "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为空\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()}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("输入错误") } }}