README

PHP >= 7.0 的数据结构。使用此库在项目中使用数据结构。

索引

安装

通过Composer直接复制粘贴

composer require siro-diaz/data-structures:"dev-master"

API

列表

支持以下列表数据结构

列表类型: 类

单链表: SinglyLinkedList
循环单链表: CircularLinkedList
循环双链表: DoublyLinkedList
数组列表: ArrayList
栈: Stack
队列: Queue

单链表

介绍

单链表是可以创建的最简单的链表。它有一个指向列表中下一个节点的指针，最后一个节点指向null。除了栈和队列之外的所有列表都有相同的方法，因为它们实现了相同的接口。

方法

size()
empty()
get($index)
getAll()
getLast()
delete($index)
clear()
pop()
insert($index, $data)
push($data)
unshift($data)
shift()
toArray()

示例

use DataStructures\Lists\SinglyLinkedList;

$myList = new SinglyLinkedList();
$myList->push(20);
echo "Size of : ". $myList->size();
$myList->unshift(100);
echo "Item at the beginnig: ". $myList->get(0);

循环链表

介绍

循环链表是一个单链表，它有一个指向最后一个和第一个节点的指针。除了栈和队列之外的所有列表都有相同的方法，因为它们实现了相同的接口。

方法

size()
empty()
get($index)
getAll()
getLast()
delete($index)
clear()
pop()
insert($index, $data)
push($data)
unshift($data)
shift()
toArray()

示例

use DataStructures\Lists\CircularLinkedList;

$myList = new CircularLinkedList();
$myList->push(20);
$myList->push(10);
echo "Size of : ". $myList->size();
$myList->unshift(100);
echo "Item at the beginnig: ". $myList->get(0);
echo "Last item: ". $myList->getLast();

双循环链表

介绍

双循环链表是一个双链表，其中每个节点都包含指向列表中下一个和前一个节点的指针。在第一个节点中，它将指向最后一个节点。它在插入、获取和删除操作中使用了某些性能技巧。

方法

size()
empty()
get($index)
getAll()
getLast()
delete($index)
clear()
pop()
insert($index, $data)
push($data)
unshift($data)
shift()
toArray()

示例

use DataStructures\Lists\DoublyLinkedList;

$myList = new DoublyLinkedList();
$myList->push(20);
$myList->push(10);
echo "Size of : ". $myList->size();
$myList->unshift(100);
echo "Item at position 1: ". $myList->get(1);
echo "Last item: ". $myList->getLast();

数组列表

介绍

数组列表使用内置数组作为列表。在PHP中所有使用哈希表，它使得数组列表在像获取这样的操作中具有性能优势，这将达到O(1)。数组列表自动增加其大小，无需手动增加。这使得实现此类列表变得非常简单。

方法

size()
empty()
get($index)
getAll()
getLast()
delete($index)
clear()
pop()
insert($index, $data)
push($data)
unshift($data)
shift()
toArray()

示例

use DataStructures\Lists\ArrayList;

$myList = new ArrayList();
$myList->push(20);
$myList->push(10);
echo "Size of : ". $myList->size();
$myList->unshift(100);
echo "Item at position 1: ". $myList->get(1);
echo "Last item: ". $myList->getLast();

栈

介绍

栈是一个后进先出（LIFO）数据结构，其工作方式与栈（正如其名称所示）。最后插入的元素将是第一个出去的。此库中使用的实现允许指定最大大小，换句话说，它可以是一个受限栈。当使用受限栈时，在插入新元素之前检查它是否已满非常重要。

方法

size()
empty()
isFull()
peek()
pop()
push($data)

示例

use DataStructures\Lists\Stack;

$myStack = new Stack(); // unlimited stack.
// new Stack(5) will contain a maximum of 5 elements.
$myStack->push(20);
$myStack->push(10);
echo "Size of : ". $myStack->size();
echo "Front element: ". $myStack->peek(1);
echo "Last element inserted and being removed: ". $myStack->pop();

树

支持以下树数据结构

树类型: 类

字典树: TrieTree
二叉搜索树: BinarySearchTree
AVL树: AVLTree

字典树

介绍

方法

size()
empty()
wordCount()
withPrefix($prefix)
startsWith($prefix)
getWords()
clear()
delete($word)
contains($word)
add($word)

示例

use DataStructures\Trees\TrieTree;

$trie = new TrieTree();
$trie->add('hello');
$trie->add('hell');
$trie->add('world');
echo "Size of : ". $trie->wordCount();  // 3
$trie->contains('hell');    // true

echo "There are words that start with 'he': ". $trie->startsWith('he');   // true

二叉搜索树

介绍

二叉搜索树（BST）是一种数据结构，它有一个根节点，该节点最多可以有2个兄弟节点。每个兄弟节点也最多可以有2个兄弟节点。如果一个节点没有兄弟节点，则称为叶子节点。左兄弟节点的值小于父节点，右兄弟节点的值大于父节点。

方法

size()
empty()
delete($key)
put($key, $data, $update = false)
putOrUpdate($key, $data)
get($key)
getRoot()
exists($key)
min()
max()
deleteMin(BinaryNodeInterface $node = null)
deleteMax(BinaryNodeInterface $node = null)
search($key)
isLeaf($node)
isRoot($node)
preorder(Callable $callback = null)
inorder(Callable $callback = null)
postorder(Callable $callback = null)

示例

use DataStructures\Trees\BinarySearchTree;

$bst = new BinarySearchTree();
$bst->put(4, 10);
$bst->put(2, 100);
$bst->put(10, 1000);
echo "Size of : ". $bst->size();
$bst->exists(100);  // false
echo "Is leaf?: ". $bst->isLeaf($bst->min());   // true

AVL树

介绍

AVL树是一种具有平衡条件的二叉搜索树。该条件是每个子节点相对于其对立侧子树的高度最多为1（这意味着一个节点的右子树的高度不能比左子树高超过1）。如果一个节点的高度为2或更多，则通过单左旋转、单右旋转、双左旋转或双右旋转来重新平衡树。

方法

与二叉搜索树相同的方法。

示例

use DataStructures\Trees\AVLTree;

$avl = new BinarySearchTree();
$avl->put(4, 10);
$avl->put(2, 100);
$avl->put(10, 1000);
echo "Size of : ". $avl->size();
$avl->exists(100);  // false
echo "Is leaf?: ". $avl->isLeaf($avl->min());   // true

siro-diaz / data-structures

维护者

详细信息