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包内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!