Go——container包（list、ring、heap）

绝地灬酷狼 2024-03-22 16:17 50阅读 0赞

### 简介 ###

container为容器数据类型：该包包含了三个数据结构：

*  List：双向链表
 *  Ring：循环链表，也就是环
 *  Heap：堆

### 一、list ###

Element为节点：

type Element struct {
        
    	next, prev *Element
    	list *List
    	Value interface{
        }
    }

方法列表：

type Element
        func (e *Element) Next() *Element                                  
        func (e *Element) Prev() *Element                                   
    type List                               
        func New() *List                                                    
        func (l *List) Back() *Element                                      
        func (l *List) Front() *Element                                     
        func (l *List) Init() *List                                         
        func (l *List) InsertAfter(v interface{
        }, mark *Element) *Element  
        func (l *List) InsertBefore(v interface{
        }, mark *Element) *Element  
        func (l *List) Len() int                                            
        func (l *List) MoveAfter(e, mark *Element)                          
        func (l *List) MoveBefore(e, mark *Element)                         
        func (l *List) MoveToBack(e *Element)                   
        func (l *List) MoveToFront(e *Element)                                      
        func (l *List) PushBack(v interface{
        }) *Element                              
        func (l *List) PushBackList(other *List)                                   
        func (l *List) PushFront(v interface{
        }) *Element                             
        func (l *List) PushFrontList(other *List)                                   
        func (l *List) Remove(e *Element) interface{
        }

func (l *List) Back() *Element
    返回值：*Element，链表中最后一个节点的指针，如果链表长度为0，则为nil
    
    func (l *List) Front() *Element
    返回值：*Element，链表中第一个节点的指针，如果链表长度为0，则为nil
    
    func (l *List) Init() *List
    返回值：*List，初始化或者清空后的链表
    功能说明: 初始化或者清空链表，该方法调用后，链表的长度为0
    
    func (l *List) Len() int
    返回值：int，链接中节点的个数
    功能说明：获得链接中节点的个数
    
    func (l *List) InsertAfter(value interface{
        }, mark *Element) *Element
    参数列表：
    - value：要插入的数据的内容
    - mark：链表中的一个节点指针
    返回值：*Element：被插入的节点指针，该节点的Value为数据内容
    功能说明：把数据value插入到mark节点的后面，并返回这个被插入的节点。
    
    func (l *List) InsertBefore(value interface{
        }, mark *Element) *Element
    参数列表：
    - value：要插入的数据的内容
    - mark：链表中的一个节点指针
    返回值：*Element：被插入的节点指针，该节点的Value为数据内容
    功能说明：把数据value插入到mark节点的前面，并返回这个被插入的节点。
    
    func (l *List) MoveToBack(e *Element)
    参数列表：
    - e：链表中的节点
    功能说明：把节点e移到链表的末尾
    
    func (l *List) MoveToFront(e *Element)
    参数列表：
    - e：链表中的节点
    功能说明：把节点e移到链表的开头
    
    func New() *List
    返回值：*List：空链表的指针
    功能说明:创建一个空链表，链表的长度为0，开头和末尾节点都是nil
    
    func (e *Element) Next() *Element
    返回值：*Element：链表中该节点的下一个节点元素的指针，如果该节点是最后一个节点，则返回nil
    功能说明：获得该节点在链表中的下一个节点元素的指针，如果该节点是最后一个节点，则返回nil
    
    func (e *Element) Prev() *Element
    返回值：*Element：链表中该节点的上一个节点元素的指针，如果该节点是第一个节点，则返回nil
    功能说明：获得该节点在链表中的上一个节点元素的指针，如果该节点是第一个节点，则返回nil
    
    func (l *List) PushBack(value interface{
        }) *Element
    参数列表：
    - value：将被存到链表末尾的任意对象
    返回值：*Element：被存到末尾的节点的指针
    功能说明：把一个对象存到链表末尾，并返回这个节点
    
    func (l *List) PushBackList(ol *List)
    参数列表：
    - ol：将被插入到链表l末尾的链表
    功能说明：把一个链表存到链表末尾
    
    func (l *List) PushFront(value interface{
        }) *Element
    参数列表：
    - value：将被存到链表开头的任意对象
    返回值：*Element：被存到开头的节点的指针
    功能说明：把一个对象存到链表开头，并返回这个节点
    
    func (l *List) PushFrontList(ol *List)
    参数列表：
    - ol：将被插入到链表l开头的链表
    功能说明：把一个链表存到链表开头
    
    func (l *List) Remove(e *Element) interface{
        }
    参数列表：
    - e：将被删除的节点，该节点必须是属于链表l的
    返回值：interface{
        }：被删除的节点的内容
    功能说明：删除指定的节点，并返回这个节点的内容

示例：

