Go‘s 数据结构

教程

Go实现栈与队列

一、链表

单链表：

type LinkNode struct {
    val  int
    next *LinkNode   
}

循环链表：

type Ring struct {
    next, prev *Ring       // 前驱和后驱节点
    Value      interface{} // 数据
}

初始化循环链表：

// 初始化空的循环链表，前驱和后驱都指向自己，因为是循环的
func (r *Ring) init() *Ring {
    r.next = r
    r.prev = r
    return r
}

数组实现链表：【静态链表】

type Value struct {
  Data      string
  NextIndex int64
}

var array [5]Value      // 五个节点的数组
array[0] = Value{"I", 3}    // 下一个节点的下标为3
array[1] = Value{"Army", 4} // 下一个节点的下标为4
array[2] = Value{"You", 1}  // 下一个节点的下标为1
array[3] = Value{"Love", 2} // 下一个节点的下标为2
array[4] = Value{"!", -1}   // -1表示没有下一个节点
node := array[0]
for {
  fmt.Println(node.Data)
  if node.NextIndex == -1 {
    break
  }
  node = array[node.NextIndex]
}

---

二、栈和队列

go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作。

栈基本操作：

// 创建空栈
stack := make([]int, 0)

// 压栈push
stack = append(stack, 10)

// 取栈顶top
top = stack[len(stack) - 1]

// 弹栈pop
stack = stack[:len(stack) - 1]

// 检查栈是否为空empty
len(stack) == 0

队列基本操作：

// 创建队列
queue := make([]int, 0)

// 入队push（放入队尾）
queue = append(queue, 10)

// 返回队头front
front = queue[0]

// 返回队尾back
back = queue[len(queue) - 1]

// 出队pop
quque = queue[1:]

// 检查队列是否为空
len(queue) == 0

---

三、字典

3.1 字典

Golang 语言中字典 map 的实现由哈希表实现，具体可参考标准库 runtime 下的 map.go 文件。

---

3.2 集合

技巧：用字典达到集合的效果

声明：

set := make(map[key]struct{})

添加元素：O(1)

set[curKey] = struct{}{}

ps: struct{}{}不占空间，所以set只占用key和自身数据结构的内存

检查存在：

if _, ok := set[curKey]; ok {
    // 元素存在
}

删除：O(1)

delete(set, curKey)

---

四、树

二叉树节点：

type TreeNode struct {
    Data  string    // 节点用来存放数据
    Left  *TreeNode // 左子树
    Right *TreeNode // 右字树
}

---

---

五、通用方法

5.1 sort

Go 语言的 sort 包提供了用于排序切片和自定义数据结构的强大工具和接口。这个包提供了几种不同的排序方法，让你能够有效地排序内置数据类型（如切片）以及通过实现 sort.Interface 来排序自定义数据类型。

1. 内置类型的排序 （但是没有现成的降序排序函数）

对于基本数据类型的切片，如 int、float64 和 string，Go 的 sort 包提供了直接的排序函数：

• 排序整数：使用 sort.Ints 函数

  a := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
  sort.Ints(a)

• 排序浮点数：使用 sort.Float64s 函数

  f := []float64{3.1, 3.14, 2.71}
  sort.Float64s(f)

• 排序字符串：使用 sort.Strings 函数

  s := []string{"Go", "Bravo", "Gopher", "Alpha"}
  sort.Strings(s)

这些函数都是对切片进行原地排序，即不创建切片的副本进行排序，而是直接在原切片上进行排序。

2. 自定义排序

如果你需要对自定义的数据结构进行排序，可以通过实现 sort.Interface 接口来实现。这个接口定义了三个方法：

• Len() 返回集合中的元素个数
• Less(i, j int) bool 报告索引 i 的元素是否应该比索引 j 的元素排在前面
• Swap(i, j int) 交换索引 i 和 j 位置的元素

通过实现这三个方法，你可以定义自定义类型的排序行为。

type Person struct {
    Name string
    Age  int
}

type ByAge []Person

func (a ByAge) Len() int       { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
    people := []Person{
    {"Bob", 31},
    {"John", 42},
    {"Michael", 17},
    {"Jenny", 26},
    }

    sort.Sort(ByAge(people))
    fmt.Println(people)
}

在这个例子中，Person 结构体按照 Age 字段进行排序。

3. 性能和稳定性

