首先我们先简单介绍一下PHP双链表(SplDoublyLinkedList)。
PHP双链表(SplDoublyLinkedList)简介
PHP双链表是一种可以双向遍历的线性结构,它能够在元素的前后两个方向上添加和删除元素,并且支持根据索引查询和修改元素。相对于PHP的普通数组来说,双链表在某些情况下会更加高效,尤其是在大量的插入和删除操作时。
PHP双链表的实现是使用了双向链表的数据结构,每个节点除了存储当前节点的值之外,还指向了前一个节点和下一个节点。PHP内置了SplDoublyLinkedList类来实现双链表,使用起来非常方便。
使用实例
接下来我们来看一下如何使用PHP双链表。
创建对象
首先我们需要创建一个SplDoublyLinkedList对象,可以使用如下代码:
$list = new SplDoublyLinkedList();
添加元素
向双链表中添加元素有两种方式:添加到头部和添加到尾部。我们可以使用以下方法来进行添加:
- push:添加到尾部
- unshift:添加到头部
例如,我们想要添加一个整数5到双链表的尾部,可以使用如下代码:
$list->push(5);
如果想要添加一个整数3到双链表的头部,可以使用如下代码:
$list->unshift(3);
删除元素
从双链表中删除元素同样可以使用两种方式:删除头部元素和删除尾部元素。我们可以使用以下方法来进行删除:
- shift:删除头部元素
- pop:删除尾部元素
例如,我们想要删除双链表的头部元素,可以使用如下代码:
$list->shift();
如果想要删除双链表的尾部元素,可以使用如下代码:
$list->pop();
获取元素
获取双链表中某个位置的元素可以使用以下方法:
- current:获取当前位置的元素
- next:将指针向后移动一位,返回移动后的元素
- previous:将指针向前移动一位,返回移动后的元素
- offsetGet:获取指定位置的元素
例如,如果我们想要获取双链表第二个元素的值,可以使用以下代码:
$list->next();
$value = $list->current();
如果我们想要获取双链表第三个元素的值,可以使用以下代码:
$list->next();
$list->next();
$value = $list->current();
如果想要获取双链表第一个元素的值,可以使用以下代码:
$value = $list->offsetGet(0);
修改元素
要修改双链表中某个位置的元素,可以使用以下方法:
- offsetSet:设置指定位置的元素为指定的值
例如,如果我们想要将双链表第二个元素改为8,可以使用以下代码:
$list->next();
$list->offsetSet($list->key(), 8);
示例1
下面是一个使用实例,我们创建一个双链表并向其中添加一些元素:
$list = new SplDoublyLinkedList();
$list->push(5);
$list->push(8);
$list->unshift(3);
$list->push(2);
然后遍历输出双链表中的元素:
for ($list->rewind(); $list->valid(); $list->next()) {
echo $list->current() . "\n";
}
运行结果如下:
3
5
8
2
示例2
这是一个更加复杂的例子,我们创建一个双链表并模拟一个简单的贪吃蛇游戏。该游戏中蛇头作为双链表的尾部,蛇尾作为双链表的头部,每次移动时都向尾部添加一个新的节点,然后删除头部节点。
$list = new SplDoublyLinkedList();
$list->push(['x' => 5, 'y' => 5]);
$list->push(['x' => 4, 'y' => 5]);
$list->push(['x' => 3, 'y' => 5]);
$dir = 'right';
while(true) {
// 获取蛇头和蛇尾节点
$head = $list->top();
$tail = $list->bottom();
// 计算下一步蛇头的位置
if($dir == 'right') {
$nextHead = ['x' => $head['x'] + 1, 'y' => $head['y']];
} elseif($dir == 'left') {
$nextHead = ['x' => $head['x'] - 1, 'y' => $head['y']];
} elseif($dir == 'up') {
$nextHead = ['x' => $head['x'], 'y' => $head['y'] - 1];
} elseif($dir == 'down') {
$nextHead = ['x' => $head['x'], 'y' => $head['y'] + 1];
}
// 添加新的蛇头节点
$list->push($nextHead);
// 判断是否撞墙
if($nextHead['x'] < 0 || $nextHead['x'] >= 10 || $nextHead['y'] < 0 || $nextHead['y'] >= 10) {
echo "Game Over\n";
break;
}
// 判断是否咬到自己
$hasOverlap = false;
for ($list->rewind(); $list->valid(); $list->next()) {
$node = $list->current();
if($node != $nextHead && $node['x'] == $nextHead['x'] && $node['y'] == $nextHead['y']) {
$hasOverlap = true;
break;
}
}
if($hasOverlap) {
echo "Game Over\n";
break;
}
// 删除蛇尾节点
$list->shift();
// 输出蛇的当前状态
for ($list->rewind(); $list->valid(); $list->next()) {
$node = $list->current();
if($node == $head) {
echo 'H';
} elseif($node == $tail) {
echo 'T';
} else {
echo 'O';
}
}
echo "\n";
// 读取玩家输入,并设置移动方向
$input = trim(fgets(STDIN));
if($input == 'w') {
$dir = 'up';
} elseif($input == 'a') {
$dir = 'left';
} elseif($input == 's') {
$dir = 'down';
} elseif($input == 'd') {
$dir = 'right';
}
}
这里我们不讨论具体的贪吃蛇算法实现,重点是演示如何使用PHP双链表模拟游戏的过程。运行该代码后,玩家可以通过键盘输入"w"、"a"、"s"、"d"来控制蛇的移动方向,每移动一步都会输出蛇的当前状态,最终当游戏结束时输出"Game Over"。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP 双链表(SplDoublyLinkedList)简介和使用实例 - Python技术站