golang数据结构与算法——稀疏数组、队列和链表

一 稀疏数组

1.1 先看一个实际的需求

编写的五子棋程序中，有存盘退出和续上盘的功能

因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据

1.2 稀疏数组基本介绍

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

稀疏数组的处理方法是:

1. 记录数组一共有几行几列，有多少个不同的值
2. 思想：把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

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

把稀疏数组存盘，并且可以从新恢复原来的二维数组数

1.3 稀疏数组举例说明

1.4 把数组转换为稀疏数组实现

思路分析：

代码实现：

package main

import (
	"bufio"
	"fmt"
	"os"
)

type ValNode struct {
	row int
	col int
	val int
}

func main() {
	filePath := "E:/golang开发学习/sparsearray.data"
	file, err := os.OpenFile(filePath, os.O_WRONLY|os.O_CREATE, 0666)
	if err != nil {
		fmt.Printf("open file err=%v\n", err)
		return
	}
	//及时关闭file句柄
	defer file.Close()

	// 1. 创建一个原始数组
	var chessMap [11][11]int
	chessMap[1][2] = 1
	chessMap[2][3] = 2

	// 2. 输出查看原始数组
	fmt.Println("原始数组为：")
	for _, v := range chessMap {
		for _, v2 := range v {
			fmt.Printf("%d\t", v2)
		}
		fmt.Println()
	}

	// 3. 转成稀疏数组
	// 思路
	// 1．遍历chessMap，如果我们发现有一个元素的值不为0，创建一个node结构体
	// 2．将其放入到对应的切片即可
	var sparseArr []ValNode

	// 添加初始节点 保存二维数组规模(行和列, 默认值)
	ValNode := ValNode{
		row: 11,
		col: 11,
		val: 0,
	}

	sparseArr = append(sparseArr, ValNode)
	for i, v := range chessMap {
		for j, v1 := range v {
			if v1 != 0 {
				// 创建一个ValNode 值节点
				ValNode.row = i
				ValNode.col = j
				ValNode.val = v1
				sparseArr = append(sparseArr, ValNode)
			}
		}
	}

	// 4. 输出稀疏数组
	fmt.Println("当前的稀疏数组是:")
	writer := bufio.NewWriter(file)
	for _, ValNode := range sparseArr {
		var s1 = fmt.Sprintf("%d %d %d\n", ValNode.row, ValNode.col, ValNode.val)
		writer.WriteString(s1)
		fmt.Printf("%s", s1)
	}
	writer.Flush()
}

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
原始数组为：
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	0	0	0	
0	0	0	2	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
当前的稀疏数组是:
11 11 0
1 2 1
2 3 2

[Done] exited with code=0 in 1.255 seconds

E:/golang开发学习/sparsearray.data：

11 11 0
1 2 1
2 3 2

1.5 把稀疏数组还原为原数组

1. 坑点一：读取后是字符串需要，分割成字符串数组，这里通过Split但是数组最后一个多一个换行符号需要去掉。
2. 坑点二：golang是无法直接在二维数组创建时传变量的。这个时候先声明一个二维切片。初始化二维切片后。填入初始值。

代码实现：

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

func main() {
	file, err := os.Open("E:/golang开发学习/sparsearray.data")
	if err != nil {
		fmt.Printf("打开文件出错:%v", err)
	}
	defer file.Close()
	
	reader := bufio.NewReader(file)
	str, err := reader.ReadString('\n')
	if err == io.EOF { //io.EOF 文件末尾
		fmt.Println("第一行 读取完毕")
	}
	// 分割字符串 通过空格
	arr := strings.Split(str, " ")
	m, _ := strconv.Atoi(arr[0])
	n, _ := strconv.Atoi(arr[1])
	v, err := strconv.Atoi(strings.Replace(arr[2], "\n", "", -1))
	if err != nil {
		// handle error
		fmt.Println(err)
		os.Exit(2)
	}
	// golang是无法直接在二维数组创建时传变量的 var chessMap [m][n]int 不能成功
	var chessMap [][]int
	for i := 0; i < m; i++ {
		arr1 := make([]int, n)            //创建一个一维切片
		chessMap = append(chessMap, arr1) //把一维切片,当作一个整体传入二维切片中
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			chessMap[i][j] = v
		}
	}

	for {
		str, err := reader.ReadString('\n') // 一次读到换行结束
		if err == io.EOF {                  //io.EOF 文件末尾
			break
		}
		//输出内容
		arr := strings.Split(str, " ")
		m, _ := strconv.Atoi(arr[0])
		n, _ := strconv.Atoi(arr[1])
		v, _ := strconv.Atoi(strings.Replace(arr[2], "\n", "", -1))
		chessMap[m][n] = v
	}
	fmt.Println("稀疏数组还原成原数组：")
	for _, v := range chessMap {
		for _, v2 := range v {
			fmt.Printf("%d\t", v2)
		}
		fmt.Println()
	}
}

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
稀疏数组还原成原数组。。。
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	0	0	0	
0	0	0	2	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	

