container ring heap list

container 容器

包含heap list ring

container/heap

堆操作。堆是具有属性的树,每个节点是其子树中的最小值节点。

import "container/heap"

方法

//Init函数用于堆初始化,接受一个实现了heap.Interface的对象,并初始化为一个堆,所有的堆在使用之前都需要进行初始化
func Init(h Interface) 

//Fix函数用于单次对堆进行调整,接收一个堆对象以及一个位置参数i
func Fix(h Interface, i int)

//Push和Pop是一对标准堆操作,Push向堆添加一个新元素,Pop弹出并返回堆顶元素,而在push和pop操作不会破坏堆的结构;
func Pop(h Interface) interface{}
func Pop(h Interface) interface{}

//Remove函数用于删除堆上特定位置的元素,这个位置是指元素在堆上的排序
func Remove(h Interface, i int) interface{}

实例

package main

import (
     "fmt"
     "container/heap"
)

func main() {
     hp := &[]RecHeap{}
     for i := 2; i <= 5; i++ {
          *hp = append(*hp, Rectangle{i, i})
          // {2, 2}, {3, 3}, {4, 4}, {5, 5}
     }
     heap.Init(hp)                         // 初始化
     heap.Push(hp, Rectangle{1, 1})
     fmt.Printf("minimum: %d\n", (*hp)[0]) // Rectangle{1, 1}
     res := heap.Pop(hp)
     fmt.Printf("minimum: %d\n", (*hp)[0]) // Rectangle{2, 2}
}

container/list

import "container/list"

方法

//延迟初始化
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}
//返回list头节点元素
func (l *List) Front() *Element {}
//返回list尾节点元素
func (l *List) Back() *Element {}
//将一个值为v的新元素插入链表的第一个位置,返回生成的新元素
func (l *List) PushFront(v interface{}) *Element {}                   
//创建链表other的拷贝,并将拷贝的最后一个位置连接到list的第一个位置
func (l *List) PushFrontList(other *List) {}
//将一个值为v的新元素插入链表的最后一个位置,返回生成的新元素                     
func (l *List) PushBack(v interface{}) *Element {}
//创建链表other的拷贝,并将拷贝的第一个位置连接到list的最后一个位置
func (l *List) PushBackList(other *List) {}
//将一个值为v的新元素插入到mark前面,并返回生成的新元素。如果mark不是l的元素,l不会被修改
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {}
//将一个值为v的新元素插入到mark后面,并返回新生成的元素。如果mark不是l的元素,l不会被修改
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {}
//将元素e移动到链表的第一个位置,如果e不是l的元素,l不会被修改
func (l *List) MoveToFront(e *Element) {}
//将元素e移动到链表的最后一个位置,如果e不是l的元素,l不会被修改
func (l *List) MoveToBack(e *Element) {}
//将元素e移动到mark的前面。如果e或mark不是l的元素,或者e==mark,l不会被修改
func (l *List) MoveBefore(e, mark *Element) {}
//将元素e移动到mark的后面。如果e或mark不是l的元素,或者e==mark,l不会被修改
func (l *List) MoveAfter(e, mark *Element) {}
//删除链表中的元素e,并返回e.Value
func (l *List) Remove(e *Element) interface{} {}

实例

package main
 
import (
	"container/list"
	"fmt"
)
 
func main() {
	l := list.New()
	l.PushFront(1)                // 1
	l.PushBack(2)                 // 1->2
	fmt.Println(l.Front().Value)  // 1
	fmt.Println(l.Back().Value)   // 2
	other := list.New()
	other.PushFront(3)
	other.PushBack(4)
	l.PushFrontList(other)        // 3->4->1->2
	fmt.Println(l.Front().Value)
	fmt.Println(l.Back().Value)
	fmt.Println(l.Len())
	l.Remove(l.Front().Next())    // 3->1->2
	fmt.Println(l.Len())
	for v := l.Front(); v != nil; v = v.Next() {
		fmt.Printf("%d ", v.Value)
	}
	fmt.Printf("\n")
}

container/ring

import "container/ring"

方法

// Ring表示环形链表中的元素。
type Ring struct {
    Value interface{} // Value类型为interface{},因此可以接受任意类型
}

// 创建一个长度为n的环形链表
func New(n int) *Ring
// 针对环形链表中的每一个元素x进行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 获取环形链表长度
func (r *Ring) Len() int
// 如果r和s在同一环形链表中,则删除r和s之间的元素,
// 被删除的元素组成一个新的环形链表,返回值为该环形链表的指针(即删除前,r->Next()表示的元素)
// 如果r和s不在同一个环形链表中,则将s插入到r后面,返回值为
// 插入s后,s最后一个元素的下一个元素(即插入前,r->Next()表示的元素)
func (r *Ring) Link(s *Ring) *Ring
// 移动 n % r.Len() 个位置,n正负均可
func (r *Ring) Move(n int) *Ring
// 返回下一个元素
func (r *Ring) Next() *Ring
// 返回前一个元素
func (r *Ring) Prev() *Ring
// 删除r后面的 n % r.Len() 个元素
func (r *Ring) Unlink(n int) *Ring

实例

遍历
func main() {
	r := ring.New(5) // 创建长度为5的环形链表
	// 遍历链表赋值,环形链表的遍历比较特殊
	for i, now := 0, r.Next(); i < r.Len(); now, i = now.Next(), i+1 {
		now.Value = i
	}
	// 遍历链表的值
	for i, now := 0, r.Next(); i < r.Len(); now, i = now.Next(), i+1 {
		log.Printf("%v = %v", i, now.Value)
	}
}
package main

import (
    "container/ring"
    "fmt"
)

type SumInt struct {
    Value int
}

func (s *SumInt) add(i interface{}) {
    s.Value += i.(int)
}

func main() {
    r := ring.New(10)

    for i := 0; i < 10; i++ {
        r.Value = i
        r = r.Next()
    }

    sum := SumInt{}
    r.Do(sum.add)
    fmt.Println(sum.Value)
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×