单向循环链表解决约瑟夫环问题 - Golang 实现

问题描述

编号为 1, 2, ... , n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m ,从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 的值,从他在顺时针方向上的下一个人开始重新从 1 报数,如此下去,直至所有人全部出列为止。

基本要求

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。

测试数据

7 个人的密码依次为:3, 1, 7, 2, 4, 8, 4 ;
m 值为 6 (正确的出列顺序应为 6, 1, 4, 7, 2, 3, 5)。

开始

单个结构体的实现

• 定义指针和结构体

package main
import "fmt"
// 定义结构体
type Person struct {
 num int // 序号
 code int // 密码
 next *Person
}
var head, tail *Person // 分别指向 ring 的头和尾

• 添加操作

/* 向 ring 中添加一个编号为 num ,密码为 code 的人 */
func (ring *Person) add_Jos(num int, code int) {
 current := &Person{code: code, num: num}
 if head == nil { // 当 ring 中还没有人时,使 head 和 tail 指向 current
 head = current
 current.next = head
 tail = current
 } else { // 将 current 作为 ring 的尾巴,设定 current.next 为 head
 tail.next = current
 current.next = head
 tail = current
 }
}

• 移除操作

/* 移除报到 code 的人,打印出这个人的序号并返回他的密码 */
func (ring *Person) remove_Jos(code int) int {
 if code == 1 { // 当要移除的人是 head 指向的人时
 code = head.code
 fmt.Printf("%d ", head.num)
 head = head.next
 tail.next = head // head 的指向改变,重新设定 tail.next 为 head
 return code
 }
 // 当要移除的人不是 head 指向的人时
 for i := 0; i < code-2; i++ { // 使 head 指向需要移除的人的前一个人
 head = head.next
 }
 code = head.next.code
 fmt.Printf("%d ", head.next.num)
 tail = head // 此时 head 指向的人作为新的 tail
 head = head.next.next // head 指向需要移除的人的下一个人,他作为新的 head
 tail.next = head // head 的指向改变,重新设定 tail.next 为 head
 return code
}

• 执行操作

/* 执行操作,m 为设定的初值 */
func Run_Jos(ring *Person, m int) {
 code := m
 for head != tail { // 当 head 和 tail 不指向同一个人时( ring 中剩余人数大于 1 )
 code = Remove_Jos(ring, code) // 进行移除操作并获取新的密码
 }
 fmt.Print(head.num) // 将 ring 中的最后一个人的序号打印出来
}

• 主函数

func main() {
 var ring *Person
 // 添加测试数据
 Add_Jos(ring, 1, 3)
 Add_Jos(ring, 2, 1)
 Add_Jos(ring, 3, 7)
 Add_Jos(ring, 4, 2)
 Add_Jos(ring, 5, 4)
 Add_Jos(ring, 6, 8)
 Add_Jos(ring, 7, 4)
 Run_Jos(ring, 6)
}

• 运行结果

6 1 4 7 2 3 5

• 总结

单向循环链表与单向链表差别并不大,只是增加了一个尾部指向头部的步骤。这个例子中使用到了 head 和 tail 两个指针用来记录 ring 中的头和尾,这样方便了向其中添加新的数据,而且头尾两个指针也有效减少了在删除过程中循环遍历结点的操作。

多个结构体的实现

• 定义结构体

package main
import "fmt"
type Person struct {
 num int // 序号
 code int // 密码
 next *Person // 指向下一个 Person
}
type Ring struct {
 head *Person // ring 的头
 tail *Person // ring 的尾
 count int // ring 中的元素数目
}

• 判断 Ring 是否为空

func (ring *Ring) isEmpty() bool {
 if ring.head != nil { // 当 head 值为 nil 时 ring 为空
 return false
 }
 return true
}

• 添加操作

func (ring *Ring) add(code int) {
 ring.count++ // 放在片段开头是为了方便设定 Person 的 num 属性
 if ring.isEmpty() { // ring 为空时首尾相同
 ring.tail = &Person{ring.count, code, nil}
 ring.head = ring.tail
 } else {
 oldTail := ring.tail // 暂存 tail
 ring.tail = &Person{ring.count, code, nil}
 oldTail.next = ring.tail
 }
 ring.tail.next = ring.head // 确保循环性
}

• 移除操作

// 根据密码值移除 Person ,有 num 和 code 两个返回值
func (ring *Ring) outFor(code int) (num int, _ int) {
 if code < 1 { // 值 -1 标志传入参数值非法
 return -1, -1
 } else if code == 1 { // 当需要移除的是 head
 code = ring.head.code
 num = ring.head.num
 ring.tail.next = ring.head.next
 ring.head = ring.tail.next
 } else { // 使用 current 确定移除位置
 current := ring.head
 for i := 0; i < code-2; i++ {
 current = current.next
 } // 循环结束后 current 指向需要移除的前一个位置
 code = current.next.code
 num = current.next.num
 ring.tail = current // current 为新的 tail
 ring.head = current.next.next // current.next 变成了孤儿,Golang 提供了自动回收机制
 ring.tail.next = ring.head // 确保循环性
 }
 ring.count--
 return num, code
}

• 执行操作

func (ring *Ring) run(code int) {
 var num int
 for ring.head != ring.tail { // 依次打印满足条件时移除元素的 num 值
 num, code = ring.outFor(code)
 fmt.Printf("%d ", num)
 }
 fmt.Print(ring.head.num) // 打印 ring 中最后一个元素的 num 值
}

• 主函数

func main() {
 // run 方法的测试
 {
 var ring Ring
 ring.add(3)
 ring.add(1)
 ring.add(7)
 ring.add(2)
 ring.add(4)
 ring.add(8)
 ring.add(4)
 ring.run(6)
 }
}

• 运行结果

6 1 4 7 2 3 5

• 总结

相比于使用单个结构体实现来说,这种方法避免了独立于结构体之外的 head 和 tail 指针的使用,在程序中减少了指针的操作,主体更容易理解。

本文来自:Segmentfault

感谢作者:孟显赫

查看原文:单向循环链表解决约瑟夫环问题 - Golang 实现

• 编辑
• 预览