Go语言数据结构和算法

图和节点

概念介绍

• 图是由顶点集合和边集合组成的数据结构。
• 节点即为图中的顶点，可以包含额外的信息如键值对。
• 边连接两个节点，表示节点之间的关系。

示例代码

type Graph struct {
    adjList map[int][]int
}

func NewGraph() *Graph {
    return &Graph{adjList: make(map[int][]int)}
}

func (g *Graph) AddEdge(v1, v2 int) {
    g.adjList[v1] = append(g.adjList[v1], v2)
    g.adjList[v2] = append(g.adjList[v2], v1)
}

算法复杂度分析

• 时间复杂度：衡量算法运行所需时间的增长率。
• 空间复杂度：衡量算法运行过程中临时占用存储空间大小的增长率。

分析方法

• 使用大O符号表示复杂度。
• 关注最坏情况下的复杂度。

Go的二叉树

基本定义

• 二叉树是一种树形结构，每个节点最多有两个子节点。
• 包括根节点、左子树、右子树。

示例代码

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func NewTreeNode(val int) *TreeNode {
    return &TreeNode{Val: val}
}

Go的哈希表

实现原理

• 使用哈希函数将键映射到数组索引。
• 解决冲突的方法有链地址法和开放地址法。

示例代码

type HashTable struct {
    size int
    data []interface{}
}

func NewHashTable(size int) *HashTable {
    return &HashTable{size: size, data: make([]interface{}, size)}
}

func (h *HashTable) put(key string, value interface{}) {
    hash := hashFunction(key, h.size)
    h.data[hash] = value
}

func hashFunction(key string, size int) int {
    var hash int
    for _, v := range key {
        hash += int(v)
    }
    return hash % size
}

Go的链表

特点

• 动态数据结构，长度可变。
• 每个元素都是一个节点，包含数据和指向下一个节点的指针。

示例代码

type ListNode struct {
    Val  int
    Next *ListNode
}

func NewListNode(val int) *ListNode {
    return &ListNode{Val: val}
}

Go的双端链表

双端链表允许从两端插入或删除元素。

示例代码

type DoubleNode struct {
    Val  int
    Prev *DoubleNode
    Next *DoubleNode
}

func NewDoubleNode(val int) *DoubleNode {
    return &DoubleNode{Val: val}
}

Go的队列

先进先出(FIFO)原则。

示例代码

type Queue struct {
    front *ListNode
    rear  *ListNode
}

func NewQueue() *Queue {
    return &Queue{}
}

func (q *Queue) Enqueue(val int) {
    node := NewListNode(val)
    if q.rear == nil {
        q.front = node
        q.rear = node
    } else {
        q.rear.Next = node
        q.rear = node
    }
}

Go的栈

后进先出(LIFO)原则。

示例代码

type Stack struct {
    top *ListNode
}

func NewStack() *Stack {
    return &Stack{}
}

func (s *Stack) Push(val int) {
    node := NewListNode(val)
    node.Next = s.top
    s.top = node
}

Go 标准库 container 包提供的数据结构

Go 的 container 包提供了多种高效的数据结构实现，包括：

List (双向链表)

特点：双向链表支持高效的插入和删除操作。

方法：

• NewList()：创建一个新的双向链表。
• Front()：返回链表的第一个元素。
• Back()：返回链表的最后一个元素。
• PushFront(value)：在链表头部插入一个新元素。
• PushBack(value)：在链表尾部插入一个新元素。
• Remove(element)：删除指定元素。

示例代码

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()

    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)

    fmt.Println("List:", l)

    front := l.Front()
    for front != nil {
        fmt.Println(front.Value)
        front = front.Next()
    }

    l.Remove(l.Front())
    fmt.Println("After removing first element:", l)
}

Heap (堆)

特点：堆是一种基于完全二叉树的结构，支持高效的插入和删除操作。

方法：

• Init(h Heap)：初始化堆。
• Push(h Heap, x interface{})：向堆中添加元素。
• Pop(h Heap) interface{}：从堆中移除并返回最小（或最大）元素。

示例代码

package main

import (
    "container/heap"
    "fmt"
)

type IntHeap []int

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

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

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, 3}
    heap.Init(h)

    heap.Push(h, 4)
    fmt.Println("Heap:", *h)

    fmt.Println("Popped:", heap.Pop(h))
    fmt.Println("Heap after pop:", *h)
}

Ring (环形缓冲区)

特点：环形缓冲区支持高效的循环访问。

方法：

• New(size int)：创建一个新的环形缓冲区。
• Value()：获取当前元素。
• Next()：移动到下一个元素。
• Prev()：移动到上一个元素。

示例代码

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r := ring.New(5)
    r.Value = "A"
    r = r.Next()
    r.Value = "B"
    r = r.Next()
    r.Value = "C"

    fmt.Println("Ring:", r)

    for i := 0; i < 5; i++ {
        fmt.Println(r.Value)
        r = r.Next()
    }
}

Go 生成随机数

方法

• 标准库：math/rand 包提供了生成随机数的功能。
• 初始化：使用 rand.NewSource 和 rand.New 初始化随机数生成器。
• 生成随机数：使用 Intn, Float64 等方法生成随机数。

示例代码

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().UnixNano())

    randomInt := rand.Intn(100)
    fmt.Println("Random integer:", randomInt)

    randomFloat := rand.Float64()
    fmt.Println("Random float:", randomFloat)
}

Go 堆栈的理解

定义

• 堆栈：一种后进先出（LIFO）的数据结构。

操作：

• Push：向堆栈顶部添加一个元素。
• Pop：从堆栈顶部移除一个元素。
• Peek：查看堆栈顶部的元素而不移除。

示例代码

package main

import (
    "fmt"
)

type Stack struct {
    items []int
}

func NewStack() *Stack {
    return &Stack{items: make([]int, 0)}
}

func (s *Stack) Push(val int) {
    s.items = append(s.items, val)
}

func (s *Stack) Pop() int {
    if len(s.items) == 0 {
        return -1 // 或者自定义错误处理
    }
    val := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return val
}

func (s *Stack) Peek() int {
    if len(s.items) == 0 {
        return -1 // 或者自定义错误处理
    }
    return s.items[len(s.items)-1]
}

func main() {
    stack := NewStack()

    stack.Push(1)
    stack.Push(2)
    stack.Push(3)

    fmt.Println("Top of stack:", stack.Peek()) // 输出 3

    fmt.Println("Popped:", stack.Pop()) // 输出 3
    fmt.Println("Popped:", stack.Pop()) // 输出 2
    fmt.Println("Popped:", stack.Pop()) // 输出 1
}