算法与数据结构（第三周）——数据结构基础：动态数组

数组

使用 Java 中的数组

二次封装属于我们自己的数组

向数组中添加元素

数组

使用 Java 中的数组

声明十个元素的数组，并进行赋值操作


        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

数组在声明的时候就有初始值


        int[] scores = new int[]{100,99,66};
        for(int i=0;i< scores.length ; i ++)
            System.out.println(scores[1]);
        for(int score: scores)//增强for
            System. out. println(score);

二次封装属于我们自己的数组

数组最大的优点:快速查询，例如scores[2]表名学号为2的学生分数，所以数组最好应用于“索引有语意'的情况。但并非所有有语意的索引都适用于数组，例如身份证号不适合作索引。

JAVA原本的数组是静态数组，我们将其二次封装为动态数组。我们将会创建Array类，对其中的data数组进行增删改查。

size：数组实际使用的容量。capacity：数组容量。

构造函数初始化数组，并进行简单的操作：


public class Array {
 
    private int[] data;
    private int size;
 
    //构造函数，传入数组的容量capacity构造Array
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }
 
    //无参数的构造函数，默认数组的容量capacity=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("AddLast failed. Array is full.");
        data [size] = e;
        size++;
        //data [size++] = e;
    }

指定位置添加元素

注意：

1.不能直接在指定位置添加元素，否则会对原有元素覆盖

2.对指定位置及其之后的元素后移

3.添加之后记得size++


    //在第Index个位置插入一个新元素e
    public void add(int index, int e) {
        if (size == data.length)
            throw new IllegalArgumentException("Add faiLed. Array is full.");
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
        //每一个元素都向后挪一个位置，直到挪到index这个元素
        //注意此时index位置上并不是没有元素，index位置上还是原来的元素，只是现在可以放心的将这个位置上的元素覆盖掉了
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];//后一个索引位置赋上前一个索引元素
        }
        data[index] = e;
        size++;
    }

addLast方法也可以复用add方法:


//向所有元素后添加一个新元素
public void addLast(int e){
    add(size, e);
}

查询元素和修改元素

toString方法打印数组：


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

测试：


public class Main {
    public static void main(String[] args) {
 
        Array arr = new Array(20);
        for (int i = 0; i < 10; i++)
            arr.addLast(i);
        System.out.println(arr);
 
        arr.add(1, 100);
        System.out.println(arr);
    }
}

获取和修改：


    //获取index索引位置的元素
    int get(int index){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Get failed. Index is illegal");
        return data[index];
    }
    //修改index索引位置的元素
    void set(int index,int e){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Set failed. Index is illegal");
        data[index] = e;
    }

数组中包含和搜索


    //查找数组中是否有元素e
    public boolean contains(int e){
        for(int i=0;i
            if(data[i] == e)
                return true;
        }
        return false;
    }
 
    //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(int e){
        for(int i=0 ;i
            if(data[i] == e)
                return i;
        }
        return -1;
    }

数组中删除

指定索引：


    //从数组中删除index位置的元素，返回删除的元素
    public int remove(int index){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Remove failed.Index id illegal.");
        int ret = data[index];
        for(int i = index+1; i < size; i++) {
            data[i-1] = data[i];
        }
        size--;
        return ret;
    }
 
    //从数组中删除第一个元素，返回删除的元素
    public int removeFirst(){
        return remove(0);
    }
    //从数组中删除最后一个元素，返回删除的元素
    public int removeLast(){
        return remove(size - 1);
    }
 
    //从数组中删除元素e
    public void removeElement(int e){
        int index = find(e);
        if(index != -1)
            remove( index);
    }

注意：

1.要删除的这个元素的位置后面的元素都要上左移动

2.删除任务结束之后size--

size既表示有多少元素，又表示第一个没有元素的位置，也就是说如果要向整个数组末尾添加元素的时候，就要添加到size的位置。

2.size下有元素是没有问题的，因为用户是看不到size所指元素的（用户指定的索引要满足index>=0&&index

测试：


arr.remove(2):
System.out.println(arr);
arr.removeELement(4); 
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);

泛型类

表示Array盛放的数据类型为E，至于这个E是什么，则可以在具体使用的时候再进行声明。

修改为泛型之后的完整代码：


public class Array {
 
    private E[] data;
    private int size;
 
    //构造函数，传入数组的容量capacity构造Array
    public Array(int capacity) {
//        data = new E[capacity];//对于java语言来讲不支持new一个泛型
        data = (E[])new Object[capacity];//合法方式
        size = 0;
    }
 
