摘要：數據結構數組數組數據結構中最基本的一個結構就是線性結構，而線性結構又分為連續存儲結構和離散存儲結構。比如容量，擴容個，沒有意義，很快就滿了容量，擴充個，太多了，容易早證浪費。

數據結構-數組

數據結構中最基本的一個結構就是線性結構，而線性結構又分為連續存儲結構和離散存儲結構。所謂的連續存儲結構其實就是數組。

優點：插入塊如果知道坐標可以快速去地存取

缺點：查找慢,刪除慢,大小固定

基類的定義

定義一個工具類名稱-Array

接受的參數包括基本類型和自定義類型（用泛型來接受，基本類型用包裝類）

自定義屬性兩個：size用來表示數組的大小，data用來表示一個準確的集合

概念區分：size表示數組的大小，capacity表示數組容量的大小

構造函數：有參構造，接受一個int值，用來初始化數組容量；無參構造：給容量一個默認值

toString()方法，輸出數組的大小和數組容量的大小，以及數組中的值

getSize()方法，調用方通過方法來獲取數組的大小

getCapacity()方法，調用方通過方法來獲取數組容量的大小

isEmpty()方法，調用方通過方法來判斷數組是否為空(指的是數組中是否有值，沒值就為空)

基類的代碼

package com.datastructure.array;

/**
 * @program: test
 * @description: 自定義數組封裝工具類
 * @author: Mr.Yang
 * @create: 2019-05-01 15:36
 **/
public class Array {

    private Integer size;

    private E[] data;




    /**
     * 有參構造函數
     * @param capacity  封裝data的容量值
     */
    public Array(Integer capacity){
        data= (E[]) new Object[capacity];
        size=0;
    }

    /**
     * 無參構造函數，設置默認容量為10
     */
    public Array(){
        this(10);
    }

    /**
     * 獲取數組中的元素個數
     * @return
     */
    public Integer getSize(){
        return size;
    }

    /**
     * 獲取數組的容量
     * @return
     */
    public Integer getCapacity(){
        return data.length;
    }

    /**
     * 判斷數組是否為空
     * @return
     */
    public boolean isEmpty(){
        return size==0;
    }

    @Override
    public String toString(){
        StringBuffer sb = new StringBuffer();
        sb.append(String.format("Array: size = %d , capacity = %d
",size,data.length));
        sb.append("[");
        for(int i =0;i
增
添加的方法


add()方法，兩個參數，添加元素的索引位置，和元素的值

addFirst()方法，在所有元素的最前面添加

addLast()方法，在所有元素的最后面添加

添加的代碼(增)
/**
     * 在索引為index的位置，插入param
     * 1.假如在索引為2的位置插入元素
     * 2.需要將原來索引為2及其以后的位置向后移動一整位
     * 3.移動完成之后，在索引為2的位置插入指定的值
     * 4.因為數組中多了一個值，所以size需要+1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失敗，索引的值不能小于0，并且索引的值不能大于數組的大小");
        }
        if (size == data.length) {
            throw new IllegalArgumentException("添加失敗，數組的大小已經等于了數組容量的大小");
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }

    /**
     * 在所有元素之前添加值
     *
     * @param param
     */
    public void addFirst(E param) {
        add(0, param);
    }

    /**
     * 在所有元素之后添加值
     *
     * @param param
     */
    public void addLast(E param) {
        add(size, param);
    }
測試代碼
package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array integerArray = new Array(20);
        for(int i = 0; i < 10 ; i ++){
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("--------------------索引為3的地方添加元素-----------------------");
        integerArray.add(3,666);
        System.out.println(integerArray);

        System.out.println("--------------------所有元素的最后面添加值-----------------------");
        integerArray.addLast(10000);
        System.out.println(integerArray);

        System.out.println("--------------------所有元素的最前面添加值-----------------------");
        integerArray.addFirst(-1);
        System.out.println(integerArray);
    }
}

測試結果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------索引為3的地方添加元素-----------------------
Array: size = 11 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9]
--------------------所有元素的最后面添加值-----------------------
Array: size = 12 , capacity = 20
[0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
--------------------所有元素的最前面添加值-----------------------
Array: size = 13 , capacity = 20
[-1, 0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
改
添加的方法

set，兩個參數，修改的元素的索引位置，和將要修改的值
添加的代碼(改)
/**
     * 修改數組中元素的值
     * @param index
     * @param param
     */
    public void set(int index,E param){
        if(index<0 || index>= size){
            throw new IllegalArgumentException("獲取失敗，索引值無效");
        }
        data[index]=param;
    }
測試代碼
package com.datastructure.array;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array integerArray = new Array(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.println("--------------------索引為3的地方修改值為1010-----------------------");
        integerArray.set(3, 1010);
        System.out.println(integerArray);

    }
}

測試結果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------索引為3的地方修改值為1010-----------------------
Array: size = 10 , capacity = 20
[0, 1, 2, 1010, 4, 5, 6, 7, 8, 9]
查
添加的方法


get()方法，一個參數，索引值，根據索引返回對應的值

contains()方法，一個參數，判斷數組中是否包含某個元素

find()方法，一個參數，查找數組中是否包含param，如果包含返回索引值，不包含返回-1

findAll()方法，一個參數，查找數組中是否包含param，返回包含的索引數組

添加的代碼(查)
 /**
     * 獲取索引位置的元素
     * @param index
     * @return
     */
    public E get(Integer index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("獲取失敗，索引的值不能小于0，并且索引的值不能大于等于數組的大小");
        }
        return data[index];
    }

    /**
     * 查看數組中是否包含某個元素
     * @param param
     * @return
     */
    public boolean contains(E param){
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                return true;
            }
        }
        return false;
    }


