第八章：第7节 PHP数据结构与算法——环形链表强化学习一（约瑟夫问题）
更新于：2017-06-24 17:44:06
约瑟夫问题-环形链表典型应用：
m 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 n 个人，令其出列。然后再从下一个人开始从 1 顺时针报数，报到第 n 个人，再令其出列，……如此下去，求出列顺序。
假设 m = 8，n=3，看图示：
约瑟夫问题特像小朋友爱玩的丢手绢游戏
接下来开始分享下韩顺平的“丢手绢”代码笔记：
思路：
（一）构建一个环形链表，链表上的每个节点，表示一个小朋友
定义一个小朋友类：
一个小朋友的情况
两个小朋友的情况
当第一个结点做完以后，1号小朋友还有一个新的指向指向它，就是cur。cur的用处，当有2号小朋友的时候，cur就发挥作用了，此时cur还是指向1号小朋友，那么$cur->next=$child;则①号线就被搭起来了，然后$child->next=$first;则②号线就被搭起来了，2号小朋友结点就指向了1号小朋友结点，环形链表就形成了。$cur=$cur->next;则cur就由原来的指向1号小朋友转为指向2号小朋友了，如图中③号线所示，这样就可以再加第3个小朋友了，依次类推。
定义添加小朋友函数和显示函数：
开始添加小朋友，并显示结果：
为什么现在只显示三个小孩呢，分析一下代码在内存中是怎么运作的
（1）语句①执行后，cur也指向了1号小朋友；
（2）然后语句②执行，进入while循环，此时cur指向1号小朋友，执行语句③，输出：小孩的编号是1，再执行语句④$cur=$cur->next;
（3）此时cur指向2号小朋友，然后语句②执行，进入while循环，此时cur指向2号小朋友，执行语句③，输出：小孩的编号是2，再执行语句④$cur=$cur->next;
（4）此时cur指向3号小朋友，，然后语句②执行，进入while循环，此时cur指向3号小朋友，执行语句③，输出：小孩的编号是3，再执行语句④$cur=$cur->next;
（5）此时cur指向4号小朋友，然后执行语句②，此时$cur->next，就指向了1号小朋友，而first也指向1号小朋友，此时$cur->next!=$first;不成立了，为假，就退出了while循环，因此就少了一个小孩，即4号小朋友。
需要对show_child函数多加一行代码，第38行代码：
注意：function add_child(&$first,$n){ //此处$first前面为什么要加地址符&呢?
变量$first是不是在add_child函数里被赋值了。通过第四章32节学习我们知道，函数的参数可以引用传值的，一个函数往函数外传值，不仅可以用“return”语句结构，还可以通过引用传值的方式。
14行代码前，$first的值还是NULL，14行代码后$first的值变成了Child的一个实例化对象——环形链表的第一个小朋友节点。
所以，如果 function add_child(&$first,$n){ 没有&符号，第15行$first的值还是NULL，那程序就会报错了。