Heim >Backend-Entwicklung >PHP-Tutorial >Einführung in die doppelt verknüpfte PHP-Liste
Einführung in die doppelt verknüpfte PHP-Liste
- 小云云Original
- 2018-03-22 09:44:251339Durchsuche
Doppelt verknüpfte Listen sind eine sehr wichtige Datenstruktur für PHP-Entwicklungsprogramme. Sie können sich ein PHP-Array als doppelt verknüpfte Liste vorstellen, und die in PHP integrierte SplDoublyLinkedList-Klasse implementiert Iteratoren, Array-Zugriff und Schnittstellen zum Abrufen von Mengen Der Zugriff auf Objekte ist so bequem wie der Zugriff auf Arrays.
SplDoublyLinkedList-Klassencode lautet wie folgt:
<?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);
}
}
}
?>Beispielbeschreibung:
<?php
$doubly=new SplDoublyLinkedList();
$doubly->push('a');
$doubly->push('b');
$doubly->push('c');
$doubly->push('d');
echo '初始链表结构：';
var_dump($doubly);
echo '<br/> 先进先出Keep模式迭代输出： <br/>';
$doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
$doubly->rewind();
foreach($doubly as $key=>$value)
{
echo $key.' '.$value."<br/>";
}
echo '<br/>后进先出Keep模式迭代输出：<br/>';
$doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP);
$doubly->rewind();
foreach($doubly as $key=>$value)
{
echo $key.' '.$value."<br/>";
}
echo '<br/>后进先出Delete模式迭代输出：<br/>';
$doubly->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);
$doubly->rewind();
foreach($doubly as $key=>$value)
{
if($key == 1) break;
echo $key.' '.$value."<br/>";
}
echo '<br/>Delete模式迭代之后的链表：';
var_dump($doubly);
?>
Ausgabe:
Anfänglich verknüpft Listenstruktur:
object(SplDoublyLinkedList)[1] private 'flags' => 0
private 'dllist' =>
array (size=4)
0 => 'a' (length=1)
1 => 'b' (length=1)
2 => 'c' (length=1)
3 => 'd' (length=1)
FIFO Keep-Modus-Iterationsausgabe:
0 a
1 b
2 c
3 d
LIFO Keep-Modus-Iterationsausgabe:
3 d
2 c
1 b
0 a
LIFO Musteriterationsausgabe löschen :
3 d
2 c
Verknüpfte Liste nach der Löschmusteriteration:
object(SplDoublyLinkedList)[1] private 'flags' => 3
private 'dllist' =>
array (size=2)
0 => 'a' (length=1)
1 => 'b' (length=1)Letzte Frage: Was ist die Iterationsausgabe des SplDoublyLinkedList::IT_MODE_FIFO |.
Verwandte Empfehlungen:
Detaillierte Erläuterung der Grundlagen von doppelt verknüpften PHP-Listen
So definieren und verwenden Sie doppelt verknüpfte JavaScript-Listen
Ein Beispielcode für die Implementierung einer doppelt verketteten Liste in PHP
Das obige ist der detaillierte Inhalt vonEinführung in die doppelt verknüpfte PHP-Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Stellungnahme：
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel：Detaillierte Erklärung des SplHeap-Heaps von PHPNächster Artikel：Detaillierte Erklärung des SplHeap-Heaps von PHP
In Verbindung stehende Artikel
Mehr sehen- So verwenden Sie cURL zum Implementieren von Get- und Post-Anfragen in PHP
- So verwenden Sie cURL zum Implementieren von Get- und Post-Anfragen in PHP
- So verwenden Sie cURL zum Implementieren von Get- und Post-Anfragen in PHP
- So verwenden Sie cURL zum Implementieren von Get- und Post-Anfragen in PHP
- Alle Ausdruckssymbole in regulären Ausdrücken (Zusammenfassung)