Go container包

原创
2017/03/05 18:56
阅读数 230

Go container包

container/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-堆

堆数据结构具体请看:

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的数据结构,

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

展开阅读全文
Go
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部