Go標準容器之Ring的使用說明

簡介

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

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方,望不吝賜教。