Go语言数据结构和算法

发表评论
58,454 views

A+

所属分类：技术

图和节点

概念介绍

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

示例代码

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
}

免责声明

发文时比特币价格：$71249

当前比特币价格：[crypto coins=”BTC” type=”text” show=”price”]

当前比特币涨幅：[crypto coins=”BTC” type=”text” show=”percent”]

免责声明：

本文不代表路远网立场，且不构成投资建议，请谨慎对待。用户由此造成的损失由用户自行承担，与路远网没有任何关系；

路远网不对网站所发布内容的准确性，真实性等任何方面做任何形式的承诺和保障；

网站内所有涉及到的区块链（衍生）项目，路远网对项目的真实性，准确性等任何方面均不做任何形式的承诺和保障；

网站内所有涉及到的区块链（衍生）项目，路远网不对其构成任何投资建议，用户由此造成的损失由用户自行承担，与路远网没有任何关系；

路远区块链研究院声明：路远区块链研究院内容由路远网发布，部分来源于互联网和行业分析师投稿收录，内容为路远区块链研究院加盟专职分析师独立观点，不代表路远网立场。