53
单向循环链表解决约瑟夫环问题 - Golang 实现
source link: https://www.tuicool.com/articles/f2IFZr2
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
问题描述
编号为 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 Add_Jos(ring *Person, 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 Remove_Jos(ring *Person, 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) }
总结
单向循环链表与单向链表差别并不大,只是增加了一个尾部指向头部的步骤。这个例子中使用到了 head
和 tail
两个指针用来记录 ring
中的头和尾,这样方便了向其中添加新的数据,而且头尾两个指针也有效减少了在删除过程中循环遍历结点的操作。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK