自己动手用Golang实现约瑟夫环算法的示例
继上一篇单向链表，单线链表可以进一步扩展为环，如下图所示：
特点：
1、第一个节点称为头部节点，最后一个节点称为尾部节点
2、每个节点都单方面的指向下一个节点
3、尾部节点下一个节点指向头部节点
题目：
17世纪的法国数学家加斯帕讲了这样一个故事：15个教徒和15个非教徒，在深海海上遇险，必须将一半的人投入海海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海海的都是非教徒。
这就是典型的约瑟夫环问题，可以用单向链表环解决，具体代码如下：
packagemain
import"fmt"
typeLinkNodestruct{
Datainterface{}
Next*LinkNode
}
typeSingleLinkstruct{
head*LinkNode
tail*LinkNode
sizeint
}
//初始化链表
funcInitSingleLink()(*SingleLink){
return&SingleLink{
head:nil,
tail:nil,
size:0,
}
}
//获取头部节点
func(sl*SingleLink)GetHead()*LinkNode{
returnsl.head
}
//获取尾部节点
func(sl*SingleLink)GetTail()*LinkNode{
returnsl.tail
}
//打印链表
func(sl*SingleLink)Print(){
fmt.Println("SingleLinksize:",sl.Length())
ifsl.size==0{
return
}
ptr:=sl.GetHead()
headNode:=sl.GetHead()
forptr!=nil{
fmt.Println("Data:",ptr.Data)
ptr=ptr.Next
ifptr.Next==headNode{
fmt.Println("Data:",ptr.Data)
break
}
}
}
//链表长度
func(sl*SingleLink)Length()int{
returnsl.size
}
//插入数据（头插）
func(sl*SingleLink)InsertByHead(node*LinkNode){
ifnode==nil{
return
}
//判断是否第一个节点
ifsl.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){
ifnode==nil{
return
}
//插入第一个节点
ifsl.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(indexint,node*LinkNode){
ifnode==nil{
return
}
//往头部插入
ifindex==0{
sl.InsertByHead(node)
}else{
ifindex>sl.Length(){
return
}elseifindex==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(indexint){
ifsl.Length()==0||index>sl.Length(){
return
}
//删除第一个节点
ifindex==0{
sl.head=sl.head.Next
sl.tail.Next=sl.head
}else{
preNode:=sl.Search(index-1)
ifindex!=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(indexint)(node*LinkNode){
ifsl.Length()==0||index>sl.Length(){
returnnil
}
//是否头部节点
ifindex==0{
returnsl.GetHead()
}
node=sl.head
fori:=0;i<=index;i++{
node=node.Next
}
return
}
func(sl*SingleLink)pop(){
popIndex:=8
delNode:=sl.Search(popIndex)
fmt.Println("POPnode:",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)
}
funcmain(){
//初始化链表
sl:=InitSingleLink()
//生成30个元素的环
fori:=0;i<30;i++{
snode:=&LinkNode{
Data:i,
}
sl.InsertByIndex(i,snode)
}
//循环淘汰第9个元素
varroundint
forsl.size>15{
fmt.Printf("================Round%d================\n",round)
sl.pop()
round++
}
//获胜者
fmt.Println("================Finish================")
fmt.Println("Peoplewhosurvived.")
sl.Print()
}
执行结果
================Round0================
POPnode: 9
Head:10,Tail:8
================Round1================
POPnode: 19
Head:20,Tail:18
================Round2================
POPnode: 29
Head:0,Tail:28
================Round3================
POPnode: 10
Head:11,Tail:8
================Round4================
POPnode: 21
Head:22,Tail:20
================Round5================
POPnode: 2
Head:3,Tail:1
================Round6================
POPnode: 14
Head:15,Tail:13
================Round7================
POPnode: 26
Head:27,Tail:25
================Round8================
POPnode: 8
Head:11,Tail:7
================Round9================
POPnode: 23
Head:24,Tail:22
================Round10================
POPnode: 6
Head:7,Tail:5
================Round11================
POPnode: 22
Head:24,Tail:20
================Round12================
POPnode: 7
Head:11,Tail:5
================Round13================
POPnode: 25
Head:27,Tail:24
================Round14================
POPnode: 13
Head:15,Tail:12
================Finish================
Peoplewhosurvived.
SingleLinksize: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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。