PHP环形链表数据结构的实现方法-php开发知识文章-编程文章分享

这篇文章主要介绍了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环形链表数据结构的实现方法

相关推荐

请登录