func main() {
        
    	list := list.New()
    	two := list.PushBack(2)
    	three := list.PushBack(3)
    	one := list.PushFront(1)
    	printList(list) // 1 2 3
    
    	list.MoveToBack(one)    // 2 3 1
    	list.MoveToFront(three) // 3 2 1
    	printList(list)         // 3 2 1
    	list.Remove(two)
    	printList(list) //3 1
    
    	list.InsertAfter(4, one)
    	list.InsertBefore(5, three)
    	printList(list) // 5 3 1 4
    
    	println(list.Len())// 4
    	list.Init()
    	println(list.Len())// 0
    }
    
    //打印链表
    func printList(l *list.List) {
        
    	for e := l.Front(); e != nil; e = e.Next() {
        
    		fmt.Printf("%d ", e.Value)
    	}
    	fmt.Printf("\n")
    }

### 二、ring ###

Go中提供的ring是一个双向的循环链表，与list的区别在于没有表头和表尾，ring表头和表尾相连，构成一个环

方法列表：

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
    	func (r *Ring) Next() *Ring
    	func (r *Ring) Prev() *Ring
    	func (r *Ring) Unlink(n int) *Ring

func New(n int) *Ring
    参数列表：
    - n：环形双向链表的节点的个数
    返回值：*Ring：空链表的指针
    功能说明:创建一个有n个节点的环形双向链表
    
    # func (r *Ring) Do(f func(interface{
        }))
    参数列表：
    - `f`：一个回调函数，该函数的参数为环形双向链表中的节点的`Value`字段值
    功能说明：正向遍历环形双向链表，并对每个链表中的元素执行回调函数`f`，如果这个回调函数`f`会修改链表`r`，那这个回调函数的行为将不可确定
    
    # func (r *Ring) Len() int
    返回值：
    - `int`：环形链表中元素的个数
    功能说明:遍历环形双向链表来统计链表中的元素的个数
    
    # func (r *Ring) Link(s *Ring) *Ring
    参数列表：
    - `s`：环形双向链表
    返回值：`*Ring`：`s`和`r`相连前`r.Next()`的值，也是相连后`s.Next()`的值
    功能说明:
    - 把一个环形双向链表`s`与环形双向链表`r`相链接，链接后`r.Next()`为s，并返回相连前时`r.Next()`的值。`r`不能为空。
    - 如果`s`和`r`不是同一个环形链表，则相连后，只产生一个环形链表，并返回相连前时`r.Next()`的值，也是相连后`s.Prev()`的值。
    - 如果`s`和`r`是同一个环形链表，但`s != r`时，相连后，产生两个环形链表，其中一个是由`r`和`s`之间的节点构成（不包括`r`和`s`），返回值为相连前时`r.Next()`的值，即`r`和`s`之间的节点（不包括`r`和`s`）构成的环形链表的表头节点。
    - 如果`s`和`r`是同一个环形链表，且`s == r`时，相连后，产生两个环形链表，其中一个是由`r`指向的节点构成的长度为1的环形链表，其他节点构成另一个环形链表，返回值为相连前时`r.Next()`的值，即其他节点构成的环形链表的表头节点。
    
    参数列表：
    - `n`：指针`r`在双向链表上移动的位置的个数。n>0时，为正向移动；反之为反向移动。
    返回值：*Ring：移动结束后，指针`r`指向的节点
    功能说明：指向节点`r`的指针，正向或者逆向移动`n % r.Len()`个节点，并返回这个指针移动后指向的节点。但是`r.Move(n)`不对改变r的值，`r`不能为空
    
    # func (r *Ring) Next() *Ring
    返回值： `*Ring`：指向下一个节点的指针
    功能说明：获得指向下一个节点的指针
    
    # func (r *Ring) Prev() *Ring
    返回值：`*Ring`：指向上一个节点的指针
    功能说明：获得指向上一个节点的指针
    
    # func (r *Ring) Unlink(n int) *Ring
    参数列表：
    - `n`：要被移除的节点的数个
    功能说明：从节点`r`的下一个节点（包含该节点）开始移除`n % r.Len()`个节点。如果`n % r.Len() == 0`，则链表不会有改变。`r`不能为空。

示例：

