数据结构之php实现数组

说到数组，几乎每个IT江湖人士都不陌生，甚至过半人还会很自信觉得它很简单。 的确，在大多数编程语言中几乎都会有数组的影子。不过它不仅仅是一种基础的数据类型，更是一种基础的数据结构。

一、概念

那什么是数组呢? 我们一起来看下定义:

在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储

维基百科

正如以上所述， 数组在应用上属于数据的一个集合， 就是一个容器。不过我需要补充一点的是， 数组在数据结构范畴属于一种线性数据结构， 也就是只有前置节点和后续节点的数据结构。除了数组， 像平时所用的队列，栈，链表等也都是属于线性结构。

数组存储图形

相比各位IT江湖人士都知道的一件事情, 大部分的变成语言中数组的下标是从 0 开始编号的, 为什么这个与我们平时生活中从1开始编号的习惯相比有点”反人类”呢？

因为，数组在内存中是连续存储的， 当数组初始化后，数组的长度固定不变；需要增加数组长度时，由于数组的存储空间附近可能被其他数据存储的空间占用， 所以只能创建一片新的存储空间用来存储数组。而获取数组元素时，获取规则为：数组下标 * 数组类型字节大小 + 数组首地址的方式进行获取。如：一个int类型（4个字节）的数组，假设首地址为“2”。那么，第一位元素的地址 = 0 * 4 + 2；第二位元素的地址 = 1 * 4 + 2。

我们列出一个公式来进行分析一下。

// 下标从0开始
arr[i] = i * type_bytes(4) + base_address

// 下标从1开始
arr[i] = (i -1) * type_bytes(4) + base_address

比较两个计算公式可以发现公式（2）每次CPU寻址需要多一次 i-1的操作，即多了一次减法的指令运算。

对于数组这种基础数据结构，无论在哪种高级程序语言中，都是频繁间接（作为容器的基础数据结构，比如Java的ArrayList）或者直接被使用的，因此要尽量减少其消耗CPU资源。

二、代码实现

<?php

class ArrayStructure
{
    // 数组实际元素
    private $size = 0;

    // 数组的容量大小
    private $capacity = 0;

    // 用于存放数据
    private $data = [];

    /**
     * ArrayStruct constructor.
     *
     * @param int $capacity 数组容量大小
     */
    public function __construct($capacity = 10)
    {
        $this->capacity = $capacity;
    }

    /**
     * Notes: 获取数组实际元素个数
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:12
     *
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;

    }

    /**
     * Notes: 扩容
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 17:08
     *
     * @param $factor
     */
    protected function resize($factor)
    {
        $this->capacity = $factor * $this->capacity;

    }

    /**
     * Notes: 获取数组的容量
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:14
     *
     * @return int
     */
    public function getCapacity(): int
    {
        return $this->capacity;

    }

    /**
     * Notes: 数组是否为空
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:16
     *
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size === 0;

    }

    /**
     * Notes: 往数组指定位置插入数据
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:27
     *
     * @param int $index 需要插入的下标/索引
     * @param int $ele   需要插入的元素
     */
    public function add(int $index, $ele): void
    {
        // 如果当前的实际大小 等于 当前容量, 则不可以进行插入
        try {
            if ($this->size === $this->capacity) {
                throw new Exception("添加失败, Array 已经到达最大容量");
            }

            if ($index < 0 || $index > $this->size) {
                throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * 从最后一个元素开始进行遍历, 直到下标 为 当前输入的 下标, 终止
             * 每次将当前遍历的数值 往后 移动一位
             */
            for ($i = $this->size - 1; $i >= $index; $i --) {
                $this->data[$i + 1] = $this->data[$i];
            }

            // 目前当前下标还是存在之前的元素, 因为当前元素已经移动到后面一位, 所以直接覆盖就好
            $this->data[$index] = $ele;

            // 维护当前实际大小
            $this->size ++;
        }
        catch (Exception $e) {
            echo $e->getMessage();
        }

    }

    /**
     * Notes: 向所有元素后添加一个元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:19
     */
    public function addLast($element): void
    {
        $this->add($this->size, $element);

    }

    /**
     * Notes: 向第一位添加一个元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:19
     */
    public function addFirst(int $element): void
    {
        $this->add(0, $element);

    }

    /**
     * Notes: 数组转字符串
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:50
     *
     * @return string
     */
    public function toString(): string
    {
        $str = 'Array: size = ' . $this->size . ',' . 'capacity = ' . $this->capacity . PHP_EOL;
        $str .= '[';
        for ($i = 0; $i < $this->size; $i ++) {
            $str .= $this->data[$i];
            if ($i != $this->size - 1) {
                $str .= ',';
            }
        }

        $str .= ']';
        return $str . PHP_EOL;

    }

    /**
     * Notes: 获取指定下标位置的元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:13
     *
     * @param int $index
     *
     * @return int
     */
    public function get($index)
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("获取失败, index require >= 0 and < " . $this->size);
            }

            return $this->data[$index];
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 获取最后一个
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 15:48
     *
     * @return int
     */
    public function getLast()
    {
        return $this->get($this->size - 1);
    }

    /**
     * Notes: 获取第一个
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 15:48
     *
     * @return int
     */
    public function getFirst()
    {
        return $this->get(0);
    }

    /**
     * Notes: 修改指定下标位置的元素为 ele
     * User: think abel
     * Date: 2021/1/9 0009
     * Time: 12:04
     *
     * @param int $index
     * @param int $ele
     *
     * @return string
     */
    public function set(int $index, int $ele)
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("获取失败, index require >= 0 and < " . $this->size);
            }

            $this->data[$index] = $ele;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除指定位置上的元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:19
     *
     * @param int $index
     *
     * @return int|string
     */
    public function remove(int $index): int
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("移除失败, index require >= 0 and < " . $this->size);
            }

            $return = $this->data[$index];

            for ($i = $index + 1; $i < $this->size; $i ++) {
                $this->data[$i - 1] = $this->data[$i];
            }

            $this->size --;
            return $return;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除第一个
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:39
     *
     * @return int
     */
    public function removeFirst(): int
    {
        try {
            return $this->remove(0);
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除最后一个
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:39
     *
     * @return int
     */
    public function removeLast()
    {
        try {
            return $this->remove($this->size - 1);
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 如果有元素, 就删除
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:44
     *
     * @param int $ele
     *
     * @return bool
     */
    public function removeElement(int $ele): bool
    {
        $index = $this->find($ele);
        if ($index != - 1) {
            $this->remove($index);
        }

    }

    /**
     * Notes: 是否包含元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:22
     *
     * @param int $ele
     *
     * @return bool
     */
    public function contains(int $ele): bool
    {
        for ($i = 0; $i < $this->size; $i ++) {
            if ($this->data[$i] == $ele) {
                return true;
            }
        }

        return false;

    }

    /**
     * Notes: 获取当前元素的索引
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:22
     *
     * @param int $ele
     *
     * @return int
     */
    public function find(int $ele): int
    {
        for ($i = 0; $i < $this->size; $i ++) {
            if ($this->data[$i] == $ele) {
                return $i;
            }
        }

        return - 1;

    }
}

三、复杂度简单分析

O: 描述是算法的运行时间 和 输入数据之间的关系 — 程序运行时间 和 数数据 成线性关系 O(n)

添加操作

addLast(num)         O(1)

**删除操作**

removeLast(num)      O(1)

查找操作

getIndex(index)     O(1)

初次发文章, 欢迎指正检讨.
最后祝各位 新年快乐、永不加班～

本作品采用《CC 协议》，转载必须注明作者和本文链接