数组
文章目录
数组
简介
- 静态数组:是在声明时已经确定子数组大小的数组,即数组元素的个数固定不变。
- 动态数组:在声明时没有确定数组大小的数组,即数组元素的个数可以发生变化。(其实也是静态数组,使用扩容resize()方法进行动态调整)
构建
创建静态数组类
- 创建一个类,类名为”ArrayClass“
声明属性
- data:数组所存具体数据
- capacity:数组的容量,最多可以存储多少个元素
- size:数组中实际存储多少个元素
- 声明构造函数
<?php
declare(strict_types=1);
class ArrayClass
{
// 数组
private array $data;
// 数组有限元素个数
private int $size;
// 创建一个数组,传入数组的容量$capacity构造出数组
public function __construct(int $capacity = 10)
{
// 默认为10位长度,长度不能小于等于0
$capacity = $capacity > 0 ? $capacity : 10;
// 构建出一个数组,长度为$capacity
$this->data = array_fill(0, $capacity, null);
$this->size = 0;
}
}- 获取数组中元素的个数
- 相当于php的
count()函数
// 获取数组中的有效元素个数
public function getSize(): int
{
return $this->size;
}- 获取数组的容量
// 获取数组容量
public function getCapacity(): int
{
return count($this->data);
}- 向数组中插入一个元素
// 在第index个位置插入一个新元素e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('需要 $index >= 0 且 $index <= $size');
}
if ($this->size === count($this->data)) {
throw new \http\Exception\RuntimeException('数组满了');
}
// 将元素往后挪一个位置,给新增的元素让位
for ($i = $this->size - 1; $i >= $index; $i--) {
$this->data[$i + 1] = $this->data[$i];
}
$this->data[$index] = $e;
$this->size++;
}- 在数组的开头插入一个元素
// 向所有的元素后添加一个新元素
public function addLast($e): void
{
$this->add($this->size, $e);
}- 在数组的最后插入一个元素
// 向所有的元素前添加一个新元素
public function addFirst($e): void
{
$this->add(0, $e);
}- 判断数组中是否有有效元素
// 判断数组中是否有有效元素
public function isEmpty(): bool
{
return $this->size === 0;
}- 根据索引值获取元素值
// 获取index索引位置的元素
public function get(int $index)
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
return $this->data[$index];
}- 设置特定索引的元素值
// 修改index索引位置的元素为e
public function set(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
$this->data[$index] = $e;
}- 查找数组中是否有元素e
// 查找数组中是否有元素e
public function contains($e): bool
{
for ($i = 0; $i < $this->size; $i++) {
if ($this->data[$i] === $e) {
return true;
}
}
return false;
}- 查找数组中元素e所存在的索引值,不存在则返回1
// 查找数组中元素e所在的索引值,如果不存在则返回-1
public function find($e): int
{
for ($i = 0; $i < $this->size; $i++) {
if ($this->data[$i] === $e) {
return $i;
}
}
return -1;
}- 删除特定位置的元素,并返回删除的元素
// 从数组中删除index位置的元素,并返回删除的元素
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
$ret = $this->data[$index];
for ($i = $index + 1; $i < $this->size; $i++) {
$this->data[$i - 1] = $this->data[$i];
}
$this->size--;
$this->data[$this->size] = null; // 设置为空,非必须
return $ret;
}- 从数组中删除第一个元素,并返回删除的元素
// 从数组中删除第一个元素,并返回删除的元素
public function removeFirst()
{
return $this->remove(0);
}- 从数组中删除最后一个元素,并返回删除的元素
// 从数组中删除最后一个元素,并返回删除的元素
public function removeLast()
{
return $this->remove($this->size - 1);
}- 根据值删除一个元素
// 从数组中删除元素e
public function removeElement($e): void
{
$index = $this->find($e);
if ($index !== -1) {
$this->remove($index);
}
}- 对象转字符串的魔术方法
// 将对象转为字符串触发该函数
public function __toString(): string
{
$count = count($this->data);
$string = "size = {$this->size},capacity = {$count}<br/>";
$string .= '[';
for ($i = 0; $i < $this->size; $i++) {
if ($i !== 0) {
$string .= ', ';
}
$string .= $this->data[$i];
}
$string .= ']<br/>';
return $string;
}构建动态数组类
- 调整数组容量的方法
// 对数组扩容
private function resize(int $newCapacity): void
{
$newData = array_fill(0, $newCapacity, null);
for ($i = 0; $i < $this->size; $i++) {
$newData[$i] = $this->data[$i];
}
$this->data = $newData;
}- 改写add方法
// 在第index个位置插入一个新元素e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('需要 $index >= 0 且 $index <= $size');
}
if ($this->size === count($this->data)) {
// 数组有效长度等于数组总容量时将扩容两倍
$this->resize(2 * count($this->data));
}
// 将元素往后挪一个位置,给新增的元素让位
for ($i = $this->size - 1; $i >= $index; $i--) {
$this->data[$i + 1] = $this->data[$i];
}
$this->data[$index] = $e;
$this->size++;
}- 改写remove方法
// 从数组中删除index位置的元素,并返回删除的元素
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
$ret = $this->data[$index];
for ($i = $index + 1; $i < $this->size; $i++) {
$this->data[$i - 1] = $this->data[$i];
}
$this->size--;
$this->data[$this->size] = null; // 设置为空,非必须
if ($this->size === count($this->data) / 4) {
// 数组有效长度等于数组总容量的四分一时将缩减数组一半
// 如果等于总容量为二分一时就缩减一半会使得太过于激进,可能导致该方法的时间复杂度震荡
$this->resize(count($this->data) / 2);
}
return $ret;
}完整代码
<?php
/**
* Created by PhpStorm
* User: 林志杰
* Email: lzj@lzjie.top
* Time: 2020/10/20 22:27
*/
declare(strict_types=1);
class ArrayClass
{
// 数组
private array $data;
// 数组有限元素个数
private int $size;
// 创建一个数组,传入数组的容量$capacity构造出数组
public function __construct(int $capacity = 10)
{
// 默认为10位长度,长度不能小于等于0
$capacity = $capacity > 0 ? $capacity : 10;
// 构建出一个数组,长度为$capacity
$this->data = array_fill(0, $capacity, null);
$this->size = 0;
}
// 获取数组中的有效元素个数
public function getSize(): int
{
return $this->size;
}
// 获取数组容量
public function getCapacity(): int
{
return count($this->data);
}
// 数组中有效元素是否为0个
public function isEmpty(): bool
{
return $this->size === 0;
}
// 在第index个位置插入一个新元素e
public function add(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('需要 $index >= 0 且 $index <= $size');
}
if ($this->size === count($this->data)) {
// 数组有效长度等于数组总容量时将扩容两倍
$this->resize(2 * count($this->data));
}
// 将元素往后挪一个位置,给新增的元素让位
for ($i = $this->size - 1; $i >= $index; $i--) {
$this->data[$i + 1] = $this->data[$i];
}
$this->data[$index] = $e;
$this->size++;
}
// 向所有的元素后添加一个新元素
public function addLast($e): void
{
$this->add($this->size, $e);
}
// 向所有的元素前添加一个新元素
public function addFirst($e): void
{
$this->add(0, $e);
}
// 获取index索引位置的元素
public function get(int $index)
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
return $this->data[$index];
}
// 获取数组起始位的元素
public function getFirst()
{
return $this->data[$this->size - 1];
}
// 获取数组末尾的元素
public function getLast()
{
return $this->data[0];
}
// 修改index索引位置的元素为e
public function set(int $index, $e): void
{
if ($index < 0 || $index > $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
$this->data[$index] = $e;
}
// 查找数组中是否有元素e
public function contains($e): bool
{
for ($i = 0; $i < $this->size; $i++) {
if ($this->data[$i] === $e) {
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引值,如果不存在则返回-1
public function find($e): int
{
for ($i = 0; $i < $this->size; $i++) {
if ($this->data[$i] === $e) {
return $i;
}
}
return -1;
}
// 从数组中删除index位置的元素,并返回删除的元素
public function remove(int $index)
{
if ($index < 0 || $index >= $this->size) {
throw new \http\Exception\RuntimeException('$index 不合法');
}
$ret = $this->data[$index];
for ($i = $index + 1; $i < $this->size; $i++) {
$this->data[$i - 1] = $this->data[$i];
}
$this->size--;
$this->data[$this->size] = null; // 设置为空,非必须
if ($this->size === count($this->data) / 4 && count($this->data) / 2 !== 0) {
// 数组有效长度等于数组总容量的四分一时将缩减数组一半
// 如果等于总容量为二分一时就缩减一半会使得太过于激进,可能导致该方法的时间复杂度
$this->resize(count($this->data) / 2);
}
return $ret;
}
// 从数组中删除第一个元素,并返回删除的元素
public function removeFirst()
{
return $this->remove(0);
}
// 从数组中删除最后一个元素,并返回删除的元素
public function removeLast()
{
return $this->remove($this->size - 1);
}
// 从数组中删除元素e
public function removeElement($e): void
{
$index = $this->find($e);
if ($index !== -1) {
$this->remove($index);
}
}
// 将对象转为字符串触发该函数
public function __toString(): string
{
$count = count($this->data);
$string = "size = {$this->size},capacity = {$count}<br/>";
$string .= '[';
for ($i = 0; $i < $this->size; $i++) {
if ($i !== 0) {
$string .= ', ';
}
$string .= $this->data[$i];
}
$string .= ']<br/>';
return $string;
}
// 对数组扩容
private function resize(int $newCapacity): void
{
$newData = array_fill(0, $newCapacity, null);
for ($i = 0; $i < $this->size; $i++) {
$newData[$i] = $this->data[$i];
}
$this->data = $newData;
}
}测试
<?php
require 'Array/ArrayClass.php';
$arrayObj = new ArrayClass(20);
for ($i = 0; $i < 10; $i++) {
$arrayObj->addLast($i);
}
$arrayObj->add(1, 100);
$arrayObj->add(1, '99');
$arrayObj->add(1, 3.1415);
$arrayObj->addFirst(-1);
$arrayObj->remove(2);
$arrayObj->get(2);
$arrayObj->set(2, true);
$arrayObj->contains(2);
$arrayObj->find(2);
$arrayObj->remove(2);
$arrayObj->removeFirst();
$arrayObj->removeLast();
$arrayObj->removeElement(2);
echo $arrayObj;时间复杂度
添加操作
addLast()为O(1)addFirst()为O(n)add()为O(n/2)~O(n)resize()为O(n)
删除操作
removeLast()为O(1)removeFirst()为O(n)remove()为O(n/2)~O(n)resize()为O(n)
修改操作
set()为O(1)
查找操作
get()为O(1)contains()为O(n)find()为O(n)
- 增:
O(n) - 删:
O(n) - 改:已知索引
O(1);未知索引O(n) - 查:已知索引
O(1);未知索引O(n)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论