func main() {
        
    	r := ring.New(10)
    	for i := 0; i < 10; i++ {
        
    		r.Value = i
    		r = r.Next()
    	}
    	ringPrint(r) //0 1 2 3 4 5 6 7 8 9
    
    	fmt.Println(r.Len()) //10
    
    	fmt.Println(r.Next().Value) //1
    	fmt.Println(r.Prev().Value) //9
    
    	r5 := r.Move(4)
    	fmt.Println(r5.Value) //4
    
    	r5.Unlink(3)
    	ringPrint(r5) //4 8 9 0 1 2 3 （5、6、7三个节点被删除）
    
    	//link两个不同的环形链表
    	linkDiffRing()
    
    	// 如果两个链表是同一个链表，但是两个指针不是指这个链表中的节点时，即s != r时
    	linkSameRing()
    
    	// 如果两个链表是同一个链表，且两个指针指向这个链表中的同一个节点时，即s == r时
    	linkSameElement()
    
    }
    
    func ringPrint(r *ring.Ring) {
        
    	r.Do(func(v interface{
        }) {
        
    		fmt.Printf("%d ", v)
    	})
    	fmt.Printf("\n")
    }
    
    func makeN(n int, begin int) *ring.Ring {
        
    	r := ring.New(n)
    	for i := begin; i < n+begin; i++ {
        
    		r.Value = i
    		r = r.Next()
    	}
    	return r
    }
    
    // Link两个不同的环形链表
    func linkDiffRing() {
        
    	r1 := makeN(5, 0)
    	ringPrint(r1) //0 1 2 3 4
    
    	r2 := makeN(5, 10)
    	ringPrint(r2) //10 11 12 13 14
    
    	r1.Link(r2)
    	fmt.Println(r1.Value) // 输出：0
    
    	ringPrint(r1) //0 10 11 12 13 14 1 2 3 4
    }
    
    // 如果两个链表是同一个链表，但是两个指针不是指这个链表中的节点时，即s != r时
    func linkSameRing() {
        
    	r1 := makeN(10, 0)
    	ringPrint(r1) //0 1 2 3 4 5 6 7 8 9
    
    	r2 := r1.Move(5)
    	fmt.Println(r1.Value, r2.Value) //0 5
    
    	r3 := r1.Link(r2)
    
    	ringPrint(r1) //0 5 6 7 8 9
    	ringPrint(r3) //1 2 3 4
    }
    
    // 如果两个链表是同一个链表，且两个指针指向这个链表中的同一个节点时，即s == r时
    func linkSameElement() {
        
    	r1 := makeN(10, 0)
    	ringPrint(r1)         //0 1 2 3 4 5 6 7 8 9
    	fmt.Println(r1.Value) // 输出：0
    
    	r2 := r1.Link(r1)
    
    	ringPrint(r1) //0
    	ringPrint(r2) //1 2 3 4 5 6 7 8 9
    }

### 3、heap ###

任何实现了heap.Interface接口的对象都可以使用heap包提供的方法对堆进行操作(堆是一个完全二叉树)。通过对heap.Interface中的Less方法的不同实现，来实现最大堆和最小堆。通常堆的数据结构为一个一维数组。

//heap.interface
    type Interface interface {
        
    	sort.Interface
    	Push(x interface{
        }) 
    	Pop() interface{
        } 
    }
    
    //sort.Interface
    type Interface interface {
        
    	Len() int
    	Less(i, j int) bool
    	Swap(i, j int)
    }

方法列表：

func Init(h Interface)
    func Pop(h Interface) interface{
        }
    func Push(h Interface, x interface{
        })
    func Remove(h Interface, i int) interface{
        }

##### 3.1、func Init(h Interface) #####

参数列表：

*  h：实现了heap.Interface接口的堆对象

功能说明：在对堆h进行操作前必须保证堆已经初始化（即符合堆结构），该方法可以在堆中元素的顺序不符合堆的要求时调用，调用后堆会调整为标准的堆结构，该方法的时间复杂度为：O(n)，n为堆h中元素的总个数。

type myHeap []int // 定义一个堆，存储结构为数组
    
    // 实现了heap.Interface中组合的sort.Interface接口的Less方法
    func (h *myHeap) Less(i, j int) bool {
        
    	return (*h)[i] < (*h)[j]
    }
    
    // 实现了heap.Interface中组合的sort.Interface接口的Swap方法
    func (h *myHeap) Swap(i, j int) {
        
    	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
    }
    
    // 实现了heap.Interface中组合的sort.Interface接口的Push方法
    func (h *myHeap) Len() int {
        
    	return len(*h)
    }
    
    // 实现了heap.Interface的Pop方法
    func (h *myHeap) Pop() (v interface{
        }) {
        
    	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
    	return
    }
    
    // 实现了heap.Interface的Push方法
    func (h *myHeap) Push(v interface{
        }) {
        
    	*h = append(*h, v.(int))
    }
    
    // 按层来遍历和打印堆数据，第一行只有一个元素，即堆顶元素
    func (h myHeap) printHeap() {
        
    	n := 1
    	levelCount := 1
    	for n <= h.Len() {
        
    		fmt.Println(h[n-1 : n-1+levelCount])
    		n += levelCount
    		levelCount *= 2
    	}
    }
    
    func main() {
        
    	data := [7]int{
        13, 25, 1, 9, 5, 12, 11}
    	aheap := new(myHeap)
    	// 用堆本身的Push方法将数组中的元素依次存入堆中
    	for _, value := range data {
        
    		aheap.Push(value)
    	}
    
    	// 此时堆数组内容为：13, 25, 1, 9, 5, 12, 11
    	// 不是正确的堆结构
    	aheap.printHeap()
    	// 输出：
    	//  [13]
    	//  [25 1]
    	//  [9 5 12 11]
    
    	heap.Init(aheap) // 对堆进行调整，调整后为规范的堆结构
    
    	fmt.Println(*aheap) // 输出：[1 5 11 9 25 12 13]
    	aheap.printHeap()
    	// 输出：
    	//	[1]
    	//	[5 11]
    	//	[9 25 12 13]
    }

