Go container包
container/list-双向链表-List
基本的数据结构
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element
// The list to which this element belongs.
list *List
// The value stored with this element.
Value interface{}
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}
双向链表是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
举例说明，
package main
import (
"container/list"
"fmt"
)
func print(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
func main() {
l := list.New()
l.PushBack(1) //尾插
l.PushBack(2)
print(l)
fmt.Println("=========")
l.PushFront(0) //头插
print(l)
fmt.Println("=========")
for e := l.Front(); e != nil; e = e.Next() {
if e.Value == 1 {
l.InsertAfter(1.1, e)
}
if e.Value == 2 {
l.InsertBefore(1.2, e)
}
}
print(l)
fmt.Println("=========")
fmt.Println(l.Front().Value) //返回链表的第一个元素
fmt.Println("=========")
fmt.Println(l.Back().Value) //返回链表的最后一个元素
fmt.Println("=========")
l.MoveToBack(l.Front())
print(l)
fmt.Println("=========")
for e := l.Back(); e != nil; e = e.Prev() {
fmt.Println(e.Value)
}
}
container/heap-堆-Heap
堆数据结构具体请看：
https://my.oschina.net/xinxingegeya/blog/703801
https://my.oschina.net/xinxingegeya/blog/705409
在Golang中，定义了一组方法来描述堆的操作。如下接口描述，
// Any type that implements heap.Interface may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
// !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
heap.Interface 组合了 sort.Interface 接口，
// 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)
}也就是说只要一个类型实现了这五个方法，便定义了一个堆。如下所示，
package main
import (
"container/heap"
"fmt"
)
type Student struct {
name string
score int
}
type StudentHeap []Student
func (h StudentHeap) Len() int { return len(h) }
func (h StudentHeap) Less(i, j int) bool {
return h[i].score < h[j].score //最小堆
//return stu[i].score > stu[j].score //最大堆
}
func (h StudentHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *StudentHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(Student))
}
func (h *StudentHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0: n-1]
return x
}
func main() {
h := &StudentHeap{
{name: "xiaoming", score: 82},
{name: "xiaozhang", score: 88},
{name: "laowang", score: 85}}
// 初始化一个堆。一个堆在使用任何堆操作之前应先初始化。
// Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。
// 本函数复杂度为O(n)，其中n等于h.Len()。
heap.Init(h)
//向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
heap.Push(h, Student{name: "xiaoli", score: 66})
for _, ele := range *h {
fmt.Printf("student name %s,score %d\n", ele.name, ele.score)
}
for i, ele := range *h {
if ele.name == "xiaozhang" {
(*h)[i].score = 60
// 在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。
// 复杂度O(log(n))，其中n等于h.Len()。
heap.Fix(h, i)
}
}
fmt.Println("==========")
for _, ele := range *h {
fmt.Printf("student name %s,score %d\n", ele.name, ele.score)
}
fmt.Println("==========")
for h.Len() > 0 {
// 删除并返回堆h中的最小元素（取决于Less函数，最大堆或最小堆）（不影响堆de约束性）
// 复杂度O(log(n))，其中n等于h.Len()。该函数等价于Remove(h, 0)
item := heap.Pop(h).(Student)
fmt.Printf("student name %s,score %d\n", item.name, item.score)
}
}
打印结果，
student name xiaoli,score 66
student name xiaoming,score 82
student name laowang,score 85
student name xiaozhang,score 88
==========
student name xiaozhang,score 60
student name xiaoli,score 66
student name laowang,score 85
student name xiaoming,score 82
==========
student name xiaozhang,score 60
student name xiaoli,score 66
student name xiaoming,score 82
student name laowang,score 85
Process finished with exit code 0
container/ring-环-Ring
Ring的数据结构，
// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
next, prev *Ring
Value interface{} // for use by client; untouched by this library
}像是双向循环链表，双向链表和双向循环链表的结构示意图，
如下代码示例，
package main
import (
"container/ring"
"fmt"
)
func main() {
ring1 := ring.New(3)
for i := 1; i <= 3; i++ {
ring1.Value = i
ring1 = ring1.Next()
}
ring2 := ring.New(3)
for i := 4; i <= 6; i++ {
ring2.Value = i
ring2 = ring2.Next()
}
r := ring1.Link(ring2)
fmt.Printf("ring length = %d\n", r.Len())
r.Do(func(p interface{}) {
fmt.Print(p.(int))
fmt.Print(",")
})
fmt.Println()
fmt.Printf("current ring is %v\n", r.Value)
fmt.Printf("next ring is %v\n", r.Next().Value)
fmt.Printf("prev ring is %v\n", r.Prev().Value)
// ring 的遍历
for p := r.Next(); p != r; p = p.Next() {
fmt.Print(p.Value.(int))
fmt.Print(",")
}
}
=======END=======
有疑问加站长微信联系（非本文作者）
