C++链表开发问题

Question

#include <iostream>
using namespace std;
struct child
{
    int num;
    child *link;
};
;void init(int n);
;void gameStart(int n,int m);
child *head;
child *present;
child *end;
;int main()
{
    int n,m;
    cout <<"请输入孩子的个数：";
    cin >>n;
    cout <<"请输入正整数m：";
    cin >>m;
    init(n);
    gameStart(n,m);
    cout <<"第" <<present->num <<"个孩子将获得胜利！" <<endl;
    delete present;
    return 0;
}
void init(int n)
{
    head=new child;
    head->num=1;
    present=head;
    for (int i=1;i<n;i++)
    {
        present->link=new child;
        present->link->num=i+1;
        present=present->link;
    }
    present->link=head;
    end=present;
    present=head;
}
void gameStart(int n,int m)
{
    child *pGuard=end;
    while (n!=1)
    {
        for (int j=1;j<m;j++)
        {
            pGuard=present;
            present=present->link;
        }
        pGuard->link=present->link;
        delete present;
        present=pGuard->link;
        n--;
    }
}

这是个约瑟夫环问题
我想问下

present->link=head;
end=present;
present=head;

具体什么意思
貌似是将首尾相连形成循环链表吧。。
请详细解释下。。谢谢！ 求解。。

Answer 1

@洃c小强 大半夜的看到这道题目，我来补充一下吧。

---

约瑟夫环的问题是说，有编号为1..n的n个犯人围坐成一圈报数，报数为m的犯人出列被kill掉，然后刚才出列犯人的下一位从1开始报数，以此类推，最终只剩一个人为止。并报告此人的编号g(n,m)。
这是计算机算法的一道经典题目。
常规的解法是根据题目进行建模。
其中

struct child{
    int num;
    child *link;
};

是犯人的模型，每个犯人有一个编号num，同时有下一个编号犯人的指针link，这样，能够建立一个单向链表。
但是，约瑟夫环是首尾循环的，所以，需要present->link=head;来将单向链表变成环链表。
完成模型建构以后，需要指定开始和结束的位置

end=present;
present=head;

就是用来完成这一功能的。
之后的gameStart就是完成根据条件删除链表节点的功能。

除去约瑟夫环的背景，其实，这段程序的基本功能只有两个：1.构建环链表；2.根据条件删除环链表节点；
这样程序就容易理解多了。^-^

另外，题目中的解法是利用模拟的办法来解决约瑟夫环的问题的。其实，在数学上，关于约瑟夫环g(n,m)=?是有直接答案的。

g(n,m) = (g(n – 1) + m) % n, (n > 1)

用Python写出的代码如下：

def josephus(n, m):
    j = 0
    for i in range(2, n + 1):
        j = (j + m) % i
    print j + 1

大概就是这些吧。

Answer 2

我没仔细看也不懂约瑟夫环也不会c++.不过看样子是

present->link=head;
end=present;
present=head;

这三句话的意图是重置present与present的link还有end指针使之都指向链表头而已,也就是说这时候约瑟夫环已经构建完毕,可以把指针都设置为链表初始值以待后用了,再看看函数名为init,我想我的推测完全没错