##### 3.2、func Pop(h Interface) interface\{\} #####

参数列表：

*  `h`：实现了`heap.Interface`的堆对象

返回值：

*  `interface{}`：堆顶的元素

功能说明：从堆`h`中取出堆顶的元素并自动调整堆结构。根据`h`的`Less`方法实现的不同，堆顶元素可以是最大的元素或者是最小的元素。该方法的时间复杂度为O(log(n))，n为堆中元素的总和。

func main() {
        
    	data := [7]int{
        13, 25, 1, 9, 5, 12, 11}
    	aheap := new(myHeap) // 创建空堆
    
    	// 用heap包中的Push方法将数组中的元素依次存入堆中，
    	// 每次Push都会保证堆是规范的堆结构
    	for _, value := range data {
        
    		heap.Push(aheap, value)
    	}
    	fmt.Println(*aheap) // 输出：[1 5 11 25 9 13 12]
    	aheap.printHeap()
    	// 输出：
    	//  [1]
    	//  [5 11]
    	//  [25 9 13 12]
    
    	// 依次调用heap包的Pop方法来获取堆顶元素
    	for aheap.Len() > 0 {
        
    		fmt.Printf("%d ", heap.Pop(aheap))
    	}
    	// 输出：1 5 9 11 12 13 25
    }

##### 3.3、func Push(h Interface, x interface\{\}) #####

参数列表：

*  h：实现了heap.Interface的堆对象
 *  x：将被存到堆中的元素对象

功能说明：把元素x存到堆中。该方法的时间复杂度为O(log(n))，n为堆中元素的总和。

func main() {
        
    	data := [7]int{
        13, 25, 1, 9, 5, 12, 11}
    	aheap := new(myHeap) // 此时是空堆
    
    	// 用heap包中的Push方法将数组中的元素依次存入堆中，
    	// 每次Push都会保证堆是规范的堆结构
    	for _, value := range data {
        
    		heap.Push(aheap, value)
    		fmt.Printf("插入%d\n", value)
    		aheap.printHeap()
    		fmt.Println()
    	}
    	fmt.Println(*aheap)
    	// 输出：
    	//	插入13
    	//	[13]
    	//
    	//	插入25
    	//	[13]
    	//	[25]
    	//
    	//	插入1
    	//	[1]
    	//	[25 13]
    	//
    	//	插入9
    	//	[1]
    	//	[9 13]
    	//	[25]
    	//
    	//	插入5
    	//	[1]
    	//	[5 13]
    	//	[25 9]
    	//
    	//	插入12
    	//	[1]
    	//	[5 12]
    	//	[25 9 13]
    	//
    	//	插入11
    	//	[1]
    	//	[5 11]
    	//	[25 9 13 12]
    	//
    	//	[1 5 11 25 9 13 12]
    
    }

##### 3.4、func Remove(h Interface, i int) interface\{\} #####

参数列表：

*  h：实现了heap.Interface的堆对象
 *  i：将被移除的元素在堆中的索引号

返回值：interface\{\}：堆顶的元素  
功能说明：把索引号为i的元素从堆中移除。该方法的时间复杂度为O(log(n))，n为堆中元素的总和。

func main() {
        
    	data := [7]int{
        13, 25, 1, 9, 5, 12, 11}
    	aheap := new(myHeap) // 创建空堆
    
    	// 用heap包中的Push方法将数组中的元素依次存入堆中，
    	// 每次Push都会保证堆是规范的堆结构
    	for _, value := range data {
        
    		heap.Push(aheap, value)
    	}
    	fmt.Println(*aheap) // 输出：[1 5 11 25 9 13 12]
    	aheap.printHeap()
    	// 输出：
    	//  [1]
    	//  [5 11]
    	//  [25 9 13 12]
    
    	value := heap.Remove(aheap, 2) // 删除索引号为2的元素（即数组中的第3个元素）
    	fmt.Println(value)             // 输出：11
    	aheap.printHeap()
    	// 输出：
    	//	[1]
    	//	[5 12]
    	//	[25 9 13]
    }