C++链表开发问题

Question

#include
usingnamespacestd;
structchild
{
intnum;
child*link;
};
;voidinit(intn);
;voidgameStart(intn,intm);
child*head;
child*present;
child*end;
;intmain()
{
intn,m;
cout<<"请输入孩子的个数：";
cin>>n;
cout<<"请输入正整数m：";
cin>>m;
init(n);
gameStart(n,m);
cout<<"第"<num<<"个孩子将获得胜利！"<deletepresent;
return0;
}
voidinit(intn)
{
head=newchild;
head->num=1;
present=head;
for(inti=1;i{
present->link=newchild;
present->link->num=i+1;
present=present->link;
}
present->link=head;
end=present;
present=head;
}
voidgameStart(intn,intm)
{
child*pGuard=end;
while(n!=1)
{
for(intj=1;j{
pGuard=present;
present=present->link;
}
pGuard->link=present->link;
deletepresent;
present=pGuard->link;
n--;
}
}
这是个约瑟夫环问题
我想问下
present->link=head;
end=present;
present=head;
具体什么意思
貌似是将首尾相连形成循环链表吧。。
请详细解释下。。谢谢！求解。。

Answer 1

@洃c小强大半夜的看到这道题目，我来补充一下吧。约瑟夫环的问题是说，有编号为1..n的n个犯人围坐成一圈报数，报数为m的犯人出列被kill掉，然后刚才出列犯人的下一位从1开始报数，以此类推，最终只剩一个人为止。并报告此人的编号g(n,m)。这是计算机算法的一道经典题目。常规的解法是根据题目进行建模。其中structchild{intnum;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写出的代码如下：defjosephus(n,m):j=0foriinrange(2,n+1):j=(j+m)%iprintj+1大概就是这些吧。

Answer 2

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