您当前的位置： 首页 > 学无止境 > 网站建设 网站首页网站建设

使用单链表(环形链表)解决约瑟夫问题

发布时间：2017-03-26 22:28:39编辑：雪饮阅读（）

 环形链表内存示意图:



 

约瑟夫丢手帕问题:



环形链表的创建与遍历:

<?php

//小孩类

class Child{

         public $no;

         public $next=null;

         public function __construct($no){

                   $this->no=$no;

         }

        

}

//定义一个指向第一个小孩的引用

$first=null;

$n=4;//$n表示有几个小朋友

//写一个函数来创建一个四个小朋友的环形链表

//一会儿我们深入的分析地址符'&'

//该函数的作用是：将n个小孩构建成一个环形链表

function addChild(&$first,$n){

         //头节点不能动

         $cur=null;

         for($i=0;$i<$n;$i++){

                   $child=new Child($i+1);//$i+1是因为现实中是以1开始计算的

                   if($i==0){

                            //朋友圈即便只有一个人，那么这个人与自身也能构成环形链表

                            $first=$child;

                            $first->next=$child;

                            $cur=$first;

                   }

                   else{

                            $cur->next=$child;

                            $child->next=$first;

                            $cur=$cur->next;

                           

                   }

         }

}

 

//遍历环形链表

function showChild($first){

         $cur=$first;

         while($cur->next!=$first){

                   echo "<br/>小孩的编号是".$cur->no;

                   $cur=$cur->next;

         }

         //当退出while循环时，已经到了环形链表的最后，所以还要处理一下最后这个小孩节点

         echo "<br/>小孩的编号是".$cur->no;

}

addChild($first,$n);

showChild($first);

?>

地址符'&':

每个变量都有一个变量地址和变量值地址

当使用&时就会共享变量值地址

 

环形链表解决丢手帕问题：

<?php

//小孩类

class Child{

         public $no;

         public $next=null;

         public function __construct($no){

                   $this->no=$no;

         }

        

}

//定义一个指向第一个小孩的引用

$first=null;

$n=4;//$n表示有几个小朋友

$m=3;//表示数到第几个

$k=2;//表示从第几个开始数

//写一个函数来创建一个四个小朋友的环形链表

//一会儿我们深入的分析地址符i'&'

//该函数的作用是：将n个小孩构建成一个环形链表

function addChild(&$first,$n){

         //头节点不能动

         $cur=null;

         for($i=0;$i<$n;$i++){

                   $child=new Child($i+1);//$i+1是因为现实中是以1开始计算的

                   if($i==0){

                            //朋友圈即便只有一个人，那么这个人与自身也能构成环形链表

                            $first=$child;

                            $first->next=$child;

                            $cur=$first;

                   }

                   else{

                            $cur->next=$child;

                            $child->next=$first;

                            $cur=$cur->next;

                           

                   }

         }

}

 

//遍历环形链表

function showChild($first){

         $cur=$first;

         while($cur->next!=$first){

                   echo "<br/>小孩的编号是".$cur->no;

                   $cur=$cur->next;

         }

         //当退出while循环时，已经到了环形链表的最后，所以还要处理一下最后这个小孩节点

         echo "<br/>小孩的编号是".$cur->no;

}

//问题简化，从第一个小孩开始数，数2，看看出圈的顺序

function countChild($first,$m,$k){

         //思考：因为我们找到一个小孩，就要把他从环形链表删除

         //为了 能够删除某个小孩，我们需要一个辅助变量，该变量指向的小孩在$first前面

         $tail=$first;

         while($tail->next!=$first){

                   $tail=$tail->next;

         }

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

        

         //考虑是从第几个人开始数

         for($i=0;$i<$k-1;$i++){

                   $tail=$tail->next;

                   $first=$first->next;

         }

        

         //让$first和$tail向后移动

         //移动一次，相当于数2下

         //移动2次，相当于数了3下，因为自己数的时候是不需要动的。

         while($tail!=$first){

                   //当$tail==$first则说明只有最后一个人了

                   for($i=0;$i<$m-1;$i++){

                   $tail=$tail->next;

                   $first=$first->next;

                   }

                   //把$first指向的节点小孩删除环形链表

                   echo "<br/>出圈的人的编号是".$first->no;

                   $first=$first->next;

                   $tail->next=$first;

         }

         echo "<br/>最后留在圈圈的人的编号是".$tail->no;

        

}

addChild($first,$n);

showChild($first);

countChild($first,$m,$k);

?>

 

 

难点剖析：

在代码片断：

for($i=0;$i<$m-1;$i++){

                   $tail=$tail->next;

                   $first=$first->next;

                   }

 

前环形结构如：



 

在该循环之后环形结构如：

 



 

当结构变成这样后又执行 ：

$first=$first->next;

$tail->next=$first;

 

后就将待剔除这个圈子的小孩剔除去了：