    //无参数的构造函数，默认数组的容量capacity=10
    public Array() {
        this(20); //用户没必要非要传入一个容量参数，我们将其默认设定
    }
 
    //获取数组中的元素个数
    public int getSize() {
        return size;
    }
 
    //获取数组的容量
    public int getCapacity() {
        return data.length;
    }
 
    //判空
    public boolean isEmpty() {
        return size == 0;
    }
 
    //获取index索引位置的元素
    E get(int index){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Get failed. Index is illegal");
        return data[index];
    }
    //修改index索引位置的元素
    void set(int index,E e){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Set failed. Index is illegal");
        data[index] = e;
    }
 
 
    //查找数组中是否有元素e
    public boolean contains(E e){
        for(int i=0;i
            if(data[i] == e)
                return true;
        }
        return false;
    }
 
    //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for(int i=0 ;i
            if(data[i] == e)
                return i;
        }
        return -1;
    }
 
    //向所有元素后添加一个新元素
    public void addLast(E e) {
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. Array is full.");
        data[size] = e;
        size++;
        //data [size++] = e;
    }
 
    //从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Remove failed.Index id illegal.");
        E ret = data[index];
        for(int i = index+1; i < size; i++) {
            data[i-1] = data[i];
        }
        size--;
        data[size] = null;
        return ret;
    }
 
    //从数组中删除第一个元人，返回创除的元素
    public E removeFirst(){
        return remove(0);
    }
    //从数组中删除最后一个元素，返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }
 
    //从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove( index);
    }
 
    //在第Index个位置插入一个新元素e
    public void add(int index, E e) {
        if (size == data.length)
            throw new IllegalArgumentException("Add faiLed. Array is full.");
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
        //每一个元素都向后挪一个位置，直到挪到index这个元素
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];//后一个索引位置赋上前一个索引元素
        }
        data[index] = e;
        size++;
    }
 
    @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();
    }
}

再次声明：Array arr = new Array<>(20);

将Student类作为泛型：

动态数组

假设现在有一个空间为4的数组并且已经装满了，如果再添加元素将会抛出异常。但是我们可以进行其他操作。

我们可以再开创一个新数组，新数组的容量比原来要大一些，capacity变为8，size不变，将data指向新数组，此时data和newdata指向的是同一片内存空间。这一整个过程封装在一个函数当中，当函数执行完毕之后newdata就失效了，而data是全局变量，保持指向新数组。那么原来的旧数组因为没人指着了，JAVA的垃圾回收机制会将其回收。


    //私有方法，用户不能自己来调用
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++)
            newData[i] = data[i];
        data = newData;
    }

添加元素：


    //在第Index个位置插入一个新元素e
    public void add(int index, E e) {
 
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
 
 
        if (size == data.length)
//            throw new IllegalArgumentException("Add faiLed. Array is full.");//当数组满了之后不载抛出异常，而是将其增加空间
            resize(2* data.length);  //扩容
        
 
 
        //每一个元素都向后挪一个位置，直到挪到index这个元素
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];//后一个索引位置赋上前一个索引元素
        }
        data[index] = e;
        size++;
    }

测试：


public class Main {
    public static void main(String[] args) {
 
        Array arr = new Array<>(10);
        for (int i = 0; i < 10; i++)
            arr.addLast(i);
        System.out.println(arr);
 
        arr.add(1, 100);//满了之后再次增加元素
        System.out.println(arr);
    }
}

在删除操作当中也可以resize：


    //从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if (index<0||index>=size)
            throw new IllegalArgumentException("Remove failed.Index id illegal.");
        E ret = data[index];
        for(int i = index+1; i < size; i++) {
            data[i-1] = data[i];
        }
        size--;
        data[size] = null;
 
        //当数组删除到只剩下数组空间的二分之一时
        if (size == data.length/2)
            resize(data.length/2);//缩小容量
 
 
        return ret;
    }

简单的复杂度分析

对于增删的操作，如果只对最后一个元素操作则是只需要O(1)，之所以还是O(n)，是因为还有resize操作，需要把整个数组元素复制一遍。

相关阅读:
初次接触Sharding-JDBC并实际应用
 redis之发布与订阅
 微生物共现网络可视化：实现布局自由
 扩展欧几里得(acwing877)
剖析虚幻渲染体系（14）- 延展篇：现代渲染引擎演变史Part 1（萌芽期）
vue3使用echarts5.3.3无法正常使用折线图
 概率论介绍
 腾讯云数据库公有云市场稳居TOP 2！
VM虚拟机 13.5 for Mac
一个简单利用WebGL绘制频谱瀑布图示例
原文地址：https://blog.csdn.net/m0_52601969/article/details/127106735