线性表的顺序存储结构

线性顺序表__顺序存储结构

在存、读数据时，时间复杂度为O(1)；而当插入或删除数据时，时间复杂度为O(n)。
说明它比较适合元素个数不大变化，而更多是存取数据的应用。

优点：
无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点：
插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的“碎片”

class Sequence
{
    private $data = [];
    private $len = 0;
    private $dataLen = 0; //线性表大小

    function __construct($dataLen, $data = [])
    {
        $this->dataLen = $dataLen;
        $this->data = $data;
        $this->len = count($data);
    }

    /**
     * 在线性表的末尾添加元素
     * @param $value
     * @return array|string
     */
    function add($value)
    {
        if (!$this->checkLen()) {
            return 'Error';
        }
        $this->data[] = $value;
        $this->len++;
        return $this->data;
    }

    /**
     * 检测线性表空间
     * @return bool
     */
    function checkLen()
    {
        if ($this->len >= $this->dataLen) {
            return false;
        }
        return true;
    }

    /**
     * 在第index的位置插入元素elem
     * @param $index
     * @param $elem
     * @return array
     */
    function Insert($index, $elem)
    {
        if (!$this->checkLen() || $index < 1 || $index > $this->dataLen) {
            return ['Error'];
        }
        if ($index <= $this->len) {
            for ($i = $this->len - 1; $i >= $index - 1; $i--) {
                $this->data[$i + 1] = $this->data[$i];
            }
        }
        $this->data[$index - 1] = $elem;
        $this->len++;
        return $this->data;
    }

    /**
     * 删除第$index位置的元素
     * @param $index
     * @return array
     */
    function Delete($index)
    {
        if (!$this->checkLen() || $index < 1 || $index > $this->dataLen) {
            return ['Error'];
        }
        if ($index <= $this->len) {
            for ($i = $index - 1; $i < $this->len - 1; $i++) {
                $this->data[$i] = $this->data[$i+1];
            }
            unset($this->data[$this->len -1]);
        }
        $this->len--;
        return $this->data;
    }
}