数组(Array
)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。PHPHa
通过本文简单介绍下数组的定义以及用 PHP
代码模拟数组的相关操作。
数组定义相关的 2
个关键词:
1、线性表(Linear List
)
顾名思义,线性表就是数据排成像⼀条线⼀样的结构。每个线性表上的数据最多只有前和后两个⽅向。其实除了数组,链表、队列、栈等也是线性表结构。⽽与它相对⽴的概念是⾮线性表,⽐如⼆叉树、堆、图等。之所以叫⾮线性,是因为,在⾮线性表中,数据之间并不是简单的前后关系。
2、连续的内存空间和相同类型的数据
正是因为这两个限制,它才有了⼀个堪称“杀⼿锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得⾮常低效,⽐如要想在数组中删除、插⼊⼀个数据,为了保证连续性,就需要做⼤量的数据搬移⼯作。
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
)