跳到主要内容

六：单向环形链表应用实例的约瑟夫环问题

前言​

一、约瑟夫介绍​

  • Josepfu（约瑟夫、约瑟夫环）问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1&lt;=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
  • 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
  • 又称丢手帕问题
     

二、单向环形链表​

单向环形链表如下图所示，就是最后的尾节点-》指向了第一个头结点。
 

三、思路分析​

3.1 约瑟夫环的分析​

  • 假定有5个小孩节点，首位相接，使用环形单链表方式，如图所示：
     
  • Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
    假定 ：
    n = 5 , 即有5个人
    k = 1, 从第一个人开始报数
    m = 2, 数2下
  • 那么出圈的顺序为：2->4-&gt;1->5-&gt;3，