本文实例讲述了PHP环形链表实现方法。分享给大家供大家参考,具体如下:
环形链表是一种链式存储结构,类似于单链表。区别是环形链表的尾节点指向头节点。
从而形成一个环,
环形链表是一种非常灵活的存储结构,可解决许多实际问题,魔术师发牌问题和约瑟夫问题
都能利用环形链表来解决,下面是一个完整的环形链表实例,使用php来实现的(参照韩顺平老师的php算法教程)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
/**
* 环形链表的实现
*
*/
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程序设计有所帮助。
原文链接:http://blog.csdn.net/qq_32439101/article/details/72860933