数据结构代码

1.稀疏数组

当一个数组中大部分元素为0或者同为一个值时，可以用稀疏数组保存。即只记录不同的值。

第一个值一般记录原始大小。

  1. package main
  3. import (
  4.     "encoding/json"
  5.     "fmt"
  6.     "io/ioutil"
  7. )
  9. const (
  10.     BLACK_CHESS = 1 // 黑子
  11.     WIHTE_CHESS = 2 // 白子
  12.     FILE_NAME = "data.json"
  13. )
  15. type ValNode struct {
  16.     Row int `json:"row"`
  17.     Col int `json:"col"`
  18.     Val int `json:"val"`
  19. }
  22. // 稀疏数组
  23. func main() {
  24.     var chessMap [10][10]int
  25.     chessMap[1][5] = BLACK_CHESS
  26.     chessMap[2][3] = WIHTE_CHESS
  27.     chessMap[4][6] = BLACK_CHESS
  28.     chessMap[7][9] = WIHTE_CHESS
  30.     for _, v := range chessMap {
  31.         for _, v2 := range v {
  32.             fmt.Printf("%d\t", v2)
  33.         }
  34.         fmt.Println()
  35.     }
  37.     var sparseArr []ValNode
  38.     // 第一个结构体记录原始数组的大小
  39.     sparseArr = append(sparseArr, ValNode{Row: len(chessMap), Col: len(chessMap[0]), Val: 0})
  40.     for r, v := range chessMap {
  41.         for c, v2 := range v {
  42.             if v2 != 0 {
  43.                 valNode := ValNode{Row: r, Col: c, Val: v2}
  44.                 sparseArr = append(sparseArr, valNode)
  45.             }
  46.         }
  47.     }
  48.     // 打印
  49.     for _, node := range sparseArr {
  50.         fmt.Println(node)
  51.     }
  52.     // 存到文件,用json格式
  53.     j, err := json.Marshal(sparseArr)
  54.     if err != nil {
  55.         fmt.Println(err)
  56.         return
  57.     }
  58.     err = ioutil.WriteFile(FILE_NAME, j, 0666)
  59.     if err != nil {
  60.         fmt.Println(err)
  61.         return
  62.     }
  63.     // 恢复
  64.     b, err := ioutil.ReadFile(FILE_NAME)
  65.     if err != nil {
  66.         fmt.Println(err)
  67.         return
  68.     }
  69.     var sparseSlice []ValNode
  70.     err = json.Unmarshal(b, &sparseSlice)
  71.     if err != nil {
  72.         fmt.Println(err)
  73.         return
  74.     }
  75.     fmt.Println("恢复后的棋盘")
  76.     for _, sp := range sparseSlice {
  77.         fmt.Println(sp)
  78.     }
  80. }