    /**
     * 查找數組中是否包含param，如果包含返回索引值，不包含返回-1
     * @param param
     * @return
     */
    public Integer find(E param){
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找數組中是否包含param
     * 1.創建一個int數組用來接收返回的索引值
     * 2.索引容量最大為數組的大小
     * 3.用臨時變量來存儲int數組的大小
     * 4.如果相等，給 int數組 為臨時變量的元素賦值(相等的索引)，臨時變量自增
     * @param param
     * @return
     */
    public Integer[] findAll(E param){
        int intTemp=0;
        Integer[] integers = new Integer[size];
        for(int i = 0 ; i < size ; i++){
            if(data[i] == param){
                integers[intTemp]=i;
                intTemp++;
            }
        }
        return integers;
    }
測試代碼
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array integerArray = new Array(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        integerArray.addLast(3);

        System.out.println(integerArray);

        System.out.println("--------------------得到索引為3的值-----------------------");
        System.out.println(integerArray.get(3));

        System.out.println("--------------------判斷是否包含有包含3的值-----------------------");
        System.out.println(integerArray.contains(3));

        System.out.println("--------------------查找是否包含參數，并返回索引-----------------------");
        System.out.println(integerArray.find(3));

        System.out.println("--------------------查找是否包含參數，并返回索引數組-----------------------");
        System.out.println(Arrays.asList(integerArray.findAll(3)));

    }
}

測試結果
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3]
--------------------得到索引為3的值-----------------------
3
--------------------判斷是否包含有包含3的值-----------------------
true
--------------------查找是否包含參數，并返回索引-----------------------
3
--------------------查找是否包含參數，并返回索引數組-----------------------
[3, 10, null, null, null, null, null, null, null, null, null]
刪
添加的方法


remove()方法，數組中刪除index位置的元素，并且返回對應的值

removeFirst()方法，刪除第一位元素

removeLast()方法，刪除最后一位元素

removeElement()方法，查看某個值是否在數組中存在，如果存在,刪除并返回true，如果不存在 返回false、

removeLast()方法， 查找所有元素，獲取所有相等的索引，遍歷移除

添加的代碼(刪)
/**
     * 從數組中刪除index位置的元素，并且返回對應的值
     * 1.假如刪除索引為3的元素
     * 2.需要將索引大于3的元素向前移動一位
     * 3.因為數組中少了一個值，所以元素-1
     * 4.用臨時變量來存儲刪除的值，用來返回
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("刪除失敗，索引的值不能小于0，并且索引的值不能大于等于數組的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){
            data[i-1]=data[i];
        }
        size--;
        return temp;
    }

    /**
     * 刪除第一位元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 刪除最后一位元素
     */
    public E removeLast(){
        return remove(size-1);
    }

    /**
     * 查看某個值是否在數組中存在，如果存在,刪除并返回true，如果不存在 返回false
     * @param param
     */
    public boolean removeElement(E param){
        Integer index = find(param);
        if(index != -1){
            remove(index);
            return true;
        }
        return false;
    }

   /**
     * 遍歷數組，移除元素
     * @param param
     */
    public void removeAllElement(E param){
        for(E d:data){
            removeElement(param);
        }
    }
測試代碼
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array integerArray = new Array(20);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        integerArray.addLast(3);
        integerArray.addLast(4);

        System.out.println(integerArray);

        System.out.println("--------------------數組中刪除6位置的元素，并且返回對應的值-----------------------");
        System.out.println(integerArray.remove(6));
        System.out.println(integerArray);

        System.out.println("--------------------刪除第一位元素-----------------------");
        System.out.println(integerArray.removeFirst());
        System.out.println(integerArray);

        System.out.println("--------------------刪除最后一位元素-----------------------");
        System.out.println(integerArray.removeLast());
        System.out.println(integerArray);

        System.out.println("--------------------查看8是否在數組中存在，返回true和fals-----------------------");
        System.out.println(integerArray.removeElement(8));
        System.out.println(integerArray);

        System.out.println("--------------------查找所有元素，獲取所有相等的索引，遍歷移除-----------------------");
        integerArray.removeAllElement(3);
        System.out.println(integerArray);

    }
}

