数据结构与算法——数组

DangoSky 发布于2019-08-16 15:45 / 2745人阅读

摘要：概述数组是一种很基础的数据结构，几乎绝大多数编程语言都会支持数组这种数据结构。数组是一种线性结构，使用一组连续的内存空间，来存储相同类型的数据。

1. 概述

数组（Array）是一种很基础的数据结构，几乎绝大多数编程语言都会支持数组这种数据结构。数组是一种线性结构，使用一组连续的内存空间，来存储相同类型的数据。

所谓线性结构，就是指数据是前后排列的，只有前后两个方向，除了数组，其他的比如链表、栈、队列都是线性结构。

因为数组是使用连续的内存空间来存储数据的，所以数组的最大的特点就是支持根据下标随机访问数据，这是数组最大的优势。但是，有利就有弊，虽然数组高效的支持下标访问，只不过在插入和删除数据的时候就比较低效了，为了保证内存的连续性，必须要进行数据搬移。

2. 插入数据

先来看看插入操作，假如有一个数组 [3, 4, 6, 8, 7, 2, 5]，第一种情况是插入的元素位于数组的最后一个位置，那么不用进行数据搬移，时间复杂度为 O(1) ，如果插入的位置是第一个，那么必须移动整个数组，时间复杂度为 O(n) 。

这里有另外一个处理思路：如果数组中存储的数据不在乎彼此顺序的话，那么插入数据的时候，我们可以直接将插入位置的元素放到数组最后一位，腾出位置给新的元素。就像下图这样：

3. 删除数据

再来看看删除操作，还是上面的数组 [3, 4, 6, 8, 7, 2, 5]，如果删除的是最后一个元素，那么不需要进行数据搬移，如果删除的是第一个元素，那么数组每一个元素都会向前移动一位。

只不过，在某些场景下，如果不是特别追求数据的连续性，那么我们可以采用另一种思路来处理删除操作。例如数组的大小为 10 ，现在存储了 7 个元素，分别是 [3, 4, 6, 8, 7, 2, 5]，如果我们要删除 3 4 6 这三个元素，我们先将其标记为删除，等到数组空间不够的时候，在集中性的进行数据搬移，这样就大大减少了数据搬移的次数！

是不是非常高效呢？

4. Java 容器

在 Java 语言中，提供了一个可以支持动态扩容的数组容器：ArrayList，如果你熟悉 Java 语言的话，几乎每天都会和这个容器打交道，它封装了一些数组的操作，并且在数组空间不够的时候，自动扩容为原来的 1.5 倍。

只不过，在使用 ArrayList 的时候，要是能够指定大小，最好指定，这样会减少申请内存空间和数据搬移的操作。

5. 代码示例

下面是简单的支持动态扩容的数组实现：

/*
 * 泛型动态数组
 */
public class GenericArray {

    private T[] data;
    private int count;//数组中存储的个数
    
    public GenericArray(int capacity) {
        this.data = (T[]) new Object[capacity];
        this.count = 0;
    }

    public GenericArray() {
        this(16);
    }
    
    //返回数组中元素的个数
    public int getSize() {
        return this.count;
    }
    
    //返回数组容量
    public int getCapacity() {
        return this.data.length;
    }

    //设置某个位置的数据
    public void set(int index, T value) {
        if (count == data.length) {
            //扩容
            resize(data.length * 2);
        }
        checkIndex(index);
        
        if (index == count) {
            data[count ++] = value;
            return;
        }
        //常规删除
        for (int i = count; i < index; i --) 
            data[i] = data[i - 1];
        data[index] = value;
        count ++;
    }
    
    //在数组末尾插入数据
    public void insert(T value) {
        set(count, value);
    }
    
    //删除数据 
    public T remove(int index) {
        if(index == count) throw new IllegalArgumentException("Index Illegal!");
        checkIndex(index);
        
        T result = data[index];
        
        for (int i = index; i < count - 1; i ++) 
            data[i] = data[i + 1];
        count --;
        
        //缩容
        if (count == data.length / 2) {
            resize(data.length / 2);
        }
        return result;
    }
    
    //检查下标的方法
    public void checkIndex(int index) {
        if(index < 0 || index > count) throw new IllegalArgumentException("Index Illegal!");
    }
    
    //重新设置数组的容量, 对应的操作是扩容和缩容
    private void resize(int capacity) {
        T[] temp = (T[]) new Object[capacity];
        for (int i = 0; i < count; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }
}

是不是很简单呢？后面接着讲数据结构与算法的知识！

混合云私有云算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

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

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

数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0
你知道和你不知道的冒泡排序

摘要：用来标示该轮冒泡排序中，数组是否是有序的。适用情况当冒泡算法运行到后半段的时候，如果此时数组已经有序了，需要提前结束冒泡排序。当第一轮冒泡排序结束后，元素会被移动到下标的位置。这篇文章包含了你一定知道的，和你不一定知道的冒泡排序。 gif看不了可以点击【原文】查看gif。源码: 【地址】 1. 什么是冒泡排序可能对于大多数的人来说比如我，接触的第一个算法就是冒泡排序。我看过的很...

Worktile 2019-08-16 18:23 评论0 收藏0
JS数据结构与算法_排序和搜索算法

摘要：上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客，也是在面试中常常会被问到的一部分内容排序和搜索。上一篇：JS数据结构与算法_树写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似冒泡排序，两层遍历啪啪啪就完事了，然后再也无心去深入研究排序相...

姘搁『 2019-08-23 16:26 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0