Go语言的数据结构与算法

Go语言的数据结构与算法为什么学习数据结构与算法数据结构与算法是计算机科学的核心基础对于Go开发者来说尤为重要提高代码效率选择合适的数据结构可以大幅提升程序性能解决复杂问题算法思维帮助你分解和解决复杂问题面试必备技术面试中算法题是必考内容代码质量良好的算法设计使代码更优雅、可维护基础数据结构数组Array数组是最基础的数据结构Go中的数组是固定长度的// 数组的基本操作 package main import fmt func main() { // 声明数组 var arr [5]int [5]int{1, 2, 3, 4, 5} // 访问元素 fmt.Println(arr[0]) // 1 // 修改元素 arr[0] 10 // 获取长度 fmt.Println(len(arr)) // 5 // 遍历数组 for i, v : range arr { fmt.Printf(索引: %d, 值: %d\n, i, v) } }数组的优缺点优点访问速度快 O(1)内存连续缺点大小固定插入删除效率低 O(n)切片Slice切片是Go语言中更常用的动态数组package main import fmt func main() { // 创建切片 slice : []int{1, 2, 3, 4, 5} // 追加元素 slice append(slice, 6) // 获取长度和容量 fmt.Printf(长度: %d, 容量: %d\n, len(slice), cap(slice)) // 切片操作 subSlice : slice[1:4] // [2, 3, 4] // 复制切片 newSlice : make([]int, len(slice)) copy(newSlice, slice) }切片实现原理type slice struct { array unsafe.Pointer // 指向底层数组的指针 len int // 长度 cap int // 容量 }链表Linked List链表是线性数据结构元素通过指针连接package main import fmt // 链表节点 type ListNode struct { Val int Next *ListNode } // 链表结构 type LinkedList struct { Head *ListNode Size int } // 在头部插入 func (l *LinkedList) InsertAtHead(val int) { newNode : ListNode{Val: val, Next: l.Head} l.Head newNode l.Size } // 在尾部插入 func (l *LinkedList) InsertAtTail(val int) { newNode : ListNode{Val: val} if l.Head nil { l.Head newNode } else { current : l.Head for current.Next ! nil { current current.Next } current.Next newNode } l.Size } // 删除节点 func (l *LinkedList) Delete(val int) bool { if l.Head nil { return false } if l.Head.Val val { l.Head l.Head.Next l.Size-- return true } current : l.Head for current.Next ! nil { if current.Next.Val val { current.Next current.Next.Next l.Size-- return true } current current.Next } return false } // 打印链表 func (l *LinkedList) Print() { current : l.Head for current ! nil { fmt.Printf(%d - , current.Val) current current.Next } fmt.Println(nil) } func main() { list : LinkedList{} list.InsertAtTail(1) list.InsertAtTail(2) list.InsertAtTail(3) list.InsertAtHead(0) list.Print() // 0 - 1 - 2 - 3 - nil list.Delete(2) list.Print() // 0 - 1 - 3 - nil }链表vs数组特性数组链表访问O(1)O(n)插入/删除O(n)O(1)内存连续分散缓存友好是否栈Stack栈是后进先出LIFO的数据结构package main import fmt // 栈结构 type Stack struct { items []int } // 入栈 func (s *Stack) Push(item int) { s.items append(s.items, item) } // 出栈 func (s *Stack) Pop() (int, bool) { if len(s.items) 0 { return 0, false } item : s.items[len(s.items)-1] s.items s.items[:len(s.items)-1] return item, true } // 查看栈顶 func (s *Stack) Peek() (int, bool) { if len(s.items) 0 { return 0, false } return s.items[len(s.items)-1], true } // 判断是否为空 func (s *Stack) IsEmpty() bool { return len(s.items) 0 } // 获取大小 func (s *Stack) Size() int { return len(s.items) } func main() { stack : Stack{} stack.Push(1) stack.Push(2) stack.Push(3) fmt.Printf(栈大小: %d\n, stack.Size()) for !stack.IsEmpty() { item, _ : stack.Pop() fmt.Printf(弹出: %d\n, item) } }栈的应用场景函数调用栈表达式求值括号匹配浏览器前进后退Undo操作队列Queue队列是先进先出FIFO的数据结构package main import fmt // 队列结构 type Queue struct { items []int } // 入队 func (q *Queue) Enqueue(item int) { q.items append(q.items, item) } // 出队 func (q *Queue) Dequeue() (int, bool) { if len(q.items) 0 { return 0, false } item : q.items[0] q.items q.items[1:] return item, true } // 查看队首 func (q *Queue) Front() (int, bool) { if len(q.items) 0 { return 0, false } return q.items[0], true } // 判断是否为空 func (q *Queue) IsEmpty() bool { return len(q.items) 0 } // 获取大小 func (q *Queue) Size() int { return len(q.items) } func main() { queue : Queue{} queue.Enqueue(1) queue.Enqueue(2) queue.Enqueue(3) fmt.Printf(队列大小: %d\n, queue.Size()) for !queue.IsEmpty() { item, _ : queue.Dequeue() fmt.Printf(出队: %d\n, item) } }双端队列Dequetype Deque struct { items []int } func (d *Deque) PushFront(item int) { d.items append([]int{item}, d.items...) } func (d *Deque) PushBack(item int) { d.items append(d.items, item) } func (d *Deque) PopFront() (int, bool) { if len(d.items) 0 { return 0, false } item : d.items[0] d.items d.items[1:] return item, true } func (d *Deque) PopBack() (int, bool) { if len(d.items) 0 { return 0, false } item : d.items[len(d.items)-1] d.items d.items[:len(d.items)-1] return item, true }哈希表Hash TableGo语言使用map实现哈希表package main import fmt func main() { // 创建map hashMap : make(map[string]int) // 添加键值对 hashMap[apple] 5 hashMap[banana] 3 hashMap[orange] 7 // 访问 fmt.Println(hashMap[apple]) // 5 // 检查键是否存在 if val, ok : hashMap[grape]; ok { fmt.Println(val) } else { fmt.Println(grape不存在) } // 删除 delete(hashMap, banana) // 遍历 for key, val : range hashMap { fmt.Printf(%s: %d\n, key, val) } }自定义哈希表实现package main import fmt const ArraySize 7 // 哈希表节点 type node struct { key string value int next *node } // 哈希表 type HashTable struct { array [ArraySize]*node } // 哈希函数 func hash(key string) int { sum : 0 for _, ch : range key { sum int(ch) } return sum % ArraySize } // 插入 func (h *HashTable) Insert(key string, value int) { index : hash(key) newNode : node{key: key, value: value} if h.array[index] nil { h.array[index] newNode } else { current : h.array[index] for current.next ! nil { if current.key key { current.value value return } current current.next } if current.key key { current.value value } else { current.next newNode } } } // 查找 func (h *HashTable) Search(key string) (int, bool) { index : hash(key) current : h.array[index] for current ! nil { if current.key key { return current.value, true } current current.next } return 0, false } // 删除 func (h *HashTable) Delete(key string) bool { index : hash(key) if h.array[index] nil { return false } if h.array[index].key key { h.array[index] h.array[index].next return true } current : h.array[index] for current.next ! nil { if current.next.key key { current.next current.next.next return true } current current.next } return false } func main() { ht : HashTable{} ht.Insert(Eric, 25) ht.Insert(Kenny, 21) ht.Insert(Kyle, 23) ht.Insert(Stan, 26) if val, ok : ht.Search(Kyle); ok { fmt.Printf(Kyle的年龄: %d\n, val) } ht.Delete(Kenny) if _, ok : ht.Search(Kenny); !ok { fmt.Println(Kenny已被删除) } }树Tree二叉树package main import fmt // 二叉树节点 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // 前序遍历 func preOrder(root *TreeNode) { if root nil { return } fmt.Printf(%d , root.Val) preOrder(root.Left) preOrder(root.Right) } // 中序遍历 func inOrder(root *TreeNode) { if root nil { return } inOrder(root.Left) fmt.Printf(%d , root.Val) inOrder(root.Right) } // 后序遍历 func postOrder(root *TreeNode) { if root nil { return } postOrder(root.Left) postOrder(root.Right) fmt.Printf(%d , root.Val) } // 层序遍历 func levelOrder(root *TreeNode) { if root nil { return } queue : []*TreeNode{root} for len(queue) 0 { node : queue[0] queue queue[1:] fmt.Printf(%d , node.Val) if node.Left ! nil { queue append(queue, node.Left) } if node.Right ! nil { queue append(queue, node.Right) } } } func main() { // 构建二叉树 root : TreeNode{Val: 1} root.Left TreeNode{Val: 2} root.Right TreeNode{Val: 3} root.Left.Left TreeNode{Val: 4} root.Left.Right TreeNode{Val: 5} fmt.Print(前序遍历: ) preOrder(root) fmt.Println() fmt.Print(中序遍历: ) inOrder(root) fmt.Println() fmt.Print(后序遍历: ) postOrder(root) fmt.Println() fmt.Print(层序遍历: ) levelOrder(root) fmt.Println() }二叉搜索树BSTpackage main import fmt type BST struct { root *TreeNode } // 插入 func (bst *BST) Insert(val int) { bst.root insertNode(bst.root, val) } func insertNode(node *TreeNode, val int) *TreeNode { if node nil { return TreeNode{Val: val} } if val node.Val { node.Left insertNode(node.Left, val) } else if val node.Val { node.Right insertNode(node.Right, val) } return node } // 查找 func (bst *BST) Search(val int) bool { return searchNode(bst.root, val) } func searchNode(node *TreeNode, val int) bool { if node nil { return false } if val node.Val { return searchNode(node.Left, val) } else if val node.Val { return searchNode(node.Right, val) } return true } // 删除 func (bst *BST) Delete(val int) { bst.root deleteNode(bst.root, val) } func deleteNode(node *TreeNode, val int) *TreeNode { if node nil { return nil } if val node.Val { node.Left deleteNode(node.Left, val) } else if val node.Val { node.Right deleteNode(node.Right, val) } else { // 找到要删除的节点 if node.Left nil { return node.Right } else if node.Right nil { return node.Left } // 有两个子节点找到右子树的最小值 minNode : findMin(node.Right) node.Val minNode.Val node.Right deleteNode(node.Right, minNode.Val) } return node } func findMin(node *TreeNode) *TreeNode { for node.Left ! nil { node node.Left } return node } func main() { bst : BST{} values : []int{50, 30, 70, 20, 40, 60, 80} for _, v : range values { bst.Insert(v) } fmt.Printf(查找40: %v\n, bst.Search(40)) fmt.Printf(查找100: %v\n, bst.Search(100)) bst.Delete(30) fmt.Printf(删除30后查找30: %v\n, bst.Search(30)) }常用算法排序算法快速排序package main import fmt func quickSort(arr []int) []int { if len(arr) 1 { return arr } pivot : arr[len(arr)/2] left : []int{} right : []int{} equal : []int{} for _, num : range arr { if num pivot { left append(left, num) } else if num pivot { right append(right, num) } else { equal append(equal, num) } } left quickSort(left) right quickSort(right) return append(append(left, equal...), right...) } func main() { arr : []int{64, 34, 25, 12, 22, 11, 90} fmt.Println(原始数组:, arr) sorted : quickSort(arr) fmt.Println(排序后:, sorted) }归并排序package main import fmt func mergeSort(arr []int) []int { if len(arr) 1 { return arr } mid : len(arr) / 2 left : mergeSort(arr[:mid]) right : mergeSort(arr[mid:]) return merge(left, right) } func merge(left, right []int) []int { result : []int{} i, j : 0, 0 for i len(left) j len(right) { if left[i] right[j] { result append(result, left[i]) i } else { result append(result, right[j]) j } } result append(result, left[i:]...) result append(result, right[j:]...) return result } func main() { arr : []int{64, 34, 25, 12, 22, 11, 90} fmt.Println(原始数组:, arr) sorted : mergeSort(arr) fmt.Println(排序后:, sorted) }搜索算法二分查找package main import fmt func binarySearch(arr []int, target int) int { left, right : 0, len(arr)-1 for left right { mid : left (right-left)/2 if arr[mid] target { return mid } else if arr[mid] target { left mid 1 } else { right mid - 1 } } return -1 } func main() { arr : []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91} target : 23 result : binarySearch(arr, target) if result ! -1 { fmt.Printf(找到目标 %d 在索引 %d\n, target, result) } else { fmt.Println(未找到目标) } }图算法图的表示package main import fmt // 邻接矩阵表示 type GraphMatrix struct { vertices int adjMatrix [][]int } func NewGraphMatrix(vertices int) *GraphMatrix { g : GraphMatrix{vertices: vertices} g.adjMatrix make([][]int, vertices) for i : range g.adjMatrix { g.adjMatrix[i] make([]int, vertices) } return g } func (g *GraphMatrix) AddEdge(u, v int) { g.adjMatrix[u][v] 1 g.adjMatrix[v][u] 1 // 无向图 } // 邻接表表示 type GraphList struct { vertices int adjList map[int][]int } func NewGraphList(vertices int) *GraphList { return GraphList{ vertices: vertices, adjList: make(map[int][]int), } } func (g *GraphList) AddEdge(u, v int) { g.adjList[u] append(g.adjList[u], v) g.adjList[v] append(g.adjList[v], u) // 无向图 }深度优先搜索DFSfunc (g *GraphList) DFS(start int) { visited : make(map[int]bool) g.dfsHelper(start, visited) } func (g *GraphList) dfsHelper(vertex int, visited map[int]bool) { visited[vertex] true fmt.Printf(%d , vertex) for _, neighbor : range g.adjList[vertex] { if !visited[neighbor] { g.dfsHelper(neighbor, visited) } } }广度优先搜索BFSfunc (g *GraphList) BFS(start int) { visited : make(map[int]bool) queue : []int{start} visited[start] true for len(queue) 0 { vertex : queue[0] queue queue[1:] fmt.Printf(%d , vertex) for _, neighbor : range g.adjList[vertex] { if !visited[neighbor] { visited[neighbor] true queue append(queue, neighbor) } } } }动态规划斐波那契数列package main import fmt // 递归低效 func fibonacciRecursive(n int) int { if n 1 { return n } return fibonacciRecursive(n-1) fibonacciRecursive(n-2) } // 动态规划高效 func fibonacciDP(n int) int { if n 1 { return n } dp : make([]int, n1) dp[0] 0 dp[1] 1 for i : 2; i n; i { dp[i] dp[i-1] dp[i-2] } return dp[n] } // 空间优化 func fibonacciOptimized(n int) int { if n 1 { return n } prev2, prev1 : 0, 1 for i : 2; i n; i { current : prev1 prev2 prev2 prev1 prev1 current } return prev1 } func main() { n : 10 fmt.Printf(斐波那契数列第%d项: %d\n, n, fibonacciDP(n)) fmt.Printf(优化版本: %d\n, fibonacciOptimized(n)) }最长公共子序列LCSpackage main import fmt func longestCommonSubsequence(text1, text2 string) int { m, n : len(text1), len(text2) dp : make([][]int, m1) for i : range dp { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if text1[i-1] text2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]) } } } return dp[m][n] } func max(a, b int) int { if a b { return a } return b } func main() { text1 : ABCDE text2 : ACE fmt.Printf(LCS长度: %d\n, longestCommonSubsequence(text1, text2)) }算法复杂度分析时间复杂度复杂度名称说明O(1)常数时间最优O(log n)对数时间很好O(n)线性时间好O(n log n)线性对数较好O(n²)平方时间较差O(2ⁿ)指数时间很差O(n!)阶乘时间极差空间复杂度空间复杂度表示算法运行所需的额外内存空间。Go语言标准库中的数据结构container/list - 双向链表package main import ( container/list fmt ) func main() { l : list.New() // 在尾部添加 l.PushBack(1) l.PushBack(2) // 在头部添加 l.PushFront(0) // 遍历 for e : l.Front(); e ! nil; e e.Next() { fmt.Println(e.Value) } }container/heap - 堆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, 5} heap.Init(h) heap.Push(h, 3) fmt.Printf(最小值: %d\n, (*h)[0]) for h.Len() 0 { fmt.Printf(%d , heap.Pop(h)) } }container/ring - 环形链表package main import ( container/ring fmt ) func main() { r : ring.New(5) // 初始化 for i : 0; i r.Len(); i { r.Value i r r.Next() } // 遍历 r.Do(func(p interface{}) { fmt.Println(p) }) }总结本文介绍了Go语言中常用的数据结构和算法数据结构数组和切片链表栈和队列哈希表树二叉树、二叉搜索树图算法排序算法快速排序、归并排序搜索算法二分查找图算法DFS、BFS动态规划掌握这些数据结构和算法将帮助你编写更高效的代码解决复杂的编程问题通过技术面试提升编程思维建议在学习过程中多动手实践通过LeetCode、牛客网等平台刷题巩固知识。