[Done] exited with code=0 in 1.473 seconds

二 队列

2.1 队列的介绍

1. 队列是一个有序列表，可以用数组或是链表来实现。
2. 遵循先入先出的原则。即:先存入队列的数据，要先取出。后存入的要后取出

2.2 数组模拟队列思路

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下

其maxSize是该队列的最大容量。

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

当我们将数据存入队列时称为”AddQueue"，AddQueue的处理需要有两个步骤:

rear+1front == rearrear == MaxSize -1

思路分析：

1. 创建一个数组 arrary ，最为队列的一个字段

2. front 初始化为-1

3. rear 表示队列的尾部，初始化为-1

4. 完成队列的基本查找

   AddQueue：加入数据到队列

   GetQueue：从队列中取出数据

   ShowQueue：显示队列

2.3 数组模拟队列代码实现

package main

import (
	"errors"
	"fmt"
	"os"
)

// 使用一个结构体管理队列
type Queue struct {
	maxSize int
	array   [5]int // 数组=>模拟队列
	front   int    //表示指向队列首
	rear    int    //表示指向队列的尾部
}

// 添加数据到队列
func (q *Queue) AddQueue(val int) (err error) {
	// 判断队列是否已经满了
	if q.rear == q.maxSize-1 { // rear包含队列尾部
		return errors.New("队列已满")
	}
	q.rear++ // rear后移
	q.array[q.rear] = val
	return
}

// 从队列中取出数据
func (q *Queue) GetQueue() (val int, err error) {
	// 先判断队列是否已满
	if q.rear == q.front { // 队空
		return -1, errors.New("queue empty")
	}
	q.front++
	val = q.array[q.front]
	return val, err
}

// 显示队列 找到队首 遍历到队尾
func (q *Queue) ShowQueue() {
	fmt.Println("队列当前的情况是:")
	// 队首不包含队首元素
	for i := q.front + 1; i <= q.rear; i++ {
		fmt.Printf("array[%d]=%d\n", i, q.array[i])
	}
	fmt.Println()
}

// 编写主函数
func main() {
	// 先创建一个队列
	var 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)
		}
	}
}

运行结果：

1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
2
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
队列当前的情况是:
array[0]=2

1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
4
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
3
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
5
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
10
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
11
队列已满
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
队列当前的情况是:
array[0]=2
array[1]=4
array[2]=3
array[3]=5
array[4]=10

1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 2
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 4
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 3
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 5
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 10
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
queue empty
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
exit

2.4 数组模拟队列弊端

1. 上面代码实现了基本队列结构，但是没有有效的利用数组空间，队列只能使用一次。
2. 使用数组实现一个环形的队列进行优化(通过取模的方式改进)

三 环形队列

3.1 数组模拟环形队列思路

(tail+1) % maxSize == headtail == head(tail+1) % maxSize = headtail ==headtail= 0head= 0(tail + maxSize - head ) % maxSize

3.2 数组模拟环形队列代码实现

package main

import (
	"errors"
	"fmt"
	"os"
)

// 使用一个结构体管理环形队列
type CircleQueue struct {
	maxSize int    // 4
	array   [5]int // 数组
	head    int    // 指向队列的头部
	tail    int    // 指向队列的尾部
}

// 入队列 AddQueue(push) GetQueue(pop)
func (q *CircleQueue) Push(val int) (err error) {
	if q.IsFull() {
		return errors.New("queue full")
	}
	// 分析出this.tail 在队列尾部 不包含最后的元素
	q.array[q.tail] = val // 把值给尾部
	// 这里要注意虽然数组容量是5 实际上队列最多只能存四个 因为下面这句话
	q.tail = (q.tail + 1) % q.maxSize
	return
}

