go版本：go1.12 windows/amd64
container目录结构如下：
├─heap
├─heap.go
├─heap_test.go
├─example_intheap_test.g
└─example_pq_test.go
├─list
├─list.go
├─list_test.go
├─example_test.go
└─ring
├─ring.go
├─ring_test.go
└─example_test.go
1. ring包介绍
环形链表的数据结构时一个环形list的元素或者圆环；
一个圆环链表是一个圆形list或者圆的元素，没有开始和结束,指向圆环中任一元素的指针作用于整个环的引用；
空环代表一个nil的指针，零环则表示环内有一个nil元素；
type Ring struct {
next, prev *Ring
Value interface{} // for use by client; untouched by this library
}
ring中的方法：
func Next() *Ring // 返回圆环的下一个元素，圆环必须不为空
func Prev() *Ring // 返回这个圆环的上一个元素
func Move(n int) *Ring // 当n<0时，向反向位移，n>0时，正向位移
func New(n int) *Ring // 新创建n个集合的圆环，每个集合的值为
func Len() int // 统计 圆环长度，Ring不为nil时长度默认为1
func Link(s *Ring) // Link连接r和s，并返回r原本的后继元素r.Next()。r不能为空。 如果r和s指向同一个环形链表，则会删除掉r和s之间的元素，删掉的元素构成一个子链表，返回指向该子链表的指针（r的原后继元素）；如果没有删除元素，则仍然返回r的原后继元素，而不是nil。如果r和s指向不同的链表，将创建一个单独的链表，将s指向的链表插入r后面，返回s原最后一个元素后面的元素（即r的原后继元素）。
func Unlink(n int) // 删除链表中n % r.Len()个元素，从r.Next()开始删除。如果n % r.Len() == 0，不修改r。返回删除的元素构成的链表，r不能为空。
func (r *Ring) Do(f func(interface{})) // 遍历环中所有元素执行f操作，如果f改变了r，则该操作造成的后果是不可预期的。
重点讲解Link跟Unlink方法：
// Link connects ring r with ring s such that r.Next()
// becomes s and returns the original value for r.Next().
// r must not be empty.
//
// If r and s point to the same ring, linking
// them removes the elements between r and s from the ring.
// The removed elements form a subring and the result is a
// reference to that subring (if no elements were removed,
// the result is still the original value for r.Next(),
// and not nil).
//
// If r and s point to different rings, linking
// them creates a single ring with the elements of s inserted
// after r. The result points to the element following the
// last element of s after insertion.
//
func (r *Ring) Link(s *Ring) *Ring {
n := r.Next()
if s != nil { //相当于把环r与s的头、尾相连
p := s.Prev()
// Note: Cannot use multiple assignment because
// evaluation order of LHS is not specified.
r.next = s
s.prev = r
n.prev = p
p.next = n
}
return n
}
// Unlink removes n % r.Len() elements from the ring r, starting
// at r.Next(). If n % r.Len() == 0, r remains unchanged.
// The result is the removed subring. r must not be empty.
//
func (r *Ring) Unlink(n int) *Ring {
if n <= 0 {
return nil
}
return r.Link(r.Move(n + 1))
}
// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
// in the ring and returns that ring element. r must not be empty.
//
func (r *Ring) Move(n int) *Ring {
if r.next == nil {
return r.init()
}
switch {
case n < 0:
for ; n < 0; n++ {
r = r.prev
}
case n > 0:
for ; n > 0; n-- {
r = r.next
}
}
return r
}
2. 示例
package ring_test
import (
"container/ring"
"fmt"
)
func ExampleRing_Len() {
// Create a new ring of size 4
r := ring.New(4)
// Print out its length
fmt.Println(r.Len())
// Output:
// 4
}
func ExampleRing_Next() {
// Create a new ring of size 5
r := ring.New(5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring and print its contents
for j := 0; j < n; j++ {
fmt.Println(r.Value)
r = r.Next()
}
// Output:
// 0
// 1
// 2
// 3
// 4
}
func ExampleRing_Prev() {
// Create a new ring of size 5
r := ring.New(5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring backwards and print its contents
for j := 0; j < n; j++ {
r = r.Prev()
fmt.Println(r.Value)
}
// Output:
// 4
// 3
// 2
// 1
// 0
}
func ExampleRing_Do() {
// Create a new ring of size 5
r := ring.New(5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring and print its contents
r.Do(func(p interface{}) {
fmt.Println(p.(int))
})
// Output:
// 0
// 1
// 2
// 3
// 4
}
func ExampleRing_Move() {
// Create a new ring of size 5
r := ring.New(5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Move the pointer forward by three steps
r = r.Move(3)
// Iterate through the ring and print its contents
r.Do(func(p interface{}) {
fmt.Println(p.(int))
})
// Output:
// 3
// 4
// 0
// 1
// 2
}
func ExampleRing_Link() {
// Create two rings, r and s, of size 2
r := ring.New(2)
s := ring.New(2)
// Get the length of the ring
lr := r.Len()
ls := s.Len()
// Initialize r with 0s
for i := 0; i < lr; i++ {
r.Value = 0
r = r.Next()
}
// Initialize s with 1s
for j := 0; j < ls; j++ {
s.Value = 1
s = s.Next()
}
// Link ring r and ring s
rs := r.Link(s)
// Iterate through the combined ring and print its contents
rs.Do(func(p interface{}) {
fmt.Println(p.(int))
})
// Output:
// 0
// 0
// 1
// 1
}
func ExampleRing_Unlink() {
// Create a new ring of size 6
r := ring.New(6)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Unlink three elements from r, starting from r.Next()
r.Unlink(3)
// Iterate through the remaining ring and print its contents
r.Do(func(p interface{}) {
fmt.Println(p.(int))
})
// Output:
// 0
// 4
// 5
}
网友评论