PHP SPL 数据结构笔记摘要-php教程-PHP中文网

PHP SPL 数据结构笔记摘要

php中文网

发布： 2016-07-29 09:08:59

原创

1499人浏览过

php spl（standard php library）主要用到的数据结构有：双向链表(spldoublylinkedlis)，栈(splstack)，队列(splqueue)，堆(splheap)，大根堆(splmaxheap)，小根堆(splminheap)，优先级队列（splpriorityqueue），固定数组（splfixedarray），对象存储（splstorageobject）。

SplDoublyLinkedList

数据结构：（c代码参考PHP7.0.0）

typedef struct _spl_ptr_llist_element {
    struct _spl_ptr_llist_element *prev;
    struct _spl_ptr_llist_element *next;
    int                            rc;      // 引用次数
    void                          *data;    // 数据类型
} spl_ptr_llist_element;

typedef struct _spl_ptr_llist {
    spl_ptr_llist_element   *head;  
    spl_ptr_llist_element   *tail;
    spl_ptr_llist_dtor_func  dtor;    // 删除元素   引用-1
    spl_ptr_llist_ctor_func  ctor;    // 创建元素   引用+1
    int count;                        // 元素个数
} spl_ptr_llist;

struct _spl_dllist_object {
    zend_object            std;
    spl_ptr_llist         *llist;
    int                    traverse_position;
    spl_ptr_llist_element *traverse_pointer;
    zval                  *retval;
    int                    flags;
    zend_function         *fptr_offset_get;
    zend_function         *fptr_offset_set;
    zend_function         *fptr_offset_has;
    zend_function         *fptr_offset_del;
    zend_function         *fptr_count;
    zend_class_entry      *ce_get_iterator;
    HashTable             *debug_info;
};

登录后复制

双向链表
SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
	/* 方法 */
	public __construct ( void )
	public void add ( mixed $index , mixed $newval )
	public mixed bottom ( void )
	public int count ( void )
	public mixed current ( void )
	public int getIteratorMode ( void )
	public bool isEmpty ( void )
	public mixed key ( void )
	public void next ( void )
	public bool offsetExists ( mixed $index )
	public mixed offsetGet ( mixed $index )
	public void offsetSet ( mixed $index , mixed $newval )
	public void offsetUnset ( mixed $index )
	public mixed pop ( void )
	public void prev ( void )
	public void push ( mixed $value )
	public void rewind ( void )
	public string serialize ( void )
	public void setIteratorMode ( int $mode )
	public mixed shift ( void )      // 删除第一个元素
	public mixed top ( void )
	public void unserialize ( string $serialized )
	public void unshift ( mixed $value )   //将value插入的第一个元素，原来的第一个元素不删除
	public bool valid ( void )
}

登录后复制

需要注意的是：

add 是5.5+版本添加的函数，其它都是5.3+

从数据结构中可以看出，虽然许多函数中都包含有直接索引第index 个元素，如果不在范围则抛出OutOfRangeException异常，实际实现时时间复杂度为O(n)。