Go 语言开发(十四),Go 语言常用标准库四
一, heap
1,heap 简介
heap 仅仅提供了最小堆的操作, 没有提供堆的数据结构, 堆的数据结构必须由开发者自己实现. heap 提供了一个 heap.Interface 接口来作为堆的操作和堆的数据结构 (开发者自己实现) 之间的桥梁, 堆的数据结构必须满足此接口:
- type Interface interface {
- sort.Interface
- Push(x interface{
- }) // add x as element Len()
- Pop() interface{
- } // remove and return element Len() - 1.
- }
sort.Interface 定义在 sort.go 中:
- 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)
- }
因此, 开发者自己实现的堆必须要定义 5 个方法才能与 heap 协作使用.
func Fix(h Interface, i int)
当索引 i 的元素的值改变时, 重建堆数据结构
func Init(h Interface)
初始化堆, 在调用其它堆操作函数前应调用 Init 函数完成堆数据结构初始化
func Pop(h Interface) interface{}
弹出堆中的最小元素, 返回弹出的元素
func Push(h Interface, x interface{})
添加元素到堆
func Remove(h Interface, i int) interface{}
移除索引为 i 的元素, 返回被移除的元素
2,heap 示例
IntHeap 实现如下:
- package IntHeap
- type IntHeap []int
- func (h IntHeap) Len() int {
- return len(h)
- }
- func (h IntHeap) Less(i, j int) bool {
- // 如果 h[i]<h[j]生成的就是小根堆, 如果 h[i]>h[j]生成的就是大根堆
- return h[i] <h[j]
- }
- func (h IntHeap) Swap(i, j int) {
- h[i], h[j] = h[j], h[i]
- }
- func (h *IntHeap) Pop() interface{
- } {
- old := *h
- n := len(old)
- x := old[n-1]
- *h = old[0 : n-1]
- return x
- }
- func (h *IntHeap) Push(x interface{
- }) {
- *h = append(*h, x.(int))
- }
IntHeap 使用:
- package main
- import (
- "GoExample/Heap/IntHeap"
- "container/heap"
- "fmt"
- )
- func main() {
- h := &IntHeap.IntHeap{
- 0, 8, 2, 3, 4, 1, 6, 7, 5
- }
- heap.Init(h)
- fmt.Println(*h) //[0 3 1 5 4 2 6 7 8]
- fmt.Println(heap.Pop(h)) //0
- heap.Push(h, 6)
- fmt.Println(*h) // [1 3 2 5 4 8 6 7 6]
- for len(*h)> 0 {
- fmt.Printf("%d", heap.Pop(h))
- }
- // 1 2 3 4 5 6 6 7 8
- }
3,heap 实现机制
heap 内部使用最小 (最大) 堆, 索引排序从根节点开始, 然后左子树, 右子树的顺序方式. 内部实现的 down 和 up 分别表示对堆中的某个元素向下保证最小 (最大) 堆和向上保证最小 (最大) 堆.
当向堆中压入一个元素的时候, 元素压入到最右子树的最后一个节点中, 然后调用 up 向上保证最小 (最大) 堆.
当从堆中弹出一个元素的时候, 先把元素和右子树最后一个节点交换, 然后弹出最后一个节点, 然后对 root 调用 down, 向下保证最小 (最大) 堆.
生成最小堆还是最大堆由 Less 方法决.
- func (h IntHeap) Less(i, j int) bool {
- // 如果 h[i]<h[j]生成的就是小根堆, 如果 h[i]>h[j]生成的就是大根堆
- return h[i] <h[j]
- }
二, list
1,list 简介
list 实现了一个双向链表, 链表及链表节点的数据结构如下:
- type Element struct {
- next, prev *Element
- list *List
- Value interface{
- }
- }
- 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
- }
Element 定义了两个 Element 类型的指针 next,prev 以及 List 类型的指针 list,Value 用来存储值, List 定义了一个 Element 作为链表的 Root,len 作为链表的长度.
list 提供的方法如下:
- func (e *Element) Next() *Element
- func (e *Element) Prev() *Element
- func New() *List
- func (l *List) Back() *Element // 返回最后一个元素
- func (l *List) Front() *Element // 返回第一个元素
- func (l *List) Init() *List // 链表初始化
- func (l *List) InsertAfter(v interface{
- }, mark *Element) *Element // 在某个元素前插入
- func (l *List) InsertBefore(v interface{
- }, mark *Element) *Element // 在某个元素后插入
- func (l *List) Len() int // 返回链表长度
- func (l *List) MoveAfter(e, mark *Element) // 把 e 元素移动到 mark 之后
- func (l *List) MoveBefore(e, mark *Element) // 把 e 元素移动到 mark 之前
- func (l *List) MoveToBack(e *Element) // 把 e 元素移动到队列最后
- func (l *List) MoveToFront(e *Element) // 把 e 元素移动到队列最头部
- func (l *List) PushBack(v interface{
- }) *Element // 在队列最后插入元素
- func (l *List) PushBackList(other *List) // 在队列最后插入接上新队列
- func (l *List) PushFront(v interface{
- }) *Element // 在队列头部插入元素
- func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
- func (l *List) Remove(e *Element) interface{
- } // 删除某个元素
2,list 使用示例
- package main
- import (
- "container/list"
- "fmt"
- )
- func main() {
- l := list.New()
- l.PushBack(123)
- l.PushBack("456")
- l.PushBack(false)
- fmt.Println(l.Len()) // 3
- fmt.Println(l.Front().Value) // 123
- fmt.Println(l.Front().Next().Value) // 456
- fmt.Println(l.Front().Next().Next().Value) // false
- fmt.Println(l.Back().Value) // false
- fmt.Println(l.Back().Prev().Value) // 456
- }
三, ring
1,ring 简介
ring 包提供了环形链表的操作, ring 导出 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
2,ring 使用示例
Josephus 问题如下: 在罗马人占领乔塔帕特后, 39 个犹太人与 Josephus 及他的朋友躲到一个洞中, 39 个犹太人决定宁愿死也不要被敌人抓到, 于是决定了一个自杀方式, 41 个人排成一个圆圈, 由第 1 个人开始报数, 每报数到第 3 人该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止. 然而 Josephus 和他的朋友并不想遵从. 首先从一个人开始, 越过 k-2 个人(因为第一个人已经被越过), 并杀掉第 k 个人. 接着, 再越过 k-1 个人, 并杀掉第 k 个人. 这个过程沿着圆圈一直进行, 直到最终只剩下一个人留下, 这个人就可以继续活着. 问题是, 给定了和, 一开始要站在什么地方才能避免被处决? Josephus 要他的朋友先假装遵从, 他将朋友与自己安排在第 16 个与第 31 个位置, 于是逃过了这场死亡游戏.
Josephus 问题使用 ring 的解决方案如下:
- package main
- import (
- "container/ring"
- "fmt"
- )
- const (
- playerCount = 41 // 玩家人数
- startPos = 1 // 开始报数位置
- deadline = 3 // 第 n 个人自杀
- aliveCount = 2 // 幸存人数
- )
- type Player struct {
- position int // 位置
- alive bool // 是否存活
- }
- var players = ring.New(playerCount)
- func Play(playerList *ring.Ring) {
- // 设置所有玩家初始值
- for i := 1; i <= playerCount; i++ {
- playerList.Value = &Player{
- i, true
- }
- playerList = playerList.Next()
- }
- // 如果开始报数的位置不为 1, 则设置开始位置
- if startPos> 1 {
- playerList = playerList.Move(startPos - 1)
- }
- counter := 1 // 报数从 1 开始
- deadCount := 0 // 死亡人数, 初始值为 0
- for deadCount < playerCount-aliveCount {
- playerList = playerList.Next() // 跳到下一个人
- // 如果是活着的人, 则报数
- if playerList.Value.(*Player).alive {
- counter++
- }
- // 如果报数为 deadline, 则此人淘汰出局
- if counter == deadline {
- playerList.Value.(*Player).alive = false
- fmt.Printf("Player %d died!\n", playerList.Value.(*Player).position)
- deadCount++
- counter = 0 // 报数置成 0
- }
- }
- }
- func main() {
- Play(players)
- players.Move(startPos)
- for i := 1; i < playerCount; i++ {
- if players.Value.(*Player).alive {
- fmt.Println("alive:", players.Value.(*Player).position)
- }
- players = players.Next()
- }
- }
四, sort
1,sort 简介
sort 包中实现了四种基本排序算法: 插入排序, 归并排序, 堆排序和快速排序, 但只被用于 sort 包内部使用. 在对数据集合排序时不必考虑应当选择哪一种排序方法, 只要实现了 sort.Interface 定义的三个方法: 获取数据集合长度的 Len()方法, 比较两个元素大小的 Less()方法和交换两个元素位置的 Swap()方法, 就可以顺利对数据集合进行排序. sort 包会根据实际数据自动选择高效的排序算法. 为了方便对常用数据类型的操作, sort 包提供了对[]int 切片,[]float64 切片和[]string 切片完整支持, 主要包括:
(1)对基本数据类型切片的排序支持.
(2)基本数据元素查找.
(3)判断基本数据类型切片是否已经排好序.
(4)对排好序的数据集合逆序.
对数据集合 (包括自定义数据类型的集合) 排序需要实现 sort.Interface 接口的三个方法:
- type Interface interface {
- // 返回要排序的数据长度
- Len() int
- // 比较下标为 i 和 j 对应的数据大小, 可自己控制升序和降序
- Less(i, j int) bool
- // 交换下标为 i,j 对应的数据
- Swap(i, j int)
- }
任何实现了 sort.Interface 的类型(一般为集合), 均可使用 sort 包中的方法进行排序, sort.Interface 接口的方法要求集合内列出元素的索引为整数.
2,sort 使用示例
- package main
- import (
- "fmt"
- "sort"
- )
- type Person struct {
- Name string
- Age int
- }
- type PersonArray []Person
- func (a PersonArray) Len() int {
- return len(a)
- }
- func (a PersonArray) Swap(i, j int) {
- a[i], a[j] = a[j], a[i]
- }
- func (a PersonArray) Less(i, j int) bool {
- return a[i].Age < a[j].Age
- }
- func main() {
- peoples := []Person{
- {
- "Bob", 31
- },
- {
- "John", 42
- },
- {
- "Michael", 17
- },
- {
- "Bauer", 26
- },
- }
- fmt.Println(peoples)
- sort.Sort(PersonArray(peoples))
- fmt.Println(peoples)
- }
- // output:
- // [{
- Bob 31
- } {
- John 42
- } {
- Michael 17
- } {
- Bauer 26
- }]
- // [{
- Michael 17
- } {
- Bauer 26
- } {
- Bob 31
- } {
- John 42
- }]
来源: http://blog.51cto.com/9291927/2343535