数组简介静态数组：是在声明时子数组大小已经确定的数组，即数组元素个数是固定的。动态数组：在声明的时候并不确定数组大小的数组，即数组元素个数是可以变化的。（其实也是静态数组，使用resize()方法进行动态调整）构建创建静态数组类创建类名为“ArrayClass”声明属性data：数组具体存放的数据capacity：容量数组的最大存储个数元素大小：数组声明构造函数中实际存储了多少个元素0?$容量：10；//构建一个长度为$capacity的数组$this->data=array_fill(0,$capacity,null);$this->size=0;}}数组元素个数相当于php的count()函数//获取数组有效元素个数publicfunctiongetSize():int{return$this->size;}获取的容量thearray//获取数组的容量publicfunctiongetCapacity():int{returncount($this->data);}向数组中插入一个元素//在索引位置插入一个新元素publicfunctionadd(int$index,$e):void{if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('需要$index>=0and$index<=$size');}如果（$this->size===count($this->data)){thrownew\http\Exception\RuntimeException('数组已满');}//将元素向后移动一个位置给新添加的元素位for($i=$this->size-1;$i>=$index;$i--){$this->data[$i+1]=$this->data[$i];}$this->data[$index]=$e;$this->size++;}Insertanelementatthebeginningofthearray//在所有元素之后添加一个新元素publicfunctionaddLast($e):void{$this->add($this->size,$e);}在数组末尾插入一个元素//在所有元素之前添加一个新元素publicfunctionaddFirst($e):void{$this->add(0,$e);}判断是否有有效元素数组中//判断数组中是否存在有效元素publicfunctionisEmpty():bool{return$this->size===0;}根据索引值获取元素值//获取位于的元素索引位置publicfunctionget(int$index){if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('$indexisillegal');}return$this->data[$index];}设置特定索引的元素值//修改索引位置的元素为publicfunctionset(int$index,$e):void{if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('$index无效');}$this->data[$index]=$e;}查找数组中是否有元素e//查找数组中是否有元素publicfunctioncontains($e):bool{for($i=0;$i<$this->size;$i++){if($this->data[$i]===$e){返回真;}}returnfalse;}在数组中查找元素e的索引值存在，不存在则返回1//在数组中查找元素e的索引值，不存在则返回-1publicfunctionfind($e):int{for($i=0;$i<$this->size;$i++){if($this->data[$i]===$e){返回$我;}}return-1;}删除指定位置的元素并返回删除的元素//从数组中删除索引位置的元素并返回删除的元素publicfunctionremove(int$index){if($index<0||$index>=$this->size){thrownew\http\Exception\RuntimeException('$index无效');}$ret=$this->data[$index];对于($i=$index+1;$i<$this->size;$i++){$this->data[$i-1]=$this->data[$i];}$this->size--;$this->data[$this->size]=null;//设置为空，不返回$ret;}从数组中删除第一个元素并返回删除的元素//从数组中移除第一个元素并返回移除的元素publicfunctionremoveFirst(){return$this->remove(0);}从数组中移除最后一个元素并返回移除的元素//从数组中删除最后一个元素并返回删除的元素publicfunctionremoveLast(){return$this->remove($this->size-1);}根据值删除一个元素//从数组中移除元素publicfunctionremoveElement($e):void{$index=$this->find($e);如果($index!==-1){$this->remove($index);}}对象转字符串魔术方法//对象转字符串触发函数publicfunction__toString():string{$count=count($this->data);$string="size={$this->size},capacity={$count}
";$字符串.='[';对于($i=0;$i<$this->size;$i++){if($i!==0){$string.=',';}$string.=$this->data[$i];}$string.=']
';return$string;}构造动态数组类调整数组容量的方法//扩充数组的容量privatefunctionresize(int$newCapacity):void{$newData=array_fill(0,$newCapacity,null);对于($i=0;$i<$this->size;$i++){$newData[$i]=$this->data[$我];}$this->data=$newData;}重写add方法//在索引位置插入一个新元素publicfunctionadd(int$index,$e):void{if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('需要$index>=0and$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->数据[$i];}$this->data[$index]=$e;$this->size++;}重写remove方法//从数组中删除index位置的元素并返回删除的元素publicfunctionremove(int$index){if($index<0||$index>=$this->size){thrownew\http\Exception\RuntimeException('$index无效');}$ret=$this->data[$index];对于($i=$index+1;$i<$this->size;$i++){$this->data[$i-1]=$this->data[$i];}$this->大小--;$this->data[$this->size]=null;//设置为空，不需要if($this->size===count($this->data)/4){//array当有效长度等于数组总容量的四分之一时，阵列将减少一半。//如果总容量等于二分之一，减半会过于激进，可能会导致方法的时间复杂度震荡。$this->resize(count($this->data)/2);}return$ret;}完整代码0?$容量：10；//构建一个长度为$capacity的数组$this->data=array_fill(0,$capacity,null);$this->size=0;}//获取数组中有效元素的个数publicfunctiongetSize():int{return$this->size;}//获取数组容量publicfunctiongetCapacity():int{returncount($this->datA）;}//数组中是否有0个有效元素publicfunctionisEmpty():bool{return$this->size===0;}//在索引位置e插入一个新元素publicfunctionadd(int$index,$e):void{if($index<0||$index>$this->size){thrownew\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;$这个->尺寸++；}//向所有元素添加一个新元素publicfunctionaddLast($e):void{$this->add($this->size,$e);}//在所有元素之前添加一个新元素publicfunctionaddFirst($e):void{$this->add(0,$e);}//获取index索引位置的元素publicfunctionget(int$index){if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('$index无效');}返回$this->数据[$index];}//获取数组开头的元素publicfunctiongetFirst(){return$this->data[$this->size-1];}//获取数组末尾的元素publicfunctiongetLast(){return$this->data[0];}//修改index位置的元素为epublicfunctionset(int$index,$e):void{if($index<0||$index>$this->size){thrownew\http\Exception\RuntimeException('$index无效');}$this->data[$index]=$e;}//查找数组中是否有元素epublicfunctioncontains($e):bool{for($i=0;$i<$this->size;$i++){if($this->data[$i]===$e){返回真；}}返回假；}//查找元素e在数组中的索引值，不存在则返回-1publicfunctionfind($e):int{for($i=0;$i<$this->size;$i++){if($this->data[$i]===$e){返回$i;}}返回-1；}//从数组中删除index位置的元素并返回删除的元素publicfunctionremove(int$index){if($index<0||$index>=$this->size){thrownew\http\Exception\RuntimeException('$index无效');}$ret=$this->data[$index];对于($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){//有效长度数组的容量等于数组总容量的四分之一Reducethearraybyhalf//如果总容量等于一半，那么减半就太激进了，可能会导致这个方法的时间复杂度$this->resize(count($this->data)/2);}返回$ret;}//从数组中删除第一个元素并返回删除的元素publicfunctionremoveFirst(){返回$this->remove(0);}//从数组中移除最后一个元素并返回移除的元素publicfunctionremoveLast(){return$this->remove($this->size-1);}//从数组中移除元素epublicfunctionremoveElement($e):void{$index=$this->find($e);如果($index!==-1){$this->remove($index);}}//将对象转换为字符串触发函数publicfunction__toString():string{$count=count($this->data);$string="size={$this->size},capacity={$count}
";$字符串.='[';对于($i=0;$i<$this->size;$i++){if($i!==0){$string.=',';}$string.=$this->data[$i];}$string.=']
';返回$字符串；}//展开数组privatefunctionresize(int$newCapacity):void{$newData=array_fill(0,$newCapacity,null);对于($i=0;$i<$this->sizee;$i++){$newData[$i]=$this->data[$i];}$this->data=$newData;}}testaddLast($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);回声$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)