測試結果
Array: size = 12 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4]
--------------------數組中刪除6位置的元素，并且返回對應的值-----------------------
6
Array: size = 11 , capacity = 20
[0, 1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
--------------------刪除第一位元素-----------------------
0
Array: size = 10 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3, 4]
--------------------刪除最后一位元素-----------------------
4
Array: size = 9 , capacity = 20
[1, 2, 3, 4, 5, 7, 8, 9, 3]
--------------------查看8是否在數組中存在，如果存在,刪除并返回true，如果不存在 返回false、-----------------------
true
Array: size = 8 , capacity = 20
[1, 2, 3, 4, 5, 7, 9, 3]
--------------------查找所有元素，獲取所有相等的索引，遍歷移除-----------------------
Array: size = 6 , capacity = 20
[1, 2, 4, 5, 7, 9]
數組動態擴容
添加的方法

resize()方法，定義為私有，調用方不能通過方法來調用，去修改，否則容易造成BUG
擴容倍數，如果用固定值，不好抉擇。比如：100容量，擴容10個，沒有意義，很快就滿了；100容量，擴充1000個，太多了，容易早證浪費。最好選擇倍數，都在同一個單位級別，這里代碼選擇的是2倍
添加的時候需要判斷擴容，刪除的時候需要刪除容量，減少資源浪費
刪除的時候，當元素減少到容量的1/4的時候開始縮，縮減到容量的1/2
如果選擇1/2的時候開始縮減，然后縮減到1/2會有一定的問題，例如：容量10，現在容量滿了，來了一個元素，需要擴容，按照設置的擴容機制，會擴容2倍，也就是20容量，如果刪除了一個元素，元素達到了容量的1/2，我們開始進行縮減，縮減1/2，容量又變為10。如果一直在這個臨界值，那么元素會一直進行擴容縮減擴容縮減，性能影響太大。
如果選擇1/4的時候開始縮減，然后縮減到1/2，這樣能夠較好的避開以上問題，例如：容量10，容量滿了，來了一個元素，擴容容量到了20，如果刪除一個元素，還不到容量的1/4，所以還不會進行縮減，如果真的到了容量的1/4的時候，我們選擇縮減1/2，容量也需要一定的元素，才會進行擴容，防止了容量一直擴容或者縮減

添加的代碼
    /**
     * 擴容方法
     * 1.需要new一個object，new E[i]  java不支持這樣寫
     * 2.object是所有類的基類，用object然后強轉一下就可以
     * 3.擴展之后，需要將原數組中的值，放入擴展之后的數組中
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for(int i=0;i
修改的代碼
add() 和 remove()
/**
     * 在索引為index的位置，插入param
     * 1.假如在索引為2的位置插入元素
     * 2.需要將原來索引為2及其以后的位置向后移動一整位
     * 3.移動完成之后，在索引為2的位置插入指定的值
     * 4.因為數組中多了一個值，所以size需要+1
     *
     * @param index 元素的索引
     * @param param 值
     */
    public void add(int index, E param) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失敗，索引的值不能小于0，并且索引的值不能大于數組的大小");
        }
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = param;
        size++;
    }


/**
     * 從數組中刪除index位置的元素，并且返回對應的值
     * 1.假如刪除索引為3的元素
     * 2.需要將索引大于3的元素向前移動一位
     * 3.因為數組中少了一個值，所以元素-1
     * 4.用臨時變量來存儲刪除的值，用來返回
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("刪除失敗，索引的值不能小于0，并且索引的值不能大于等于數組的大小");
        }
        E temp=data[index];
        for(int i = index+1 ; i < size ; i++){
            data[i-1]=data[i];
        }
        size--;
        if(size == data.length / 4 ){
            resize(data.length / 2 );
        }
        return temp;
    }
測試代碼
package com.datastructure.array;

import java.util.Arrays;

/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-01 16:46
 **/
public class ArrayTest {

    public static void main(String[] args) {
        Array integerArray = new Array(10);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.printf("--------------------將容量設置為10，添加10個元素，元素的容量 : %d -------------------
",integerArray.getCapacity());

        integerArray.addLast(21);
        System.out.printf("--------------------元素+1，元素的容量 : %d --------------------
",integerArray.getCapacity());


        integerArray.removeLast();
        System.out.printf("--------------------元素-1，元素的容量 : %d --------------------
",integerArray.getCapacity());

        integerArray.removeLast();
        System.out.printf("--------------------元素-1，元素的容量 : %d --------------------
",integerArray.getCapacity());

        for(int x=0;x<=5;x++){
            integerArray.removeLast();
        }
        System.out.printf("--------------------元素-1/4，元素的容量 : %d --------------------
",integerArray.getCapacity());


    }
}

測試結果
Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--------------------將容量設置為10，添加10個元素，元素的容量 : 10 -------------------
--------------------元素+1，元素的容量 : 20 --------------------
--------------------元素-1，元素的容量 : 20 --------------------
--------------------元素-1，元素的容量 : 20 --------------------
--------------------元素-1/4，元素的容量 : 10 --------------------