数据结构-PHP实现Array

码农天地 - 2020-10-19 08:11:19

---

这篇文章是展示如何使用PHP语言实现Array这种数据结构。

1.ArrayStruct 类

<?php
class ArrayStruct
{
    //用于存放数据
    protected $data = [];
    //用于标记数组大小
    protected $size = 0;
    //用于标记数组的容量
    protected $capacity = 10;
    /**
     * 构造函数 定义数组容量
     * ArrayStruct constructor.
     * @param int $capacity
     */
    public function __construct(int $capacity = 10) {
        $this->capacity = $capacity;
    }
    /**
     * 获取数组元素个数
     * @return int
     */
    public function getSize(): int {
        return $this->size;
    }
    /**
     * 获取数组的容量
     * @return int
     */
    public function getCapacity(): int {
        return $this->capacity;
    }
    /**
     * 判断数组是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }
    /**
     * 向数组指定位置插入元素
     * @param int $index
     * @param $e
     * @throws Exception
     */
    public function add(int $index, $e): void {
        if ($this->size == $this->capacity) {
            $this->resize(2); //扩大到原来的2倍
        }
        if ($index < 0 || $index > $this->size) {
            echo "添加位置超出数组大小";
            exit;
        }
        //为了方便理解，[1,2,4,5,6],假设 $index = 3; $e = 100,插入之后[1,2,4,100,5,6]
        for ($i = $this->size; $i >= $index; $i--) {
            $this->data[$i] = $this->data[$i - 1];
        }
        $this->data[$index] = $e;
        $this->size++;
    }
    /**
     * 向数组末尾添加元素
     * @param $e
     * @throws Exception
     */
    public function addLast($e): void {
        $this->add($this->size, $e);
    }
    /**
     * 向数组开头插入元素
     * @param $e
     * @throws Exception
     */
    public function addFirst($e): void {
        $this->add(0, $e);
    }
    /**
     * 获取 index 位置数组元素
     * @param int $index
     * @return mixed
     */
    public function get(int $index) {
        if ($index < 0 || $index > $this->size) {
            echo "index值超出元素的位置范围，";
            exit;
        }
        return $this->data[$index];
    }
    /**
     * 判断数组中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        for ($i = 1; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                return true;
            }
        }
        return false;
    }
    /**
     * 查某个元素在数组的位置索引值，若不存在则返回 -1
     * @param $e
     * @return int
     */
    public function find($e): int {
        for ($i = 0; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                return $i;
            }
        }
        return -1;
    }
    /**
     * 删除数组指定位置元素，返回删除元素的值
     * @param $index
     * @return mixed
     */
    public function remove($index) {
        if ($index < 0 || $index > $this->size) {
            echo "index值超出元素的位置范围，";
            exit;
        }
        $e = $this->data[$index];
        for ($i = $index; $i < $this->size - 1; $i++) {
            $this->data[$i] = $this->data[$i + 1];
        }
        $this->size--;
        $this->data[$this->size] = null;  //loitering objects ! =memory
        /** 若当前数组大小，小于容量的一半，则重新分配一半的数组空间大小 **/
        if ($this->size <= $this->capacity / 4 && $this->capacity % 2 == 0) {
            $this->resize(0.5);
        }
        return $e;
    }
    /**
     * 删除数组首个元素，返回删除元素的值
     */
    public function removeFirst() {
        return $this->remove(0);
    }
    /**
     * 删除数组首个元素，返回删除元素的值
     */
    public function removeLast() {
        return $this->remove($this->size);
    }
    /**
     * 删除数组中特定元素
     * @param $e
     */
    public function removeElement($e) {
        for ($i = 0; $i < $this->size; $i++) {
            if ($this->data[$i] == $e) {
                $this->remove($i);
                $this->removeElement($e);
                break;
            }
        }
    }
    /**
     * 数组扩容，若是其他语言，如JAVA这里需要重新开辟空间
     * @param $factor
     */
    protected function resize($factor) {
        $this->capacity = $factor * $this->capacity;
    }
    /**
     * 将数组转化为字符串
     * @return string
     */
    public function toString(): string {
        $str = "[";
        foreach ($this->data as $value) {
            $str .= $value . ",";
        }
        $str = trim($str, ",");
        $str .= "]";
        return $str;
    }
}

2.index.php

<?php
require 'ArrayStruct.php';
$array = new ArrayStruct(10);
$array->addLast(1);
$array->addLast("aa");
$array->addLast(1);
$array->addLast("cc");
$array->addFirst("cc");
$array->addFirst("ff");
$array->addLast(100);
$array->addLast(100);
$array->addLast(100);
$array->addLast(100);
$array->addLast(100);
$array->addLast(100);
$array->addFirst("ad");
$array->addFirst("ss");
$array->addFirst("nn");
$array->addFirst("mm");
echo $array->toString();
//打印结果 [mm,nn,ss,ad,ff,cc,1,aa,1,cc,100,100,100,100,100,100]

3.简单的复杂度分析3.1 添加操作

addLast(num)   O(1)
addFirst(num)  O(n)
addIndex(index，num)  O(n)   严格计算需要一些概率论知识
resize(size)  O(1)

Tips：由于PHP语言本身的数组底层会自动实现扩容，这里 resize()复杂度暂且看做 O(1)，若是其他语言，如 JAVA 实现resize() 需要重新开辟空间转移数据，复杂度看做 O(n) 。3.2 删除操作

removeLast(num)   O(1)
removeFisrt()     O(n)
remove(index，num)   O(n/2) = O(n)
resize(size)  O(1)

Tips：由于PHP语言本身的数组底层会自动实现扩容，这里 resize()复杂度暂且看做 O(1)，若是其他语言，如 JAVA 实现resize() 需要重新开辟空间转移数据，复杂度看做 O(n) 。3.3 查找操作

getIndex(index)    O(1)
isset(num)          O(n)
find(num)            O(n)

3.4 均摊复杂度

addLast(num)    O(1)
resize()   O(1)
上述两个组合在一起均摊在一起复杂度相当于 O(1)

Tips：由于PHP语言本身的数组底层会自动实现扩容，这里 resize()复杂度暂且看做 O(1)，若是其他语言，如 JAVA 实现resize() 需要重新开辟空间转移数据，复杂度看做 O(n) 。3.5 防止复杂度的震荡

若把 resize() 复杂度看做 O(n)，则需要考虑复杂度震荡问题：

addLast(num)   O(1)
resize    O(n)
removeLast(num)    O(1)

Tips:当容量满了的时候可能存在一直触发 resize() ，使得时间复杂度变为 O(n)，这种情况称为复杂度震荡，解决办法是，当 size 小于等于 1/2 容量的时候才缩小容量。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

php程序员算法

扩展阅读