1. 特色
汇合内的元素不会反复，所以在增加的时候就须要判断是否有元素存在
2. 工夫复杂度剖析
| 操作 | 工夫复杂度 |
|---|
| 增加 | O(1) |
| 删除 | O(n) |
| 查问 | O(n) |
3. 代码
/** * content: 汇合的元素结点 * create: 2020-11-03 */<?phpnamespace SetBundle;class Node{ /** * 尾指针 * @var Node|null */ protected $tail; /** * 该节点存储额值 * @var mixed */ protected $value; public function __construct($value = null, ?Node $tail = null) { $this->setTail($tail)->setValue($value); } /** * 设置尾结点 * @param Node|null $tail * @return $this */ public function setTail(?Node $tail): self { $this->tail = $tail; return $this; } /** * 获取尾结点 * @return Node|null */ public function getTail(): ?Node { return $this->tail; } /** * 设置值 * @param mixed $value * @return $this */ public function setValue($value): self { $this->value = $value; return $this; } /** * 获取结点里的值 * @return mixed */ public function getValue() { return $this->value; }}
<?php/** * content: 汇合（链表实现） * auth: 俞佳明 * create: 2020-11-03 */namespace SetBundle;class LinkSet{ /** * @var Node|null */ protected $node; /** * 汇合大小 * @var int */ protected $size; public function __construct() { $this->node = null; $this->size = 0; } /** * 获取汇合中的元素 * @return int */ public function getSize(): int { return $this->size; } /** * 查问是否存在该值的结点 * @param $value * @return Node|null */ public function contains($value): ?Node { $node = $this->node; while (!is_null($node)) { if ($node->getValue() === $value) { return $node; } $node = $node->getTail(); } return null; } /** * 插入 * @param string|int $value * @return Node * @throws \Exception */ public function add($value): Node { $newNode = new Node($value, null); if (is_null($this->node)) { $this->node = $newNode; } else { if (!is_null($this->contains($value))) { throw new \Exception('插入的元素已存在！'); } $newNode->setTail($this->node); $this->node = $newNode; } $this->size++; return $newNode; } /** * 删除 * @param $value */ public function remove($value) { $node = $this->node; while (!is_null($node) && !is_null($node->getTail())) { if ($node->getTail()->getValue() === $value) { $node->setTail($node->getTail()->getTail()); $this->size--; return; } $node = $node->getTail(); } return; } public function varDump() { $node = $this->node; while (!is_null($node)) { echo $node->getValue(). PHP_EOL; $node = $node->getTail(); } }}
4. 示例
<?phprequire_once __DIR__ . '/../../vendor/autoload.php';$set = new SetBundleLinkSet();$set->add(1);$set->add(2);$set->add(3);$set->add(4);$set->add(5);$set->add(6);$set->varDump();
654321