资讯专栏INFORMATION COLUMN

我理解的数据结构(一)—— 数组(Array)

Worktile / 1104人阅读

摘要:我理解的数据结构一数组首先,我是一个,但是毕竟是一个脚本语言,如果使用脚本语言去理解数据结构具有一定的局限性。

我理解的数据结构(一)—— 数组(Array)
首先,我是一个phper,但是毕竟php是一个脚本语言,如果使用脚本语言去理解数据结构具有一定的局限性。因为脚本语言是不需要编译的,如果你的语法写的不错,可能执行起来会要比用一个更好的数据结构来的更快、更高效(在数据量不大的情况下)。而且数据结构是脱离任何一门语言存在的。所以,下面会选用java去更深入的理解数据结构。

注:这里不会去过多的解释java的语法。

一、定义一个数组的两种方式

int[] arr = new int[10];

int[] arr = new int[] {10, 20, 30};

二、数组基础

数组的容量在数组一开始定义的时候就固定了。

数组最大的优点:根据索引快速查询。如:arr[2]

数组最好应用于“索引有语意”的情况下。

但并非所有有语意的索引都适用于数组:比如索引是一个人的身份证号,会开辟过大的空间,不现实。

下面会讨论数组“索引没有语意”的情况,基于java数组,二次封装属于我们自己的数组类,更深入的理解数组。

三、创建一个最基本的数组类
学习任何一个数据结构,CRUD必不可少。下面,让我们来一起一步步完善属于我们自己的数组的增、删、改、查
public class Array {

    // 数组的实际大小
    private int size;
    // 数组
    private int[] data;

    // 构造函数,根据传入的容纳量定义一个int类型的数组
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    // 重载,没有传入容纳量,定义一个长度为10的int类型数组
    public Array() {
        this(10);
    }

    // 数组的实际大小
    public int getSize() {
        return size;
    }

    // 数组的容纳量
    public int getCapacity() {
        return data.length;
    }

    // 数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}
四、增
//往数组的任意位置插入
public void add(int index, int ele) {

    // 数组已满
    if (size == data.length) {
        throw new IllegalArgumentException("add failed. arr is full");
    }

    // 插入的索引位不合法
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("add failed. index < 0 or index >= size");
    }

    // 从index向后的所有元素均向后赋值
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = ele;
    size++;
}

// 第一个位置插入
public void addFirst(int ele) {
    add(0, ele);
}

// 最后一个位置插入
public void addLast(int ele) {
    add(size, ele);
}
五、查和改
// 查询index索引位置的元素
public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("get failed. index is illegal");
    }
    return data[index];
}

// 查询ele元素的索引,不存在返回-1
public int find(int ele) {
    for (int i = 0; i < size; i++) {
        if (data[i] == ele) {
            return i;
        }
    }
    return  -1;
}

// 更新Index的元素
public void set(int index, int ele) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("get failed. index is illegal");
    }
    data[index] = ele;
}
六、删
// 根据索引删除数组中的第一个ele,返回ele
public int remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }

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

    return data[index];
}

// 删除第一个元素
public int removeFirst() {
    return remove(0);
}

// 删除最后一个
public int removeLast() {
    return remove(size - 1);
}

