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=======

本文来自:开源中国博客

感谢作者:xxggy

查看原文:Go container包

• 编辑
• 预览