データ構造の配列-初日の学習

配列はシーケンス構造の線形テーブルであり、すべての要素のメモリアドレスは連続している.
ダイナミック配列(Dynamic Array)インタフェース設計

size();//要素の数

isEmpty();//空

contains(item);//ある要素が含まれているかどうか

add(E element);//一番後ろの

に要素を追加

get(int index);//index位置に対応する要素

を返す

set(int index,item);//index位置を設定する要素

add(int index,item);//index位置に要素

を追加

remove(int index);//index位置に対応する要素

を削除

indexOf(item);//要素を表示する場所

clear();//すべての要素を消去

capacity = max(self::DEFAULT_CAPACITY,$capacity);
    }

    /**
     * @return int
     *             
     */
    public function size():int
    {
        return $this->size;
    }

    /**
     * @return bool
     *     
     */
    public function isEmpty():bool
    {
        return 0===$this->size;
    }

    /**
     *         
     * @param $item
     * @return bool
     */
    public function contains($item):bool
    {
        return $this->indexOf($item) != self::ITEM_NOT_FOUND;
    }

    /**
     * @param $item
     *       ,   
     */
    public function add($item)
    {
        return $this->insert($this->size,$item);
    }

    /**
     * @param int $index
     * @return mixed
     * 1,2,3,4       1   ， 1,3,4。  2 。 
     */
    public function remove(int $index)
    {
        $this->rangeCheck($index);
        $old = $this->elements[$index];
        for($i=$index+1; $isize; $i++){
            $this->elements[$i-1] = $this->elements[$i];
        }
        $this->elements[--$this->size] = null;
        return $old;
    }

    /**
     *        
     */
    public function clear(){
        for($i=0;$isize;$i++){
            $this->elements[$i] = null;
        }
        $this->size=0;
    }

    /**
     * @param int $index
     * @param $item
     *   index     
     * @return mixed
     */
    public function set(int $index,$item)
    {
        $this->rangeCheck($index);
        $old = $this->elements[$index];
        $this->elements[$index] = $item;
        return $old;
    }

    /**
     * @param int $index
     * @param $item
     *       
     *  1,3,4,5    0    2    2,1,3,4,5
     *              ,        
     * @return mixed
     */
    public function insert(int $index,$item)
    {
        $this->rangeCheckForInsert($index);
        //         

        for($i=$this->size;$i>$index;$i--){
            $this->elements[$i] = $this->elements[$i-1];
        }
        $this->elements[$index] = $item;
        $this->size++;
        return $item;
    }

    /**
     * @param int $index
     *   index     
     * @return mixed
     */
    public function get(int $index)
    {
        $this->rangeCheck($index);
        return $this->elements[$index];
    }

    /**
     * @param $item
     *        
     * @return int
     */
    public function indexOf($item) :int
    {
        for($i=0;$isize;$i++)
            if($this->elements[$i] === $item) return $i;
        return self::ITEM_NOT_FOUND;
    }

    /**
     *       
     * @param int $capacity        
     */
    private function ensureCapacity(int $capacity){
        $oldCapacity = count($this->elements);
        if($this->capacity >= $capacity) return;
        //      
        $this->capacity = $this->capacity + ($this->capacity>>1);
    }

    /**
     *     
     * @param int $index
     * @throws Exception
     */
    private function outOfBoundsException(int $index){
        throw new Exception("Index:{$index} , Size:{$this->size}");
    }

    private function rangeCheck(int $index)
    {
        if($index<0 || $index>=$this->size){
            $this->outOfBoundsException($index);
        }
    }

    private function rangeCheckForInsert(int $index){
        if($index<0 || $index>$this->size){
            $this->outOfBoundsException($index);
        }
    }

   public function __toString()
   {
       $string = "size={$this->size}，[";
       for($i=0;$isize;$i++){
           if(0!=$i) $string.=",";
           $string.=$this->elements[$i];
       }
       $string.=']';
       return $string;
   }
}

$list = new ArrayList();
$list->add(1);
$list->add(2);
$list->add(3);
$list->insert(1,4);
$list->clear();


//var_dump((string)$list);

次の操作を行います.

$list = new ArrayList();
$list->add(1);
$list->add(2);
$list->add(3);
$list->insert(1,4);
$list->clear();

phpを用いて配列のデータ構造を実現し、初日の学習を記録し、データ構造の美しさを感じる.