算法数据与结构——数据结构基础

DBC 1.6K 0

1.数组基础

数组最大的优点：快速查询。scores【2】
数组最好应用于“索引有语意”的情况

但并非所有有语意的索引都适用于数组

身份证号：1101031985121666666
数组也可以处理“索引没有语意”情况。
我们在这一章，主要处理“索引没有语意”的情况数组的使用

2.封装我们自己的数组（并且简单的添加元素）

package List;

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) {
        add(size,e);
    }

    //在所有元素前添加一个元素
    public void addFirst(int e){
        add(0,e);
    }
    //  在第index个位置插入一个新元素e
    public void add(int index, int e) {
        if (size == data.length)
            System.out.println("插入新元素方法失败，数组长度不足！");
        if (index < 0 || index > size)
            System.out.println("添加新元素方法失败，插入位置不可以为负数，也不可以大于数组长度");
        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];
        data[index] = e;
        size++;
    }
}

3.为我们的数组添加tostring方法，以及get、set

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

    //获取index索引位置的元素
    int get(int  index){
        if (index<0 || index >= size)
            System.out.println("传入不合法！");
        return data[index];
    }
    //修改index索引位置的元素为e
    void set(int index,int e){
        if (index<0 || index >= size)
            System.out.println("传入不合法！");
        data[index] = e;
    }

4.数组中的搜索、删除

    // 查找数组中是否有元素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)
            System.out.println("传入不合法！");
        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);
    }

我们测试一下

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);

        arr.addFirst(-1);
        System.out.println(arr);

        arr.remove(1);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);
    }
}
控制台输出

5.泛型类

首先我们现将我们的自定义数组类给改造一下，放出完整改造内容

package List;

import java.util.Objects;

public class Array<E> {
    private E[] data;
    private int size;

    //  构造函数，传入数组的容量capacity构造Array
    public Array(int capacity) {
        data = (E[]) new Object[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(E e) {
        add(size, e);
    }

    //在所有元素前添加一个元素
    public void addFirst(E e) {
        add(0, e);
    }

    //  在第index个位置插入一个新元素e
    public void add(int index, E e) {
        if (size == data.length)
            System.out.println("插入新元素方法失败，数组长度不足！");
        if (index < 0 || index > size)
            System.out.println("添加新元素方法失败，插入位置不可以为负数，也不可以大于数组长度");
        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));
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        return res.toString();
    }

    //获取index索引位置的元素
    E get(int index) {
        if (index < 0 || index >= size)
            System.out.println("传入不合法！");
        return data[index];
    }

    //修改index索引位置的元素为e
    void set(int index, E e) {
        if (index < 0 || index >= size)
            System.out.println("传入不合法！");
        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)
            System.out.println("传入不合法！");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null;  //loitering objects != memory leak
        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);
    }
}
这里需要注意的内容，我这里提一下
    // 查找数组中是否有元素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;
    }
温馨提示

这两个，之前我们是用的==，现在我们是用的是equals，具体区别相信很简单，引用地址变成了值的比较

    //从数组中删除index位置的元素，返回删除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            System.out.println("传入不合法！");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null;  //loitering objects != memory leak
        return ret;
    }
温馨提示

这里要注意的是这一行
data[size] = null; //loitering objects != memory leak
之前我们说过，我们不用管size所指定的是什么，因为我们指的是int类型，现在我们指的是一个类对象，那么虽然我们移除了它，但是可能指针依然指向它，导致垃圾回收并不会回收它，所以我们这里手动移除它！

这里注意一个点，就是下面这个类型，是Object，而不是Objects，博主在这里粗心大意，浪费了一些时间！

data = (E[]) new Object[capacity];

接下来测试一个自定义类的操作

package List;

public class Student implements Comparable<Student>{
    private String name;
    private int score;
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }


    @Override
    public boolean equals(Object student){
        if (this==student)
            return true;
        if (student==null)
            return false;
        if (this.getClass() != student.getClass())
            return false;
        Student another = (Student) student;
        return this.name.toLowerCase().equals(another.name.toLowerCase());
    }

    @Override
    public int compareTo(Student another) {
//        if (this.score < another.score)
//            return -1;
//        else if (this.score == another.score)
//            return 0;
//        return 1;

        return this.score - another.score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }

    public static void main(String[] args) {
        Array<Student> arr = new Array<Student>();
        arr.addLast(new Student("大名",100));
        arr.addLast(new Student("小猪",50));
        arr.addLast(new Student("大猪",80));
        System.out.println(arr);
    }
}
控制台输出

6.动态数组

    //  在第index个位置插入一个新元素e
    public void add(int index, E e) {

        if (index < 0 || index > size)
            System.out.println("添加新元素方法失败，插入位置不可以为负数，也不可以大于数组长度");
        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++;
    }

关键代码

resize(2 * data.length);

    // 扩容两倍
    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位置的元素，返回删除的元素
    public E remove(int index) {
        if (index < 0 || index >= size)
            System.out.println("传入不合法！");
        E ret = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
        data[size] = null;  //loitering objects != memory leak

        //动态减小数组
        if (size == data.length / 2)
            resize(data.length / 2);
        return ret;
    }

关键代码

//动态减小数组
if (size == data.length / 2)
resize(data.length / 2);

7.时间复杂度分析

如下图

算法数据与结构——数据结构基础插图
算法数据与结构——数据结构基础插图2
算法数据与结构——数据结构基础插图4
算法数据与结构——数据结构基础插图2
总结

算法数据与结构——数据结构基础插图6

温馨提示

在一种极端情况的时候，会发生复杂度震荡，也就是扩容和缩容情况。如下面红色代码块的极端情况

在数组满的时候，如果我们再增加一条数据，那么就会扩容2倍，然后我们减小一条数据，那么数组又会缩容为二分之一，这样就会发生复杂度震荡

解决方案

之前我们使用了一种比较激进的处理方案，在数组发生一些变化的时候我们就对数组进行了一次较大的O（n）级别的操作，我们可以使用一种比较懒惰的操作，如果数组中数据的内容为数组长度的四分之一，那么我们再进行缩容操作，这样是一种比较简洁、易修改的操作方案，下面是代码实操例子，也是在我们之前的例子上面操作！
 //动态减小数组
        if (size == data.length / 4 && data.length / 2 !=0)
            resize(data.length / 2);
温馨提示

判断中新增了一个判断，避免数组的BUG长度出现！

本文作者为DBC，转载请注明。

发表评论 取消回复
表情 图片 链接 代码

分享