2.环形队列

  1. package main
  3. import (
  4.     "errors"
  5.     "fmt"
  6. )
  8. /**
  9. 环形队列
  10. 思路：
  11. 1.创建一个数组，设置最大值
  12. 2.一个指向队首的指针front和一个指向队尾的指针real，初始化为0
  13. 3.提供三个方法：push,pop和show
  14. 4.当push的时候，real 指针往后移
  15. 5.pop的时候front指针往后移
  16. 6.当两个指针重合的时候，就空了
  17. 7.当real指针加一取模后等于头就满了
  19. 实际容量是数组容量减一
  20. */
  22. type CircleQueue struct {
  23.     MaxSize int  // 最大数量
  24.     Array [5]int  // slice
  25.     Head int     // 指向队首
  26.     Tail int     // 指向队尾
  27. }
  29. // 加入队列
  30. func (queue *CircleQueue) Push(val int) error {
  31.     if queue.IsFull() {
  32.         return errors.New("queue is full")
  33.     }
  34.     queue.Array[queue.Tail] = val
  35.     queue.Tail = (queue.Tail + 1) % queue.MaxSize
  36.     return nil
  37. }
  39. // 弹出
  40. func (queue *CircleQueue) Pop() (val int, err error) {
  41.     if queue.IsEmpty() {
  42.         return 0, errors.New("queue is empty")
  43.     }
  44.     val = queue.Array[queue.Head]
  45.     queue.Head = (queue.Head + 1) % queue.MaxSize
  46.     return val, nil
  47. }
  49. // 显示队列
  50. func (queue *CircleQueue) ShowQueue() {
  51.     size := queue.Size()
  52.     if size == 0 {
  53.         fmt.Println("queue is empty")
  54.         return
  55.     }
  56.     var tempHead = queue.Head
  57.     for i := 0; i < size; i++ {
  58.         fmt.Printf("arr[%d]=%d\t", tempHead, queue.Array[tempHead])
  59.         tempHead = (tempHead + 1) % queue.MaxSize
  60.     }
  61.     fmt.Println()
  62. }
  64. // 判断队列已满
  65. func (queue *CircleQueue)IsFull() bool {
  66.     return (queue.Tail + 1) % queue.MaxSize == queue.Head
  67. }
  69. // 是否为空
  70. func (queue *CircleQueue) IsEmpty() bool {
  71.     return queue.Head == queue.Tail
  72. }
  74. // 有多少个元素
  75. func (queue *CircleQueue) Size() int {
  76.     return (queue.Tail - queue.Head + queue.MaxSize) % queue.MaxSize
  77. }
  79. func main() {
  80.     // 队列
  81.     circleQueue := CircleQueue{MaxSize: 5}
  83.     circleQueue.ShowQueue()
  85.     err := circleQueue.Push(1)
  86.     ifError(err)
  88.     err = circleQueue.Push(4)
  89.     ifError(err)
  91.     err = circleQueue.Push(6)
  92.     ifError(err)
  94.     err = circleQueue.Push(5)
  95.     ifError(err)
  97.     err = circleQueue.Push(7)
  98.     ifError(err)
  100.     circleQueue.ShowQueue()
  102.     err = circleQueue.Push(7)
  103.     ifError(err)
  105.     v, err := circleQueue.Pop()
  106.     ifError(err)
  107.     fmt.Printf("pop value=%d\n", v)
  109.     circleQueue.ShowQueue()
  110. }
  112. func ifError(err error) {
  113.     if err != nil {
  114.         fmt.Println(err)
  115.     }
  117. }

3.单链表

一般来说，为了比较好的对单链表进行增删改查，我们会给它设置一个头节点，主要作用是标识链表头，而且不存放数据。

