数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。PHPHa 通过本文简单介绍下数组的定义以及用 PHP 代码模拟数组的相关操作。

数组定义相关的 2 个关键词:

1、线性表(Linear List

顾名思义,线性表就是数据排成像⼀条线⼀样的结构。每个线性表上的数据最多只有前和后两个⽅向。其实除了数组,链表、队列、栈等也是线性表结构。⽽与它相对⽴的概念是⾮线性表,⽐如⼆叉树、堆、图等。之所以叫⾮线性,是因为,在⾮线性表中,数据之间并不是简单的前后关系。

2、连续的内存空间和相同类型的数据

正是因为这两个限制,它才有了⼀个堪称“杀⼿锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得⾮常低效,⽐如要想在数组中删除、插⼊⼀个数据,为了保证连续性,就需要做⼤量的数据搬移⼯作。

/**
 * 数据结构之数组
 * PHP代码模拟
 * @author PHPHa<mail@phpha.com>
 */
namespace PHPHa;

class MyArray
{
    // 数据
    private $data;
    // 容量
    private $capacity;
    // 长度
    private $length;

    /**
     * 初始化
     *
     * @param int $catacity            
     */
    public function __construct($catacity)
    {
        $this->data = [];
        $this->capacity = max(1, $catacity);
        $this->length = 0;
    }

    /**
     * 数组是否已满
     *
     * @return bool
     */
    public function isFull()
    {
        return $this->length >= $this->capacity;
    }

    /**
     * 索引是否越界
     *
     * @return bool
     */
    public function isOutOfRange($index)
    {
        return $index >= $this->length;
    }

    /**
     * 查找指定索引对应的元素
     *
     * @param int $index            
     * @return int|bool
     */
    public function find($index)
    {
        if ($index < 0 || $this->isOutOfRange($index)) {
            return false;
        }
        return $this->data[$index];
    }

    /**
     * 在指定索引位置插入元素
     *
     * @param int $index            
     * @param int $value            
     * @return bool
     */
    public function insert($index, $value)
    {
        if ($index < 0 || $this->isFull()) {
            return false;
        }
        // 指定索引之后的元素后移
        for ($i = $this->length - 1; $i >= $index; $i --) {
            $this->data[$i + 1] = $this->data[$i];
        }
        // 插入当前元素
        $this->data[$index] = $value;
        // 长度
        $this->length ++;
    }

    /**
     * 删除指定索引位置的元素
     *
     * @param int $index            
     * @return bool
     */
    public function delete($index)
    {
        if ($index < 0 || $this->isOutOfRange($index)) {
            return false;
        }
        // 指定索引之后的元素前移
        for ($i = $index; $i < $this->length - 1; $i ++) {
            $this->data[$i] = $this->data[$i + 1];
        }
        unset($this->data[$this->length - 1]);
        // 长度
        $this->length --;
    }

    /**
     * 打印当前数组元素
     */
    public function print()
    {
        print_r($this->data);
    }
}

// 【调用示例】
$array = new MyArray(10);
echo '初始化', PHP_EOL;
for ($i = 0; $i < 9; $i ++) {
    $array->insert($i, 100 + $i);
}
$array->print();
echo '[index=5] 插入 [500]', PHP_EOL;
$array->insert(5, 500);
$array->print();
echo '删除 [index=3]', PHP_EOL;
$array->delete(3);
$array->print();

输出:

初始化
Array
(
    [0] => 100
    [1] => 101
    [2] => 102
    [3] => 103
    [4] => 104
    [5] => 105
    [6] => 106
    [7] => 107
    [8] => 108
)
[index=5] 插入 [500]
Array
(
    [0] => 100
    [1] => 101
    [2] => 102
    [3] => 103
    [4] => 104
    [5] => 500
    [6] => 105
    [7] => 106
    [8] => 107
    [9] => 108
)
删除 [index=3]
Array
(
    [0] => 100
    [1] => 101
    [2] => 102
    [3] => 104
    [4] => 500
    [5] => 105
    [6] => 106
    [7] => 107
    [8] => 108
)

标签:数据结构