Go语言开发(十四)、Go语言常用标准库四

栏目: Go · 发布时间: 5年前

内容简介:heap仅仅提供了最小堆的操作,没有提供堆的数据结构,堆的数据结构必须由开发者自己实现。heap提供了一个heap.Interface接口来作为堆的操作和堆的数据结构(开发者自己实现)之间的桥梁,堆的数据结构必须满足此接口:sort.Interface定义在sort.go中:IntHeap实现如下:

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}]

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CSS权威指南(第三版)

CSS权威指南(第三版)

[美] Eric A.Meyer / 侯妍、尹志忠 / 中国电力出版社 / 2007-10 / 58.00

你是否既想获得丰富复杂的网页样式,同时又想节省时间和精力?本书为你展示了如何遵循CSS最新规范(CSS2和CSS2.1)将层叠样式表的方方面面应用于实践。 通过本书提供的诸多示例,你将了解如何做到仅在一处建立样式表就能创建或修改整个网站的外观,以及如何得到HTML力不能及的更丰富的表现效果。 资深CSS专家Eric A.Meyer。利用他独有的睿智和丰富的经验对属性、标记、标记属性和实......一起来看看 《CSS权威指南(第三版)》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换