自己动手用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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。