// 出队列
func (q *CircleQueue) Pop() (val int, err error) {
	if q.IsEmpty() {
		return 0, errors.New("queue empty")
	}
	// 取出, head 是指向队首 并且含队首元素
	val = q.array[q.head]
	q.head = (q.head + 1) % q.maxSize
	return val, err
}

// 显示队列
func (q *CircleQueue) ListQueue() {
	fmt.Println("环形队列的情况如下:")
	// 取出当前队列有多少个元素
	size := q.Size()
	if size == 0 {
		fmt.Println("队列为空")
	}
	// 设计一个辅助变量. 指向head
	tempHead := q.head
	for i := 0; i < size; i++ {
		fmt.Printf("arr[%d]=%d\t", tempHead, q.array[tempHead])
		tempHead = (tempHead + 1) % q.maxSize
	}
	fmt.Println()
}

// 判断环形队列为满
func (q *CircleQueue) IsFull() bool {
	return (q.tail+1)%q.maxSize == q.head
}

// 判断环形队列为空
func (q *CircleQueue) IsEmpty() bool {
	return q.tail == q.head
}

// 取出环形队列有多少个元素
func (q *CircleQueue) Size() int {
	return (q.tail + q.maxSize - q.head) % q.maxSize
}

// 编写主函数
func main() {
	// 先创建一个环形队列
	var 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. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
环形队列的情况如下:
队列为空

1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add 
输入数据入队
1
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
2
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
3
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
4
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
环形队列的情况如下:
arr[0]=1        arr[1]=2        arr[2]=3        arr[3]=4
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 1
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
环形队列的情况如下:
arr[1]=2        arr[2]=3        arr[3]=4
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
5
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
环形队列的情况如下:
arr[1]=2        arr[2]=3        arr[3]=4        arr[4]=5
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
6
queue full
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 2
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 3
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 4
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
从队列中取出数据： 5
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
get
queue empty
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
add
输入数据入队
10
加入队列成功
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
show
环形队列的情况如下:
arr[0]=10
1. 输入add 添加元素到队列
2. 输入get 从队列中获取元素
3. 输入show 显示队列中的元素
4. 输入exit 退出程序
exit

四 链表

4.1 链表介绍

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

4.2 单向链表

单链表的示意图：

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

4.3 单向链表的应用实例

案例的说明：

• 使用带 head 头的单向链表实现 –水浒英雄排行榜管理
• 完成对英雄人物的增删改查操作

4.3.1 单链表的添加与显示

第一种方法在添加英雄时，直接添加到链表的尾部

代码实现：

package main

import (
	"fmt"
)

// 定义一个HeroNode
type HeroNode struct {
	no       int       // 编号
	name     string    // 名称
	nickname string    // 花名
	next     *HeroNode //这个表示指向下一个节点
}

// 给链表插入一个节点
// 编写第一种插入方法, 在单链表的最后加入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
	// 思路 1. 先找到该链表的最后这个节点
	// 2. 创建一个辅助节点 【用来帮忙的】
	temp := head
	for {
		if temp.next == nil { //表示找到最后了
			break
		}
		temp = temp.next // 让temp不断的指向下一个节点
	}
	// 3. 加入到链表的最后 (现在temp已经位于链表末尾了)
	temp.next = newHeroNode
}

// 显示链表的所有节点信息
func ListHeroNode(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 main() {
	// 1.先创建一个头节点
	head := &HeroNode{}
	// 2. 创建一个新的HeroNode
	hero1 := &HeroNode{
		no:       1,
		name:     "宋江",
		nickname: "及时雨",
	}
	hero2 := &HeroNode{
		no:       2,
		name:     "卢俊义",
		nickname: "玉麒麟",
	}
	hero3 := &HeroNode{
		no:       3,
		name:     "林冲",
		nickname: "豹子头",
	}
	// 3. 加入一个节点
	InsertHeroNode(head, hero1)
	InsertHeroNode(head, hero3)
	InsertHeroNode(head, hero2)
	// 4. 显示
	ListHeroNode(head)
	fmt.Println()
}

运行结果：

[1, 宋江, 及时雨]==>[3, 林冲, 豹子头]==>[2, 卢俊义, 玉麒麟]==>

此方法排序跟插入顺序有关，若插入时无序，则输出结果也会无序。

4.3.2 单链表的有序插入

第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败并给出提示)

代码实现：

