php链表结构 环型链表（三）
环型链表结构，我们这边的环型链表其实和双向链表相似，就是最后一个节点指向了我们的开始节点上，我们这边定义一个节点类，属性有当前值(data)和指向下一个节点的(next)， 和指向上一个节点的（previous）。
class Node {
public $data;
public $next;
public $previous;
public function __construct($data)
{
$this->data = $data;
}
}
之后是链表结构类 ，我们定义一个头节点，以头节点开始，next指向下一个节点，previous指向上一个节点，具体看情况添加你所需要的其他属性，并且将最后一个节点的next指向第一个节点
class LoopLinkedList
{
private $headList;
public function __construct($data)
{
$this->headList = new Node($data);
$this->headList->next = $this->headList;
$this->headList->previous = $this->headList;
}
}
1. 往链表中插入一个值(尾部插入)
public function insert($data) {
$currentNode = $this->headList;
while ($currentNode->next !== $this->headList) {
$currentNode = $currentNode->next;
}
$newNode = new Node($data);
$currentNode->next = $newNode;
$newNode->previous = $currentNode;
$newNode->next = $this->headList;
$this->headList->previous = $newNode;
}
$loop_link = new LoopLinkedList(1);
$loop_link->insert(2);
$loop_link->insert(3);
var_dump($loop_link);
结果：
object(LoopLinkedList)#1 (1) {
["headList":"LoopLinkedList":private]=>
object(Node)#2 (3) {
["data"]=>
int(1)
["next"]=>
object(Node)#3 (3) {
["data"]=>
int(2)
["next"]=>
object(Node)#4 (3) {
["data"]=>
int(3)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
["previous"]=>
*RECURSION*
}
["previous"]=>
object(Node)#4 (3) {
["data"]=>
int(3)
["next"]=>
*RECURSION*
["previous"]=>
object(Node)#3 (3) {
["data"]=>
int(2)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
}
}
}
2. 查询链表中的某个节点
public function find($query) {
$currentNode = $this->headList;
if ($currentNode->next === $this->headList) {
if ($currentNode->data == $query) {
return $currentNode;
} else {
return NULL;
}
}
$flag = false;
while ($currentNode->next !== $this->headList) {
if ($currentNode->data == $query) {
$flag = true;
return $currentNode;
}
$currentNode = $currentNode->next;
}
if ($currentNode->next === $this->headList && !$flag) {
if ($currentNode->data == $query) {
return $currentNode;
}
}
return NULL;
}
$loop_link = new LoopLinkedList(1);
$loop_link->insert(2);
$loop_link->insert(3);
$result = $loop_link->find(2);
var_dump($result);
结果:
object(Node)#3 (3) {
["data"]=>
int(2)
["next"]=>
object(Node)#4 (3) {
["data"]=>
int(3)
["next"]=>
object(Node)#2 (3) {
["data"]=>
int(1)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
["previous"]=>
*RECURSION*
}
["previous"]=>
object(Node)#2 (3) {
["data"]=>
int(1)
["next"]=>
*RECURSION*
["previous"]=>
object(Node)#4 (3) {
["data"]=>
int(3)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
}
}
3. 删除链表中的指定值的节点(不过有个特殊点，该方法返回的是删除节点的下一个节点，后续实战例子将使用到)
public function display($data) {
$currentNode = $this->headList;
$flag = false;
//只有一个节点的情况
if ($currentNode->next == $this->headList) {
if ($currentNode->data == $data) {
$flag = true;
$this->headList = NULL;
return NULL;
}
}
//开始节点到最后节点，不包括最后一个节点
while ($currentNode->next !== $this->headList && !$flag) {
if ($currentNode->data == $data) {
$flag = true;
$upPointer = $currentNode->previous;
$downPointer = $currentNode->next;
$currentNode->next->previous = $upPointer;
$currentNode->previous->next = $downPointer;
return $currentNode->next;
}
$currentNode = $currentNode->next;
}
//处理最后一个节点
if ($currentNode->data = $data && !$flag) {
$upPointer = $currentNode->previous;
$downPointer = $currentNode->next;
$currentNode->next->previous = $upPointer;
$currentNode->previous->next = $downPointer;
return $currentNode->next;
}
}
$loop_link = new LoopLinkedList(1);
$loop_link->insert(2);
$loop_link->insert(3);
$Node = $loop_link->display(2);
var_dump($Node);
结果：
object(Node)#4 (3) {
["data"]=>
int(3)
["next"]=>
object(Node)#2 (3) {
["data"]=>
int(1)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
["previous"]=>
object(Node)#2 (3) {
["data"]=>
int(1)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
}
至于还有别的方式，本次就不再一一介绍，接下来给大家一个实战例子
学校中经典常用到的，一群学生有各自的标号，围成一圈，一个红领巾将交给开始的学生，从这名开始学生开始计数之后每过3人，则将拿到红领巾的学生剔除，最终剩下的人一一约瑟夫环问题
约瑟夫环处理方式
//通过开始位置与偏移量，获取最后剩下的节点
public function getLastSurvivalNode($offset, $query = NULL) {
$position = 1;
if ($query == NULL) {
$queryNode = $this->headList;
} else {
//指定位置
$queryNode = $this->find($query);
if ( is_null($queryNode) ) {
echo "查询开始节点失败".PHP_EOL;
return;
}
}
while ( $queryNode->next != $queryNode ) {
if ($position == $offset) {
$queryNode = $this->display($queryNode->data);
$position = 1;
}
$queryNode = $queryNode->next;
$position++;
}
return $queryNode;
}
$loop_link = new LoopLinkedList(1);
$loop_link->insert(2);
$loop_link->insert(3);
$loop_link->insert(4);
$loop_link->insert(5);
$lastNode = $loop_link->getLastSurvivalNode(3);
var_dump($lastNode);
结果:
object(Node)#5 (3) {
["data"]=>
int(4)
["next"]=>
*RECURSION*
["previous"]=>
*RECURSION*
}
上一篇：PHP 链表结构之双链表（二）
author: clown
