Maison > Article > développement back-end > PHP n'a-t-il pas un type de liste chaînée ?
PHP n'a-t-il pas un type de liste chaînée ?
- (*-*)浩original
- 2019-09-23 09:32:233097parcourir
La bibliothèque standard PHP SPL implémente plusieurs listes linéaires simples et structures arborescentes, y compris des listes à double lien et des implémentations de listes à double lien de files d'attente et de piles, de tas maximum, de tas minimum et de files d'attente prioritaires. La liste doublement chaînée est une structure de stockage linéaire importante. Pour chaque nœud de la liste doublement chaînée, elle stocke non seulement ses propres informations, mais stocke également les adresses des nœuds prédécesseurs et successeurs.
La liste double chaînée est une structure de données très importante pour les programmes de développement PHP. Vous pouvez considérer un tableau PHP comme une liste doublement chaînée construite par PHP. -in La classe SplDoublyLinkedList rend l'accès du programme aux objets aussi pratique que l'accès aux tableaux en implémentant des interfaces pour les itérateurs, l'accès aux tableaux et l'acquisition de quantités. (Apprentissage recommandé : Programmation PHP de l'entrée à la maîtrise)
Le code de la classe SplDoublyLinkedList est le suivant :
<?php
/**
* PS：预定义接口Iterator, ArrayAccess, Countable
*/
class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable
{
/**
* @var _llist 定义一个数组用于存放数据
*/
protected $_llist = array();
/**
* @var _it_mode 链表的迭代模式
*/
protected $_it_mode = 0;
/**
* @var _it_pos 链表指针
*/
protected $_it_pos = 0;
/**
* 迭代模式
* @see setIteratorMode
*/
const IT_MODE_LIFO = 0x00000002;
const IT_MODE_FIFO = 0x00000000;
const IT_MODE_KEEP = 0x00000000;
const IT_MODE_DELETE = 0x00000001;
/**
* @return 返回被移出尾部节点元素
* @throw RuntimeException 如果链表为空则抛出异常
*/
public function pop()
{
if (count($this->_llist) == 0) {
throw new RuntimeException("Can't pop from an empty datastructure");
}
return array_pop($this->_llist);
}
/**
* @return 返回被移出头部节点元素
* @throw RuntimeException 如果链表为空则抛出异常
*/
public function shift()
{
if (count($this->_llist) == 0) {
throw new RuntimeException("Can't shift from an empty datastructure");
}
return array_shift($this->_llist);
}
/**
* 往链表尾部添加一个节点元素
* @param $data 要添加的节点元素
*/
public function push($data)
{
array_push($this->_llist, $data);
return true;
}
/**
* 往链表头部添加一个节点元素
* @param $data 要添加的节点元素
*/
public function unshift($data)
{
array_unshift($this->_llist, $data);
return true;
}
/**
* @return 返回尾部节点元素，并把指针指向尾部节点元素
*/
public function top()
{
return end($this->_llist);
}
/**
* @return 返回头部节点元素，并把指针指向头部节点元素
*/
public function bottom()
{
return reset($this->_llist);
}
/**
* @return 返回链表节点数
*/
public function count()
{
return count($this->_llist);
}
/**
* @return 判断链表是否为空
*/
public function isEmpty()
{
return ($this->count() == 0);
}
/**
* 设置迭代模式
* - 迭代的顺序 (先进先出、后进先出)
* - SplDoublyLnkedList::IT_MODE_LIFO (堆栈)
* - SplDoublyLnkedList::IT_MODE_FIFO (队列)
*
* - 迭代过程中迭代器的行为
* - SplDoublyLnkedList::IT_MODE_DELETE (删除已迭代的节点元素)
* - SplDoublyLnkedList::IT_MODE_KEEP (保留已迭代的节点元素)
*
* 默认的模式是 0 : SplDoublyLnkedList::IT_MODE_FIFO | SplDoublyLnkedList::IT_MODE_KEEP
*
* @param $mode 新的迭代模式
*/
public function setIteratorMode($mode)
{
$this->_it_mode = $mode;
}
/**
* @return 返回当前的迭代模式
* @see setIteratorMode
*/
public function getIteratorMode()
{
return $this->_it_mode;
}
/**
* 重置节点指针
*/
public function rewind()
{
if ($this->_it_mode & self::IT_MODE_LIFO) {
$this->_it_pos = count($this->_llist)-1;
} else {
$this->_it_pos = 0;
}
}
/**
* @return 判断指针对应的节点元素是否存在
*/
public function valid()
{
return array_key_exists($this->_it_pos, $this->_llist);
}
/**
* @return 返回当前指针的偏移位置
*/
public function key()
{
return $this->_it_pos;
}
/**
* @return 返回当前指针对应的节点元素
*/
public function current()
{
return $this->_llist[$this->_it_pos];
}
/**
* 将指针向前移动一个偏移位置
*/
public function next()
{
if ($this->_it_mode & self::IT_MODE_LIFO) {
if ($this->_it_mode & self::IT_MODE_DELETE) {
$this->pop();
}
$this->_it_pos--;
} else {
if ($this->_it_mode & self::IT_MODE_DELETE) {
$this->shift();
} else {
$this->_it_pos++;
}
}
}
/**
* @return 偏移位置是否存在
*
* @param $offset 偏移位置
* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常
*/
public function offsetExists($offset)
{
if (!is_numeric($offset)) {
throw new OutOfRangeException("Offset invalid or out of range");
} else {
return array_key_exists($offset, $this->_llist);
}
}
/**
* @return 获取偏移位置对应的值
*
* @param $offset 偏移位置
* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常
*/
public function offsetGet($offset)
{
if ($this->_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this->_llist)-$offset;
} else {
$realOffset = $offset;
}
if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
} else {
return $this->_llist[$realOffset];
}
}
/**
* @return 设置偏移位置对应的值
*
* @param $offset 偏移位置
* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常
*/
public function offsetSet($offset, $value)
{
if ($offset === null) {
return $this->push($value);
}
if ($this->_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this->_llist)-$offset;
} else {
$realOffset = $offset;
}
if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
} else {
$this->_llist[$realOffset] = $value;
}
}
/**
* @return 删除偏移位置对应的值
*
* @param $offset 偏移位置
* @throw OutOfRangeException 如果偏移位置超出范围或者无效则抛出异常
*/
public function offsetUnset($offset)
{
if ($this->_it_mode & self::IT_MODE_LIFO) {
$realOffset = count($this->_llist)-$offset;
} else {
$realOffset = $offset;
}
if (!is_numeric($offset) || !array_key_exists($realOffset, $this->_llist)) {
throw new OutOfRangeException("Offset invalid or out of range");
} else {
array_splice($this->_llist, $realOffset, 1);
}
}
}
?>Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!