Golang-内置container包
-目录-
Go常见数据结构包container
Heap
container/heap
首先需要实现这这个接口（包含5个方法），heap实现并维护小顶堆（大根堆）或者说是优先队列。
type Interface interface {
sort.Interface
Push(x interface{}) // 向末尾添加元素
Pop() interface{} // 从末尾删除元素
}
//sort.Interface
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
简单例子
package main
import (
"container/heap"
"fmt"
)
type myHeap []int
func (m myHeap) Len() int {
return len(m)
}
func (m myHeap) Less(i, j int) bool {
return m[i] < m[j]
}
func (m myHeap) Swap(i, j int) {
m[i], m[j] = m[j], m[i]
}
//指针接收！
func (m *myHeap) Push(x interface{}) {
//heap包会自动对最后一个进行堆排序
*m = append(*m, x.(int))
}
func (m *myHeap) Pop() interface{} {
//heap包会自动对整个堆进行维护
x := (*m)[len(*m)-1]
*m = (*m)[:len(*m)-1]
return x
}
func main() {
h := &myHeap{2, 1, 5, 6, 3}
heap.Init(h)
heap.Push(h, 4)
total := h.Len()
for i := 0; i < total; i++ {
fmt.Println(heap.Pop(h))
}
}
//输出
//1
//2
//3
//4
//5
//6
List
container/list
实现了一个双向链表，内部原理是有头节点的双向链表但并不是环形链表，不过这个头节点（root）对使用方是透明的，任何只会在特意访问root时用到。使用时可完全忽略头节点。
功能有：
- 创建一个双向链表 New()
- 在某个节点前/后插入节点 InsertBrfore(v,node) InsertAfter(v,node)
- 在整个链表前/后插入节点 PushFront(v) PushBack(v)
- xxxxxxxxxx package mainimport “fmt"type Person struct { first string last string age int}type MyEInterface interface {}type MyIInterface1 interface { Func1()}type MyIInterface2 interface { Func1()}type MyIInterface3 interface { Func3()}func (p Person) Func1() {}func (p Person) Func3() {}func main() { var e MyEInterface var i1 MyIInterface1 = Person{“John”, “Doe”, 30} var i2 MyIInterface1 = Person{“John”, “Doe”, 32} var i3 MyIInterface2 = Person{“John”, “Doe”, 32} //var i4 MyIInterface3 = Person{“John”, “Doe”, 30} var x1 interface{} var x2 interface{} = []int{3, 5} var x3 interface{} = []int{3, 5} a := i1 == i2 //静态类型相同(interface包含方法都为空),动态类型不同 false b := x2 == x3 //静态类型相同(interface包含方法都为空),动态类型不能比较 panic c := e == x1 //静态类型相同(interface包含方法都为空),动态类型相同(包含数据都为空) true d := i2 == i3 //静态类型相同(interface包含方法完全一样),动态类型相同 true //f := i2 == i4 //静态类型不同,panic g := x1 == i1 //静态类型不同但是其中一个是空interface所以可以比较,动态类型可以比较 false h := e == i1 //同上 false fmt.Println(a, b, c, d, g, h)}go
- 在整个链表前/后插入另一个双向链表 PushFrontList() PushBackList()
- 获取第一个/最后一个元素，获取链表长度 Front() Back() Len()
- 移动元素到前/后/最前/最后 MoveBefore MoveAfter MoveToFront MoveToBack
简单例子
package main
import (
"container/list"
"fmt"
)
func main() {
loop := []int{1, 2, 3, 4, 5, 6, 7}、
//虚拟头节点
l := list.New()
for _, v := range loop {
l.PushBack(v)
}
for v := l.Front(); v != nil; v = v.Next() {
fmt.Print(v.Value)
}
fmt.Println()
for v := l.Back(); v != nil; v = v.Prev() {
fmt.Print(v.Value)
}
}
//输出
//1234567
//7654321
例子：链表反转
package main
import (
"container/list"
"fmt"
)
func main() {
//list reverse
l := list.New()
for i := 0; i < 5; i++ {
l.PushBack(i)
}
head := l.Front()
newHead := l.PushFront(0)
for head.Next() != nil {
l.InsertAfter(l.Remove(head.Next()), newHead)
newHead = newHead.Next()
}
for r := l.Front().Next(); r != nil; r = r.Next() {
fmt.Println(r.Value)
}
}
Ring
container/ring
实现了双向环形链表，创建时每个节点预置为nil，对每个节点进行相应操作
功能有：
- 创建一个n个节点的环形链表，内部值为nil New(n)
- 移动到下一个/上一个/指定步数 Next() Prev() Move(n)
- 删除n个节点 Unlink(n)
- 添加另一个节点（环形链表）Link
- 对所有节点进行操作，Do
简单例子
package main
import (
"container/ring"
"fmt"
)
func main() {
//解决约瑟夫环问题，数到3出列
r := ring.New(10)
for i := 0; i < r.Len(); i++ {
r.Value = i
r = r.Next()
}
for r.Len() != 1 {
r = r.Move(1)
fmt.Print(r.Next().Value)
r.Unlink(1)
r = r.Next()
}
fmt.Print(r.Value)
}
//输出
//2581607493