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

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