簡介
Go的標準包Container中包含了常用的容器類型，包括conatiner/list，container/heap，container/ring，本篇講解container/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
示例
Ring的用法
package main
import (
"container/ring"
"fmt"
)
func main() {
const rLen = 3
// 創建新的Ring
r := ring.New(rLen)
for i := 0; i rLen; i++ {
r.Value = i
r = r.Next()
}
fmt.Printf("Length of ring: %d\n", r.Len()) // Length of ring: 3
// 該匿名函數用來打印Ring中的數據
printRing := func(v interface{}) {
fmt.Print(v, " ")
}
r.Do(printRing) // 0 1 2
fmt.Println()
// 將r之后的第二個元素的值乘以2
r.Move(2).Value = r.Move(2).Value.(int) * 2
r.Do(printRing) // 0 1 4
fmt.Println()
// 刪除 r 與 r+2 之間的元素，即刪除 r+1
// 返回刪除的元素組成的Ring的指針
result := r.Link(r.Move(2))
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 1
fmt.Println()
another := ring.New(rLen)
another.Value = 7
another.Next().Value = 8 // 給 another + 1 表示的元素賦值，即第二個元素
another.Prev().Value = 9 // 給 another - 1 表示的元素賦值，即第三個元素
another.Do(printRing) // 7 8 9
fmt.Println()
// 插入another到r后面，返回插入前r的下一個元素
result = r.Link(another)
r.Do(printRing) // 0 7 8 9 4
fmt.Println()
result.Do(printRing) // 4 0 7 8 9
fmt.Println()
// 刪除r之后的三個元素，返回被刪除元素組成的Ring的指針
result = r.Unlink(3)
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 7 8 9
fmt.Println()
}
模擬約瑟夫問題
環形列表可以模擬約瑟夫問題。約瑟夫問題描述如下：
來自百度：
據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
用代碼模擬如下：
package main
import (
"container/ring"
"fmt"
)
type Player struct {
position int // 位置
alive bool // 是否存活
}
func main() {
const (
playerCount = 41 // 玩家人數
startPos = 1 // 開始報數位置
)
deadline := 3
r := ring.New(playerCount)
// 設置所有玩家初始值
for i := 1; i = playerCount; i++ {
r.Value = Player{i, true}
r = r.Next()
}
// 如果開始報數的位置不為1，則設置開始位置
if startPos > 1 {
r = r.Move(startPos - 1)
}
counter := 1 // 報數從1開始，因為下面的循環從第二個開始計算
deadCount := 0 // 死亡人數，初始值為0
for deadCount playerCount { // 直到所有人都死亡，否則循環一直執行
r = r.Next() // 跳到下一個人
// 如果是活著的人，則報數
if r.Value.(*Player).alive {
counter++
}
// 如果報數為deadline，則此人淘汰出局
if counter == deadline {
r.Value.(*Player).alive = false
fmt.Printf("Player %d died!\n", r.Value.(*Player).position)
deadCount++
counter = 0 // 報數置成0
}
}
}
輸出如下，可以看到16和31是最后兩個出隊列的，因此Josephus將他的朋友與自己安排在第16個與第31個位置是安全的。
Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!
補充：go語言中container容器數據結構heap、list、ring
heap堆的使用：
package main
import (
"container/heap"
"fmt"
)
type IntHeap []int
//我們自定義一個堆需要實現5個接口
//Len(),Less(),Swap()這是繼承自sort.Interface
//Push()和Pop()是堆自已的接口
//返回長度
func (h *IntHeap) Len() int {
return len(*h);
}
//比較大小(實現最小堆)
func (h *IntHeap) Less(i, j int) bool {
return (*h)[i] (*h)[j];
}
//交換值
func (h *IntHeap) Swap(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i];
}
//壓入數據
func (h *IntHeap) Push(x interface{}) {
//將數據追加到h中
*h = append(*h, x.(int))
}
//彈出數據
func (h *IntHeap) Pop() interface{} {
old := *h;
n := len(old);
x := old[n-1];
//讓h指向新的slice
*h = old[0: n-1];
//返回最后一個元素
return x;
}
//打印堆
func (h *IntHeap) PrintHeap() {
//元素的索引號
i := 0
//層級的元素個數
levelCount := 1
for i+1 = h.Len() {
fmt.Println((*h)[i: i+levelCount])
i += levelCount
if (i + levelCount*2) = h.Len() {
levelCount *= 2
} else {
levelCount = h.Len() - i
}
}
}
func main() {
a := IntHeap{6, 2, 3, 1, 5, 4};
//初始化堆
heap.Init(a);
a.PrintHeap();
//彈出數據，保證每次操作都是規范的堆結構
fmt.Println(heap.Pop(a));
a.PrintHeap();
fmt.Println(heap.Pop(a));
a.PrintHeap();
heap.Push(a, 0);
heap.Push(a, 8);
a.PrintHeap();
}
list鏈表的使用：
package main;
import (
"container/list"
"fmt"
)
func printList(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ");
}
fmt.Println();
}
func main() {
//創建一個鏈表
l := list.New();
//鏈表最后插入元素
a1 := l.PushBack(1);
b2 := l.PushBack(2);
//鏈表頭部插入元素
l.PushFront(3);
l.PushFront(4);
printList(l);
//取第一個元素
f := l.Front();
fmt.Println(f.Value);
//取最后一個元素
b := l.Back();
fmt.Println(b.Value);
//獲取鏈表長度
fmt.Println(l.Len());
//在某元素之后插入
l.InsertAfter(66, a1);
//在某元素之前插入
l.InsertBefore(88, a1);
printList(l);
l2 := list.New();
l2.PushBack(11);
l2.PushBack(22);
//鏈表最后插入新鏈表
l.PushBackList(l2);
printList(l);
//鏈表頭部插入新鏈表
l.PushFrontList(l2);
printList(l);
//移動元素到最后
l.MoveToBack(a1);
printList(l);
//移動元素到頭部
l.MoveToFront(a1);
printList(l);
//移動元素在某元素之后
l.MoveAfter(b2, a1);
printList(l);
//移動元素在某元素之前
l.MoveBefore(b2, a1);
printList(l);
//刪除某元素
l.Remove(a1);
printList(l);
}
ring環的使用：
package main;
import (
"container/ring"
"fmt"
)
func printRing(r *ring.Ring) {
r.Do(func(v interface{}) {
fmt.Print(v.(int), " ");
});
fmt.Println();
}
func main() {
//創建環形鏈表
r := ring.New(5);
//循環賦值
for i := 0; i 5; i++ {
r.Value = i;
//取得下一個元素
r = r.Next();
}
printRing(r);
//環的長度
fmt.Println(r.Len());
//移動環的指針
r.Move(2);
//從當前指針刪除n個元素
r.Unlink(2);
printRing(r);
//連接兩個環
r2 := ring.New(3);
for i := 0; i 3; i++ {
r2.Value = i + 10;
//取得下一個元素
r2 = r2.Next();
}
printRing(r2);
r.Link(r2);
printRing(r);
}
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。如有錯誤或未考慮完全的地方，望不吝賜教。
您可能感興趣的文章:- go語言中GOPATH GOROOT的作用和設置方式
- go設置多個GOPATH的方式
- 淺談golang 中time.After釋放的問題
- golang 定時任務方面time.Sleep和time.Tick的優劣對比分析
- golang日志包logger的用法詳解
- golang elasticsearch Client的使用詳解
- goland設置顏色和字體的操作
- go 類型轉換方式(interface 類型的轉換)
