Golang实现CLRS算法与数据结构学习插件库

CLRS（《算法导论》）是计算机科学领域经典的算法教材，下面我将介绍如何在Go语言中实现CLRS中的核心算法与数据结构，并构建一个可复用的学习插件库。

基本数据结构实现

1. 链表

package algorithms

// 链表节点
type ListNode struct {
    Value interface{}
    Next  *ListNode
}

// 链表基本操作
type LinkedList struct {
    Head *ListNode
    Size int
}

func NewLinkedList() *LinkedList {
    return &LinkedList{nil, 0}
}

func (l *LinkedList) Insert(value interface{}) {
    newNode := &ListNode{Value: value, Next: l.Head}
    l.Head = newNode
    l.Size++
}

func (l *LinkedList) Search(value interface{}) *ListNode {
    current := l.Head
    for current != nil {
        if current.Value == value {
            return current
        }
        current = current.Next
    }
    return nil
}

2. 二叉搜索树

package algorithms

// 二叉树节点
type TreeNode struct {
    Key   int
    Left  *TreeNode
    Right *TreeNode
}

// 二叉搜索树
type BinarySearchTree struct {
    Root *TreeNode
}

func NewBST() *BinarySearchTree {
    return &BinarySearchTree{nil}
}

func (t *BinarySearchTree) Insert(key int) {
    t.Root = insertNode(t.Root, key)
}

func insertNode(node *TreeNode, key int) *TreeNode {
    if node == nil {
        return &TreeNode{Key: key}
    }
    
    if key < node.Key {
        node.Left = insertNode(node.Left, key)
    } else if key > node.Key {
        node.Right = insertNode(node.Right, key)
    }
    return node
}

// 中序遍历
func (t *BinarySearchTree) InOrder() []int {
    result := make([]int, 0)
    inOrderTraversal(t.Root, &result)
    return result
}

func inOrderTraversal(node *TreeNode, result *[]int) {
    if node != nil {
        inOrderTraversal(node.Left, result)
        *result = append(*result, node.Key)
        inOrderTraversal(node.Right, result)
    }
}

核心算法实现

1. 排序算法

package algorithms

// 快速排序 (CLRS第7章)
func QuickSort(arr []int) {
    if len(arr) <= 1 {
        return
    }
    
    pivot := partition(arr)
    QuickSort(arr[:pivot])
    QuickSort(arr[pivot+1:])
}

func partition(arr []int) int {
    pivot := arr[len(arr)-1]
    i := -1
    
    for j := 0; j < len(arr)-1; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    
    arr[i+1], arr[len(arr)-1] = arr[len(arr)-1], arr[i+1]
    return i + 1
}

// 归并排序 (CLRS第2章)
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 := make([]int, 0, len(left)+len(right))
    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
}

2. 图算法

package algorithms

// 图的邻接表表示
type Graph struct {
    Vertices int
    Adj      [][]int
}

func NewGraph(vertices int) *Graph {
    return &Graph{
        Vertices: vertices,
        Adj:      make([][]int, vertices),
    }
}

func (g *Graph) AddEdge(u, v int) {
    g.Adj[u] = append(g.Adj[u], v)
}

// BFS (CLRS第22章)
func (g *Graph) BFS(start int) []int {
    visited := make([]bool, g.Vertices)
    queue := []int{start}
    visited[start] = true
    result := make([]int, 0)
    
    for len(queue) > 0 {
        vertex := queue[0]
        queue = queue[1:]
        result = append(result, vertex)
        
        for _, neighbor := range g.Adj[vertex] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    
    return result
}

// DFS (CLRS第22章)
func (g *Graph) DFS(start int) []int {
    visited := make([]bool, g.Vertices)
    result := make([]int, 0)
    g.dfsUtil(start, visited, &result)
    return result
}

func (g *Graph) dfsUtil(vertex int, visited []bool, result *[]int) {
    visited[vertex] = true
    *result = append(*result, vertex)
    
    for _, neighbor := range g.Adj[vertex] {
        if !visited[neighbor] {
            g.dfsUtil(neighbor, visited, result)
        }
    }
}

插件库设计

package algorithms

// 插件接口
type AlgorithmPlugin interface {
    Name() string
    Description() string
    Execute(input interface{}) (interface{}, error)
}

// 插件注册器
type PluginRegistry struct {
    plugins map[string]AlgorithmPlugin
}

func NewPluginRegistry() *PluginRegistry {
    return &PluginRegistry{
        plugins: make(map[string]AlgorithmPlugin),
    }
}

func (r *PluginRegistry) Register(plugin AlgorithmPlugin) {
    r.plugins[plugin.Name()] = plugin
}

func (r *PluginRegistry) GetPlugin(name string) (AlgorithmPlugin, bool) {
    plugin, exists := r.plugins[name]
    return plugin, exists
}

// 示例插件实现
type QuickSortPlugin struct{}

func (p *QuickSortPlugin) Name() string {
    return "quicksort"
}

func (p *QuickSortPlugin) Description() string {
    return "Implements the QuickSort algorithm from CLRS Chapter 7"
}

func (p *QuickSortPlugin) Execute(input interface{}) (interface{}, error) {
    arr, ok := input.([]int)
    if !ok {
        return nil, fmt.Errorf("input must be []int")
    }
    
    QuickSort(arr)
    return arr, nil
}

// 使用示例
func ExampleUsage() {
    registry := NewPluginRegistry()
    registry.Register(&QuickSortPlugin{})
    
    if plugin, exists := registry.GetPlugin("quicksort"); exists {
        result, err := plugin.Execute([]int{5, 2, 9, 1, 5, 6})
        if err != nil {
            fmt.Println("Error:", err)
            return
        }
        fmt.Println("Sorted array:", result)
    }
}

测试与验证

package algorithms_test

import (
    "testing"
    "github.com/yourusername/algorithms"
)

func TestQuickSort(t *testing.T) {
    arr := []int{5, 2, 9, 1, 5, 6}
    expected := []int{1, 2, 5, 5, 6, 9}
    
    algorithms.QuickSort(arr)
    
    for i := range arr {
        if arr[i] != expected[i] {
            t.Errorf("Expected %v, got %v", expected, arr)
            break
        }
    }
}

func TestBSTInsert(t *testing.T) {
    bst := algorithms.NewBST()
    keys := []int{5, 3, 7, 2, 4, 6, 8}
    
    for _, key := range keys {
        bst.Insert(key)
    }
    
    result := bst.InOrder()
    expected := []int{2, 3, 4, 5, 6, 7, 8}
    
    for i := range result {
        if result[i] != expected[i] {
            t.Errorf("Expected %v, got %v", expected, result)
            break
        }
    }
}

总结

这个Go实现的CLRS算法与数据结构库包含以下特点：

1. 实现了CLRS中的核心数据结构和算法
2. 采用模块化设计，便于扩展
3. 提供了插件接口，可以轻松添加新算法
4. 包含完整的测试用例

使用建议：

• 可以作为学习CLRS的实践项目
• 可以作为算法竞赛的参考实现
• 可以集成到需要算法功能的项目中

要扩展此库，只需实现新的AlgorithmPlugin接口并注册到PluginRegistry中即可。