PHP环形链表实现方法示例


            本文实例讲述了PHP环形链表实现方法。分享给大家供大家参考，具体如下：

环形链表是一种链式存储结构，类似于单链表。区别是环形链表的尾节点指向头节点。

从而形成一个环，

环形链表是一种非常灵活的存储结构，可解决许多实际问题，魔术师发牌问题和约瑟夫问题

都能利用环形链表来解决，下面是一个完整的环形链表实例，使用php来实现的（参照韩顺平老师的php算法教程）





/** 

 *  环形链表的实现

 *  

 */

class child

{

  public $no;//序号

  public $next;//指向下个节点的指针

  public function __construct($no=''){

    $this ->no = $no;

  }

}

/**

 * 创建一个环形链表

 * @param $first null  链表的头节点

 * @param $num  integer 需要添加节点的数量

 */

function create(&$first,$num)

{

  $cur = null;

  for ($i=0;$i<$num;$i++)

  {

    $child = new child($i+1);

    if ($i==0)

    {  

      $first = $child;

      $first->next = $first;//将链表的尾节点指向头节点 形成环形链表

      $cur = $first;//链表的头节点不能动 需要交给一个临时变量

    } else {

      $cur->next = $child;

      $cur->next->next = $first;//将链表的尾节点指向头节点 形成环形链表

      $cur = $cur->next;

    }

  }

}

/**

 * 遍历环形链表

 * @param $first object 环形链表的头

 * 

 */

function show ($first)

{

  //头节点不能动，交个一个临时变量

  $cur = $first;

  while ($cur->next!=$first)//当$cur->next==$first说明到了链表的最后一个节点

  {

    echo $cur->no.'</br>';

    $cur = $cur->next;

  }

  //当退出循环的时候$cur->next=$first 刚好会忽略当前节点本身的遍历 所以退出的时候还要输出一下 否则会少遍历一个节点

  echo $cur->no;

}







更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。