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 包提供了多种高效的数据结构实现，包括：

...