Go container包的介紹

Posted on by

1.簡介

Container — 容器數據類型：該包實現瞭三個復雜的數據結構：堆、鏈表、環

  • List：Go中對鏈表的實現，其中List：雙向鏈表，Element：鏈表中的元素
  • Ring：實現的是一個循環鏈表，也就是我們俗稱的環
  • Heap：Go中對堆的實現

2.list

簡單實用：

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

方法列表：

type Element
    func (e *Element) Next() *Element                                   // 返回該元素的下一個元素，如果沒有下一個元素則返回 nil
    func (e *Element) Prev() *Element                                   // 返回該元素的前一個元素，如果沒有前一個元素則返回nil

type 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 和 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數據結構

節點定義：

type Element struct {
 // 後繼指針，前向指針
 next, prev *Element

 // 鏈表指針，屬於哪個鏈表
 list *List

 // 節點value
 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
}

初始化：

// 通過工廠方法返回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節點作為一個根節點，不承擔數據，也不是實際的鏈表節點，節點數量len沒算上它，再初始化的時候，root節點會成為一個隻有一個節點的環（前後指針都指向自己）

2.2插入元素

頭插法:

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

尾插法:

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

在指定元素後新增元素:

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，把初始化操作延後，僅在實際需要的時候才進行

func (l *List) lazyInit() {
 if l.root.next == nil {
  l.Init()
 }
}

移除元素：

// remove 從雙向鏈表中移除一個元素e，遞減鏈表的長度，返回該元素e 
func (l *List) remove(e *Element) *Element {
  e.prev.next = e.next
  e.next.prev = e.prev
  e.next = nil // 防止內存泄漏
  e.prev = nil // 防止內存泄漏
  e.list = nil
  l.len --
  return e 
}

3.ring

Go中提供的ring是一個雙向的循環鏈表，與list的區別在於沒有表頭和表尾，ring表頭和表尾相連，構成一個環

使用demo：

func main()  {

 // 初始化3個元素的環，返回頭節點
 r := ring.New(3)
 // 給環填充值
 for i := 1;i <= 3;i++{
  r.Value = i
  r = r.Next()
 }
 sum := 0
 // 對環的每個元素進行處理
 r.Do(func(i interface{}) {
  sum = i.(int) + sum
 })
 fmt.Println(sum)
}

方法列表：

type Ring
    func New(n int) *Ring  // 初始化環
    func (r *Ring) Do(f func(interface{}))  // 循環環進行操作
    func (r *Ring) Len() int // 環長度
    func (r *Ring) Link(s *Ring) *Ring // 連接兩個環
    func (r *Ring) Move(n int) *Ring // 指針從當前元素開始向後移動或者向前（n 可以為負數）
    func (r *Ring) Next() *Ring // 當前元素的下個元素
    func (r *Ring) Prev() *Ring // 當前元素的上個元素
    func (r *Ring) Unlink(n int) *Ring // 從當前元素開始，刪除 n 個元素

3.1數據結構

環節點數據結構：

type Ring struct {
 next, prev *Ring // 前繼和後繼指針
 Value      interface{} // for use by client; untouched by this library
}

初始化一個環：後繼和前繼指針都指向自己

func (r *Ring) init() *Ring {
 r.next = r
 r.prev = r
 return r
}

初始化指定數量個節點的環

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
}

遍歷環，對個元素執行指定操作：

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中堆使用的數據結構是最小二叉樹，即根節點比左邊子樹和右邊子樹的所有值都小

使用demo：需要實現Interface接口，go中堆都是實現這個接口，定義瞭排序，插入和刪除方法

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

實現接口：

// An IntHeap is a min-heap of ints.
type IntHeap []int

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{}) {
 // 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數據結構

上浮：

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

下沉：

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
}

到此這篇關於Go container包的介紹的文章就介紹到這瞭,更多相關Go container包內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：