• [go学习笔记.第十八章.数据结构] 1.基本介绍,稀疏数组,队列(数组实现),链表

    一.基本介绍

    1.数据结构(算法)的介绍

    (1).数据结构是一门研究算法的学科，自从有了编程语言也就有了数据结构,学好数据结构可以编写出更加漂亮，更加有效率的代码

    (2).要学习好数据结构就要多多考虑如何将生活中遇到的问题用程序去实现解决

    (3).程序＝ 数据结构 + 算法

    2.数据结构和算法的关系

    • 算法是程序的灵魂，为什么有些网站能够在高并发，在海量吞吐情况下依然坚如磐石,大家可能会说：网站使用了服务器群集技术、数据库读写分离和缓存技术（比如 redis等）,那么如果再深入的问一句，这些优化技术又是怎样被那些天才的技术高手设计出来的呢？
    • 大家请思考一个问题，是什么让不同的人写出的代码从功能看是一样的，但从效率上却有天壤之别，比如:我是做服务器的，环境是UNIX ，功能是要支持上千万人同时在线，并保证数据传输的稳定，在服务器上线前，做内侧，一切 OK.可上线后，服务器就支撑不住了,公司的CTO对我的代码进行优化，再次上线，坚如磐石,那一瞬间，我认识到程序是有灵魂的，就是算法.如果你不想永远都是代码工人，那就花时间来研究下算法

    3.案例

    (1).试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数

    代码如下：

    1. func main() {
    2.     var str string = "go, golang, hello world"
    3.     str = strings.Replace(str, "go", "c"， -1)
    4.     fmt.Println(str)
    5. }

    (2).五子棋：如何判断游戏的输赢，并可以完成存盘退出和继续上局的功能

    (3).约瑟夫问题（丢手帕问题）

            设编号为 1 , 2 ， … n 的 n 个人围坐一圈，约定编号为 k ( 1 <= k  <= n）的人从 1 开始报数，数到m的那个人出列,它的下一位又从 1 开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列.

    提示：

            用一个不带头结点的循环链表来处理josephu问题，先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到m时，对应结点从链表中删除．然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除，算法结束.

    (4).邮差问题

            战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄

            各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里

    问：

            如何计算出G村庄到 其它各个村庄的最短距离?如果从其它点出发到各个点的最短距离又是多少?

    (5).最短路径问题

            首先是迷宫的表示。如下图，起始位置是左上角黄色位置，重点位置是右下角黄色位置。在这个二维矩阵里，0表示道路通畅，可走；1表示有障碍物，不可走。最终计算出来的结果如右下角所示，从左上角0开始，每走一步，累加一次，这样就可以显示出整条路径的先后顺序。要走最短路径，只要从终点位置，不断递减1寻找上一步的位置直到回到起始位置即可.

    (6).汉诺塔

    假设这个游戏中有 3 个柱子，即 A、B 和 C,需要移动的是方块，其中一个柱子上已经有 N 个有序的方块，最大的在底部，方块按顺序越来越小。另外 2 个是空柱子。

    基本条件：

    • 一次只能移动一颗方块
    • 小方块一定要在大方块上面
    • 最终目标是将柱子上的所有方块移到另一根柱子上

    (7).八皇后问题

    1. 首先定义一个8*8的棋盘
    2. 我们有八个皇后在手里，目的是把八个都放在棋盘中
    3. 位于皇后的水平和垂直方向的棋格不能有其他皇后
    4. 位于皇后的斜对角线上的棋格不能有其他皇后
    5. 解出能将八个皇后都放在棋盘中的摆法

    二.稀疏数组

    1.需求

    编写五子棋程序,存盘退出和续上盘功能

    分析:

           上图中,二维数组中很多数都是默认值(0),因此纪录了很多没有意义的数据,故使用稀疏数组来进行处理 

    2.基本介绍

    当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

    稀疏数组的处理方法是:

    (1).记录数组一共有几行几列，有多少个不同的值

    (2).把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

     

     3.应用实例

    (1).使用稀疏数组，来保留类似前面的二维数组棋盘、地图等等）

    (2).把稀疏数组存盘，并且可以从新恢复原来的二维数组数
    (3).整休思路分析

    (4).代码实现

      

    代码如下:

    1. package main
    2.  
    3. import(
    4.     "fmt"
    5.     "os"
    6.     "bufio"
    7.     "io"
    8.     "strings"
    9.     "strconv"
    10. )
    11.  
    12. type ValNode struct {
    13.     row int 
    14.     col int
    15.     val int
    16. }
    17.  
    18. //编写五子棋程序, 有存盘退出和续上盘的功能
    19. func main() {
    20.     //1.先创建一个原始数组
    21.     var chessMap [11][11]int
    22.     chessMap[1][2] = 1 //黑子
    23.     chessMap[2][3] = 2 //蓝子
    24.     //2.输出原始数组看看
    25.     for _, v := range chessMap {
    26.         for _, v2 := range v {
    27.             fmt.Printf("%d\t", v2)
    28.         }
    29.         fmt.Println()
    30.     }
    31.     //3.转换成稀疏数组
    32.     //思路:
    33.     //1).遍历chessMap,如果发现有一个元素不为零,创建一个node结构体
    34.     //2).将其放入对应的切片即可
    35.     //定义切片
    36.     var spaseArr []ValNode
    37.     //标准的一个稀疏数组应该还有一个记录元素的二维数组的规模(行和列,默认值)
    38.     //创建一个ValNode节点
    39.     valNode := ValNode {
    40.         row: 11,
    41.         col: 11,
    42.         val: 0,
    43.     }
    44.     //追加到spaseArr切片中
    45.     spaseArr = append(spaseArr, valNode)
    46.     //循环chessMap,把不为零的元素放到spaseArr中
    47.     for i, v := range chessMap {
    48.         for j, v2 := range v {
    49.             if v2 != 0 {
    50.                 //创建一个ValNode 值节点
    51.                 valNode = ValNode{
    52.                     row: i,
    53.                     col: j,
    54.                     val: v2,
    55.                 }
    56.                 spaseArr = append(spaseArr, valNode)
    57.             }
    58.         }
    59.     }
    60.     //输出稀疏数组
    61.     fmt.Println("当前的稀疏数组为:")
    62.     for i, valNode := range spaseArr {
    63.         fmt.Printf("%d: %d %d %d\n", i, valNode.row, valNode.col, valNode.val)
    64.     }
    65.     //将稀疏数组存盘
    66.     //创建一个新文件
    67.     //打开一个文件 "f:/www/test2.txt"
    68.     filePath :=  "f:/www/chessMap.data"
    69.     file, err := os.OpenFile(filePath, os.O_WRONLY | os.O_CREATE, 0666)
    70.     if err != nil {
    71.         fmt.Printf("open file err =%v\n", err)
    72.     }
    73.     //及时关闭file
    74.     defer file.Close()
    75.     var content string
    76.     //准备写入
    77.     writer := bufio.NewWriter(file)
    78.     for _, valNode := range spaseArr {
    79.         content = fmt.Sprintf("%d %d %d\n", valNode.row, valNode.col, valNode.val)
    80.         writer.WriteString(content)
    81.     }
    82.     writer.Flush()
    83.  
    84.     //把存盘的稀疏数组恢复到原始数组
    85.     //创建一个原始数组
    86.     var chessMap2 [11][11]int
    87.     //打开文件,遍历每一行数据
    88.     file, err = os.Open(filePath)
    89.     if err != nil {
    90.         fmt.Println("os.Open file fail, err = ", err)
    91.     }
    92.     defer file.Close()
    93.     //创建一个Reader
    94.     reader := bufio.NewReader(file)
    95.     //循环读取reader里的内容
    96.     //文件中第一行数据过滤掉
    97.     i := 1
    98.     for {
    99.         str, err := reader.ReadString('\n')
    100.         if err == io.EOF {  //读到文件末尾就退出
    101.             break
    102.         }
    103.         if i == 1 {
    104.             i++
    105.             continue
    106.         }
    107.  
    108.         //通过空格切割字符串,并转换成数组
    109.         arr := strings.Fields(string(str))
    110.         row, err := strconv.ParseInt(arr[0], 10, 64)
    111.         col, err := strconv.ParseInt(arr[1], 10, 64)
    112.         val, err := strconv.ParseInt(arr[2], 10, 64)
    113.         chessMap2[row][col] = int(val)
    114.     }
    115.     //打印稀疏数组
    116.     for _, v := range chessMap2 {
    117.         for _, v2 := range v {
    118.             fmt.Printf("%d\t", v2)
    119.         }
    120.         fmt.Println()
    121.     }
    122. }

    三.队列(数组实现)

    1.队列的应用场景

    银行排队案例:

    2.队列介绍

    队列是一个有序列表，可以用数组或是链表来实现.遵循先入先出的原则。即：先存入队列的数据，要先取出,后存入的要后取出示意图,使用数组模拟队列示意图如下:

    3.数组模拟队列

    队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下:其中 maxSize 是该队列的最大容量

    因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标， front 会随着数据输出而改变，而rear则是随着数据输入而改变,如图所示：

    将数据存入队列时称为"addqueue", addqueue 的处理需要有两个步骤

    (1).将尾指针往后移： rear + 1 , front ==real ［空］

    (2).若尾指引 rear 小于等于队列的最大下标 MaxSize -1, 则将数据存入 rear 所指的数组元素,否则无法存入数据

    1. package main
    2.  
    3. import (
    4.     "fmt"
    5.     "errors"
    6.     "os"
    7. )
    8.  
    9. //定义一个结构体,存放队列相关数据
    10. type Queue struct {
    11.     maxSize int //队列最大数
    12.     array [5]int // 数组=>模拟队列
    13.     front int //指向队列首部  
    14.     rear int //指向队列尾部
    15. }
    16.  
    17. //添加队列数据
    18. func (this *Queue) AddQueue(val int) (err error)  {
    19.     //判断队列是否已满
    20.     if this.maxSize -1 == this.rear { // rear是队列尾部(含最后一个元素)
    21.         return errors.New("queue full")
    22.     }   
    23.     this.rear++ //rear后移
    24.     this.array[this.rear] = val
    25.     return
    26. }
    27.  
    28. //显示队列:找到队首,然后遍历
    29. func (this *Queue) ShowQueue () {
    30.     fmt.Println("队列当前情况:")
    31.     //this.front是不包含队首的元素
    32.     for i := this.front + 1; i <= this.rear; i++ {
    33.         fmt.Printf("arrar[%d]=%d\n", i, this.array[i])
    34.     }
    35. }
    36.  
    37. //从队列中取出数据
    38. func (this *Queue) GetQueue() (val int, err error) {
    39.     //先判断队列是否为空
    40.     if this.rear == this.front { //队列为空了
    41.         return -1, errors.New("queue empty")
    42.     }
    43.     this.front++
    44.     val = this.array[this.front]
    45.     return val, err
    46. }
    47.  
    48. func main()  {
    49.     //先创建一个队列
    50.     queue := &Queue {
    51.         maxSize: 5,
    52.         front: -1,
    53.         rear: -1,
    54.     }
    55.  
    56.     var key string
    57.     var val int
    58.     for {
    59.         fmt.Println("1. 输入add,表示添加数据到队列")
    60.         fmt.Println("2. 输入get,表示从队列获取数据")
    61.         fmt.Println("3. 输入show,表示显示队列")
    62.         fmt.Println("4. 输入exit,表示退出队列")
    63.         fmt.Scanln(&key)
    64.         switch key {
    65.             case "add":
    66.                 fmt.Println("输入要入队的对数:")
    67.                 fmt.Scanln(&val)
    68.                 err := queue.AddQueue(val)
    69.                 if err != nil {
    70.                     fmt.Println(err.Error())
    71.                 } else {
    72.                     fmt.Println("加入队列成功")
    73.                 }
    74.             case "get":
    75.                 val, err := queue.GetQueue()
    76.                 if err != nil {
    77.                     fmt.Println(err.Error())
    78.                 } else {
    79.                     fmt.Printf("从队列中取出的数为:%d\n", val)
    80.                 }
    81.             case "show":
    82.                 queue.ShowQueue()
    83.             case "exit":
    84.                 os.Exit(0)
    85.             default:
    86.                 fmt.Println("输入有误,请重新输入")
    87.         }
    88.     }
    89. }

     对上面代码的小节和说明:

    (1).上面代码实现了基本队列结构，但是役有有效的利用数组空间

    (2).请思考:如何使用数组实现一个环形的队列

    4.环形数组队列 

    对前面的数组模拟队列的优化，充分利用数组,因此将数组看做是一个环形的( 通过取模的方式来实现即可）

    提醒：

    (1).尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(tail+1)%maxSize == head(满)

    (2).tail == head (空)

    分析思路:

    (1).什么时候表示队列满? (tail+1)%maxSize == head

    (2).什么时候表示队列空? tail == head

    (3).初始化时,tail == 0,head == 0

    (4).怎么统计该队列有多少个元素? (tail + maxSize - head) % maxSize

    代码如下:

    1. package main
    2.  
    3. import(
    4.     "fmt"
    5.     "errors"
    6.     "os"
    7. )
    8.  
    9. //定义一个结构体管理环形队列
    10. type CircleQueue struct{    
    11.     maxSize int //队列最大值:5
    12.     array [5]int //使用数组 =>队列
    13.     head int //指向队列队首:0
    14.     tail int //指向队列队尾:0
    15. }
    16.  
    17. //入队列 AddQueue(push)
    18. func (this *CircleQueue) Push(val int) (err error)  {
    19.     //判断环形队列是否满了
    20.     if this.IsFull() {
    21.         return errors.New("queue full")
    22.     }
    23.     //this.tail在队列尾部,但是不包含最后一个元素
    24.     this.array[this.tail] = val //把值给尾部
    25.     this.tail = (this.tail + 1) % this.maxSize
    26.     return 
    27. }
    28.  
    29. //出队列 GetQueue(pop)
    30. func (this *CircleQueue) Pop() (val int, err error) {
    31.     //判断环形队列是否为空
    32.     if this.IsEmpty() {
    33.         return 0, errors.New("queue empty")
    34.     }
    35.     //取出:head是指向队首,并且含队首元素
    36.     val = this.array[this.head]
    37.     this.head = (this.head + 1) % this.maxSize
    38.     return val, err
    39. }
    40.  
    41. //判断环形队列是否满了
    42. func (this *CircleQueue) IsFull() bool {
    43.     return (this.tail + 1) % this.maxSize == this.head
    44. }
    45.  
    46. //判断环形队列是否为空
    47. func (this *CircleQueue) IsEmpty() bool {
    48.     return this.tail == this.head
    49. }
    50.  
    51. //取出环形队列有多少个元素
    52. func (this *CircleQueue) Size() int {
    53.     //这是个关键的点
    54.     return (this.tail + this.maxSize - this.head) % this.maxSize
    55. }
    56.  
    57. //显示队列
    58. func (this *CircleQueue) ListQueue() {
    59.     fmt.Println("环形队列情况如下:")
    60.     //取出当前队列有多少个元素
    61.     size := this.Size()
    62.     if size ==  0 {
    63.         fmt.Println("队列为空")
    64.     }
    65.     //定义一个临时变量,指向head
    66.     tempHead := this.head
    67.     for i := 0; i < size; i++ {
    68.         fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])
    69.         tempHead = (tempHead + 1) % this.maxSize
    70.     }
    71.  
    72.  
    73. }
    74. func main() {
    75.     //先创建一个队列
    76.     queue := &CircleQueue {
    77.         maxSize: 5,
    78.         head: 0,
    79.         tail: 0,
    80.     }
    81.  
    82.     var key string
    83.     var val int
    84.     for {
    85.         fmt.Println("1. 输入push,表示添加数据到队列")
    86.         fmt.Println("2. 输入pop,表示从队列获取数据")
    87.         fmt.Println("3. 输入list,表示显示队列")
    88.         fmt.Println("4. 输入exit,表示退出队列")
    89.         fmt.Scanln(&key)
    90.         switch key {
    91.             case "push":
    92.                 fmt.Println("输入要入队的对数:")
    93.                 fmt.Scanln(&val)
    94.                 err := queue.Push(val)
    95.                 if err != nil {
    96.                     fmt.Println(err.Error())
    97.                 } else {
    98.                     fmt.Println("加入队列成功")
    99.                 }
    100.             case "pop":
    101.                 val, err := queue.Pop()
    102.                 if err != nil {
    103.                     fmt.Println(err.Error())
    104.                 } else {
    105.                     fmt.Printf("从队列中取出的数为:%d\n", val)
    106.                 }
    107.             case "list":
    108.                 queue.ListQueue()
    109.             case "exit":
    110.                 os.Exit(0)
    111.             default:
    112.                 fmt.Println("输入有误,请重新输入")
    113.         }
    114.     }
    115. }

    四.链表

    1.链表的介绍

    链表是有序的列表,它在内存中的存储如下

    2.单链表的介绍

    示意图如下:

    说明: 一般来说,为了比较好的对单链表进行增删改查的操作,都会给其设置一个头结点,头结点的作用主要是用来标识链表头,本身这个结点不存放数据

    3.单链表的应用实例

    使用带 head 头的单向链表实现\:水浒英雄排行榜管理

    完成对英雄人物的增删改查操作

    在添加英雄时，直接添加到链表的尾部

    1. package main
    2.  
    3. import (
    4.     "fmt"
    5. )
    6.  
    7. //定义一个HeroNode结构体
    8. type HeroNode struct {
    9.     no int
    10.     name string
    11.     nickname string
    12.     next *HeroNode //表示指向下一个结点
    13. }
    14.  
    15. //给链表插入一个结点
    16. //编写第一种插入方式:在单链表的最后插入
    17. func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode)  {
    18.     //1.先找到链表最后这个结点
    19.     //2.创建一个辅助结点
    20.     temp := head
    21.     for {
    22.         if temp.next == nil { //表示找到了最后
    23.             break
    24.         }
    25.         temp = temp.next //让temp不断指向下一个结点
    26.     }
    27.     //当for结束时,temp一定是找到了最后一个节点的
    28.     //3.将newHeroNode加入道最后
    29.     temp.next = newHeroNode
    30. }
    31.  
    32. //编写第二种插入方式: 根据no的编号从小到大插入 
    33. func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode)  {
    34.     //1.先找适当的结点
    35.     //2.创建一个辅助结点
    36.     temp := head
    37.     flag := true
    38.     //让插入结点的no和temp的下一个结点的no比较
    39.     for {
    40.         if temp.next == nil { //表示到了最后的链表
    41.             break
    42.         } else if temp.next.no > newHeroNode.no {
    43.             //说明newHeroNode就应该插入到temp后面
    44.             break
    45.         } else if temp.next.no == newHeroNode.no {
    46.             //说明链表中已经有这个no,就不允许插入了
    47.             flag = false
    48.             break
    49.         }
    50.         temp = temp.next //让temp不断指向下一个结点
    51.     }
    52.     if !flag {
    53.         fmt.Println("已存在no=", newHeroNode.no)
    54.         return
    55.     } else {
    56.         newHeroNode.next = temp.next
    57.         temp.next = newHeroNode
    58.     }
    59. }
    60.  
    61. //显示链表的所有结点信息
    62. func ListHeroNode(head *HeroNode) {
    63.     //1.创建一个辅助结点
    64.     temp := head
    65.     //先判断该链表是不是空的链表
    66.     if temp.next == nil { 
    67.         fmt.Println("空的链表")
    68.         return
    69.     }
    70.     //2.遍历链表
    71.     for {
    72.         fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)
    73.         //判断链表是否最后
    74.         temp = temp.next
    75.         if temp.next == nil {
    76.             break
    77.         }
    78.     }
    79. }
    80.  
    81. //删除一个结点
    82. func DelHeroNode(head *HeroNode, id int) {
    83.     temp := head
    84.     flag := false
    85.     //找到要删除的结点的no,和temp的下一个结点的no比较
    86.     for {
    87.         if temp.next == nil {//说明到了链表的最后
    88.             break
    89.         } else if temp.next.no == id {
    90.             //说明找到了
    91.             flag = true
    92.             break
    93.         }
    94.         temp = temp.next
    95.     }
    96.     if flag {//找到了,就行删除操作
    97.         temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收
    98.     } else {
    99.         fmt.Println("要删除的结点id不存在")
    100.     }
    101. }
    102. func main()  {
    103.     //1.先创建一个头结点
    104.     head := &HeroNode{}
    105.     //2.创建一个新的结点
    106.     head1 := &HeroNode{
    107.         no: 1,
    108.         name: "宋江",
    109.         nickname: "及时雨",
    110.     }
    111.     head2 := &HeroNode{
    112.         no: 2,
    113.         name: "陆静怡",
    114.         nickname: "玉骑铃",
    115.     }
    116.     head3 := &HeroNode{
    117.         no: 3,
    118.         name: "零充",
    119.         nickname: "包子头",
    120.     }
    121.      //3.加入
    122.     //第一种方法
    123.     // InsertHeroNode(head, head1)
    124.     // InsertHeroNode(head, head3)
    125.     // InsertHeroNode(head, head2)
    126.     
    127.     //第二种方法
    128.     InsertHeroNode2(head, head1)
    129.     InsertHeroNode2(head, head3)
    130.     InsertHeroNode2(head, head2)
    131.     //4.列表
    132.     ListHeroNode(head)
    133.     //5.删除
    134.     fmt.Println()
    135.     DelHeroNode(head, 2)
    136.     ListHeroNode(head)
    137. }

    4.双向链表的应用实例

    使用带 head 头的双向链表实现：水浒英雄排行榜管理

    单向链表的缺点分析:

    (1).单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找

    (2).单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面单链表删除时节点，总是找到 temp 的下一个节点来删除

    1. package main
    2.  
    3. import (
    4.     "fmt"
    5. )
    6.  
    7. //定义一个HeroNode结构体
    8. type HeroNode struct {
    9.     no int
    10.     name string
    11.     nickname string
    12.     pre *HeroNode //表示指向上一个结点
    13.     next *HeroNode //表示指向下一个结点
    14. }
    15.  
    16. //给链表插入一个结点
    17. //编写第一种插入方式:在链表的最后插入
    18. func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode)  {
    19.     //1.先找到链表最后这个结点
    20.     //2.创建一个辅助结点
    21.     temp := head
    22.     for {
    23.         if temp.next == nil { //表示找到了最后
    24.             break
    25.         }
    26.         temp = temp.next //让temp不断指向下一个结点
    27.     }
    28.     //当for结束时,temp一定是找到了最后一个节点的
    29.     //3.将newHeroNOde加入道最后
    30.     temp.next = newHeroNode
    31.     //4.再将temp指向newHeroNode.pre
    32.     newHeroNode.pre = temp
    33. }
    34.  
    35. //编写第二种插入方式: 根据no的编号从小到大插入 
    36. func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode)  {
    37.     //1.先找适当的结点
    38.     //2.创建一个辅助结点
    39.     temp := head
    40.     flag := true
    41.     //让插入结点的no和temp的下一个结点的no比较
    42.     for {
    43.         if temp.next == nil { //表示到了最后的链表
    44.             break
    45.         } else if temp.next.no > newHeroNode.no {
    46.             //说明newHeroNode就应该插入到temp后面
    47.             break
    48.         } else if temp.next.no == newHeroNode.no {
    49.             //说明链表中已经有这个no,就不允许插入了
    50.             flag = false
    51.             break
    52.         }
    53.         temp = temp.next //让temp不断指向下一个结点
    54.     }
    55.     if !flag {
    56.         fmt.Println("已存在no=", newHeroNode.no)
    57.         return
    58.     } else {
    59.         newHeroNode.next = temp.next
    60.         newHeroNode.pre = temp
    61.         if temp.next != nil {
    62.             temp.next.pre = newHeroNode
    63.         }
    64.         temp.next = newHeroNode
    65.     }
    66. }
    67.  
    68. //显示链表的所有信息:顺序方式
    69. func ListHeroNode(head *HeroNode) {
    70.     //1.创建一个辅助结点
    71.     temp := head
    72.     //先判断该链表是不是空的链表
    73.     if temp.next == nil { 
    74.         fmt.Println("空的链表")
    75.         return
    76.     }
    77.     //2.遍历链表
    78.     for {
    79.         fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)
    80.         //判断链表是否最后
    81.         temp = temp.next
    82.         if temp.next == nil {
    83.             break
    84.         }
    85.     }
    86. }
    87.  
    88. //显示链表的所有信息:逆序方式
    89. func ListHeroNode2(head *HeroNode) {
    90.     //1.创建一个辅助结点
    91.     temp := head
    92.  
    93.     //先判断该链表是不是空的链表
    94.     if temp.next == nil { 
    95.         fmt.Println("空的链表")
    96.         return
    97.     }
    98.     //2.让temp定位到双向链表的最后结点
    99.     for {
    100.         if temp.next == nil {
    101.             break
    102.         }
    103.         temp = temp.next
    104.     }
    105.  
    106.     //2.遍历链表
    107.     for {
    108.         fmt.Printf("[%d, %s, %s] <== ", temp.no, temp.name, temp.nickname)
    109.         //判断链表是否到head
    110.         temp = temp.pre
    111.         if temp.pre == nil {
    112.             break
    113.         }
    114.     }
    115. }
    116.  
    117. //删除一个结点
    118. func DelHeroNode(head *HeroNode, id int) {
    119.     temp := head
    120.     flag := false
    121.     //找到要删除的结点的no,和temp的下一个结点的no比较
    122.     for {
    123.         if temp.next == nil {//说明到了链表的最后
    124.             break
    125.         } else if temp.next.no == id {
    126.             //说明找到了
    127.             flag = true
    128.             break
    129.         }
    130.         temp = temp.next
    131.     }
    132.     if flag {//找到了,就行删除操作
    133.         temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收
    134.         if temp.next != nil {   //当下一个结点存在时,才操作
    135.             temp.next.pre = temp
    136.         }
    137.     } else {
    138.         fmt.Println("要删除的结点id不存在")
    139.     }
    140. }
    141. func main()  {
    142.     //1.先创建一个头结点
    143.     head := &HeroNode{}
    144.     //2.创建一个新的结点
    145.     head1 := &HeroNode{
    146.         no: 1,
    147.         name: "宋江",
    148.         nickname: "及时雨",
    149.     }
    150.     head2 := &HeroNode{
    151.         no: 2,
    152.         name: "陆静怡",
    153.         nickname: "玉骑铃",
    154.     }
    155.     head3 := &HeroNode{
    156.         no: 3,
    157.         name: "零充",
    158.         nickname: "包子头",
    159.     }
    160.      //3.加入
    161.     //第一种方法
    162.     InsertHeroNode(head, head1)
    163.     InsertHeroNode(head, head2)
    164.     InsertHeroNode(head, head3)
    165.     
    166.     //第二种方法
    167.     // InsertHeroNode2(head, head1)
    168.     // InsertHeroNode2(head, head3)
    169.     // InsertHeroNode2(head, head2)
    170.     // //4.列表
    171.     //顺序
    172.     ListHeroNode(head)
    173.     fmt.Println()
    174.     //逆序
    175.     ListHeroNode2(head)
    176.     // //5.删除
    177.     // fmt.Println()
    178.     DelHeroNode(head, 2)
    179.     ListHeroNode(head)
    180. }

    5.单向环形链表的应用场景

    josephu 问题:

    设编号为1, 2 ，... n 的n个人围坐一圈, 约定编号为 k (1<=k<=n ）的人从 1 开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列

    提示：

    用一个不带头结点的循环链表来处理josephu问题,先构成一个有 n 个结点的单循环链表，然后由 k 结点起从1开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除,算法结束

    6.环形单向链表的介绍

    7.环形单向链表应用案例

    完成对单向环形链表的添加结点,删除结点和显示

    删除一个环形单向琏表的思路如下：

    1.先让 temp 指向 head

    2.让 helper 指向环形链表最后

    3.让temp 和要删除的id进行比较,如果相同，则同helper完成删除(这里必须考虑如果删除的就是头结点)

    1. package main
    2.  
    3. import (
    4.     "fmt"
    5. )
    6.  
    7. //定义一个CatNode结构体
    8. type CatNode struct {
    9.     no int //猫的编号
    10.     name string //名字
    11.     next *CatNode //下一个结点
    12. }
    13.  
    14. //插入环形链表
    15. func InsertCatNode(head *CatNode, newCatNode *CatNode)  {
    16.     //判断是不是添加第一只猫
    17.     if head.next == nil {
    18.         head.no = newCatNode.no
    19.         head.name = newCatNode.name
    20.         head.next = head // 构成一个环形
    21.         fmt.Println(newCatNode, "加入到环形的链表")
    22.         return 
    23.     } 
    24.     //先定义一个临时的变量,找到环形的最后结点
    25.     temp := head
    26.     for {
    27.         if temp.next == head {
    28.             break
    29.         }
    30.         temp = temp.next
    31.     }
    32.     //加入到链表
    33.     temp.next = newCatNode
    34.     newCatNode.next = head
    35. }
    36.  
    37. //显示环形链表
    38. func ListCircleLink(head *CatNode)  {
    39.     temp := head
    40.     if temp.next == nil {
    41.         fmt.Println("空的链表")
    42.         return
    43.     }
    44.     for {
    45.         fmt.Printf("猫的信息为:no=%d,name=%s, =>\n", temp.no, temp.name)
    46.         if temp.next == head {//说明链表环状查询完毕
    47.             break
    48.         }
    49.         temp = temp.next
    50.     }
    51. }
    52.  
    53. //删除
    54. func DelCircleCatNode(head *CatNode, id int) *CatNode {
    55.     temp := head
    56.     helper := head
    57.     //空链表
    58.     if temp.next == nil {
    59.         fmt.Println("空链表")
    60.         return head
    61.     }
    62.     //如果只有一个结点
    63.     if temp.next == head {
    64.         temp.next = nil
    65.         return head
    66.     }
    67.  
    68.     //将helper定位到环形链表最后
    69.     for {
    70.         if helper.next == head {
    71.             break
    72.         }
    73.         helper = helper.next
    74.     }
    75.     //如果有两个以及以上的结点
    76.     flag := true
    77.     for {
    78.         if temp.next == head { //说明已经比较到最后一个(最后一个还没比较)
    79.             break
    80.         }
    81.         if temp.no == id { // 找到了
    82.             if temp == head { // 说明删除的是头结点
    83.                 head = temp.next
    84.             }
    85.             //可以在这里删除
    86.             helper.next = temp.next
    87.             fmt.Printf("猫:%d已经被删除了\n", id)
    88.             flag = false
    89.             break
    90.         }
    91.         temp = temp.next // 移动,目的是为了 "比较"
    92.         helper = helper.next // 移动,目的是为了删除结点
    93.     }
    94.     //这里还要比较一次
    95.     if flag {   //  如果flag为true,则上面没有删除
    96.         if temp.no == id {
    97.             helper.next = temp.next
    98.             fmt.Printf("猫:%d已经被删除了\n", id)
    99.         } else {
    100.             fmt.Printf("没有该猫,no=%d\n", id)
    101.         }
    102.     }
    103.     return head
    104. }
    105. func main()  {
    106.     //初始化一个环形链表的头结点
    107.     head := &CatNode{}
    108.     //创建一只猫
    109.     cat1 := &CatNode{
    110.         no: 1,
    111.         name: "tom",
    112.     }
    113.     cat2 := &CatNode{
    114.         no: 2,
    115.         name: "jack",
    116.     }
    117.     cat3 := &CatNode{
    118.         no: 3,
    119.         name: "mary",
    120.     }
    121.     InsertCatNode(head, cat1)
    122.     InsertCatNode(head, cat2)
    123.     InsertCatNode(head, cat3)
    124.     ListCircleLink(head)
    125.  
    126.     head = DelCircleCatNode(head, 2)
    127.     ListCircleLink(head)
    128. }

     创建一个链表模拟队列,实现数据入队列,数据出队列,显示队列

    1. package main
    2.  
    3. import (
    4. 	"fmt"
    5. 	"errors"
    6. 	"os"
    7. )
    8.  
    9. //定义一个结构体管理环形队列
    10. type CircleQueue struct {
    11. 	maxSize int    //队列最大值:5
    12. 	array   [5]int //使用数组 =>队列
    13. 	head    int    //指向队列队首:0
    14. 	tail    int    //指向队列队尾:0
    15. }
    16.  
    17. //入队列 AddQueue(push)
    18. func (this *CircleQueue) Push(val int) (err error) {
    19. 	//判断环形队列是否满了
    20. 	if this.IsFull() {
    21. 		return errors.New("queue full")
    22. 	}
    23. 	//this.tail在队列尾部,但是不包含最后一个元素
    24. 	this.array[this.tail] = val //把值给尾部
    25. 	this.tail = (this.tail + 1) % this.maxSize
    26. 	return
    27. }
    28.  
    29. //出队列 GetQueue(pop)
    30. func (this *CircleQueue) Pop() (val int, err error) {
    31. 	//判断环形队列是否为空
    32. 	if this.IsEmpty() {
    33. 		return 0, errors.New("queue empty")
    34. 	}
    35. 	//取出:head是指向队首,并且含队首元素
    36. 	val = this.array[this.head]
    37. 	this.head = (this.head + 1) % this.maxSize
    38. 	return val, err
    39. }
    40.  
    41. //判断环形队列是否满了
    42. func (this *CircleQueue) IsFull() bool {
    43. 	return (this.tail+1)%this.maxSize == this.head
    44. }
    45.  
    46. //判断环形队列是否为空
    47. func (this *CircleQueue) IsEmpty() bool {
    48. 	return this.tail == this.head
    49. }
    50.  
    51. //取出环形队列有多少个元素
    52. func (this *CircleQueue) Size() int {
    53. 	//这是个关键的点
    54. 	return (this.tail + this.maxSize - this.head) % this.maxSize
    55. }
    56.  
    57. //显示队列
    58. func (this *CircleQueue) ListQueue() {
    59. 	fmt.Println("环形队列情况如下:")
    60. 	//取出当前队列有多少个元素
    61. 	size := this.Size()
    62. 	if size == 0 {
    63. 		fmt.Println("队列为空")
    64. 	}
    65. 	//定义一个临时变量,指向head
    66. 	tempHead := this.head
    67. 	for i := 0; i < size; i++ {
    68. 		fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])
    69. 		tempHead = (tempHead + 1) % this.maxSize
    70. 	}
    71.  
    72. }
    73. func main() {
    74. 	//先创建一个队列
    75. 	queue := &CircleQueue{
    76. 		maxSize: 5,
    77. 		head:    0,
    78. 		tail:    0,
    79. 	}
    80.  
    81. 	var key string
    82. 	var val int
    83. 	for {
    84. 		fmt.Println("1. 输入push,表示添加数据到队列")
    85. 		fmt.Println("2. 输入pop,表示从队列获取数据")
    86. 		fmt.Println("3. 输入list,表示显示队列")
    87. 		fmt.Println("4. 输入exit,表示退出队列")
    88. 		fmt.Scanln(&key)
    89. 		switch key {
    90. 		case "push":
    91. 			fmt.Println("输入要入队的对数:")
    92. 			fmt.Scanln(&val)
    93. 			err := queue.Push(val)
    94. 			if err != nil {
    95. 				fmt.Println(err.Error())
    96. 			} else {
    97. 				fmt.Println("加入队列成功")
    98. 			}
    99. 		case "pop":
    100. 			val, err := queue.Pop()
    101. 			if err != nil {
    102. 				fmt.Println(err.Error())
    103. 			} else {
    104. 				fmt.Printf("从队列中取出的数为:%d\n", val)
    105. 			}
    106. 		case "list":
    107. 			queue.ListQueue()
    108. 		case "exit":
    109. 			os.Exit(0)
    110. 		default:
    111. 			fmt.Println("输入有误,请重新输入")
    112. 		}
    113. 	}
    114. }

    [上一节][go学习笔记.第十七章.redis的使用] 1.redis的使用

    [下一节][go学习笔记.第十八章.数据结构] 2.约瑟夫问题,排序,栈,递归,哈希表,二叉树的三种遍历方式 

  • 相关阅读:
    影单：分享一下最近在看的一些电影
    Java之转换流的详细解析
    【7z密码】7z压缩包密码忘记了，怎么办？i
    零信任架构在企业中的应用
    Go中的有限状态机FSM的详细介绍
    2、CSS基础
    这些嵌入式知识助你秋招，也助你进阶
    Java学习之super关键字
    git命令
    分享一个python无人超市管理系统django项目实战源码调试 lw 开题
  • 原文地址：https://blog.csdn.net/zhoupenghui168/article/details/128061769