自己动手用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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。