循环链表解决约瑟夫环问题

Love The Way You Lie 2022-04-10 08:22 172阅读 0赞

约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。

什么是约瑟夫环？

“约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。”（[百度百科][Link 1]中的解决办法列出了很多，可以看到循环链表并不是最简单的方法）

这道面试题考察了循环链表的“创建”，“遍历”和“删除”。

创建的循环链表的结构图：

![2012101015571941.jpg][]

解决约瑟夫环问题的过程

![2012101016082279.jpg][]

C++实现代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 循环链表解决约瑟夫问题

1 /**循环链表解决约瑟夫环问题
     2  * 问题：约瑟夫环
     3  * 有编号从1到N的N个人坐成一圈报数，从第K个人开始报数，报到M的人出局，
     4  * 下一位再从1开始报数，如此持续，直止剩下一位为止，报告此人的编号X。
     5  * 输入N,K,M，求出X。
     6  */
     7 
     8 #include <iostream>
     9 using namespace std;
    10 
    11 struct MyNode
    12 {
    13     MyNode(int a_data):m_data(a_data),m_pNext(NULL) {}
    14     
    15     int    m_data;
    16     MyNode *m_pNext;
    17 };
    18 
    19 class Josephus
    20 {
    21 public:
    22     Josephus(int a_N, int a_K, int a_M):m_N(a_N),m_K(a_K),m_M(a_M)
    23     {
    24         createList();
    25         outputList();
    26     }
    27     
    28 protected:
    29     void createList();
    30     void outputList();
    31     
    32 private:
    33     MyNode *m_pHead;//循环链表的头节点
    34     int    m_N;     //链表节点个数
    35     int    m_K;     //第一个报数人的序号
    36     int    m_M;     //报数出局的数
    37 };
    38 
    39 void Josephus::createList()
    40 {
    41     MyNode *pre = NULL;
    42     MyNode *cur = NULL;
    43     MyNode *p = new MyNode(1);
    44     m_pHead = p;
    45     cur = p;
    46     for (int i=2; i<=m_N; i++)
    47     {
    48         p = new MyNode(i);
    49         pre = cur;
    50         cur = p;
    51         pre->m_pNext = cur;
    52     }
    53     cur->m_pNext = m_pHead;
    54     
    55     int n=m_N;
    56     p = m_pHead;
    57     while (n--)
    58     {
    59         cout << p->m_data << ",";
    60         p = p->m_pNext;
    61     }
    62     cout << endl;
    63 }
    64 
    65 void Josephus::outputList()
    66 {
    67     MyNode *pre = NULL;
    68     MyNode *cur = m_pHead;
    69     m_K--;
    70     while (m_K--)            //寻找第K个人（开始报数的人）
    71     {
    72         pre = cur;
    73         cur = cur->m_pNext;
    74     }
    75     while (m_N--)            //输出链表中所有的节点值
    76     {
    77         int s = m_M-1;
    78         while (s--)            //寻找间隔M的人
    79         {
    80             pre = cur;
    81             cur = cur->m_pNext;
    82         }
    83         MyNode *p = cur;
    84         cout << p->m_data << ",";
    85         cur = cur->m_pNext;    //删除节点的过程
    86         pre->m_pNext = cur;
    87         delete p;
    88         p=NULL;
    89     }
    90 }
    91 
    92 int main()
    93 {
    94     Josephus josephus(100,5,5);
    95     return 0;
    96 }

测试结果：

![2012101015463765.jpg][]

[Link 1]: http://baike.baidu.com/view/717633.htm#3
[2012101015571941.jpg]: /images/20220401/ba7c8a3b7176405d8f92340abeb4fcb6.png
[2012101016082279.jpg]: /images/20220401/2da69ec2ca704a95b5c3fdc300e029f3.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220401/9367d495170d4326940bc043f07757c9.png
[2012101015463765.jpg]: /images/20220401/b113ad29ca144573a48bef980cafc2d1.png