单向循环链表解决约瑟夫环问题 - 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 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)
}

总结

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

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章