Go語(yǔ)言開(kāi)發(fā)（十四）、Go語(yǔ)言常用標(biāo)準(zhǔn)庫(kù)四

一、heap

1、heap簡(jiǎn)介

heap僅僅提供了最小堆的操作，沒(méi)有提供堆的數(shù)據(jù)結(jié)構(gòu)，堆的數(shù)據(jù)結(jié)構(gòu)必須由開(kāi)發(fā)者自己實(shí)現(xiàn)。heap提供了一個(gè)heap.Interface接口來(lái)作為堆的操作和堆的數(shù)據(jù)結(jié)構(gòu)（開(kāi)發(fā)者自己實(shí)現(xiàn)）之間的橋梁，堆的數(shù)據(jù)結(jié)構(gòu)必須滿足此接口：

羅湖ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書(shū)未來(lái)市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書(shū)銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書(shū)合作）期待與您的合作！

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

因此，開(kāi)發(fā)者自己實(shí)現(xiàn)的堆必須要定義5個(gè)方法才能與heap協(xié)作使用。
func Fix(h Interface, i int)
當(dāng)索引i的元素的值改變時(shí)，重建堆數(shù)據(jù)結(jié)構(gòu)
func Init(h Interface)
初始化堆，在調(diào)用其它堆操作函數(shù)前應(yīng)調(diào)用Init函數(shù)完成堆數(shù)據(jù)結(jié)構(gòu)初始化
func Pop(h Interface) interface{}
彈出堆中的最小元素，返回彈出的元素
func Push(h Interface, x interface{})
添加元素到堆
func Remove(h Interface, i int) interface{}
移除索引為i的元素，返回被移除的元素

2、heap示例

IntHeap實(shí)現(xiàn)如下：

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實(shí)現(xiàn)機(jī)制

heap內(nèi)部使用最小(大)堆，索引排序從根節(jié)點(diǎn)開(kāi)始，然后左子樹(shù)，右子樹(shù)的順序方式。內(nèi)部實(shí)現(xiàn)的down和up分別表示對(duì)堆中的某個(gè)元素向下保證最小(大)堆和向上保證最小(大)堆。
當(dāng)向堆中壓入一個(gè)元素的時(shí)候，元素壓入到最右子樹(shù)的最后一個(gè)節(jié)點(diǎn)中，然后調(diào)用up向上保證最小(大)堆。
當(dāng)從堆中彈出一個(gè)元素的時(shí)候，先把元素和右子樹(shù)最后一個(gè)節(jié)點(diǎn)交換，然后彈出最后一個(gè)節(jié)點(diǎn)，然后對(duì)root調(diào)用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簡(jiǎn)介

list實(shí)現(xiàn)了一個(gè)雙向鏈表，鏈表及鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

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定義了兩個(gè)Element類型的指針next，prev以及List類型的指針list，Value用來(lái)存儲(chǔ)值，List定義了一個(gè)Element作為鏈表的Root，len作為鏈表的長(zhǎng)度。
list提供的方法如下：

func (e *Element) Next() *Element
func (e *Element) Prev() *Element
func New() *List
func (l *List) Back() *Element                                     // 返回最后一個(gè)元素
func (l *List) Front() *Element                                    // 返回第一個(gè)元素
func (l *List) Init() *List                                        // 鏈表初始化
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  // 在某個(gè)元素前插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某個(gè)元素后插入
func (l *List) Len() int                                           // 返回鏈表長(zhǎng)度
func (l *List) MoveAfter(e, mark *Element)                         // 把e元素移動(dòng)到mark之后
func (l *List) MoveBefore(e, mark *Element)                        // 把e元素移動(dòng)到mark之前
func (l *List) MoveToBack(e *Element)                              // 把e元素移動(dòng)到隊(duì)列最后
func (l *List) MoveToFront(e *Element)                             // 把e元素移動(dòng)到隊(duì)列最頭部
func (l *List) PushBack(v interface{}) *Element                    // 在隊(duì)列最后插入元素
func (l *List) PushBackList(other *List)                           // 在隊(duì)列最后插入接上新隊(duì)列
func (l *List) PushFront(v interface{}) *Element                   // 在隊(duì)列頭部插入元素
func (l *List) PushFrontList(other *List)                          // 在隊(duì)列頭部插入接上新隊(duì)列
func (l *List) Remove(e *Element) interface{}                      // 刪除某個(gè)元素

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簡(jiǎn)介

ring包提供了環(huán)形鏈表的操作，ring導(dǎo)出Ring類型，數(shù)據(jù)結(jié)構(gòu)如下：

// Ring表示環(huán)形鏈表中的元素。
type Ring struct {
   Value interface{} // Value類型為interface{}，因此可以接受任意類型
}

// 創(chuàng)建一個(gè)長(zhǎng)度為n的環(huán)形鏈表
func New(n int) *Ring

// 針對(duì)環(huán)形鏈表中的每一個(gè)元素x進(jìn)行f(x)操作
func (r *Ring) Do(f func(interface{}))

// 獲取環(huán)形鏈表長(zhǎng)度
func (r *Ring) Len() int

// 如果r和s在同一環(huán)形鏈表中，則刪除r和s之間的元素，
// 被刪除的元素組成一個(gè)新的環(huán)形鏈表，返回值為該環(huán)形鏈表的指針（即刪除前，r->Next()表示的元素）
// 如果r和s不在同一個(gè)環(huán)形鏈表中，則將s插入到r后面，返回值為
// 插入s后，s最后一個(gè)元素的下一個(gè)元素（即插入前，r->Next()表示的元素）
func (r *Ring) Link(s *Ring) *Ring

// 移動(dòng) n % r.Len() 個(gè)位置，n正負(fù)均可
func (r *Ring) Move(n int) *Ring

// 返回下一個(gè)元素
func (r *Ring) Next() *Ring

// 返回前一個(gè)元素
func (r *Ring) Prev() *Ring

// 刪除r后面的 n % r.Len() 個(gè)元素
func (r *Ring) Unlink(n int) *Ring

2、ring使用示例

Josephus問(wèn)題如下：在羅馬人占領(lǐng)喬塔帕特后，39個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從。首先從一個(gè)人開(kāi)始，越過(guò)k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過(guò)），并殺掉第k個(gè)人。接著，再越過(guò)k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過(guò)程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問(wèn)題是，給定了和，一開(kāi)始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。
Josephus問(wèn)題使用ring的解決方案如下：

package main

import (
   "container/ring"
   "fmt"
)

const (
   playerCount = 41 // 玩家人數(shù)
   startPos    = 1  // 開(kāi)始報(bào)數(shù)位置
   deadline    = 3  // 第n個(gè)人自殺
   aliveCount  = 2  // 幸存人數(shù)
)

type Player struct {
   position int  // 位置
   alive    bool // 是否存活
}

var players = ring.New(playerCount)

func Play(playerList *ring.Ring) {
   // 設(shè)置所有玩家初始值
   for i := 1; i <= playerCount; i++ {
      playerList.Value = &Player{i, true}
      playerList = playerList.Next()
   }

   // 如果開(kāi)始報(bào)數(shù)的位置不為1，則設(shè)置開(kāi)始位置
   if startPos > 1 {
      playerList = playerList.Move(startPos - 1)
   }

   counter := 1   // 報(bào)數(shù)從1開(kāi)始
   deadCount := 0 // 死亡人數(shù)，初始值為0

   for deadCount < playerCount-aliveCount {
      playerList = playerList.Next() // 跳到下一個(gè)人
      // 如果是活著的人，則報(bào)數(shù)
      if playerList.Value.(*Player).alive {
         counter++
      }
      // 如果報(bào)數(shù)為deadline，則此人淘汰出局
      if counter == deadline {
         playerList.Value.(*Player).alive = false
         fmt.Printf("Player %d died!\n", playerList.Value.(*Player).position)
         deadCount++
         counter = 0 // 報(bào)數(shù)置成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簡(jiǎn)介

sort包中實(shí)現(xiàn)了四種基本排序算法：插入排序、歸并排序、堆排序和快速排序，但只被用于sort包內(nèi)部使用。在對(duì)數(shù)據(jù)集合排序時(shí)不必考慮應(yīng)當(dāng)選擇哪一種排序方法，只要實(shí)現(xiàn)了sort.Interface定義的三個(gè)方法：獲取數(shù)據(jù)集合長(zhǎng)度的Len()方法、比較兩個(gè)元素大小的Less()方法和交換兩個(gè)元素位置的Swap()方法，就可以順利對(duì)數(shù)據(jù)集合進(jìn)行排序。sort包會(huì)根據(jù)實(shí)際數(shù)據(jù)自動(dòng)選擇高效的排序算法。為了方便對(duì)常用數(shù)據(jù)類型的操作，sort包提供了對(duì)[]int切片、[]float64切片和[]string切片完整支持，主要包括：
（1）對(duì)基本數(shù)據(jù)類型切片的排序支持。
（2）基本數(shù)據(jù)元素查找。
（3）判斷基本數(shù)據(jù)類型切片是否已經(jīng)排好序。
（4）對(duì)排好序的數(shù)據(jù)集合逆序。
對(duì)數(shù)據(jù)集合（包括自定義數(shù)據(jù)類型的集合）排序需要實(shí)現(xiàn)sort.Interface接口的三個(gè)方法：

type Interface interface {
   // 返回要排序的數(shù)據(jù)長(zhǎng)度
   Len() int
   //比較下標(biāo)為i和j對(duì)應(yīng)的數(shù)據(jù)大小，可自己控制升序和降序
   Less(i, j int) bool
   // 交換下標(biāo)為i，j對(duì)應(yīng)的數(shù)據(jù)
   Swap(i, j int)
}

任何實(shí)現(xiàn)了sort.Interface 的類型（一般為集合），均可使用sort包中的方法進(jìn)行排序，sort.Interface接口的方法要求集合內(nèi)列出元素的索引為整數(shù)。

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

本文名稱：Go語(yǔ)言開(kāi)發(fā)（十四）、Go語(yǔ)言常用標(biāo)準(zhǔn)庫(kù)四-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)路徑：http://jinyejixie.com/article28/ccpscp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站收錄、網(wǎng)站排名、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站內(nèi)鏈、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)