Go语言数据结构和算法

  • A+
所属分类:技术

chatGPT账号

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
}

免责声明

发文时比特币价格:$71249

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

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

免责声明:

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

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

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

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

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

本文是全系列中第21 / 309篇:行业技术

  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的电报
  • 这是我的电报扫一扫
  • weinxin
chatGPT账号
路远

发表评论

您必须登录才能发表评论!