• 性能：Go 的排序算法主要是快速排序，它的平均时间复杂度是 O(n log n)。在最坏的情况下，也就是当输入数组已经接近排序完成时，快速排序的性能会降低，但 Go 实现中通过引入其他算法（如堆排序）作为补充来优化这种情况。
• 稳定排序：如果你需要保持等值元素的相对顺序，可以使用 sort.Stable 方法。这确保如果 Less 方法报告元素 i 和 j 相等（即 !Less(i, j) && !Less(j, i)），它们的相对顺序不会改变。

sort.Stable(ByAge(people))

这提供了在复杂数据排序时更细粒度的控制，特别是当数据的次序有实际意义时。

---

5.2 堆（优先级队列）

在 Go 语言中，优先级队列（Priority Queue）通常通过最小堆或最大堆实现。Go 标准库的 container/heap 包提供了堆的基础操作，可以帮助我们构建自定义的优先级队列。

1. 基本原理

在 Go 中，container/heap 包实现的是最小堆（Min-Heap）。这意味着堆顶（即堆中第一个元素）总是最小的元素。如果我们需要实现最大堆（Max-Heap），可以通过对元素的比较操作进行反转来实现。

2. 使用 container/heap 实现优先级队列

要使用 container/heap 实现优先级队列，需要实现 heap.Interface 接口。该接口要求以下方法：

• Len() int：返回堆中元素的数量。
• Less(i, j int) bool：决定索引 i 的元素是否应排在索引 j 的元素之前。在最小堆中，Less(i, j) 应该返回 true 表示 i 小于 j。
• Swap(i, j int)：交换索引 i 和索引 j 的元素。
• Push(x interface{})：将元素 x 推入堆。
• Pop() interface{}：从堆中移除并返回堆顶元素。

3. 示例：最小堆优先级队列

以下是一个简单的示例，演示如何使用 container/heap 实现一个整数优先级队列（最小堆）：

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap 定义了一个整数堆，实现了 heap.Interface 接口
type IntHeap []int

// Len 方法返回堆的长度
func (h *IntHeap) Len() int { return len(*h) }

// Less 方法定义元素的优先级，最小堆需要 h[i] < h[j]
func (h *IntHeap) Less(i, j int) bool { return (*h)[i] < (*h)[j] }

// Swap 方法交换两个元素
func (h *IntHeap) Swap(i, j int) { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }

// Push 方法将元素推入堆（实现堆的插入操作）
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 方法从堆中移除并返回堆顶元素
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h) // 初始化堆

	// 向堆中添加元素
	heap.Push(h, 3)
	heap.Push(h, 6)
	heap.Push(h, 4)

	// 弹出所有元素
	fmt.Println("Priority Queue:")
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

4. 最大堆优先级队列

要实现最大堆，只需反转 Less 方法的逻辑即可：

func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }

将 Less 改为 h[i] > h[j] 后，container/heap 包会将其视为最大堆。

5. 自定义优先级的结构体

你可以使用自定义的结构体来存储元素，例如任务调度的场景中，需要优先处理优先级更高的任务。以下是一个示例，定义了一个任务结构体的优先级队列：

package main

import (
    "container/heap"
    "fmt"
)

// Task 表示任务的结构体
type Task struct {
    priority int
    name     string
}

// TaskHeap 定义了任务堆，实现了 heap.Interface 接口
type TaskHeap []Task

func (h *TaskHeap) Len() int           { return len(*h) }
func (h *TaskHeap) Less(i, j int) bool { return (*h)[i].priority < (*h)[j].priority }
func (h *TaskHeap) Swap(i, j int)      { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }

func (h *TaskHeap) Push(x interface{}) {
    *h = append(*h, x.(Task))
}

func (h *TaskHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &TaskHeap{
        {priority: 3, name: "Write Code"},
        {priority: 1, name: "Fix Bug"},
        {priority: 2, name: "Test Code"},
    }
    heap.Init(h)

    heap.Push(h, Task{priority: 4, name: "Code Review"})
    heap.Push(h, Task{priority: 0, name: "Deployment"})

    fmt.Println("Tasks by priority:")
    for h.Len() > 0 {
    task := heap.Pop(h).(Task)
    fmt.Printf("Task: %s, Priority: %d\n", task.name, task.priority)
    }
}

在这个例子中，优先级更小的任务会被优先处理。

---

5.3 数学计算

以下是 Go 语言 math 包中常用的函数的总结，包括说明、使用方法以及时间复杂度：

---

1. math.Abs(x float64) float64

说明: 计算并返回 x 的绝对值。

使用:

import "math"

