本文展示了如何使用PHP语言实现Array数据结构。可能有人会问为什么用PHP而不用其他语言呢？这里我想说明一下，很多PHP程序员缺乏数据结构和算法的基础知识。在这里，我主要是想通过PHP实现数据结构的过程来学习数据结构的原理。读者不必担心使用哪种语言。理解清楚原理后，读者可以根据自己的喜好选择其他任何一种语言来实现。1.ArrayStructclasscapacity=$capacity;}/***获取数组元素个数*@returnint*/publicfunctiongetSize():int{return$this->size;}/***获取数组的容量*@returnint*/publicfunctiongetCapacity():int{return$this->capacity;}/***判断数组是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->size==0;}/***向数组的指定位置插入一个元素*@paramint$index*@param$e*@throwsException*/publicfunctionadd(int$index,$e):void{if($this->size==$this->capacity){$this->resize(2);//扩大到原来的2倍}if($index<0||$index>$this->size){echo"添加的位置超出了数组的大小";出口;}//为了便于理解，[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;$这个->尺寸++；}/***添加一个元素到数组的末尾*@param$e*@throwsException*/publicfunctionaddLast($e):void{$this->add($this->size,$e);}/***在数组的开头插入一个元素*@param$e*@throwsException*/publicfunctionaddFirst($e):void{$this->add(0,$e);}/***获取索引位置数组元素*@paramint$index*@returnmixed*/publicfunctionget(int$index){if($index<0||$index>$this->size){echo"索引值超出元素的位置范围,";出口;}返回$this->data[$index];}/***判断数组中是否存在一个元素*@param$e*@returnbool*/publicfunctioncontains($e):bool{for($i=1;$i<$this->size;$i++){if($this->data[$i]==$e){返回真；}}返回假；}/***检查数组中某个元素的位置索引值，如果不存在则返回-1*@param$e*@returnint*/publicfunctionfind($e):int{for($i=0;$i<$this->size;$i++){if($this->data[$i]==$e){返回$i;}}返回-1；}/***删除数组中指定位置的元素，并返回删除元素的值*@param$index*@returnmixed*/publicfunctionremove($index){if($index<0||$index>$this->size){echo"索引值超出元素的位置范围，";出口;$e=$this->data[$index];对于($i=$index;$i<$this->size-1;$i++){$this->data[$i]=$this->data[$i+1];}$这个->大小--;$this->data[$this->size]=null;//游荡的物体！=memory/**如果当前数组大小小于容量的一半，重新分配数组空间大小的一半**/if($this->size<=$this->capacity/4&&$this->capacity%2==0){$this->resize(0.5);}返回$e;}/***删除数组第一个元素，返回删除元素的值*/publicfunctionremoveFirst(){return$this->remove(0);}/***删除数组第一个元素，返回删除元素的值*/publicfunctionremoveLast(){return$this->remove($this->size);}/***删除数组中的特定元素*@param$e*/publicfunctionremoveElement($e){for($i=0;$i<$this->size;$i++){if($this->data[$i]==$e){$this->remove($i);$this->removeElement($e);休息;}}}/***数组扩容，如果是其他语言，比如JAVA，这里需要重新开辟空间*@param$factor*/protectedfunctionresize($factor){$this->capacity=$factor*$this->capacity;}/***将数组转换为字符串*@returnstring*/publicfunctiontoString():string{$str="[";foreach($this->dataas$value){$str.=$value.",";}$str=trim($str,",");$str.="]";返回$str;}}2.index.phpaddLast(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("广告");$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(iindex,num)O(n)严格计算需要一些概率论知识，如果其他语言，如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)resizeO(n)removeLast(num)O(1)Tips:当容量满了，可能会一直触发resize()，这样时间复杂度就变成了O(n)。这种情况称为复杂性振荡。减少容量。代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
