5.データ構造(PHP実装)--集合(チェーンテーブルで実装)

1.特徴

集合内の要素は重複しないので、追加時に

の要素が存在するか否かを判断する必要がある.
2.時間複雑度分析
操作
時間の複雑さ
追加
O(1)
削除
O(n)
検索
O(n)
3.コード

要素ノード

/**
 * content:        
 * create: 2020-11-03
 */
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;
    }
}

セットのコード

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)
    {
        //             
        if (is_null($this->node)) return;
        
        //            
        if ($this->node->getKey() == $key) {
            $this->node = $this->node->getTail();
            $this->size--;
            return;
        }
        //           
        $node = $this->node;
        while (!is_null($node->getTail())) {
            if ($node->getTail()->getKey() === $key) {
                $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.例

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