Go container包的介绍
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包内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/weixin_41922289/article/details/121592
相关文章
- PHP+Ajax有许多的功能都会用到它小编今天就有使用PHP+Ajax实现的一个微信登录功能了,下面我们来看一个PHP+Ajax手机发红包的程序例子,具体如下所示。 PHP发红包基本...2016-11-25
- 在程序员中,尤其是go新手,经常听到的一个讨论话题是:如何处理错误,这篇文章主要给大家介绍了关于Go应用中优雅处理Error的一些相关技巧,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了解决idea2020 maven无法自动导包的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-13
Django def clean()函数对表单中的数据进行验证操作
这篇文章主要介绍了Django def clean()函数对表单中的数据进行验证操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-09将c#编写的程序打包成应用程序的实现步骤分享(安装,卸载) 图文
时常会写用c#一些程序,但如何将他们和photoshop一样的大型软件打成一个压缩包,以便于发布....2020-06-25- 这篇文章主要介绍了Pyinstaller打包文件太大的解决方案,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
Postman安装与使用详细教程 附postman离线安装包
这篇文章主要介绍了Postman安装与使用详细教程 附postman离线安装包,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-05- 这篇文章主要介绍了PHP实现创建以太坊钱包转账等功能,对以太坊感兴趣的同学,可以参考下...2021-04-20
- 本文主要介绍了手把手教你uniapp和小程序分包,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-02
- 这篇文章主要介绍了golang官方嵌入文件到可执行程序,本文通过示例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-20
- 这篇文章主要介绍了C# 实现抓包的方法,文中讲解非常细致,代码帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-08-04
- 这篇文章主要介绍了go浮点数转字符串保留小数点后N位解决办法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-05-11
- 将外部作用域中的局部变量封闭起来的函数对象称为闭包(Closure),被封闭起来的变量与封闭它的函数对象有相同的生命周期,这在JavaScript中比较难理解而且十分重要,接下来带大家一起来全面理解JavaScript中的闭包:...2016-05-14
- 这篇文章主要介绍了Go语言使用读写OPC详解,图文讲解的很清晰,有感兴趣的同学可以学习下...2021-03-05
- 这篇文章主要介绍了Go项目的目录结构,对基础目录做了讲解,对项目开发中的其它目录也一并做了介绍,需要的朋友可以参考下...2020-05-01
- 这篇文章主要介绍了改变R语言默认存储包的路径操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- string与[]byte经常需要互相转化,普通转化会发生底层数据的复制,下面这篇文章主要给大家介绍了关于Go中string与[]byte高效互转的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考下...2021-09-20
intellij idea如何将web项目打成war包的实现
这篇文章主要介绍了intellij idea如何将web项目打成war包的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-07-04- 在本篇文章里小编给大家分享的是一篇关于R语言“包”的知识点总结内容,有兴趣的朋友们可以学习下。...2021-05-06