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

三、字典

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

四、树

二叉树节点：

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

五、排序算法

快排

查看输出

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)
}

输出为：

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

易错点

列表传参数使用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 后超过了原始容量。