Go标准库 - Go包——container - 《够浪》

list
- 常用方法
ring
- 常用方法
heap
- Push
- Pop
参考

源码地址https://github.com/golang/go/tree/master/src/container

list

链表就是一个有 prev 和 next 指针的数组了

type Element struct {
    next, prev *Element  // 上一个和下一个元素
    list *List  // 元素所在的链表
    Value interface{}  // 元素
}
type List struct {
    root Element  // 链表的根节点
    len  int      // 链表的长度
}

常用方法

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element   // 最后一个元素
    func (l *List) Front() *Element  // 第一个元素
    func (l *List) Init() *List  // 链表初始化
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某个元素前插入
    func (l *List) Len() int // 在链表长度
    func (l *List) MoveAfter(e, mark *Element)  // 把 e 元素移动到 mark 之后
    func (l *List) MoveBefore(e, mark *Element)  // 把 e 元素移动到 mark 之前
    func (l *List) MoveToBack(e *Element) // 把 e 元素移动到队列最后
    func (l *List) MoveToFront(e *Element) // 把 e 元素移动到队列最头部
    func (l *List) PushBack(v interface{}) *Element  // 在队列最后插入元素
    func (l *List) PushBackList(other *List)  // 在队列最后插入接上新队列
    func (l *List) PushFront(v interface{}) *Element  // 在队列头部插入元素
    func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
    func (l *List) Remove(e *Element) interface{} // 删除某个元素

eg:

package main
import (
    "container/list"
    "fmt"
)
func main() {
    l := list.New()
    for i:=1;i<5;i++{
        l.PushBack(i)
    }
    fmt.Println(l.Front().Value)//输出首部元素的值
    fmt.Println(l.Back().Value)//输出尾部元素的值
    // 遍历链表
    for e :=l.Front();e!=nil;e =e.Next(){
        fmt.Print(e.Value)
    }
    fmt.Println("")
    l.InsertBefore(0, l.Front())  //首部元素之前插入0
    l.MoveToBack(l.Front()) //将0元素移动到末尾
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value)
    }
    fmt.Println("")
    l2 := list.New()
    l2.PushBackList(l) //将l中元素放在l2的末尾
    l2.MoveToFront(l2.Back()) // 将末尾元素移到首部
    for e := l2.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value)
    }
    fmt.Println("")
    l.Init() //清空l
    fmt.Println(l.Len()) //0
}

程序执行结果

ring

环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。它不需要像 list 一样保持 list 和 element 两个结构，只需要保持一个结构就行

type Ring struct {
    next, prev *Ring
    Value      interface{}
}

常用方法

    func New(n int) *Ring  // 初始化环
    func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
    func (r *Ring) Len() int // 环长度
    func (r *Ring) Link(s *Ring) *Ring // 连接两个环
    func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前（n 可以为负数）
    func (r *Ring) Next() *Ring // 当前元素的下个元素
    func (r *Ring) Prev() *Ring // 当前元素的上个元素
    func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除 n 个元素

heap

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

package sort
// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

堆结构继承自 sort.Interface, 回顾下 sort.Interface，它需要实现三个方法

Len() int
Less(i, j int) bool
Swap(i, j int)

加上堆接口定义的两个方法

Push(x interface{})
Pop() interface{}

Push

push方法，其官方注释要求实现的功能写的很简单，事实上也确实很简单。
将x添加在数组最后即可，所以实现代码如下：

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

你可能会疑惑，如果只是实现这样得Push函数，并没有保证堆的性质啊，你只是把这个数放到了数组最后。实际上这是官方为了避免我们写太多代码而做的设计，我们在push时实际上是调用heap.Push(h, 3) ,这是在heap.go中的一个函数，其具体实现为：

func Push(h Interface, x interface{}) {
    h.Push(x)
    up(h, h.Len()-1)
}
func up(h Interface, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}

Pop

func Pop(h Interface) interface{} {
    n := h.Len() - 1
    h.Swap(0, n)
    down(h, 0, n)
    return h.Pop()
}
func down(h Interface, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2  // right child
        }
        if !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        i = j
    }
    return i > i0
}

eg:

package main
import (
    "container/heap"
    "fmt"
)
type myHeap []int
func(h myHeap)Len()int{
    return len(h)
}
func(h myHeap)Swap(i,j int){
    h[i],h[j] = h[j],h[i]
}
func(h myHeap)Less(i,j int)bool{
    return h[i]>h[j]
}
func(h *myHeap)Push(v interface{}){
    *h = append(*h,v.(int))
}
func(h *myHeap)Pop()(v interface{}){
    *h,v =(*h)[:len(*h)-1],(*h)[len(*h)-1]
    return
}
// 按层来遍历和打印堆数据，第一行只有一个元素，即堆顶元素
func (h myHeap) printHeap() {
    n := 1
    levelCount := 1
    for n <= h.Len() {
        fmt.Println(h[n-1 : n-1+levelCount])
        n += levelCount
        levelCount *= 2
    }
}
// 大顶堆小堆的结果主要swap
func main() {
    list :=[7]int{13,12,45,24,11,9,20}
    hq := make(myHeap,0)
    for i :=range list{
        hq.Push(list[i])
    }
    heap.Init(&hq)
    hq.printHeap()
}

打印结果

[45]
[24 20]
[12 11 9 13]

参考

https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.3.html
https://blog.csdn.net/weixin_40631132/article/details/105208272