数据结构-数组

数据结构-数组

数组

  • 数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构。所谓的连续存储结构其实就是数组。
  • 优点:插入块如果知道坐标可以快速去地存取
  • 缺点:查找慢,删除慢,大小固定

二次封装数组的增删改查

基类的定义
  • 定义一个工具类名称-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<E> {

    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\n",size,data.length));
        sb.append("[");
        for(int i =0;i<size;i++){
            sb.append(data[i]);
            if(i !=size-1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
添加的方法
  • 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<Integer> integerArray = new Array<Integer>(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<Integer> integerArray = new Array<Integer>(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<Integer> integerArray = new Array<Integer>(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<Integer> integerArray = new Array<Integer>(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<size;i++){
            newData[i]=data[i];
        }
        data=newData;
    }
修改的代码
  • 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<Integer> integerArray = new Array<Integer>(10);
        for (int i = 0; i < 10; i++) {
            integerArray.addLast(i);
        }
        System.out.println(integerArray);

        System.out.printf("--------------------将容量设置为10,添加10个元素,元素的容量 : %d -------------------\r\n",integerArray.getCapacity());

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


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

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

        for(int x=0;x<=5;x++){
            integerArray.removeLast();
        }
        System.out.printf("--------------------元素-1/4,元素的容量 : %d --------------------\r\n",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 --------------------

相关推荐