// 给链表插入一个节点 排好之后插入数据库 会节省很多order_by内存
// 编写第二种插入方法, 根据no 的编号从小到大插入..
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode){
	// 1. 找到适当的节点
	// 2. 创建一个辅助节点 【用来帮忙的】
	temp := head
	flag := true
	for {
		// 让插入节点的no 和temp的下一个节点的no 进行比较
		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{
		// 3. 插入节点
		newHeroNode.next = temp.next
		temp.next = newHeroNode
	}
}

运行结果：

[1, 宋江, 及时雨]==>[2, 卢俊义, 玉麒麟]==>[3, 林冲, 豹子头]==>

这样优化后，无论怎样的顺序插入，输出结果都是根据no排好输出。

4.3.3 单链表的删除

代码实现：

// 删除节点
func DelHeroNode(head *HeroNode, id int) {
	temp := head
	flag := false
	
	// 找到要删除的节点 no，和temp的下一个节点 no 进行比较
	for {
		if temp.next == nil {	// 说明到链表的表尾
			break
		} else if temp.next.no > id {
			break
		} else if temp.next.no == id {	// 说明找到了要删除的节点
			flag = true
			break
		}
		temp = temp.next
	}
	if !flag {
		fmt.Println("要删除的id不存在...", id)
		return
	} else {
		temp.next = temp.next.next
	}
}

五 双向链表

5.1 双向链表介绍

单向链表的缺点分析：

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找
• 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp的下一个节点来删除的。

双向链表示意图：

5.2 双向链表的创建与输出

package main

import (
	"fmt"
)

// 定义一个HeroNode
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. 加入到链表的最后 (现在temp已经位于链表末尾了)
	temp.next = newHeroNode
	newHeroNode.pre = temp
}

// 编写第二种插入方法, 按顺序添加
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
	// 1. 找到适当的节点
	// 2. 创建一个辅助节点 【用来帮忙的】
	temp := head
	flag := true
	for {
		// 让插入节点的no 和temp的下一个节点的no 进行比较
		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 {
		// 3. 插入节点
		newHeroNode.next = temp.next
		newHeroNode.pre = temp
		if temp.next != nil {
			temp.next.pre = newHeroNode
		}
		temp.next = newHeroNode
	}
}

// 显示链表的所有节点信息
func ListHeroNode(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 ListHeroNode1(head *HeroNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("链表为空链表!")
		return
	}
	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:       1,
		name:     "宋江",
		nickname: "及时雨",
	}
	hero2 := &HeroNode{
		no:       2,
		name:     "卢俊义",
		nickname: "玉麒麟",
	}
	hero3 := &HeroNode{
		no:       3,
		name:     "林冲",
		nickname: "豹子头",
	}
	// 3. 加入一个节点
	InsertHeroNode2(head, hero1)
	InsertHeroNode2(head, hero2)
	InsertHeroNode2(head, hero3)
	// 4. 显示
	ListHeroNode(head)
	fmt.Println()
	fmt.Println("逆序打印：")
	ListHeroNode1(head)
	fmt.Println()
}

运行结果：

[1, 宋江, 及时雨]==>[2, 卢俊义, 玉麒麟]==>[3, 林冲, 豹子头]==>
逆序打印：
[3, 林冲, 豹子头]==>[2, 卢俊义, 玉麒麟]==>[1, 宋江, 及时雨]==>

5.3 双向链表的删除

// 删除节点
func DelHeroNode(head *HeroNode, id int) {
	temp := head
	flag := false

	// 找到要删除的节点 no，和temp的下一个节点 no 进行比较
	for {
		if temp.next == nil { // 说明到链表的表尾
			break
		} else if temp.next.no > id {
			break
		} else if temp.next.no == id { // 说明找到了要删除的节点
			flag = true
			break
		}
		temp = temp.next
	}
	if !flag {
		fmt.Println("要删除的id不存在...", id)
		return
	} else {
		temp.next = temp.next.next
		if temp.next != nil {
			// 这里需要注意 上面除了连线 还移动了一下
			temp.next.pre = temp.next
		}
	}
}

六 单向环形链表

6.1 单向环形链表介绍

6.2 单向环形链表的创建和显示

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 // 形成环形
		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("空的环形列表")
	}
	for {
		fmt.Printf("猫的信息为=[id=%d name=%s]->", temp.no, temp.name)
		if temp.next == nil {
			break
		}
		if temp.next == head {
			break
		}
		temp = temp.next
	}
}

