Go标准容器之Ring的使用说明
作者:Cynhard85 发布时间:2023-09-21 02:18:14
简介
Go的标准包Container中包含了常用的容器类型,包括conatiner/list,container/heap,container/ring,本篇讲解container/ring的使用。
ring包
ring包提供了环形链表的操作。它仅导出了一个类型,Ring:
// Ring表示环形链表中的元素。
type Ring struct {
Value interface{} // Value类型为interface{},因此可以接受任意类型
}
// 创建一个长度为n的环形链表
func New(n int) *Ring
// 针对环形链表中的每一个元素x进行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 获取环形链表长度
func (r *Ring) Len() int
// 如果r和s在同一环形链表中,则删除r和s之间的元素,
// 被删除的元素组成一个新的环形链表,返回值为该环形链表的指针(即删除前,r->Next()表示的元素)
// 如果r和s不在同一个环形链表中,则将s插入到r后面,返回值为
// 插入s后,s最后一个元素的下一个元素(即插入前,r->Next()表示的元素)
func (r *Ring) Link(s *Ring) *Ring
// 移动 n % r.Len() 个位置,n正负均可
func (r *Ring) Move(n int) *Ring
// 返回下一个元素
func (r *Ring) Next() *Ring
// 返回前一个元素
func (r *Ring) Prev() *Ring
// 删除r后面的 n % r.Len() 个元素
func (r *Ring) Unlink(n int) *Ring
示例
Ring的用法
package main
import (
"container/ring"
"fmt"
)
func main() {
const rLen = 3
// 创建新的Ring
r := ring.New(rLen)
for i := 0; i < rLen; i++ {
r.Value = i
r = r.Next()
}
fmt.Printf("Length of ring: %d\n", r.Len()) // Length of ring: 3
// 该匿名函数用来打印Ring中的数据
printRing := func(v interface{}) {
fmt.Print(v, " ")
}
r.Do(printRing) // 0 1 2
fmt.Println()
// 将r之后的第二个元素的值乘以2
r.Move(2).Value = r.Move(2).Value.(int) * 2
r.Do(printRing) // 0 1 4
fmt.Println()
// 删除 r 与 r+2 之间的元素,即删除 r+1
// 返回删除的元素组成的Ring的指针
result := r.Link(r.Move(2))
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 1
fmt.Println()
another := ring.New(rLen)
another.Value = 7
another.Next().Value = 8 // 给 another + 1 表示的元素赋值,即第二个元素
another.Prev().Value = 9 // 给 another - 1 表示的元素赋值,即第三个元素
another.Do(printRing) // 7 8 9
fmt.Println()
// 插入another到r后面,返回插入前r的下一个元素
result = r.Link(another)
r.Do(printRing) // 0 7 8 9 4
fmt.Println()
result.Do(printRing) // 4 0 7 8 9
fmt.Println()
// 删除r之后的三个元素,返回被删除元素组成的Ring的指针
result = r.Unlink(3)
r.Do(printRing) // 0 4
fmt.Println()
result.Do(printRing) // 7 8 9
fmt.Println()
}
模拟约瑟夫问题
环形列表可以模拟约瑟夫问题。约瑟夫问题描述如下:
来自百度:
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个 * 方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须 * ,然后再由下一个重新报数,直到所有人都 * 身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
用代码模拟如下:
package main
import (
"container/ring"
"fmt"
)
type Player struct {
position int // 位置
alive bool // 是否存活
}
func main() {
const (
playerCount = 41 // 玩家人数
startPos = 1 // 开始报数位置
)
deadline := 3
r := ring.New(playerCount)
// 设置所有玩家初始值
for i := 1; i <= playerCount; i++ {
r.Value = &Player{i, true}
r = r.Next()
}
// 如果开始报数的位置不为1,则设置开始位置
if startPos > 1 {
r = r.Move(startPos - 1)
}
counter := 1 // 报数从1开始,因为下面的循环从第二个开始计算
deadCount := 0 // 死亡人数,初始值为0
for deadCount < playerCount { // 直到所有人都死亡,否则循环一直执行
r = r.Next() // 跳到下一个人
// 如果是活着的人,则报数
if r.Value.(*Player).alive {
counter++
}
// 如果报数为deadline,则此人淘汰出局
if counter == deadline {
r.Value.(*Player).alive = false
fmt.Printf("Player %d died!\n", r.Value.(*Player).position)
deadCount++
counter = 0 // 报数置成0
}
}
}
输出如下,可以看到16和31是最后两个出队列的,因此Josephus将他的朋友与自己安排在第16个与第31个位置是安全的。
Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!
补充:go语言中container容器数据结构heap、list、ring
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);
}
以上为个人经验,希望能给大家一个参考,也希望大家多多支持
来源:https://blog.csdn.net/u011304970/article/details/72830017


