关于数据结构:5-数据结构PHP实现-集合-用链表来实现

1. 特色

• 汇合内的元素不会反复，所以在增加的时候就须要判断是否有元素存在

2. 工夫复杂度剖析

3. 代码

• 元素结点

/**
 * content: 汇合的元素结点
 * create: 2020-11-03
 */
<?php
namespace 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. 示例

<?php
require_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();

6
5
4
3
2
1