func main() {
	// 这里我们初始化一个环形链表的头节点
	head := &CatNode{}
	// 创建一只猫
	cat1 := &CatNode{
		no:   1,
		name: "tom",
	}
	cat2 := &CatNode{
		no:   2,
		name: "Som",
	}
	cat3 := &CatNode{
		no:   3,
		name: "pom",
	}
	InsertCatNode(head, cat1)
	InsertCatNode(head, cat2)
	InsertCatNode(head, cat3)
	ListCircleLink(head)
}

运行结果：

环形链表输出如下
猫的信息为=[id=1 name=tom]->猫的信息为=[id=2 name=Som]->猫的信息为=[id=3 name=pom]->

6.3 单向环形链表的删除

思路如下:

• 先让temp指向head
• 再让helper指向head，遍历后，让helper指向环形链表最后.
• 让temp和要删除的id进行比较，如果相同，则同helepr完成删除[这里必须考虑如果删除就是头结点]
• 返回一个新的head, 防止head指向删除节点

代码实现：

// 删除一个节点
func DeleteCatNode(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("删除了no=%d的猫猫", id)
			return head
		}
		fmt.Printf("没有no是%d猫", id)
		return head
	}
	// 将helper 定位到链表的最后
	for {
		if helper.next == head {
			break
		}
		helper = helper.next
	}
	// 如果有两个以上的节点
	flag := true
	for {
		if temp.next == head { // 找了一圈还没找到 [最后一个还没比较]
			break
		}
		if temp.no == id {
			// 删除的刚好是头节点
			if temp == head {
				head = head.next
			}
			// 找到要删除的节点
			helper.next = temp.next
			fmt.Printf("删除了no=%d的猫猫", id)
			flag = false
			break
		}
		temp = temp.next     // 移动 用于比较
		helper = helper.next // 移动 找到helper能帮我们删除它
	}
	// 这里是上面的最后一个
	// 还要比较一次
	if flag { //上面没有删除过flag为真
		if temp.no == id {
			helper.next = temp.next
			fmt.Printf("删除了no=%d的猫猫", id)
		} else {
			fmt.Printf("没有no是%d猫", id)
		}
	}
	return head
}

七 约瑟夫问题

7.1 约瑟夫问题介绍

Josephu 问题：

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

提示：

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

示意图：

7.2 约瑟夫问题解决

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,
		}
		// 分析构成循环链表，需要一个辅助指针[帮忙的]
		//1. 第一个小孩比较特殊
		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 GetNumBoy(first *Boy) int {
	curBoy := first
	sum := 0
	if first.Next == nil {
		fmt.Println("链表为空")
		return sum
	}
	for {
		sum++
		if curBoy.Next == first {
			break
		}
		curBoy = curBoy.Next
	}
	return sum
}

//分析思路
//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
	}
	fmt.Println(GetNumBoy(first))
	if startNo > GetNumBoy(first) {
		fmt.Println("参数输入错误")
		return
	}
	// 2. 创建一个辅助节点, 帮我们删除小孩
	tail := first
	// 3. 让tail执行环形链表的最后一个小孩 tail在删除时需要用到
	for {
		if tail.Next == first { //说明tail到了最后一个小孩
			break
		}
		tail = tail.Next
	}
	// 4. 让fisrt移动到startNo [后面我们删除小孩 就用first做标准]
	for i := 0; i < startNo-1; i++ {
		first = first.Next
		tail = tail.Next
	}
	// 5. 开始数countNum 然后就删除first 指向的小孩
	for {
		// 开始数countNum-1次
		for i := 0; i < countNum-1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Printf("小孩编号为%d出圈->", first.No)
		// 删除first 指向的小孩
		first = first.Next
		tail.Next = first
		// 如果tail==first,圈中只有一个小孩
		if tail == first {
			break
		}
	}
	fmt.Printf("小孩编号为%d出圈->", first.No)
}

func main() {
	first := AddBoy(5)
	// 显示
	ShowBoy(first)
	PlayGame(first, 2, 3)
}

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
小孩编号=1 ->小孩编号=2 ->小孩编号=3 ->小孩编号=4 ->小孩编号=5 ->5
小孩编号为4出圈->小孩编号为2出圈->小孩编号为1出圈->小孩编号为3出圈->小孩编号为5出圈->
[Done] exited with code=0 in 1.142 seconds