SPL 标准库之数据结构

[huliuqing]

SPL 标准库之数据结构

SPL 标准库 : 数据结构文档

1. SplDoublyLinkedList : 双向链表

2. SplStack: 堆栈

3. SplQueue: 队列

4. SplHeap: 堆

5. SplMaxHeap: 最大堆

6. SplMinHeap: 最小堆

7. SplPriorityQueue: 优先队列

8. SplFixedArray: 定长数组

9. SplObjectStorage: 类提供从对象到数据的映射，或通过忽略数据来提供对象集

SPL 学习博文

一 SplDoublyLinkedList 双向链表

SplDoublyLinkedList : 双向链表

1.1 摘要

• SplDoublyLinkedList::__construct

  • — Constructs a new doubly linked list

• SplDoublyLinkedList::add(mixed $index, mixed $value)

  • — 向链表指定的位置新增或插入元素 (Add/insert a new value at the specified index)

• SplDoublyLinkedList::count()

  • — 获取双向链表元素个数 (Counts the number of elements in the doubly linked list.)

• SplDoublyLinkedList::isEmpty()

  • — 判断链表是否为空 (Checks whether the doubly linked list is empty.)

• SplDoublyLinkedList::valid()

  • — 判断链表是否有更多元素 (Check whether the doubly linked list contains more nodes)

• SplDoublyLinkedList::offsetExists(mixed $index)

  • — 判断指定位置索引 $index 的元素是否存在 (Returns whether the requested $index exists)

• SplDoublyLinkedList::offsetGet(mixed $index)

  • — 获取给定位置索引 $index 元素值 (Returns the value at the specified $index)

• SplDoublyLinkedList::offsetSet(mixed $index, mixed $newValue)

  • — 设置给定位置索引 $index 元素值 (Sets the value at the specified $index to $newval)

• SplDoublyLinkedList::offsetUnset(mixed $index)

  • — 删除给定位置索引 $index 元素 (Unsets the value at the specified $index)

• SplDoublyLinkedList::rewind()

  • — 重置链表指针至链表表头 (Rewind iterator back to the start)

• SplDoublyLinkedList::prev()

  • — 将链表指针移至上一个位置 (Move to previous entry)

• SplDoublyLinkedList::next()

  • — 将链表指针移至下一个位置 (Move to next entry)

• SplDoublyLinkedList::current()

  • — Return current array entry

• SplDoublyLinkedList::key()

  • — 获取当前元素所在位置索引 (Return current node index)

• SplDoublyLinkedList::shift()

  • — 移除链表表头元素 (Shifts a node from the beginning of the doubly linked list)

• SplDoublyLinkedList::unshift(mixed $value)

  • — 向链表表头插入元素 (Prepends the doubly linked list with an element)

• SplDoublyLinkedList::pop()

  • — 从链表尾部弹出元素 (Pops a node from the end of the doubly linked list)

• SplDoublyLinkedList::push(mixed $value)

  • — 向链表尾部推入元素 (Pushes an element at the end of the doubly linked list)

• SplDoublyLinkedList::bottom()

  • — 获取链表表头元素值 (Peeks at the node from the beginning of the doubly linked list)

• SplDoublyLinkedList::top()

  • — 获取链表表尾元素 (Peeks at the node from the end of the doubly linked list)

• SplDoublyLinkedList::serialize()

  • — Serializes the storage

• SplDoublyLinkedList::unserialize(string $serialized)

  • — Unserializes the storage

• SplDoublyLinkedList::setIteratorMode(int $mode)

  • — Sets the mode of iteration

• SplDoublyLinkedList::getIteratorMode()

  • — Returns the mode of iteration

<?php
function d($data, $title = null)
{
    printf("--- BEGIN %s---%s", is_null($title) ? '' : ':' . $title, PHP_EOL);
    var_dump($data);
    printf('--- END ---%s', PHP_EOL);
}

$numStore = new SplDoublyLinkedList();

if ($numStore->isEmpty()) {
    $i = 0;
    while ($i < 5) {
        $numStore->add($i, $i + 1);
        ++$i;
    }
}

d($numStore, 'DEBUG numStore');
d($numStore->isEmpty(), 'is empty ?');//false
d($numStore->count(), "num count");//5

//-------------------------
$numStore->unshift(0);//表头添加元素 0
$numStore->push(6);//表尾添加元素 6
d($numStore, 'DEBUG numStore');

//-------------------------
$topVal = $numStore->top();//获取顶部(即表尾)元素
$btmVal = $numStore->bottom();//获取底部(即表头)元素
d($topVal, 'top value');//6
d($btmVal, 'bottom value');//0
d($numStore, 'DEBUG numStore');

