文西马龙：http://blog.csdn.net/wenximalong/
现在我们对单链表有了基本的了解，现在学习一下环形链表。
环形链表的内存示意图
环形链表的好处：可以模拟许多实际的情景
如丢手帕问题，就是经典的用环形链表来解决的
现在我们来完成约瑟夫问题的解决方案！
Josephu问题
Josephu问题为：射编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？
提示：用一个不带头节点的循环链表来处里Josephu问题，先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。
思路：
（一）构建一个环形链表，链表上的每个节点，表示一个小朋友（PHP语言实现）
一个小朋友的情况
两个小朋友的情况
当第一个结点做完以后，1号小朋友还有一个新的指向指向它，就是cur。cur的用处，当有2号小朋友的时候，cur就发挥作用了，此时cur还是指向1号小朋友，那么$cur->next=$child;则①号线就被搭起来了，然后$child->next=$first;则②号线就被搭起来了，2号小朋友结点就指向了1号小朋友结点，环形链表就形成了。$cur=$cur->next;则cur就由原来的指向1号小朋友转为指向2号小朋友了，如图中③号线所示，这样就可以再加第3个小朋友了，依次类推。
（二）写一个函数来显示所有的小孩子
josephu.php
<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->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->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild($first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
$cur=$first;
while($cur->next!=$first){ //cur没有到结尾，就遍历
//显示
echo'<br/>小孩的编号是'.$cur->no;
//继续
$cur=$cur->next;
}
}
addChild($first,$n);
showChild($first);
?>
</body>
</html>
为什么现在只显示三个小孩呢，分析一下代码在内存中是怎么运作的
图片大，在新窗口中打开图片，观看完整图片
（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
<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->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->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild($first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
$cur=$first;
while($cur->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
<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->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=new Dog(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=new Dog(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，看看出列的顺序
分析图
现在我们已经有了环形链表，并且$first指向了1号小朋友节点，开始数，first就向下移动，2号小朋友节点出不了列，为什么呢？当$first指向2号小朋友节点，然后让2号小朋友出列，是做不到的，如果是让2号小朋友出列，是形成如下图所示的环形列表，
让1号小朋友的next指向3号小朋友，2号就出列了。但是这个$first是指向了2号本身。所以单链表的麻烦事情： ★★它不能自己把自己删除掉。
因此必须保证$first前面还有一个指针，如下图所示，在$first的前面添加一个$tail指针
这个时候就可以把2号人物给删除了，先让$first先向走一步，让$first指向3号小朋友，此时tail指向1号小朋友，让tail的next指向$first，就是1号小朋友指向了3号小朋友，2号小朋友就出列了，如下图所示
就是现在需要一个辅助指针，就是在运行之前，要先拿一个指针指向$first的前面，如下图所示
-------------
josephu3.php
<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->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->next=$child; //自己指向自己
$cur=$first; //当$i==0的时候，就让cur和first指向同一个地方
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild($first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
$cur=$first;
while($cur->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->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'<br/>最后留在圈圈的人的编号是'.$tail->no;
}
addChild($first,$n);
showChild($first);
//真正来玩游戏
countChild($first);
?>
</body>
</html>
（2）现在把数2做成变量m
josephu4.php
<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->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->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild($first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
$cur=$first;
while($cur->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->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'<br/>最后留在圈圈的人的编号是'.$tail->no;
}
addChild($first,$n);
showChild($first);
//真正来玩游戏
countChild($first,$m);
?>
</body>
</html>
（3）再考虑从第几个人数的问题，变量k；和出列显示
josephu5.php
<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->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->next=$child; //自己指向自己
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
//继续指向下一个
$cur=$cur->next;
}
}
}
//遍历所有的小孩，并显示
function showChild($first){
//遍历 cur变量是帮助我们遍历循环列表的，所以不能动
$cur=$first;
while($cur->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->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->next=$first;
}
echo'<br/>最后留在圈圈的人的编号是'.$tail->no;
}
addChild($first,$n);
showChild($first);
//真正来玩游戏
countChild($first,$m,$k);
?>
</body>
</html>
关键是要在脑海中，有一个内存分布和运行的大致图。
一旦人多了，比如4000个人，从第31个人，数20，这时候就发现程序的力量了，你人工去数，可想而知。
用程序来完成你能完成的事情，但是是快速的完成。
找工作的时候，很容易被考的问题：约瑟夫问题，排序和查找，二叉树的遍历，前序遍历后序遍历，霍夫曼数，最小堆等
有档次的公司都喜欢考算法