欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP SPL 数据结构笔记摘要

程序员文章站 2022-03-25 10:00:21
...
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)。

具体函数详细可参考php官方手册

以上就介绍了PHP SPL 数据结构笔记摘要,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。