go语言中container容器数据结构heap、list、ring

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

heap堆的使用：

package main

import (
	"container/heap"
	"fmt"
)

type IntHeap []int

//我们自定义一个堆需要实现5个接口
//Len(),Less(),Swap()这是继承自sort.Interface
//Push()和Pop()是堆自已的接口

//返回长度
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{}) {
	//将数据追加到h中
	*h = append(*h, x.(int))
}

//弹出数据
func (h *IntHeap) Pop() interface{} {
	old := *h;
	n := len(old);
	x := old[n-1];
	//让h指向新的slice
	*h = old[0: n-1];
	//返回最后一个元素
	return x;
}

//打印堆
func (h *IntHeap) PrintHeap() {
	//元素的索引号
	i := 0
	//层级的元素个数
	levelCount := 1
	for i+1 <= h.Len() {
		fmt.Println((*h)[i: i+levelCount])
		i += levelCount
		if (i + levelCount*2) <= h.Len() {
			levelCount *= 2
		} else {
			levelCount = h.Len() - i
		}
	}
}

func main() {
	a := IntHeap{6, 2, 3, 1, 5, 4};
	//初始化堆
	heap.Init(&a);
	a.PrintHeap();
	//弹出数据，保证每次操作都是规范的堆结构
	fmt.Println(heap.Pop(&a));
	a.PrintHeap();
	fmt.Println(heap.Pop(&a));
	a.PrintHeap();
	heap.Push(&a, 0);
	heap.Push(&a, 8);
	a.PrintHeap();
}

list链表的使用：

package main;

import (
	"container/list"
	"fmt"
)

func printList(l *list.List) {
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ");
	}
	fmt.Println();
}

func main() {
	//创建一个链表
	l := list.New();

	//链表最后插入元素
	a1 := l.PushBack(1);
	b2 := l.PushBack(2);

	//链表头部插入元素
	l.PushFront(3);
	l.PushFront(4);

	printList(l);

	//取第一个元素
	f := l.Front();
	fmt.Println(f.Value);

	//取最后一个元素
	b := l.Back();
	fmt.Println(b.Value);

	//获取链表长度
	fmt.Println(l.Len());

	//在某元素之后插入
	l.InsertAfter(66, a1);

	//在某元素之前插入
	l.InsertBefore(88, a1);

	printList(l);

	l2 := list.New();
	l2.PushBack(11);
	l2.PushBack(22);
	//链表最后插入新链表
	l.PushBackList(l2);
	printList(l);

	//链表头部插入新链表
	l.PushFrontList(l2);
	printList(l);

	//移动元素到最后
	l.MoveToBack(a1);
	printList(l);

	//移动元素到头部
	l.MoveToFront(a1);
	printList(l);

	//移动元素在某元素之后
	l.MoveAfter(b2, a1);
	printList(l);

	//移动元素在某元素之前
	l.MoveBefore(b2, a1);
	printList(l);

	//删除某元素
	l.Remove(a1);
	printList(l);
}

ring环的使用：

package main;

import (
	"container/ring"
	"fmt"
)

func printRing(r *ring.Ring) {
	r.Do(func(v interface{}) {
		fmt.Print(v.(int), " ");
	});
	fmt.Println();
}

func main() {
	//创建环形链表
	r := ring.New(5);
	//循环赋值
	for i := 0; i < 5; i++ {
		r.Value = i;
		//取得下一个元素
		r = r.Next();
	}
	printRing(r);
	//环的长度
	fmt.Println(r.Len());

	//移动环的指针
	r.Move(2);

	//从当前指针删除n个元素
	r.Unlink(2);
	printRing(r);

	//连接两个环
	r2 := ring.New(3);
	for i := 0; i < 3; i++ {
		r2.Value = i + 10;
		//取得下一个元素
		r2 = r2.Next();
	}
	printRing(r2);

	r.Link(r2);
	printRing(r);
}