                        <div class="htmledit_views">

文西马龙：http://blog.csdn.net/wenximalong/

现在我们对单链表有了基本的了解，现在学习一下环形链表。
环形链表的内存示意图
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理
环形链表的好处：可以模拟许多实际的情景
如丢手帕问题，就是经典的用环形链表来解决的

现在我们来完成约瑟夫问题的解决方案！
Josephu问题
Josephu问题为：射编号为1，2，…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？
提示：用一个不带头节点的循环链表来处里Josephu问题，先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。

思路：
（一）构建一个环形链表，链表上的每个节点，表示一个小朋友（PHP语言实现）
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理
一个小朋友的情况

两个小朋友的情况

当第一个结点做完以后，1号小朋友还有一个新的指向指向它，就是cur。cur的用处，当有2号小朋友的时候，cur就发挥作用了，此时cur还是指向1号小朋友，那么cur->next=child;则①号线就被搭起来了，然后child->next=first;则②号线就被搭起来了，2号小朋友结点就指向了1号小朋友结点，环形链表就形成了。 cur= cur->next;则cur就由原来的指向1号小朋友转为指向2号小朋友了，如图中③号线所示，这样就可以再加第3个小朋友了，依次类推。
（二）写一个函数来显示所有的小孩子
josephu.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>约瑟夫问题解决</h1>
<?php
//先构建一个环形链表，链表上的每个节点，表示一个小朋友
//小孩类
class Child{
public no;  </li><li class="">                public ;
public next=null;
//构造函数
public function __construct(no){  </li><li class="alt">                    $this->no=$no;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //定义一个指向第一个小朋友的引用  </li><li class="alt">            //定义一个空头  </li><li class="">            ){
$this->no=$no;
}
}
//定义一个指向第一个小朋友的引用
//定义一个空头
first=null;
n=4; //=4; //n表示有几个小朋友
//写一个函数来创建一个四个小朋友的环形链表
/*
addChild函数的作用是：把 n个小孩在构建成一个环形链表， first变量就指向该环形链表的第一个小孩子
*/
function addChild(& first,<spanclass="vars"> ,n){ //此处要加地址符
//1.头结点不能动 first不能动  </li><li class="">
cur=first;  </li><li class="alt">                for(;
for(i=0;i<<n;i++){  </li><li class="">                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的  </li><li class="alt">                    //怎么构成一个环形链表呢  </li><li class="">                    if($i==0){ //第一个小孩的情况  </li><li class="alt">                        $first=$child; //让first指向child，但是还没有构建环形链表  </li><li class="">                        $first->next=$child; //自己指向自己  </li><li class="alt">                        $cur=$first;  </li><li class="">                    }else{  </li><li class="alt">                        $cur->next=$child;  </li><li class="">                        $child->next=$first;  </li><li class="alt">                        //继续指向下一个  </li><li class="">                        $cur=$cur->next;  </li><li class="alt">                    }  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //遍历所有的小孩，并显示  </li><li class="alt">            function showChild(++){
$child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
//怎么构成一个环形链表呢
if($i==0){ //第一个小孩的情况
$first=$child; //让first指向child，但是还没有构建环形链表
$first->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild(first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
cur=<spanclass="vars"> =first;
while(cur->next!=->next!=first){ //cur没有到结尾，就遍历
//显示
echo‘ 小孩的编号是’.cur->no;  </li><li class="alt">                    //继续  </li><li class="">                    ->no;
//继续
cur=cur->next;  </li><li class="alt">                }  </li><li class="">            }  </li><li class="alt">            addChild(->next;
}
}
addChild(first,n);  </li><li class="">            showChild();
showChild(first);
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>约瑟夫问题解决</h1>
        <?php
            //先构建一个环形链表，链表上的每个节点，表示一个小朋友
            //小孩类
            class Child{
                public $no;
                public $next=null;
                //构造函数
                public function __construct($no){
                    $this-&gt;no=$no;
                }
            }
            //定义一个指向第一个小朋友的引用
            //定义一个空头
            $first=null;
            $n=4; //$n表示有几个小朋友
            //写一个函数来创建一个四个小朋友的环形链表
            /*
             addChild函数的作用是：把$n个小孩在构建成一个环形链表，$first变量就指向该环形链表的第一个小孩子
             */
            function addChild(&$first,$n){ //此处要加地址符
                //1.头结点不能动 $first不能动
                $cur=$first;
                for($i=0;$i<$n;$i++){
                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
                    //怎么构成一个环形链表呢
                    if($i==0){ //第一个小孩的情况
                        $first=$child; //让first指向child，但是还没有构建环形链表
                        $first-&gt;next=$child; //自己指向自己
                        $cur=$first;
                    }else{
                        $cur-&gt;next=$child;
                        $child-&gt;next=$first;
                        //继续指向下一个
                        $cur=$cur->next;
                    }
                }
            }
            //遍历所有的小孩，并显示
            function showChild($first){
                //遍历 cur变量是帮助我们遍历循环列表的，所以不能动
                $cur=$first;
                while($cur-&gt;next!=$first){ //cur没有到结尾，就遍历
                    //显示
                    echo'<br/>小孩的编号是'.$cur->no;
                    //继续
                    $cur=$cur->next;
                }
            }
            addChild($first,$n);
            showChild($first);
        ?>
    </body>
</html>

韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

为什么现在只显示三个小孩呢，分析一下代码在内存中是怎么运作的

图片大，在新窗口中打开图片，观看完整图片

（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号小朋友。
所以要对josephu.php修改，即josephu2.php
josephu2.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>约瑟夫问题解决</h1>
<?php
//先构建一个环形链表，链表上的每个节点，表示一个小朋友
//小孩类
class Child{
public no;  </li><li class="">                public ;
public next=null;
//构造函数
public function __construct(no){  </li><li class="alt">                    $this->no=$no;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //定义一个指向第一个小朋友的引用  </li><li class="alt">            //定义一个空头  </li><li class="">            ){
$this->no=$no;
}
}
//定义一个指向第一个小朋友的引用
//定义一个空头
first=null;
n=4; //=4; //n表示有几个小朋友
//写一个函数来创建一个四个小朋友的环形链表
/*
addChild函数的作用是：把 n个小孩在构建成一个环形链表， first变量就指向该环形链表的第一个小孩子
*/
function addChild(& first,<spanclass="vars"> ,n){ //此处要加地址符
//1.头结点不能动 first不能动  </li><li class="">
cur=first;  </li><li class="alt">                for(;
for(i=0;i<<n;i++){  </li><li class="">                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的  </li><li class="alt">                    //怎么构成一个环形链表呢  </li><li class="">                    if($i==0){ //第一个小孩的情况  </li><li class="alt">                        $first=$child; //让first指向child，但是还没有构建环形链表  </li><li class="">                        $first->next=$child; //自己指向自己  </li><li class="alt">                        $cur=$first;  </li><li class="">                    }else{  </li><li class="alt">                        $cur->next=$child;  </li><li class="">                        $child->next=$first;  </li><li class="alt">                        //继续指向下一个  </li><li class="">                        $cur=$cur->next;  </li><li class="alt">                    }  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //遍历所有的小孩，并显示  </li><li class="alt">            function showChild(++){
$child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
//怎么构成一个环形链表呢
if($i==0){ //第一个小孩的情况
$first=$child; //让first指向child，但是还没有构建环形链表
$first->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild(first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
cur=<spanclass="vars"> =first;
while(cur->next!=->next!=first){ //cur没有到结尾，就遍历
//显示
echo‘ 小孩的编号是’.cur->no;  </li><li class="alt">                    //继续  </li><li class="">                    ->no;
//继续
cur=cur->next;  </li><li class="alt">                }  </li><li class="">                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点  </li><li class="alt">                echo' 小孩的编号是'.->next;
}
//当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
echo' 小孩的编号是'.cur->no;
}
addChild( first,<spanclass="vars"> ,n);
showChild($first);
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>约瑟夫问题解决</h1>
        <?php
            //先构建一个环形链表，链表上的每个节点，表示一个小朋友
            //小孩类
            class Child{
                public $no;
                public $next=null;
                //构造函数
                public function __construct($no){
                    $this-&gt;no=$no;
                }
            }
            //定义一个指向第一个小朋友的引用
            //定义一个空头
            $first=null;
            $n=4; //$n表示有几个小朋友
            //写一个函数来创建一个四个小朋友的环形链表
            /*
             addChild函数的作用是：把$n个小孩在构建成一个环形链表，$first变量就指向该环形链表的第一个小孩子
             */
            function addChild(&$first,$n){ //此处要加地址符
                //1.头结点不能动 $first不能动
                $cur=$first;
                for($i=0;$i<$n;$i++){
                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
                    //怎么构成一个环形链表呢
                    if($i==0){ //第一个小孩的情况
                        $first=$child; //让first指向child，但是还没有构建环形链表
                        $first-&gt;next=$child; //自己指向自己
                        $cur=$first;
                    }else{
                        $cur-&gt;next=$child;
                        $child-&gt;next=$first;
                        //继续指向下一个
                        $cur=$cur->next;
                    }
                }
            }
            //遍历所有的小孩，并显示
            function showChild($first){
                //遍历 cur变量是帮助我们遍历循环列表的，所以不能动
                $cur=$first;
                while($cur-&gt;next!=$first){ //cur没有到结尾，就遍历
                    //显示
                    echo'<br/>小孩的编号是'.$cur->no;
                    //继续
                    $cur=$cur->next;
                }
                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
                echo'<br/>小孩的编号是'.$cur->no;
            }
            addChild($first,$n);
            showChild($first);
        ?>
    </body>

</html>

注意：function addChild(& first, n){ //此处$first前面为什么要加地址符&呢

修改的是值还是地址

test.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>function addChild(& first,<spanclass="vars"> ,n){ //此处first前面为什么要加地址符&呢</h1>  </li><li class="alt">        <?php  </li><li class="">            class Dog{  </li><li class="alt">                public $age;  </li><li class="">                public function __construct($age){  </li><li class="alt">                    $this->age=$age;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            function test(
<?php
class Dog{
public $age;
public function __construct($age){
$this->age=$age;
}
}
function test(dog){
dog->age=30;  </li><li class="">            }  </li><li class="alt">            //创建一个狗对象实例  </li><li class="">            ->age=30;
}
//创建一个狗对象实例
dog1=new Dog(100);
//调用test（调用函数就会开辟一个新栈）
test(dog1);  </li><li class="alt">  </li><li class="">            echo );
echo dog1->age; //为什么会输出30呢
echo ‘ ’;
function test2(dog){  </li><li class="">                $dog=new Dog(200);  </li><li class="alt">            }  </li><li class="">            //创建一个狗对象实例  </li><li class="alt">            ){
$dog=new Dog(200);
}
//创建一个狗对象实例
dog1=new Dog(100);
//调用test（调用函数就会开辟一个新栈）
test2(dog1);  </li><li class="">            echo );
echo dog1->age; //此时输出100还是200呢，输出100
echo ‘ ’;
//& 表示用地址传递
function test3(&dog){  </li><li class="alt">                $dog=new Dog(200);  </li><li class="">            }  </li><li class="alt">            //创建一个狗对象实例  </li><li class="">            ){
$dog=new Dog(200);
}
//创建一个狗对象实例
dog1=new Dog(100);
//调用test（调用函数就会开辟一个新栈）
test3(dog1);  </li><li class="alt">            echo );
echo dog1->age; //此时输出100还是200呢，输出200
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>function addChild(&$first,$n){ //此处$first前面为什么要加地址符&呢</h1>
        <?php
            class Dog{
                public $age;
                public function __construct($age){
                    $this-&gt;age=$age;
                }
            }
            function test($dog){
                $dog->age=30;
            }
            //创建一个狗对象实例
            $dog1=new Dog(100);
            //调用test（调用函数就会开辟一个新栈）
            test($dog1);

            echo $dog1->age; //为什么会输出30呢
            echo '<br/>';

            function test2($dog){
                $dog=new Dog(200);
            }
            //创建一个狗对象实例
            $dog1=new Dog(100);
            //调用test（调用函数就会开辟一个新栈）
            test2($dog1);
            echo $dog1->age; //此时输出100还是200呢，输出100
            echo '<br/>';

            //& 表示用地址传递
            function test3(&$dog){
                $dog=new Dog(200);
            }
            //创建一个狗对象实例
            $dog1=new Dog(100);
            //调用test（调用函数就会开辟一个新栈）
            test3($dog1);
            echo $dog1->age; //此时输出100还是200呢，输出200

        ?>
    </body>
</html>

内存分析图

图片大，在新窗口中打开图片，观看完整图片

（1）语句①执行完后，主栈里就会有一个dog1变量，dog1变量指向了一个堆，对象实例的数据是放在堆区的；
（2）然后执行语句②，调用函数，不管哪种语言，只要调用函数，就会开辟一个新栈，在新栈test栈中，在test栈区中有一个变量

dog，此 dog变量本身的地址是0x56，面向对象是引用传递的，

dog变量存的值是0x34，即 dog变量也指向堆区的0x34地址，当在test栈中执行

dog−>age=30;这个语句后，因为指向同一个地方，就把原来堆区中的100修改为30，此时test函数就执行完毕，就返回了主栈，原来的test栈就消失了被回收了。（3）接着在主栈执行语句③echo dog1->age;，在主栈中$dog1指向堆区地址0x34，此时100已经被修改为30了，所以最后输出：30

再加深一下

内存分析图

图片大，在新窗口中打开图片，观看完整图片

（1）语句①执行完后，主栈里就会有一个dog1变量，dog1变量指向了一个堆，对象实例的数据是放在堆区的；
（2）然后执行语句②，调用函数，不管哪种语言，只要调用函数，就会开辟一个新栈，在新栈test2栈中，在test2栈区中有一个变量

dog，此 dog变量本身的地址是0x56，面向对象是引用传递的，

dog变量存的值是0x34，即 dog变量也指向堆区的0x34地址，然后执行

dog=newDog(200);此时就会在堆区开辟一个新的区间，地址为0x88，存储的值为200，此时在test2栈中的 dog的0x34就会被修改为0x88，此时的

dog变量就不再指向堆区的0x56了，而是指向了堆区地址0x88，，此时test2函数就执行完毕，就返回了主栈，原来的test2栈就消失了被回收了。（堆区地址0x34的值并没有被修改）（3）接着在主栈执行语句③echo dog1->age;，在主栈中$dog1指向堆区地址0x34，此时100并没有被修改，所以最后输出：100

现在考虑加入地址符&的情况

内存分析图

图片大，在新窗口中打开图片，观看完整图片

（1）语句①执行完后，主栈里就会有一个dog1变量，dog1变量指向了一个堆，对象实例的数据是放在堆区的；
（2）然后执行语句②，调用函数，不管哪种语言，只要调用函数，就会开辟一个新栈，在新栈test3栈中，在test3栈区中有一个变量

dog，此 dog变量本身的地址是0x56，在传递参数的时候，用的是&

dog，这个时候 dog变量存的值就是0x34，然后执行

dog=newDog(200);此时就会在堆区开辟一个新的区间，地址为0x88，存储的值为200，此时在test3栈中的 dog的0x34就会被修改为0x88，主栈中

dog1的值0x34也会被同步修改为0x88，此时新栈中的 dog变量和主栈中的

dog1变量都指向了堆区地址0x88，，此时test3函数就执行完毕，就返回了主栈，原来的test3栈就消失了被回收了。（3）接着在主栈执行语句③echo dog1->age;，在主栈中$dog1已经由指向堆区地址0x34转为指向堆区地址0x88，所以最后输出：200
=========

（三）真正来玩游戏
（1）先问题简化，从第一个小孩开始数，数2，看看出列的顺序
分析图
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

现在我们已经有了环形链表，并且

first指向了1号小朋友节点，开始数，first就向下移动，2号小朋友节点出不了列，为什么呢？当 first指向2号小朋友节点，然后让2号小朋友出列，是做不到的，如果是让2号小朋友出列，是形成如下图所示的环形列表，
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

让1号小朋友的next指向3号小朋友，2号就出列了。但是这个$first是指向了2号本身。所以单链表的麻烦事情： ★★它不能自己把自己删除掉。
因此必须保证

first前面还有一个指针，如下图所示，在 first的前面添加一个$tail指针
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

这个时候就可以把2号人物给删除了，先让

first先向走一步，让 first指向3号小朋友，此时tail指向1号小朋友，让tail的next指向$first，就是1号小朋友指向了3号小朋友，2号小朋友就出列了，如下图所示
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

就是现在需要一个辅助指针，就是在运行之前，要先拿一个指针指向$first的前面，如下图所示
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

————-

josephu3.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>约瑟夫问题解决</h1>
<?php
//先构建一个环形链表，链表上的每个节点，表示一个小朋友
//小孩类
class Child{
public no;  </li><li class="">                public ;
public next=null;
//构造函数
public function __construct(no){  </li><li class="alt">                    $this->no=$no;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //定义一个指向第一个小朋友的引用  </li><li class="alt">            //定义一个空头  </li><li class="">            ){
$this->no=$no;
}
}
//定义一个指向第一个小朋友的引用
//定义一个空头
first=null;
n=4; //=4; //n表示有几个小朋友
//写一个函数来创建一个四个小朋友的环形链表
/*
addChild函数的作用是：把 n个小孩在构建成一个环形链表， first变量就指向该环形链表的第一个小孩子
*/
function addChild(& first,<spanclass="vars"> ,n){ //此处要加地址符
//1.头结点不能动 first不能动， cur=first;让cur来帮我们穿针引线  </li><li class="">
cur=first;  </li><li class="alt">                for(;
for(i=0;i<<n;i++){  </li><li class="">                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的  </li><li class="alt">                    //怎么构成一个环形链表呢  </li><li class="">                    if($i==0){ //第一个小孩的情况  </li><li class="alt">                        $first=$child; //让first指向child，但是还没有构建环形链表  </li><li class="">                        $first->next=$child; //自己指向自己  </li><li class="alt">                        $cur=$first; //当$i==0的时候，就让cur和first指向同一个地方  </li><li class="">                    }else{  </li><li class="alt">                        $cur->next=$child;  </li><li class="">                        $child->next=$first;  </li><li class="alt">                        //继续指向下一个  </li><li class="">                        $cur=$cur->next;  </li><li class="alt">                    }  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //遍历所有的小孩，并显示  </li><li class="alt">            function showChild(++){
$child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
//怎么构成一个环形链表呢
if($i==0){ //第一个小孩的情况
$first=$child; //让first指向child，但是还没有构建环形链表
$first->next=$child; //自己指向自己
$cur=$first; //当$i==0的时候，就让cur和first指向同一个地方
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild(first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
cur=<spanclass="vars"> =first;
while(cur->next!=->next!=first){ //cur没有到结尾，就遍历
//显示
echo‘ 小孩的编号是’.cur->no;  </li><li class="alt">                    //继续  </li><li class="">                    ->no;
//继续
cur=cur->next;  </li><li class="alt">                }  </li><li class="">                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点  </li><li class="alt">                echo' 小孩的编号是'.->next;
}
//当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
echo' 小孩的编号是'.cur->no;
}
//问题简化，从第一个小孩开始数，数2，看看出拳的顺序
function countChild(first){  </li><li class="">                //思考：因为我们每找到一个小孩，就要把他从环形链表中删除  </li><li class="alt">                //为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面，在$first的前面，因为是环形的，就相当于在队尾了。  </li><li class="">                $tail=$first;  </li><li class="alt">                while($tail->next!=$first){ //只要tail的next不等于first,就要tail不停的向下走，即$tail=$tail->next;  </li><li class="">                    $tail=$tail->next;  </li><li class="alt">                }  </li><li class="">                //上面的代码，就是生成指向最后一个小孩的$tail  </li><li class="alt">                //当退出while时，我们的$tail就指向了最后这个小孩  </li><li class="">  </li><li class="alt">                //让$first和$tail向后移动  </li><li class="">                //移一下就相当于数了两下，因为还要数自己一下  </li><li class="alt">                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。  </li><li class="">                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动  </li><li class="alt">                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了  </li><li class="">                    for($i=0;$i<1;$i++){  </li><li class="alt">                        $tail=$tail->next;  </li><li class="">                        $first=$first->next;  </li><li class="alt">                    }  </li><li class="">                    //把$first指向的节点小孩删除环形链表  </li><li class="alt">                    $first=$first->next;  </li><li class="">                    $tail->next=$first;  </li><li class="alt">                }  </li><li class="">                echo' 最后留在圈圈的人的编号是'.$tail->no;  </li><li class="alt">            }  </li><li class="">  </li><li class="alt">            addChild(){
//思考：因为我们每找到一个小孩，就要把他从环形链表中删除
//为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面，在$first的前面，因为是环形的，就相当于在队尾了。
$tail=$first;
while($tail->next!=$first){ //只要tail的next不等于first,就要tail不停的向下走，即$tail=$tail->next;
$tail=$tail->next;
}
//上面的代码，就是生成指向最后一个小孩的$tail
//当退出while时，我们的$tail就指向了最后这个小孩
//让$first和$tail向后移动
//移一下就相当于数了两下，因为还要数自己一下
//如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
//移动2次，相当于数了3下，因为自己数的时候，自己不需要动
while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
for($i=0;$i<1;$i++){
$tail=$tail->next;
$first=$first->next;
}
//把$first指向的节点小孩删除环形链表
$first=$first->next;
$tail->next=$first;
}
echo' 最后留在圈圈的人的编号是'.$tail->no;
}
addChild(first,n);  </li><li class="">            showChild();
showChild(first);
//真正来玩游戏
countChild($first);
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>约瑟夫问题解决</h1>
        <?php
            //先构建一个环形链表，链表上的每个节点，表示一个小朋友
            //小孩类
            class Child{
                public $no;
                public $next=null;
                //构造函数
                public function __construct($no){
                    $this-&gt;no=$no;
                }
            }
            //定义一个指向第一个小朋友的引用
            //定义一个空头
            $first=null;
            $n=4; //$n表示有几个小朋友
            //写一个函数来创建一个四个小朋友的环形链表
            /*
             addChild函数的作用是：把$n个小孩在构建成一个环形链表，$first变量就指向该环形链表的第一个小孩子
             */
            function addChild(&$first,$n){ //此处要加地址符
                //1.头结点不能动 $first不能动，$cur=$first;让cur来帮我们穿针引线
                $cur=$first;
                for($i=0;$i<$n;$i++){
                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
                    //怎么构成一个环形链表呢
                    if($i==0){ //第一个小孩的情况
                        $first=$child; //让first指向child，但是还没有构建环形链表
                        $first-&gt;next=$child; //自己指向自己
                        $cur=$first; //当$i==0的时候，就让cur和first指向同一个地方
                    }else{
                        $cur-&gt;next=$child;
                        $child-&gt;next=$first;
                        //继续指向下一个
                        $cur=$cur->next;
                    }
                }
            }
            //遍历所有的小孩，并显示
            function showChild($first){
                //遍历 cur变量是帮助我们遍历循环列表的，所以不能动
                $cur=$first;
                while($cur-&gt;next!=$first){ //cur没有到结尾，就遍历
                    //显示
                    echo'<br/>小孩的编号是'.$cur->no;
                    //继续
                    $cur=$cur->next;
                }
                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
                echo'<br/>小孩的编号是'.$cur->no;
            }

            //问题简化，从第一个小孩开始数，数2，看看出拳的顺序
            function countChild($first){
                //思考：因为我们每找到一个小孩，就要把他从环形链表中删除
                //为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面，在$first的前面，因为是环形的，就相当于在队尾了。
                $tail=$first;
                while($tail-&gt;next!=$first){ //只要tail的next不等于first,就要tail不停的向下走，即$tail=$tail->next;
                    $tail=$tail->next;
                }
                //上面的代码，就是生成指向最后一个小孩的$tail
                //当退出while时，我们的$tail就指向了最后这个小孩

                //让$first和$tail向后移动
                //移一下就相当于数了两下，因为还要数自己一下
                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动
                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
                    for($i=0;$i<1;$i++){
                        $tail=$tail->next;
                        $first=$first->next;
                    }
                    //把$first指向的节点小孩删除环形链表
                    $first=$first->next;
                    $tail-&gt;next=$first;
                }
                echo'<br/>最后留在圈圈的人的编号是'.$tail->no;
            }

            addChild($first,$n);
            showChild($first);

            //真正来玩游戏
            countChild($first);
        ?>
    </body>
</html>

（2）现在把数2做成变量m
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

josephu4.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>约瑟夫问题解决</h1>
<?php
//先构建一个环形链表，链表上的每个节点，表示一个小朋友
//小孩类
class Child{
public no;  </li><li class="">                public ;
public next=null;
//构造函数
public function __construct(no){  </li><li class="alt">                    $this->no=$no;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //定义一个指向第一个小朋友的引用  </li><li class="alt">            //定义一个空头  </li><li class="">            ){
$this->no=$no;
}
}
//定义一个指向第一个小朋友的引用
//定义一个空头
first=null;
n=10; //=10; //n表示有几个小朋友
//写一个函数来创建一个四个小朋友的环形链表
/*
addChild函数的作用是：把 n个小孩在构建成一个环形链表， first变量就指向该环形链表的第一个小孩子
*/
function addChild(& first,<spanclass="vars"> ,n){ //此处要加地址符
//1.头结点不能动 first不能动  </li><li class="">
cur=first;  </li><li class="alt">                for(;
for(i=0;i<<n;i++){  </li><li class="">                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的  </li><li class="alt">                    //怎么构成一个环形链表呢  </li><li class="">                    if($i==0){ //第一个小孩的情况  </li><li class="alt">                        $first=$child; //让first指向child，但是还没有构建环形链表  </li><li class="">                        $first->next=$child; //自己指向自己  </li><li class="alt">                        $cur=$first;  </li><li class="">                    }else{  </li><li class="alt">                        $cur->next=$child;  </li><li class="">                        $child->next=$first;  </li><li class="alt">                        //继续指向下一个  </li><li class="">                        $cur=$cur->next;  </li><li class="alt">                    }  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //遍历所有的小孩，并显示  </li><li class="alt">            function showChild(++){
$child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
//怎么构成一个环形链表呢
if($i==0){ //第一个小孩的情况
$first=$child; //让first指向child，但是还没有构建环形链表
$first->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild(first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
cur=<spanclass="vars"> =first;
while(cur->next!=->next!=first){ //cur没有到结尾，就遍历
//显示
echo‘ 小孩的编号是’.cur->no;  </li><li class="alt">                    //继续  </li><li class="">                    ->no;
//继续
cur=cur->next;  </li><li class="alt">                }  </li><li class="">                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点  </li><li class="alt">                echo' 小孩的编号是'.->next;
}
//当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
echo' 小孩的编号是'.cur->no;
}
//为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在 first前面，在 first的前面，因为是环形的，就相当于在队尾了。
m=3;  </li><li class="">            function countChild(=3;
function countChild(first,m){  </li><li class="alt">                $tail=$first;  </li><li class="">                while($tail->next!=$first){  </li><li class="alt">                    $tail=$tail->next;  </li><li class="">                }  </li><li class="alt">                //当退出while时，我们的$tail就指向了最后这个小孩  </li><li class="">  </li><li class="alt">                //让$first和$tail向后移动  </li><li class="">                //移一下就相当于数了两下，因为还要数自己一下  </li><li class="alt">                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。  </li><li class="">                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动  </li><li class="alt">                //移动m-1次，相当于数了m下   </li><li class="">                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了  </li><li class="alt">                    for($i=0;$i<$m-1;$i++){  </li><li class="">                        $tail=$tail->next;  </li><li class="alt">                        $first=$first->next;  </li><li class="">                    }  </li><li class="alt">                    //把$first指向的节点小孩删除环形链表  </li><li class="">                    $first=$first->next;  </li><li class="alt">                    $tail->next=$first;  </li><li class="">                }  </li><li class="alt">                echo' 最后留在圈圈的人的编号是'.$tail->no;  </li><li class="">            }  </li><li class="alt">  </li><li class="">            addChild(){
$tail=$first;
while($tail->next!=$first){
$tail=$tail->next;
}
//当退出while时，我们的$tail就指向了最后这个小孩
//让$first和$tail向后移动
//移一下就相当于数了两下，因为还要数自己一下
//如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
//移动2次，相当于数了3下，因为自己数的时候，自己不需要动
//移动m-1次，相当于数了m下
while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
for($i=0;$i<$m-1;$i++){
$tail=$tail->next;
$first=$first->next;
}
//把$first指向的节点小孩删除环形链表
$first=$first->next;
$tail->next=$first;
}
echo' 最后留在圈圈的人的编号是'.$tail->no;
}
addChild(first,n);  </li><li class="alt">            showChild();
showChild(first);
//真正来玩游戏
countChild( first,<spanclass="vars"> ,m);
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>约瑟夫问题解决</h1>
        <?php
            //先构建一个环形链表，链表上的每个节点，表示一个小朋友
            //小孩类
            class Child{
                public $no;
                public $next=null;
                //构造函数
                public function __construct($no){
                    $this-&gt;no=$no;
                }
            }
            //定义一个指向第一个小朋友的引用
            //定义一个空头
            $first=null;
            $n=10; //$n表示有几个小朋友
            //写一个函数来创建一个四个小朋友的环形链表
            /*
             addChild函数的作用是：把$n个小孩在构建成一个环形链表，$first变量就指向该环形链表的第一个小孩子
             */
            function addChild(&$first,$n){ //此处要加地址符
                //1.头结点不能动 $first不能动
                $cur=$first;
                for($i=0;$i<$n;$i++){
                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
                    //怎么构成一个环形链表呢
                    if($i==0){ //第一个小孩的情况
                        $first=$child; //让first指向child，但是还没有构建环形链表
                        $first-&gt;next=$child; //自己指向自己
                        $cur=$first;
                    }else{
                        $cur-&gt;next=$child;
                        $child-&gt;next=$first;
                        //继续指向下一个
                        $cur=$cur->next;
                    }
                }
            }
            //遍历所有的小孩，并显示
            function showChild($first){
                //遍历 cur变量是帮助我们遍历循环列表的，所以不能动
                $cur=$first;
                while($cur-&gt;next!=$first){ //cur没有到结尾，就遍历
                    //显示
                    echo'<br/>小孩的编号是'.$cur->no;
                    //继续
                    $cur=$cur->next;
                }
                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
                echo'<br/>小孩的编号是'.$cur->no;
            }

            //为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面，在$first的前面，因为是环形的，就相当于在队尾了。
            $m=3;
            function countChild($first,$m){
                $tail=$first;
                while($tail-&gt;next!=$first){
                    $tail=$tail->next;
                }
                //当退出while时，我们的$tail就指向了最后这个小孩

                //让$first和$tail向后移动
                //移一下就相当于数了两下，因为还要数自己一下
                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动
                //移动m-1次，相当于数了m下 
                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
                    for($i=0;$i<$m-1;$i++){
                        $tail=$tail->next;
                        $first=$first->next;
                    }
                    //把$first指向的节点小孩删除环形链表
                    $first=$first->next;
                    $tail-&gt;next=$first;
                }
                echo'<br/>最后留在圈圈的人的编号是'.$tail->no;
            }

            addChild($first,$n);
            showChild($first);

            //真正来玩游戏
            countChild($first,$m);
        ?>
    </body>
</html>

（3）再考虑从第几个人数的问题，变量k；和出列显示
韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

josephu5.php

[php] view plain copy print ?

<html>
<head>
<meta http-equiv=”Content-Type” content=“text/html; charset=gb2312” />
</head>
<body>
<h1>约瑟夫问题解决</h1>
<?php
//先构建一个环形链表，链表上的每个节点，表示一个小朋友
//小孩类
class Child{
public no;  </li><li class="">                public ;
public next=null;
//构造函数
public function __construct(no){  </li><li class="alt">                    $this->no=$no;  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //定义一个指向第一个小朋友的引用  </li><li class="alt">            //定义一个空头  </li><li class="">            ){
$this->no=$no;
}
}
//定义一个指向第一个小朋友的引用
//定义一个空头
first=null;
n=10; //=10; //n表示有几个小朋友
//写一个函数来创建一个四个小朋友的环形链表
/*
addChild函数的作用是：把 n个小孩在构建成一个环形链表， first变量就指向该环形链表的第一个小孩子
*/
function addChild(& first,<spanclass="vars"> ,n){ //此处要加地址符
//1.头结点不能动 first不能动  </li><li class="">
cur=first;  </li><li class="alt">                for(;
for(i=0;i<<n;i++){  </li><li class="">                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的  </li><li class="alt">                    //怎么构成一个环形链表呢  </li><li class="">                    if($i==0){ //第一个小孩的情况  </li><li class="alt">                        $first=$child; //让first指向child，但是还没有构建环形链表  </li><li class="">                        $first->next=$child; //自己指向自己  </li><li class="alt">                        $cur=$first;  </li><li class="">                    }else{  </li><li class="alt">                        $cur->next=$child;  </li><li class="">                        $child->next=$first;  </li><li class="alt">                        //继续指向下一个  </li><li class="">                        $cur=$cur->next;  </li><li class="alt">                    }  </li><li class="">                }  </li><li class="alt">            }  </li><li class="">            //遍历所有的小孩，并显示  </li><li class="alt">            function showChild(++){
$child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
//怎么构成一个环形链表呢
if($i==0){ //第一个小孩的情况
$first=$child; //让first指向child，但是还没有构建环形链表
$first->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild(first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
cur=<spanclass="vars"> =first;
while(cur->next!=->next!=first){ //cur没有到结尾，就遍历
//显示
echo‘ 小孩的编号是’.cur->no;  </li><li class="alt">                    //继续  </li><li class="">                    ->no;
//继续
cur=cur->next;  </li><li class="alt">                }  </li><li class="">                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点  </li><li class="alt">                echo' 小孩的编号是'.->next;
}
//当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
echo' 小孩的编号是'.cur->no;
}
//为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在 first前面，在 first的前面，因为是环形的，就相当于在队尾了。
m=3;  </li><li class="">            =3;
k=2;
function countChild( first,<spanclass="vars"> ,m,k){  </li><li class="">                $tail=$first;  </li><li class="alt">                while($tail->next!=$first){  </li><li class="">                    $tail=$tail->next;  </li><li class="alt">                }  </li><li class="">  </li><li class="alt">                //考虑是从第几个人开始数的问题，变量k  </li><li class="">                //首先要定位  </li><li class="alt">                //因为动一下，就相当于数了两下，算上自己了，所以k-1  </li><li class="">                for($i=0;$i<$k-1;$i++){  </li><li class="alt">                    $tail=$tail->next;  </li><li class="">                    $first=$first->next;  </li><li class="alt">                }  </li><li class="">  </li><li class="alt">                //当退出while时，我们的$tail就指向了最后这个小孩  </li><li class="">  </li><li class="alt">                //让$first和$tail向后移动  </li><li class="">                //移一下就相当于数了两下，因为还要数自己一下  </li><li class="alt">                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。  </li><li class="">                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动  </li><li class="alt">                //移动m-1次，相当于数了m下   </li><li class="">                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了  </li><li class="alt">                    for($i=0;$i<$m-1;$i++){  </li><li class="">                        $tail=$tail->next;  </li><li class="alt">                        $first=$first->next;  </li><li class="">                    }  </li><li class="alt">                    //把$first指向的节点小孩删除环形链表  </li><li class="">                    //出列显示，应该在first没有改变之前先打印输出  </li><li class="alt">                    echo' 出圈的人的编号是'.$first->no;  </li><li class="">                    $first=$first->next;  </li><li class="alt">                    $tail->next=$first;  </li><li class="">                }  </li><li class="alt">                echo' 最后留在圈圈的人的编号是'.$tail->no;  </li><li class="">            }  </li><li class="alt">  </li><li class="">            addChild(){
$tail=$first;
while($tail->next!=$first){
$tail=$tail->next;
}
//考虑是从第几个人开始数的问题，变量k
//首先要定位
//因为动一下，就相当于数了两下，算上自己了，所以k-1
for($i=0;$i<$k-1;$i++){
$tail=$tail->next;
$first=$first->next;
}
//当退出while时，我们的$tail就指向了最后这个小孩
//让$first和$tail向后移动
//移一下就相当于数了两下，因为还要数自己一下
//如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
//移动2次，相当于数了3下，因为自己数的时候，自己不需要动
//移动m-1次，相当于数了m下
while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
for($i=0;$i<$m-1;$i++){
$tail=$tail->next;
$first=$first->next;
}
//把$first指向的节点小孩删除环形链表
//出列显示，应该在first没有改变之前先打印输出
echo' 出圈的人的编号是'.$first->no;
$first=$first->next;
$tail->next=$first;
}
echo' 最后留在圈圈的人的编号是'.$tail->no;
}
addChild(first,n);  </li><li class="alt">            showChild();
showChild(first);
//真正来玩游戏
countChild( first,<spanclass="vars"> ,m,$k);
?>
</body>
</html>

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
    </head>
    <body>
        <h1>约瑟夫问题解决</h1>
        <?php
            //先构建一个环形链表，链表上的每个节点，表示一个小朋友
            //小孩类
            class Child{
                public $no;
                public $next=null;
                //构造函数
                public function __construct($no){
                    $this-&gt;no=$no;
                }
            }
            //定义一个指向第一个小朋友的引用
            //定义一个空头
            $first=null;
            $n=10; //$n表示有几个小朋友
            //写一个函数来创建一个四个小朋友的环形链表
            /*
             addChild函数的作用是：把$n个小孩在构建成一个环形链表，$first变量就指向该环形链表的第一个小孩子
             */
            function addChild(&$first,$n){ //此处要加地址符
                //1.头结点不能动 $first不能动
                $cur=$first;
                for($i=0;$i<$n;$i++){
                    $child=new Child($i+1); //为什么要加1，因为for循环中i是从开始的，但是小朋友的编号是从1开始的
                    //怎么构成一个环形链表呢
                    if($i==0){ //第一个小孩的情况
                        $first=$child; //让first指向child，但是还没有构建环形链表
                        $first-&gt;next=$child; //自己指向自己
                        $cur=$first;
                    }else{
                        $cur-&gt;next=$child;
                        $child-&gt;next=$first;
                        //继续指向下一个
                        $cur=$cur->next;
                    }
                }
            }
            //遍历所有的小孩，并显示
            function showChild($first){
                //遍历 cur变量是帮助我们遍历循环列表的，所以不能动
                $cur=$first;
                while($cur-&gt;next!=$first){ //cur没有到结尾，就遍历
                    //显示
                    echo'<br/>小孩的编号是'.$cur->no;
                    //继续
                    $cur=$cur->next;
                }
                //当退出while循环时，已经到了环形链表的最后，即cur此时指向最后一个小孩，所以还要处里一下最后这个小孩节点
                echo'<br/>小孩的编号是'.$cur->no;
            }

            //为了能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面，在$first的前面，因为是环形的，就相当于在队尾了。
            $m=3;
            $k=2;
            function countChild($first,$m,$k){
                $tail=$first;
                while($tail-&gt;next!=$first){
                    $tail=$tail->next;
                }

                //考虑是从第几个人开始数的问题，变量k
                //首先要定位
                //因为动一下，就相当于数了两下，算上自己了，所以k-1
                for($i=0;$i<$k-1;$i++){
                    $tail=$tail->next;
                    $first=$first->next;
                }

                //当退出while时，我们的$tail就指向了最后这个小孩

                //让$first和$tail向后移动
                //移一下就相当于数了两下，因为还要数自己一下
                //如从1号小朋友到2号小朋友，只移动了一下，那么是1号小朋友数1 再数2，因为还数了自己一下。
                //移动2次，相当于数了3下，因为自己数的时候，自己不需要动
                //移动m-1次，相当于数了m下 
                while($tail!=$first){ //当$tail==$first则说明只有最后一个人了
                    for($i=0;$i<$m-1;$i++){
                        $tail=$tail->next;
                        $first=$first->next;
                    }
                    //把$first指向的节点小孩删除环形链表
                    //出列显示，应该在first没有改变之前先打印输出
                    echo'<br/>出圈的人的编号是'.$first->no;
                    $first=$first->next;
                    $tail-&gt;next=$first;
                }
                echo'<br/>最后留在圈圈的人的编号是'.$tail->no;
            }

            addChild($first,$n);
            showChild($first);

            //真正来玩游戏
            countChild($first,$m,$k);
        ?>
    </body>
</html>

关键是要在脑海中，有一个内存分布和运行的大致图。
一旦人多了，比如4000个人，从第31个人，数20，这时候就发现程序的力量了，你人工去数，可想而知。
用程序来完成你能完成的事情，但是是快速的完成。
找工作的时候，很容易被考的问题：约瑟夫问题，排序和查找，二叉树的遍历，前序遍历后序遍历，霍夫曼数，最小堆等
有档次的公司都喜欢考算法

韩顺平_PHP程序员玩转算法公开课_学习笔记_源代码图解_PPT文档整理_目录

秒客网

韩顺平_PHP程序员玩转算法公开课(第一季)05_使用单链表解决约瑟夫问题_学习笔记_源代码图解_PPT文档整理

</html>

相关文章