//-------------------------
$shiftVal = $numStore->shift();
$popVal = $numStore->pop();

d($shiftVal, 'shift value');//6
d($popVal, 'pop value');//0
d($numStore, 'DEBUG numStore');

//-------------------------
$offset = ceil($numStore->count() / 2);
$exists = $numStore->offsetExists($offset);
$offsetVal = $numStore->offsetGet($offset);

d($exists, sprintf("is idx:%s exists", $offset));//true
d($offsetVal, 'offset val');//true

$numStore->offsetSet($offset, 4.4);
$offsetValAfterSet = $numStore->offsetGet($offset);
d($offsetValAfterSet, 'offsetValAfterSet');
d($numStore, 'DEBUG numStore5');

$numStore->offsetUnset($offset);
d($numStore, 'DEBUG numStore6');


//-------------------------
//遍历
$numStore->rewind();
while ($numStore->valid()) {
    printf("key: %s => val: %s %s", $numStore->key(), $numStore->current(), PHP_EOL);
    $numStore->next();
}

二 SplStack 堆栈

SplStack: 堆栈

SplStack 继承自 SplDoublyLinkedList，所有方法和父类相同

<?php

function d($data, $title = null)
{
    printf("--- BEGIN %s---%s", is_null($title) ? '' : ':' . $title, PHP_EOL);
    var_dump($data);
    printf('--- END ---%s', PHP_EOL);
}

$reflector = new ReflectionClass('SplStack');

d($reflector->getParentClass(), 'parent class');//获取父类
d($reflector->getMethods());//获取方法
d($reflector->getInterfaces(), 'interfaces');//获取接口

三 SplQueue 队列

SplQueue

SplQueue 继承自 SplDoublyLinkedList，所有方法和父类相同

新增方法

• SplQueue::enqueue(mixed $value)

  • — 向队列加入元素 Adds an element to the queue

• SplQueue::dequeue()

  • — 从队列删除元素 Dequeues a node from the queue

<?php

function d($data, $title = null)
{
    printf("--- BEGIN %s---%s", is_null($title) ? '' : ':' . $title, PHP_EOL);
    var_dump($data);
    printf('--- END ---%s', PHP_EOL);
}

// $reflector = new ReflectionClass('SplQueue');

// d($reflector->getParentClass(), 'parent class');//获取父类
// d($reflector->getMethods());//获取方法
// d($reflector->getInterfaces(), 'interfaces');//获取接口

$waitQueue = new SplQueue();

//------------------
//入列，出列
$waitQueue->enqueue(1);
$waitQueue->enqueue(2);
d($waitQueue, "q");

$waitQueue->dequeue();
d($waitQueue, "q");
$waitQueue->dequeue();
d($waitQueue, "q");

//-------------------
//继承方法
$waitQueue->push(1);
$waitQueue->push(2);
$waitQueue->push(3);

d($waitQueue, 'q');

$waitQueue->unshift(0);
d($waitQueue, 'q');

d($waitQueue->bottom(), "bottom");
d($waitQueue->top(), "top");

$waitQueue->offsetSet(1, 1.1);
d($waitQueue, "q");

四 Heap 堆

Wiki 堆

堆(Heap)就是为了实现优先队列而设计的一种数据结构，它是通过构造二叉堆(二叉树的一种)实现。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。

• PHP标准库(SPL)学习之SplHeap

4.1 SplHeap 堆

SplHeap 文档

** SplHeap** 是一个抽象类，必须实现 compare() 方法

abstract SplHeap implements Iterator , Countable {
    /* 方法 */
    public __construct ( void )
    abstract protected int compare ( mixed $value1 , mixed $value2 )//比较元素，以便在筛选时正确地将它们放置在堆中
    public int count ( void )
    public mixed current ( void )
    public mixed extract ( void )//从堆顶部提取一个节点并进行筛选。
    public void insert ( mixed $value )
    public bool isEmpty ( void )
    public mixed key ( void )
    public void next ( void )
    public void recoverFromCorruption ( void )//Recover from the corrupted state and allow further actions on the heap
    public void rewind ( void )
    public mixed top ( void )
    public bool valid ( void )
}

资料

https://zhuanlan.zhihu.com/p/26766321
http://www.cppblog.com/guogangj/archive/2013/05/10/99729.html
https://zh.wikipedia.org/wiki/%E5%A0%86_%28%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%29
https://zmis.me/detail_898
http://www.cppblog.com/guogangj/default.html?page=6