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