这篇文章主要介绍了自己动手用Golang实现约瑟夫环算法的示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

继上一篇单向链表,单线链表可以进一步扩展为环,如下图所示:

特点:

1、第一个节点称为头部节点,最后一个节点称为尾部节点

2、每个节点都单方面的指向下一个节点

3、尾部节点下一个节点指向头部节点

题目:

17世纪的法国数学家加斯帕讲了这样一个故事: 15个教徒和15 个非教徒,在深海海上遇险,必须将一半的人投入海海中,其余的人才能幸免于难,于是想了一个办法: 30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海海的都是非教徒。

这就是典型的约瑟夫环问题,可以用单向链表环解决,具体代码如下:

package main

import "fmt"

type LinkNode struct {
 Data interface{}
 Next *LinkNode
}

type SingleLink struct {
 head *LinkNode
 tail *LinkNode
 size int
}

// 初始化链表
func InitSingleLink()(*SingleLink){
 return &SingleLink{
 head:nil,
 tail:nil,
 size:0,
 }
}

// 获取头部节点
func (sl *SingleLink)GetHead()*LinkNode{
 return sl.head
}

// 获取尾部节点
func (sl *SingleLink)GetTail()*LinkNode{
 return sl.tail
}

// 打印链表
func (sl *SingleLink) Print(){
 fmt.Println("SingleLink size:",sl.Length())
 if sl.size == 0{
 return
 }
 ptr := sl.GetHead()
 headNode := sl.GetHead()
 for ptr != nil{
 fmt.Println("Data:",ptr.Data)
 ptr = ptr.Next
 if ptr.Next == headNode{
  fmt.Println("Data:",ptr.Data)
  break
 }
 }
}

//链表长度
func (sl *SingleLink) Length() int{
 return sl.size
}

//插入数据(头插)
func (sl *SingleLink) InsertByHead(node *LinkNode){
 if node == nil{
 return
 }
 // 判断是否第一个节点
 if sl.Length() == 0{
 sl.head = node
 sl.tail = node
 node.Next = nil
 }else{
 oldHeadNode := sl.GetHead()
 sl.head = node
 sl.tail.Next = node
 sl.head.Next = oldHeadNode
 }
 sl.size++
}

//插入数据(尾插)
func (sl *SingleLink) InsertByTail(node *LinkNode) {
 if node == nil{
 return
 }
 // 插入第一个节点
 if sl.size == 0{
 sl.head = node
 sl.tail = node
 node.Next = nil
 }else{
 sl.tail.Next = node
 node.Next = sl.head
 sl.tail = node
 }
 sl.size ++
}

//插入数据(下标)位置
func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){
 if node == nil{
 return
 }
 // 往头部插入
 if index == 0 {
 sl.InsertByHead(node)
 }else{
 if index > sl.Length(){
  return
 }else if index == sl.Length(){
  //往尾部添加节点
  sl.InsertByTail(node)
 }else{
  preNode := sl.Search(index-1)   // 下标为 index 的上一个节点
  currentNode := sl.Search(index) // 下标为 index 的节点
  preNode.Next = node
  node.Next = currentNode
  sl.size++
 }
 }
}

//删除数据(下标)位置
func (sl *SingleLink) DeleteByIndex(index int) {
 if sl.Length() == 0 || index > sl.Length(){
 return
 }
 // 删除第一个节点
 if index == 0{
 sl.head = sl.head.Next
 sl.tail.Next = sl.head
 }else{
 preNode := sl.Search(index-1)
 if index != sl.Length()-1{
  nextNode := sl.Search(index).Next
  preNode.Next = nextNode
 }else{
  sl.tail = preNode
  preNode.Next = sl.head
 }
 }
 sl.size--
}

// 查询数据
func (sl *SingleLink) Search(index int)(node *LinkNode) {
 if sl.Length() == 0 || index > sl.Length(){
 return nil
 }
 // 是否头部节点
 if index == 0{
 return sl.GetHead()
 }
 node = sl.head
 for i:=0;i<=index;i++{
 node = node.Next
 }
 return
}


