自己动手用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

来源：https://blog.51cto.com/pmghong/2462943