Go语言开发(十四)、Go语言常用标准库四-创新互联
Go语言开发(十四)、Go语言常用标准库四
一、heap
1、heap简介
heap仅仅提供了最小堆的操作,没有提供堆的数据结构,堆的数据结构必须由开发者自己实现。heap提供了一个heap.Interface接口来作为堆的操作和堆的数据结构(开发者自己实现)之间的桥梁,堆的数据结构必须满足此接口:
罗湖ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!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]生成的就是大根堆
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]生成的就是大根堆
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}]
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前标题:Go语言开发(十四)、Go语言常用标准库四-创新互联
当前URL:http://myzitong.com/article/ccpscp.html