用链表实现队列更方便，效率更高。

  1. package main
  3. import "fmt"
  5. // 单链表
  6. type HeroNode struct {
  7.     no       int
  8.     name     string
  9.     nickName string
  10.     next     *HeroNode    // 指向下一个节点
  11. }
  13. // 直接在最后插入
  14. func insertLast(head *HeroNode, new *HeroNode) {
  15.     temp := head
  16.     for {
  17.         if temp.next == nil {  // 如果找到最后则跳出
  18.             break
  19.         }
  20.         temp = temp.next  // 不断指向下一个节点
  21.     }
  22.     temp.next = new
  23. }
  25. // 排序插入，根据no的大小
  26. func insertSort(head *HeroNode, new *HeroNode) {
  27.     temp := head
  28.     flag := true
  29.     // 比较新节点和temp的下一个节点
  30.     for {
  31.         if temp.next == nil { // 到了链表最后
  32.             break
  33.         } else if new.no < temp.next.no  {
  34.             // new 应该插入到temp的下一个
  35.             break
  36.         } else if new.no == temp.next.no {
  37.             flag = false
  38.         }
  39.         temp = temp.next  // 不断指向下一个节点
  40.     }
  41.     if !flag {
  42.         fmt.Println("对不起，节点已经存在,no=", new.no)
  43.         return
  44.     } else {
  45.         // 插入节点
  46.         new.next = temp.next
  47.         temp.next = new
  48.     }
  49. }
  51. // 删除一个节点
  52. // no : 删除的number
  53. func deleteNode(head *HeroNode, no int)  {
  54.     temp := head
  55.     finded := false
  56.     for {
  57.         if temp.next == nil { // 到了链表最后
  58.             break
  59.         } else if no == temp.next.no {
  60.             finded = true
  61.             break
  62.         }
  63.         temp = temp.next  // 不断指向下一个节点
  64.     }
  65.     if finded {
  66.         temp.next = temp.next.next
  67.     } else {
  68.         fmt.Println("没有找到")
  69.     }
  70. }
  72. func showAll(head *HeroNode) {
  73.     temp := head
  74.     // 先判断是不是空链表
  75.     if temp.next == nil {
  76.         fmt.Println("空空如也")
  77.         return
  78.     }
  79.     // 遍历链表
  80.     for {
  81.         fmt.Printf("[%d, %s, %s]->", temp.next.no, temp.next.name, temp.next.nickName)
  82.         temp = temp.next
  83.         if temp.next == nil {
  84.             break
  85.         }
  86.     }
  87.     fmt.Println()
  88. }
  90. func main() {
  91.     head := HeroNode{}
  92.     node1 := HeroNode{no: 1, name: "宋江", nickName: "及时雨"}
  93.     node2 := HeroNode{no: 2, name: "吴用", nickName: "智多星"}
  94.     node3 := HeroNode{no: 3, name: "林冲", nickName: "豹子头"}
  95.     node4 := HeroNode{no: 4, name: "X", nickName: "x"}
  96.     //insertLast(&head, &node2)
  97.     //insertLast(&head, &node3)
  98.     //insertLast(&head, &node1)
  99.     insertSort(&head, &node2)
  100.     insertSort(&head, &node4)
  101.     insertSort(&head, &node3)
  102.     insertSort(&head, &node1)
  103.     showAll(&head)
  104.     deleteNode(&head, 3)
  105.     showAll(&head)
  106. }

还有 双向链表 和 环形链表，先放一放，估计也很少用到。

4. 栈

应用场景：

  1. 子程序调用：在跳往子程序前，会将下个指令的地址保存在栈中，直到子程序执行完，再从栈中取出；
  2. 处理递归调用；
  3. 表达式的求值与转换；
  4. 二叉树遍历；
  5. 图形的深度优先搜索法。
  1. package chapter2
  3. import (
  4.     "errors"
  5.     "fmt"
  6. )
  8. // 实现一个栈
  9. // 出栈、入栈、遍历
  11. type Stack struct {}
  13. var arr [5]int        // 用数组实现栈
  14. var pointer = -1    // 位置指针
  16. // 出栈
  17. func (this *Stack) Pop() (val int, err error){
  18.     if pointer < 0 {
  19.         return -1, errors.New("stack is empty")
  20.     }
  21.     val = arr[pointer]
  22.     pointer -= 1
  23.     return val, nil
  24. }
  26. // 入栈
  27. func (this *Stack) Push(val int) {
  28.     if pointer >= len(arr)-1 {
  29.         fmt.Println("stack is full")
  30.         return
  31.     }
  32.     pointer += 1
  33.     arr[pointer] = val
  34. }
  36. // 遍历
  37. func (this *Stack) List() {
  38.     if pointer < 0 {
  39.         fmt.Println("stack is empty")
  40.         return
  41.     }
  42.     fmt.Println("stack list:")
  43.     for i := pointer; i >= 0; i-- {
  44.         fmt.Println(arr[i])
  45.     }
  46. }

表达式求值思路：

  1. 用两个栈，一个保存数，一个保存操作符；
  2. 如果已经入栈的操作符优先级比要入栈的低，那么先计算