1.簡介
Container — 容器數(shù)據(jù)類型：該包實現(xiàn)了三個復雜的數(shù)據(jù)結(jié)構(gòu)：堆、鏈表、環(huán)
-
List：Go中對鏈表的實現(xiàn)，其中List：雙向鏈表，Element：鏈表中的元素 -
Ring：實現(xiàn)的是一個循環(huán)鏈表，也就是我們俗稱的環(huán) -
Heap：Go中對堆的實現(xiàn)
2.list
簡單實用：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func main() { // 初始化雙向鏈表 l := list.New() // 鏈表頭插入 l.PushFront(1) // 鏈表尾插入 l.PushBack(2) l.PushFront(3) // 從頭開始遍歷 for head := l.Front();head != nil;head = head.Next() { fmt.Println(head.Value) }} |
方法列表：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
type Element func (e *Element) Next() *Element // 返回該元素的下一個元素，如果沒有下一個元素則返回 nil func (e *Element) Prev() *Element // 返回該元素的前一個元素，如果沒有前一個元素則返回niltype List func New() *List // 返回一個初始化的list func (l *List) Back() *Element // 獲取list l的最后一個元素 func (l *List) Front() *Element // 獲取list l的第一個元素 func (l *List) Init() *List // list l 初始化或者清除 list l func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之后插入一個值為 v 的元素，并返回該元素，如果 mark 不是list中元素，則 list 不改變 func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之前插入一個值為 v 的元素，并返回該元素，如果 mark 不是list中元素，則 list 不改變 func (l *List) Len() int // 獲取 list l 的長度 func (l *List) MoveAfter(e, mark *Element) // 將元素 e 移動到元素 mark 之后，如果元素e 或者 mark 不屬于 list l，或者 e==mark，則 list l 不改變 func (l *List) MoveBefore(e, mark *Element) // 將元素 e 移動到元素 mark 之前，如果元素e 或者 mark 不屬于 list l，或者 e==mark，則 list l 不改變 func (l *List) MoveToBack(e *Element) // 將元素 e 移動到 list l 的末尾，如果 e 不屬于list l，則list不改變 func (l *List) MoveToFront(e *Element) // 將元素 e 移動到 list l 的首部，如果 e 不屬于list l，則list不改變 func (l *List) PushBack(v interface{}) *Element // 在 list l 的末尾插入值為 v 的元素，并返回該元素 func (l *List) PushBackList(other *List) // 在 list l 的尾部插入另外一個 list，其中l(wèi) 和 other 可以相等 func (l *List) PushFront(v interface{}) *Element // 在 list l 的首部插入值為 v 的元素，并返回該元素 func (l *List) PushFrontList(other *List) // 在 list l 的首部插入另外一個 list，其中 l 和 other 可以相等 func (l *List) Remove(e *Element) interface{} // 如果元素 e 屬于list l，將其從 list 中刪除，并返回元素 e 的值 |
2.1數(shù)據(jù)結(jié)構(gòu)
節(jié)點定義：
|
1
2
3
4
5
6
7
8
9
10
|
type Element struct { // 后繼指針，前向指針 next, prev *Element // 鏈表指針，屬于哪個鏈表 list *List // 節(jié)點value Value interface{}} |
雙向鏈表定義：
|
1
2
3
4
5
6
|
type List struct { // 根元素 root Element // sentinel list element, only &root, root.prev, and root.next are used // 實際節(jié)點數(shù)量 len int // current list length excluding (this) sentinel element} |
初始化：
|
1
2
3
4
5
6
7
8
9
|
// 通過工廠方法返回list指針func New() *List { return new(List).Init() }func (l *List) Init() *List { l.root.next = &l.root l.root.prev = &l.root l.len = 0 return l} |
這里可以看到root節(jié)點作為一個根節(jié)點，不承擔數(shù)據(jù)，也不是實際的鏈表節(jié)點，節(jié)點數(shù)量len沒算上它，再初始化的時候，root節(jié)點會成為一個只有一個節(jié)點的環(huán)（前后指針都指向自己）
2.2插入元素
頭插法:
|
1
2
3
4
5
6
7
8
9
10
11
|
func (l *List) Front() *Element { if l.len == 0 { return nil } return l.root.next}func (l *List) PushFront(v interface{}) *Element { l.lazyInit() return l.insertValue(v, &l.root)} |
尾插法:
|
1
2
3
4
5
6
7
8
9
10
11
|
func (l *List) Back() *Element { if l.len == 0 { return nil } return l.root.prev}func (l *List) PushBack(v interface{}) *Element { l.lazyInit() return l.insertValue(v, l.root.prev)} |
在指定元素后新增元素:
|
1
2
3
4
5
6
7
8
9
|
func (l *List) insert(e, at *Element) *Element { e.prev = at e.next = at.next e.prev.next = e e.next.prev = e e.list = l l.len++ return e} |
這里有個延遲初始化的邏輯：lazyInit，把初始化操作延后，僅在實際需要的時候才進行
|
1
2
3
4
5
|
func (l *List) lazyInit() { if l.root.next == nil { l.Init() }} |
移除元素：
|
1
2
3
4
5
6
7
8
9
10
|
// remove 從雙向鏈表中移除一個元素e，遞減鏈表的長度，返回該元素e func (l *List) remove(e *Element) *Element { e.prev.next = e.next e.next.prev = e.prev e.next = nil // 防止內(nèi)存泄漏 e.prev = nil // 防止內(nèi)存泄漏 e.list = nil l.len -- return e } |
3.ring
Go中提供的ring是一個雙向的循環(huán)鏈表，與list的區(qū)別在于沒有表頭和表尾，ring表頭和表尾相連，構(gòu)成一個環(huán)
使用demo：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func main() { // 初始化3個元素的環(huán)，返回頭節(jié)點 r := ring.New(3) // 給環(huán)填充值 for i := 1;i <= 3;i++{ r.Value = i r = r.Next() } sum := 0 // 對環(huán)的每個元素進行處理 r.Do(func(i interface{}) { sum = i.(int) + sum }) fmt.Println(sum)} |
方法列表：
|
1
2
3
4
5
6
7
8
9
|
type Ring func New(n int) *Ring // 初始化環(huán) func (r *Ring) Do(f func(interface{})) // 循環(huán)環(huán)進行操作 func (r *Ring) Len() int // 環(huán)長度 func (r *Ring) Link(s *Ring) *Ring // 連接兩個環(huán) func (r *Ring) Move(n int) *Ring // 指針從當前元素開始向后移動或者向前（n 可以為負數(shù)） func (r *Ring) Next() *Ring // 當前元素的下個元素 func (r *Ring) Prev() *Ring // 當前元素的上個元素 func (r *Ring) Unlink(n int) *Ring // 從當前元素開始，刪除 n 個元素 |
3.1數(shù)據(jù)結(jié)構(gòu)
環(huán)節(jié)點數(shù)據(jù)結(jié)構(gòu)：
|
1
2
3
4
|
type Ring struct { next, prev *Ring // 前繼和后繼指針 Value interface{} // for use by client; untouched by this library} |
初始化一個環(huán)：后繼和前繼指針都指向自己
|
1
2
3
4
5
|
func (r *Ring) init() *Ring { r.next = r r.prev = r return r} |
初始化指定數(shù)量個節(jié)點的環(huán)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func New(n int) *Ring { if n <= 0 { return nil } r := new(Ring) p := r for i := 1; i < n; i++ { p.next = &Ring{prev: p} p = p.next } p.next = r r.prev = p return r} |
遍歷環(huán)，對個元素執(zhí)行指定操作：
|
1
2
3
4
5
6
7
8
|
func (r *Ring) Do(f func(interface{})) { if r != nil { f(r.Value) for p := r.Next(); p != r; p = p.next { f(p.Value) } }} |
4.heap
Go中堆使用的數(shù)據(jù)結(jié)構(gòu)是最小二叉樹，即根節(jié)點比左邊子樹和右邊子樹的所有值都小
使用demo：需要實現(xiàn)Interface接口，go中堆都是實現(xiàn)這個接口，定義了排序，插入和刪除方法
|
1
2
3
4
5
|
type Interface interface { sort.Interface Push(x interface{}) // add x as element Len() Pop() interface{} // remove and return element Len() - 1.} |
實現(xiàn)接口：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// An IntHeap is a min-heap of ints.type IntHeap []intfunc (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{}) { // Push and Pop use pointer receivers because they modify the slice's length, // not just its contents. *h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x}// This example inserts several ints into an IntHeap, checks the minimum,// and removes them in order of priority.func Example_intHeap() { h := &IntHeap{2, 1, 5} heap.Init(h) heap.Push(h, 3) fmt.Printf("minimum: %d\n", (*h)[0]) for h.Len() > 0 { fmt.Printf("%d ", heap.Pop(h)) } // Output: // minimum: 1 // 1 2 3 5} |
4.1數(shù)據(jù)結(jié)構(gòu)
上浮：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func Push(h Interface, x interface{}) { h.Push(x) up(h, h.Len()-1)}func up(h Interface, j int) { for { i := (j - 1) / 2 // parent if i == j || !h.Less(j, i) { break } h.Swap(i, j) j = i }} |
下沉：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func Pop(h Interface) interface{} { n := h.Len() - 1 h.Swap(0, n) down(h, 0, n) return h.Pop()}func down(h Interface, i0, n int) bool { i := i0 for { j1 := 2*i + 1 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow break } j := j1 // left child if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { j = j2 // = 2*i + 2 // right child } if !h.Less(j, i) { break } h.Swap(i, j) i = j } return i > i0} |
到此這篇關(guān)于Go container包的介紹的文章就介紹到這了,更多相關(guān)Go container包內(nèi)容請搜索服務器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/weixin_41922289/article/details/121592261