猜你喜欢
- python和PHP相比较,python适合做爬虫。原因如下抓取网页本身的接口相比与其他静态编程语言,如java,c#,C++,python
- python 3.10支持match语句,3,10以下不支持。match语句接受一个表达式,并将其值与作为一个或多个case块给出的连续模式
- 本文实例讲述了JS高阶函数原理与用法。分享给大家供大家参考,具体如下:如果您正在学习JavaScript,那么您必须遇到高阶函数这个术语。这
- 1、查看数据库的字符集数据库的字符集必须和Linux下设置的环境变量一致,不然会有乱码。以下两个sql语句都可以查到:select * fr
- 使用Python解析各种格式的数据都很方便,比如json、txt、xml、csv等。用于处理简单的数据完全足够用了,而且代码简单易懂。前段时
- 简介程序中的数在计算机内存中都是以二进制的形式存在的,位运算就是直接对整数在内存中对应的二进制位进行操作,一般是将数字化为二进制数后进行操作
- 我们在平常的系统开发中常常会遇到像无限级分类这样的树型结构数据,现提供一个可用的数据库存储过程,可以完成树型结构数据的排序。环境:windo
- Python实现微信表情包炸群效果,具体代码如下所示;# -*- coding = utf-8 -*-# @Time : 2021/1/26
- 在使用python爬虫技术采集数据信息时,经常会遇到在返回的网页信息中,无法抓取动态加载的可用数据。例如,获取某网页中,商品价格时就会出现此
- fileno()方法返回所使用的底层实现,要求从操作系统I/O操作的整数文件描述符。语法以下是fileno()方法的语法:fil
- 背景在开发中,我们常常会遇到一些耗时任务,举个例子:上传并解析一个 1w 条数据的 Excel 文件,最后持久化至数据库。在我的程序中,这个
- 前言说起面试,很多同学都经历过,但是 面试中 可能会遇到各种问题,MySQL 的问题 也是非常多,最近我也经常面试,也希望问一些数据库一些偏
- 一 multiprocessing模块介绍python中的多线程无法利用多核优势,如果想要充分地使用多核CPU的资源(os.cpu\_cou
- 导入模块from bs4 import BeautifulSoupsoup = BeautifulSoup(html_doc,"h
- 这篇文章主要介绍了python tkinter canvas使用实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习
- 一、前言这篇文章主要是记录一下php生成静态页面的大致步骤,关于页面静态化,大家想必都听说过,但是真正用的时候反而不是很多。有些页面考虑到访
- 本文实例为大家分享了Python网站注册验证码生成类的具体代码,供大家参考,具体内容如下# -*- coding:utf-8 -*-'
- 我们知道map() 会根据提供的函数对指定序列做映射。 第一个参数 function 以参数序列中的每一个元素调用 function函数,返
- 随机相对强弱指数简称为StochRSI,是一种技术分析指标,用于确定资产是否处于超买或超卖状态,也用于确定当前市场的态势。顾名思义,Stoc
- PHP ini_set用来设置php.ini的值,在函数执行的时候生效,脚本结束后,设置失效。无需打开php.ini文件,就能修改配置,对于