数据结构(二)数组

从这篇开始就研究数组这个最基本的数据结构。

数组基础:

把数据码成一排进行存放

image.png

如上图所示,数组应该有一个自己的名字用来和其他数组区分,数组的索引是从0开始的,也就是想取到数组中的第三个数字,那么得取索引为2的值,即arr[2];

接下来说一下Java中的数组,Java数组中的每一个元素需要我们存放相同类型的元素,下面我们来演示一下Java数组的基本操作。

Java数组:

package com.wjy329;

public class Main {

    public static void main(String[] args) {
        //初始化一个int数组
       int[] scores = new int[10];
        //结果输出为: 0 0  0  0 0 。。。
        //默认的值都为0
       for(int i : scores){
           System.out.println(i);
        }
        //给数组赋值为数组的索引
        //打印结果:0 1 2 3 4 5 。。。
        for(int j=0;j < scores.length;j++){
           scores[j] = j;
            System.out.println(scores[j]);
        }
        
    }
}

当然,上面是最简单的Java数组的操作;

数组最大的优点是快速查询,可以直接根据索引查找,所以数组最好应用于“索引有语意”的情况。

Java为我们提供的数组不能进行添加和删除操作,下面我们来自己做一个我们自己的数组来实现此类功能;

封装我们自己的数组:

开始的时候,我们只需要简单的声明以及写出每个方法即可,最后我会将完整的封装的数组代码写上。

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array {
    private int[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = new int[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
}

以上就是自定义数组的初始化和一些简单获取数组容量和元素个数的方法;我们对数组需要进行等操作,所以下面我们也将一一实现。

增:

//向所有元素后添加一个元素
public void addLast(int e){
    if(size == data.length){
        throw new IllegalArgumentException("添加元素失败,数组容量已满");
    }
    data[size] = e;
    size ++;
    //复用添加方法
    //add(size,e);
}
//在所有元素前添加一个元素e
public void addFirst(int e){
    add(0,e);
}

//在第index位置插入一个新元素e
public void add(int index,int e){
    if(size == data.length){
        throw new IllegalArgumentException("添加元素失败,数组容量已满");
    }
    if(index < 0 || index > size){
        throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
    }
    for(int i = size - 1;i >= index;i --){
        data[i + 1] = data[i];
    }
    data[index]=e;
    size++;
}

代码很好理解,我主要的说在指定位置添加元素方法,我们从后往前依次向后移一位,直到指定位置停止;size-1 为最后一个数的索引值,然后将其后移一位,接下来再后移其他位置的数据;

删:

//从数组中删除index位置的元素,返回删除的元素
public int remove(int index){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
    int del = data[index];
    for(int i = index + 1;i < size;i++){
        data[i-1] = data[i];
    }
    size--;
    return del;
}

上面是删除指定位置元素,删除的思路就是指定位置后的元素都向前移一位即可;下面是删除指定元素,需要用到后面的查找方法,查找到元素的索引,然后删除。

//删除数组中指定的元素
public void delElement(int e){
    int index = find(e);
    if(index != -1){
        remove(index);
    }
}

查、

//获取指定位置的元素
 int get(int index){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
    return data[index];
}
//将index位置的元素换为e
void set(int index,int e){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
     data[index] = e;
}

//查找数组中是否存在元素e
public boolean contains(int e){
    for(int i=0;i < size; i++){
        if(data[i] == e){
            return true;
        }
    }
    return false;
}

//查找数组中元素e所在的索引,如果不存在元素e,返回-1
public int find(int e){
    for(int i=0;i < size; i++){
        if(data[i] == e){
            return i;
        }
    }
    return -1 ;
}

 上面就是基本的思路,当然其中有些不足,比如相同元素的查找和删除等,上面的代码只会查找一个或者删除一个,并不会全部删除,这是因为主要演示的是思路和逻辑,会了上面的,后面的设计也就会显得轻车熟路了。

下面给上封装数组的完整代码:

Array.java:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array {
    private int[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = new int[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(int e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(int e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,int e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }
    //获取指定位置的元素
     int get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    void set(int index,int e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(int e){
        for(int i=0;i < size; i++){
            if(data[i] == e){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(int e){
        for(int i=0;i < size; i++){
            if(data[i] == e){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public int remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        int del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        return del;
    }
    //删除数组中的第一个元素
    public int delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public int delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(int e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

上面仅仅是对int型数组的探索,为了让我们自定义的数组适合任意类型,我们将其定义为范型数组,下面直接给出代码:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array<E> {
    private E[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(E e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }
    //获取指定位置的元素
     public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        E del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        return del;
    }
    //删除数组中的第一个元素
    public E delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public E delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

动态数组:

我们使用上面的代码一段时间后发现,这个TM的还是静态数组啊,还是指定的大小没法扩充啊,还是毫无卵用啊。。。别急,接下来,我们就添加几行代码使其动态的扩展。

动态的思路也是很简单的,当我们添加元素时,如果发现已经满了,那么我们再新建一个比之前更大的数组(假设为2倍),然后将其值都赋值给新的数组,这样实现了添加的扩容;当我们删除到一定量的时候,我们发现太多的空间被浪费了,那么我们将其按照一定的比例缩小数组(当数组内元素个数为当前容量的一半时,我们就缩减为一半),以此来保证数组的空间合理性。

扩容的方法代码:

private void resize(int newCapacity) {
    E[] newData = (E[])new Object[newCapacity];
    for(int i= 0;i < size;i++){
        newData[i] = data[i];
    }
    data = newData;
}

最终代码:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array<E> {
    private E[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(E e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        if(size == data.length){
            resize(2 * data.length);
        }

        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }

    //获取指定位置的元素
     public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        E del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        if(size == data.length/2){
            resize(data.length/2);
        }

        return del;
    }
    //删除数组中的第一个元素
    public E delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public E delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i= 0;i < size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}

1 Comment

  1. […] 数据结构(二)数组 […]

    回复

Leave a Reply