// 删除指定元素
public void removeElement(int ele) {
    int index = find(ele);
    if (index != -1) {
        remove(index);
    }
}
七、包含和重写toString
Override
public String toString() {
    StringBuffer res = new StringBuffer();
    res.append(String.format("Array: size = %d, capacity = %d
", 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();
}

// 查询数组中是否包含元素ele
public boolean contain(int ele) {
    for (int i = 0; i < size; i++) {
        if (data[i] == ele) {
            return true;
        }
    }
    return  false;
}

注:通过以上方法我们已经创建了一个最最最最最基本的数组类(见下图)。当然,你也可以去添加一些自己需要的方法,例如:removeAllfindAll之类的。

但是,我们现在的数组只支持int类型,太过局限。接下来,我们去给我们的数组升华一哈~
八、使用泛型让我们的数组支持“任意”数据类型
首先,为什么我要在任意这两个字加上引号,因为java的泛型不支持基本数据类型,只能是类的对象。
但是,这并不代表如果我们使用了泛型,就不可以使用基本数据类型了,因为每一个基本数据类型都有一个对应的包装类
使用泛型的时候,我们只需要传入对应的包装类即可。
java的基本数据类型
基本数据类型 包装类
boolean Boolean
byte Byte
char Char
short Short
int Int
long Long
float Float
double Double
所以,我们的代码只需要进行极小的改动即可:
public class ArrayNew {
    // 数组的实际大小
    private int size;
    // 数组
    private E[] data;

    // 构造函数,根据传入的容纳量定义一个 E 类型的数组
    public ArrayNew(int capacity) {
        // 强转
        data = (E[]) new Object[capacity];
        size = 0;
    }

    // 重载,没有传入容纳量,定义一个长度为10的int类型数组
    public ArrayNew() {
        this(10);
    }

    // 数组的实际大小
    public int getSize() {
        return size;
    }

    // 数组的容纳量
    public int getCapacity() {
        return data.length;
    }

    // 数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 往数组的任意位置插入
    public void add(int index, E ele) {

        // 数组已满
        if (size == data.length) {
            throw new IllegalArgumentException("add failed. arr is full");
        }

        // 插入的索引位不合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add failed. index < 0 or index > size");
        }

        // 从index向后的所有元素均向后赋值
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = ele;
        size++;
    }

    // 第一个位置插入
    public void addFirst(E ele) {
        add(0, ele);
    }

    // 最后一个位置插入
    public void addLast(E ele) {
        add(size, ele);
    }

    // 查询index索引位置的元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed. index is illegal");
        }
        return data[index];
    }

    // 查询ele元素的索引,不存在返回-1
    public int find(E ele) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(ele)) {
                return i;
            }
        }
        return  -1;
    }

    // 更新Index的元素
    public void set(int index, E ele) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed. index is illegal");
        }
        data[index] = ele;
    }

    // 根据索引删除数组中的第一个ele,返回ele
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed. index is illegal");
        }
        
        E result = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = (data[i]);
        }
        // 空间释放,垃圾回收会自动回收
        data[--size] = null;

        return result;
    }

    // 删除第一个元素
    public E removeFirst() {
        return remove(0);
    }

    // 删除最后一个
    public E removeLast() {
        return remove(size - 1);
    }

    // 删除指定元素
    public void removeElement(E ele) {
        int index = find(ele);
        if (index != -1) {
            remove(index);
        }
    }

    // 查询数组中是否包含元素ele
    public boolean contain(E ele) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(ele)) {
                return true;
            }
        }
        return  false;
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append(String.format("Array: size = %d, capacity = %d
", 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();
    }

}

注:创建数组时,只需ArrayNew arr = new ArrayNew<>(20);即可。

九、动态数组
原理:其实,动态数组的原理非常简单,如果我们希望我们的数组具有可伸缩性,只需要我们在添加或者删除元素时判断size是否到达临界。然后去创建一个新capacity的数组,然后把旧数组的引用指向新数组即可。
所以,我们上述代码的改变极小,只需要改变addremove即可。然后添加一个resize方法。
// 往数组的任意位置插入
public void add(int index, E ele) {
    // 插入的索引位不合法
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add failed. index < 0 or index > size");
    }

    // 如果size == data.length,数组长度已满
    if (size == data.length) {
        resize(data.length * 2);
    }

    // 从index向后的所有元素均向后赋值
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = ele;
    size++;
}

// 根据索引删除数组中的第一个ele,返回ele
public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }

    E result = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = (data[i]);
    }
    // 空间释放,垃圾回收会自动回收
    data[--size] = null;

    // 减小数组长度,不要浪费空间
    if (size == data.length / 2 && size != 0) {
        resize(size);
    }

    return result;
}

// 自动伸缩数组
private void resize(int newCapacity) {
    E[] newData = (E[])new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData;
}
十、简单复杂度分析我们封装的数组
通过上面的分析和代码实现,我们封装了一个自己的数组,并且实现了一些数组最基本的功能,包括支持增、删、改、查、支持任意数据类型以及动态数组。那么我们就来分析一下我们自己封装数组的复杂度。
操作 复杂度
O(n)
O(n)
已知索引O(1);未知索引O(n)
已知索引O(1);未知索引O(n)

但是:在我们的数组中,增和删我们都调用了resize方法,如果size < data.length,其实我们执行addLast复杂度只是O(1)而已(removeLast同理)。所以,我们应该怎么去分析resize方法所带来的复杂度呢?

十一、均摊复杂度和防止复杂度的震荡 (1)均摊复杂度
让我们拿  来举例
方法 复杂度
addLast(ele) O(1)
addFirst(ele) O(n)
add(index, ele) O(n/2) = O(n)
resize(newCapacity) O(n)

其实,在执行addLast的时候,我们并不是每次都会触发resize方法,更多的时候,复杂度只是O(1)而已。
比方说:
当前的capacity = 8,并且每一次添加操作都使用addLast,第9次addLast操作,触发resize,总共17次基本操作(resize方法会进行8次操作,addLast方法进行9次操作)。平均,每次addLast操作,进行2次基本操作(17 / 9 ≈ 2)。
假设:
capacity = nn + 1addLast,触发resize,总共进行了2n + 1次操作,平均每次addLast操作,进行了2次基本操作。

这样均摊计算,时间复杂度是O(1)!