x := -5.3
result := math.Abs(x)  // result = 5.3

时间复杂度: O(1) – 绝对值的计算是一个简单的单步操作。

2. math.Ceil(x float64) float64

说明: 向上取整，将 x 向上舍入到最接近的整数值。

使用:

import "math"

x := 5.3
result := math.Ceil(x)  // result = 6.0

时间复杂度: O(1) – 向上取整也是一个简单的单步操作。

3. math.Floor(x float64) float64

说明: 向下取整，将 x 向下舍入到最接近的整数值。

使用:

import "math"

x := 5.7
result := math.Floor(x)  // result = 5.0

时间复杂度: O(1) – 向下取整也是一个单步操作。

4. math.Pow(x, y float64) float64

说明: 计算 x 的 y 次方。

使用:

import "math"

x := 2.0
y := 3.0
result := math.Pow(x, y)  // result = 8.0

时间复杂度: O(log y) – 使用快速幂算法实现，次方计算的时间复杂度与 y 的大小有关，通常为 O(log y)。

5. math.Sqrt(x float64) float64

说明: 计算 x 的平方根。

使用:

import "math"

x := 16.0
result := math.Sqrt(x)  // result = 4.0

时间复杂度: O(1) – 由于平方根使用高效算法实现，在硬件和算法优化下通常为常数时间。

6. math.Max(x, y float64) float64

说明: 返回 x 和 y 中的最大值。

使用:

import "math"

x := 5.0
y := 8.0
result := math.Max(x, y)  // result = 8.0

时间复杂度: O(1) – 最大值的计算仅涉及一次比较操作，因此是常数时间。

7. math.Min(x, y float64) float64

说明: 返回 x 和 y 中的最小值。

使用:

import "math"

x := 5.0
y := 8.0
result := math.Min(x, y)  // result = 5.0

时间复杂度: O(1) – 最小值的计算仅涉及一次比较操作，因此是常数时间。

---

六、排序算法（例）

• 快排

查看输出

package main

import "fmt"

func partition(arr []int, left, right int) int { // [left, right]
    pivotVal := arr[left] // 取第一个数作为枢轴的值
    for left < right {
    for left < right && pivotVal <= arr[right] {
        right--
    }
    arr[left] = arr[right]
    for left < right && pivotVal >= arr[left] {
        left++
    }
    arr[right] = arr[left]
    }
    arr[left] = pivotVal
    return left
}

func quicksort(arr []int, left, right int) { // [left, right]
    if left < right {
    pivot := partition(arr, left, right)
    quicksort(arr, left, pivot-1)
    quicksort(arr, pivot+1, right)
    }
}

func main() {
    arr := []int{15, 22, 55, 34, 25, 16, 7, 58, 79, 10}
    quicksort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

输出为：

[7 10 15 16 22 25 34 55 58 79]

---

易错点

1. 列表传参数使用append函数

查看案例

列表是一个指针：

package main

import "fmt"

func main() {
    arr := [5]int{1, 2, 3, 4, 5}
    sli := arr[2:5]
    sli[1] = 100
    fmt.Println(sli) // 输出为[3 100 5]
    fmt.Println(arr) // 输出为[1 2 3 100 5]
}

但是下面逻辑出错：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    inorder(root, ans)
    return ans
}

func inorder(root *TreeNode, ans []int) {
    if root == nil {
    return
    }
    inorder(root.Left, ans)
    ans = append(ans, root.Val)
    inorder(root.Right, ans)
}

在 Go 中，slice 是通过引用传递的，但是对于 append 函数的具体行为，需要特别注意：

• 当 append 导致 slice 容量增加时，会创建一个新的底层数组，原始的 slice 引用的数组不会被改变。
• 当 append 操作未超过原 slice 的容量时，它会在原数组的基础上修改数据，并影响所有引用该数组的 slice。
• 在 inorder 中对 ans 使用了 append，这可能导致 ans 的底层数组发生变化（扩容操作），尤其是在多次 append 后超过了原始容量。

• 当 append 导致扩容时，它返回的是一个指向新底层数组的新 slice。这意味着，虽然 ans 在 inorder 函数中被修改，但是这些修改不会反映到 inorderTraversal 函数中的 ans 上，因为它们可能指向不同的底层数组。

2. 代码块问题

查看案例

这种内部范围的变量覆盖了返回值变量

修改方法：
1.内部范围变量重命名
2.return err

---

others

max min函数 https://blog.csdn.net/caspar_notes/article/details/132843940