func (sl *SingleLink)pop(){
 popIndex := 8
 delNode := sl.Search(popIndex)
 fmt.Println("POP node : ",delNode.Data)
 sl.DeleteByIndex(popIndex)
 sl.tail = sl.Search(popIndex - 1)
 sl.head = sl.Search(popIndex)
 fmt.Printf("Head:%v , Tail:%v\n",sl.head.Data,sl.tail.Data)
}

func main() {
 // 初始化链表
 sl := InitSingleLink()

 // 生成30个元素的环
 for i:=0;i<30;i++{
 snode := &LinkNode{
  Data:i,
 }
 sl.InsertByIndex(i,snode)
 }

 //循环淘汰第9个元素
 var round int
 for sl.size > 15{
 fmt.Printf("================ Round %d ================\n",round)
 sl.pop()
 round ++
 }

 // 获胜者
 fmt.Println("================ Finish ================")
 fmt.Println("People who survived.")
 sl.Print()
}

执行结果

================ Round 0 ================
POP node :  9
Head:10 , Tail:8
================ Round 1 ================
POP node :  19
Head:20 , Tail:18
================ Round 2 ================
POP node :  29
Head:0 , Tail:28
================ Round 3 ================
POP node :  10
Head:11 , Tail:8
================ Round 4 ================
POP node :  21
Head:22 , Tail:20
================ Round 5 ================
POP node :  2
Head:3 , Tail:1
================ Round 6 ================
POP node :  14
Head:15 , Tail:13
================ Round 7 ================
POP node :  26
Head:27 , Tail:25
================ Round 8 ================
POP node :  8
Head:11 , Tail:7
================ Round 9 ================
POP node :  23
Head:24 , Tail:22
================ Round 10 ================
POP node :  6
Head:7 , Tail:5
================ Round 11 ================
POP node :  22
Head:24 , Tail:20
================ Round 12 ================
POP node :  7
Head:11 , Tail:5
================ Round 13 ================
POP node :  25
Head:27 , Tail:24
================ Round 14 ================
POP node :  13
Head:15 , Tail:12
================ Finish ================
People who survived.
SingleLink size: 15
Data: 15
Data: 16
Data: 17
Data: 18
Data: 20
Data: 24
Data: 27
Data: 28
Data: 0
Data: 1
Data: 3
Data: 4
Data: 5
Data: 11
Data: 12

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持爱安网。

最新资讯
造车新势力格局大洗牌 竞逐智能化

造车新势力格局大洗牌

“中国市场还需不需要新品牌”的争论,在造车新势力车企
上海临港将打造全产业链生态 聚焦芯片、AI等前沿产业

上海临港将打造全产业

9月24日,上海市经信委、临港新片区管委会等7部门联合印
智能汽车操作系统之争:两条路线仍在博弈

智能汽车操作系统之争

汽车产业正面临巨大变革,“智能座舱”“人机交互”已成
央行副行长:我国支付产业数字化水平不断提高

央行副行长:我国支付产

中国人民银行副行长范一飞24日表示,我国支付产业数字化
罗永浩还清4亿债 再创业还需修炼内功“多做少说”

罗永浩还清4亿债 再创

企业家还需要善于合作及整合各种外部资源的精神。
房产代理移植网络基因已是大势所趋

房产代理移植网络基因

互联网就像金手指。它正在赋予房产代理这个传统的行业
最新文章
GoLang 逃逸分析的机制详解

GoLang 逃逸分析的机

这篇文章主要介绍了GoLang-逃逸分析的机制详解,文中通
golang 生成二维码海报的实现代码

golang 生成二维码海

这篇文章主要介绍了golang 生成二维码海报的实现代码,
golang语言实现的文件上传与文件下载功能示例

golang语言实现的文件

这篇文章主要介绍了golang语言实现的文件上传与文件下
Golang 实现插入排序的方法示例(2种)

Golang 实现插入排序

这篇文章主要介绍了Golang 实现插入排序的方法示例,文
图文详解go语言反射实现原理

图文详解go语言反射实

这篇文章主要介绍了图文详解go语言反射实现原理,本文
Golang中的Slice与数组及区别详解

Golang中的Slice与数

数组是一种具有固定长度的基本数据结构,在golang中与C