(2)防止复杂度的震荡
让我们来假设这样一种情况:
size == data.length时,我们执行了addLast方法添加一个元素,这个时候我们需要去执行resize方法,此时,addLast的复杂度为O(n)
然后,我去removeLast,此时的removeLast复杂度也是O(n)
再然后,我再去执行addLast
.
.
.

有没有发现,在这样一种极端情况下,addLastremoveLast的复杂度变成了O(n),其实,这个就是复杂度的震荡

为什么我们会产生这种震荡?

add情况下,我们去扩容数组无可厚非。但是remove情况下,我们立刻去缩容数组就有点不合适了。

怎么去解决这种情况?

因为我们之前采取的措施是Eager

所以,我们采取一种Lazy的方式:当size == data.length / 2,我们不要立刻缩容,当size == data.length / 4时,我们才去缩容,就可以很好的解决这种震荡。

具体代码如下,其实只是对remove进行了极小的改变
public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove failed. index is illegal");
    }
    
    E result = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    // 空间释放,垃圾回收会自动回收
    data[--size] = null;

    // 减小数组长度,不要浪费空间,防止震荡
    if (size == data.length / 4 && data.length / 2 != 0) {
        resize(data.length / 2);
    }

    return result;
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/29281.html

相关文章

  • 理解数据结构(三)—— 队列(Queue)

    摘要:我理解的数据结构三队列一队列队列是一种线性结构相比数组,队列对应的操作是数组的子集只能从一端队尾添加元素,只能从另一端队首取出元素队列是一种先进先出的数据结构二数组队列与循环队列数组队列如果你有看过我之前的文章不要小看了数组或者栈,你就会发 我理解的数据结构(三)—— 队列(Queue) 一、队列 队列是一种线性结构 相比数组,队列对应的操作是数组的子集 只能从一端(队尾)添加元素,...

    hlcc 评论0 收藏0
  • 理解数据结构(三)—— 队列(Queue)

    摘要:我理解的数据结构三队列一队列队列是一种线性结构相比数组,队列对应的操作是数组的子集只能从一端队尾添加元素,只能从另一端队首取出元素队列是一种先进先出的数据结构二数组队列与循环队列数组队列如果你有看过我之前的文章不要小看了数组或者栈,你就会发 我理解的数据结构(三)—— 队列(Queue) 一、队列 队列是一种线性结构 相比数组,队列对应的操作是数组的子集 只能从一端(队尾)添加元素,...

    wean 评论0 收藏0
  • 理解数据结构(二)—— 栈(Stack)

    摘要:以数组的最后一个元素当成栈顶元素。解题思路首先,我们可以把左括号直接压入栈,不论是小括号中括号还是大括号。拿出栈顶元素,如果与之右括号不匹配,则返回。如果字符串比较完成,没有返回,则判断栈是否为空。 我理解的数据结构(二)—— 栈(Stack) 一、栈基础 栈是一种线性结构 相比较数组,栈对应的操作是数组的子集 只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶 栈是一种后...

    lcodecorex 评论0 收藏0
  • 理解数据结构(二)—— 栈(Stack)

    摘要:以数组的最后一个元素当成栈顶元素。解题思路首先,我们可以把左括号直接压入栈,不论是小括号中括号还是大括号。拿出栈顶元素,如果与之右括号不匹配,则返回。如果字符串比较完成,没有返回,则判断栈是否为空。 我理解的数据结构(二)—— 栈(Stack) 一、栈基础 栈是一种线性结构 相比较数组,栈对应的操作是数组的子集 只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶 栈是一种后...

    Charlie_Jade 评论0 收藏0
  • 关于Array.reduce理解与拓展

    摘要:而则从数组的最后一项开始,向前遍历到第一项。传给和的函数接收个参数前一个值当前值项的索引和数组对象。这个函数返回的任何值都会作为第一个参数自动传给下一项。第二次,是加的结果,是数组的第三项。 2018年1月6日 首先我要感谢我的同事徒步上山看日出在我第一份实习的时候对我的指导,现在我也开始跟他一样开始养成写博客的习惯 现在开始讨论我遇到的第一个问题,这是我在看javascript高级程...

    keithxiaoy 评论0 收藏0
  • 关于Array.reduce理解与拓展

    摘要:而则从数组的最后一项开始,向前遍历到第一项。传给和的函数接收个参数前一个值当前值项的索引和数组对象。这个函数返回的任何值都会作为第一个参数自动传给下一项。第二次,是加的结果,是数组的第三项。 2018年1月6日 首先我要感谢我的同事徒步上山看日出在我第一份实习的时候对我的指导,现在我也开始跟他一样开始养成写博客的习惯 现在开始讨论我遇到的第一个问题,这是我在看javascript高级程...

    李世赞 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<