Algorithms_基础数据结构(01)_线性表之数组&数组的应用案例分析-阿里云开发者社区

大纲图

数组的经典面试题目

给你一个文件里面包含全国人民（14亿）的年龄数据（0~180），现在要你统计每一个年龄有多少人？给定机器为单台+2CPU+2G内存。不得使用现成的容器，比如map等。

文件格式

18
19
21
18
3
9
....
....

数据结构三要素

我们都知道数据结构三要素

数据逻辑结构
数据存储结构
数据的运算

数据逻辑结构（线性结构&非线性结构）

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。

数据存储结构（顺序存储、链式存储、索引存储和散列存储）

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

顺序存储

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。

优点是可以实现随机存取，每个元素占用最少的存储空间；
缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

链式存储

不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。

优点是不会出现碎片现象，充分利用所有存储单元；
缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。

索引存储

存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。

优点是检索速度快；
缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。

散列存储

根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。

优点是检索、增加和删除结点的操作都很快；
缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

线性表

我们知道具有“一对一”逻辑关系的数据，最好的存储方式是使用线性表。

线性表，形象的可以理解为物理空间中的一段内存区域中存储的数据，用一条线串起来的，前后相连

其中又可以细分为：顺序表和链表

顺序表：将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构,简称顺序表

链表：数据分散的存储在物理空间中，通过指针维系它们之间的逻辑关系，这种存储结构称为链式存储结构，简称链表

数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。例如，图 1 显示的这组数据，其中 1、2、3、4 和 5 都是这组数据钟的一个元素。

某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；
某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组，接下来我们就以数组为例来演示线性表吧

什么是数组

数组是一个有限的、类型相同的数据的集合，在内存中是一段连续的内存区域。

perceive : 感知

store in RAM : 在 Random Access Memory 中的存储。

consecutive: 连续的

数组下标从0开始，如上图对应着下标依次是0、1、2、3、4、5。
数组里面存储的数据类型必一致，上图中存的都是int类型。
数组中的全部元素是“连续”的存储在一块内存空间中的，如上图右侧，元素与元素之间不会有别的存储隔离。
另外，也是因为数组需要连续的内存空间，所以数组在定义的时候就需要提前指定固定大小，不能改变。

数组的访问

数组支持随机访问.

我们可以通过下标随机访问数组中任何一个元素, 因为数组元素的存储是连续的，所以我们可以通过数组内存空间的首地址加上元素的偏移量计算出某一个元素的内存地址，如下：

array[n]的地址 = array数组内存空间的首地址 + 每个元素大小*n

举个例子：有一个长度为10的int数组，int[] a = new int[10].

计算机给数组a[10]分配了一块连续的内存空间1000~1039,其中，内存块的首地址为base_address = 1000.

计算机会为每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算即需要随机访问数组中的某个元素的时候，它会首先通过下面的寻址公式，计算该元素存存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中data_type_size表示数组中每个元素的大小。例如，数组中存储的int类型的数据，所以，data_type_size就是4字节。

通过上述公式可知：数组中通过下标去访问数据时并不需要遍历整个数组，因此数组的访问时间复杂度是 O(1).

当然这里需要注意，如果不是通过下标去访问，而是通过内容去查找数组中的元素，则时间复杂度不是O(1)，极端的情况下需要遍历整个数组的元素，时间复杂度可能是O(n).

通过不同的查找算法所需的时间复杂度是不一样的。

数组的插入与删除

因为数组元素的连续性要求，所以导致数组在插入和删除元素的时候效率比较低.

举个例子

插入

假设要在数组中间插入一个新元素，就必须要将相邻的后面的元素全部往后移动一个位置，留出空位给这个新元素。

还是拿上面那图举例，如果需要在下标为2的地方插入一个新元素11，那就需要将原有的2、3、4、5几个下标的元素往后移动一位，新元素再插入下标为2的位置，最后形成新的数组是 23、4、11、6、15、5、7

删除

数组的删除与数组的插入类似。删除一个元素，就必须要将相邻的后面的元素全部往前移动一个位。

如果新元素是插入在数组的最开头位置，那整个原始数组都需要向后移动一位，此时的时间复杂度为最坏情况即O(n).
如果新元素要插入的位置是最末尾，则无需其它元素移动，则此时时间复杂度为最好情况即O(1）
所以数组插入的时间复杂度是O(n)

如果需要删除一个元素，需要把它后面的元素全部一个一个往前移动（不能同时移动！），元素越多，耗时越长。

举个例子：把第三个元素删除后引起了4次元素移动。

或者下面的这个图更直观一些

数组的CRUD

约定好哈： 按顺序添加，不要跳着添加参数

我们知道数组是内存内连续的一段区域，虽然初始化数组后，通过首地址以及数组内元素类型的长度，可以任意的找到下标对应元素的内存地址，为啥不建议跳着插入呢？，举个例子比如 1个数组，容量为10 ，下标 0 ~9 ，你跳着插入a[9] ,然后又在a[9]前面未插入值的下标位置插入了一个值，那么该下标后面的元素都要后移一，最后一位没地方可以存了。。。这种情况就必须得扩容了，才能保证数据不丢失。 (扩容也很简单：弄个临时数组，容量为原来的2倍，把原来的数组的数据copy过去。至于什么时候触发这个扩容，JDK中的加载因子是原数组的容量使用了0.75的时候)

这样搞得话，是不是造成了空间的浪费？？？

增加

/**
     * @param index   数组下标
     * @param element 目标值
     */
    public void add(int index, int element) {
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        if (size == arr.length) {
            throw new IllegalArgumentException("Array Full");
        }
        // Step 1 : 从最后一个元素一直到index位置的元素，往后挪动一位
        for (int i = (arr.length - 1); i > index; i--) {
            // 从最后一位开始，不能写成 arr[i+1] = arr[i];  第一次循环 下标为最后一位 index +1 下标越界
            arr[i] = arr[i -1 ];
        }
        // Step 2 : 空出来的那个下标位置，赋值
        arr[index] = element;
        // Step 3 : 维护数组当前size
        size++;
    }

核心代码：

// Step 1 : 从最后一个元素一直到index位置的元素，往后挪动一位
  for (int i = (arr.length - 1); i > index; i--) {
        // 从最后一位开始，不能写成 arr[i+1] = arr[i];  第一次循环 下标为最后一位 +1 下标越界
        arr[i] = arr[i -1 ];
    }
  // Step 2 : 空出来的那个下标位置，赋值
  arr[index] = element;

解释下：

数组的特性，是内存中一段连续的区域，

-------> 初始化特定容量的数组后，这个数组所占用的内存大小就是确定的

------> 继而每个下标对应的元素在内存中的地址就是可以通过如下公式计算出来的　a[i]_address = base_address + i * data_type_size

------>

删除

public void delete(int index){
        if (index < 0 || index > (arr.length -1)){
            throw new IllegalArgumentException("参数不合法");
        }
        for (int i = index ; i< (arr.length -1); i++) {
            if (i != arr.length-1){ // 防止最后一位，进入运算后 i+1 导致数据组下标越界
                arr[i] = arr[i+1];
            }else{// 最后一位 初始
                arr[i] = 0 ;
            }
        }
        size--;
    }

修改

public void update(int index, int element){
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        arr[index] = element;
    }

查找

public int get(int index){
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        return arr[index];
    }

完整示例

/**
 * @author 小工匠
 * @version v1.0
 * @create 2019-12-25 21:59
 * @motto show me the code ,change the word
 * @blog https://artisan.blog.csdn.net/
 * @description
 **/
public class ArtisanArray {
    /**
     * 存储元素的数组
     */
    private int[] arr;
    /**
     * 当前数组中元素的个数
     */
    private int size;
    /**
     * 默认初始化容量为16的int数组
     */
    public ArtisanArray() {
        this.arr = new int[16];
        this.size = 0;
    }
    /**
     * 指定数组容量
     *
     * @param capacity
     */
    public ArtisanArray(int capacity) {
        this.arr = new int[capacity];
        this.size = 0;
    }
    /**
     * @param index   数组下标
     * @param element 目标值
     */
    public void add(int index, int element) {
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        if (size == arr.length) {
            throw new IllegalArgumentException("Array Full");
        }
        // Step 1 : 从最后一个元素一直到index位置的元素，往后挪动一位
        for (int i = (arr.length - 1); i > index; i--) {
            // 从最后一位开始，不能写成 arr[i+1] = arr[i];  第一次循环 下标为最后一位 index +1 下标越界
            arr[i] = arr[i -1 ];
        }
        // Step 2 : 空出来的那个下标位置，赋值
        arr[index] = element;
        // Step 3 : 维护数组当前size
        size++;
    }
    public void delete(int index){
        if (index < 0 || index > (arr.length -1)){
            throw new IllegalArgumentException("参数不合法");
        }
        for (int i = index ; i< (arr.length -1); i++) {
            if (i != arr.length-1){ // 防止最后一位，进入运算后 i+1 导致数据组下标越界
                arr[i] = arr[i+1];
            }else{// 最后一位 初始
                arr[i] = 0 ;
            }
        }
        size--;
    }
    public void update(int index, int element){
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        arr[index] = element;
    }
    public int get(int index){
        if (index < 0 || index > (arr.length - 1)) {
            throw new IllegalArgumentException("参数错误");
        }
        return arr[index];
    }
    public static void main(String[] args) {
        ArtisanArray artisanArray = new ArtisanArray(10);
        System.out.println("Init...");
        // 初始化几个数据
        artisanArray.add(0, 10);
        artisanArray.add(1, 11);
        artisanArray.add(2, 12);
        artisanArray.add(3, 13);
        artisanArray.add(4, 14);
        artisanArray.add(5, 15);
        artisanArray.add(6, 16);
        artisanArray.add(7, 17);
        artisanArray.print();
        System.out.println("ADD... INDEX = 5");
        artisanArray.add(5, 25);
        artisanArray.print();
        System.out.println("UPDATE... INDEX = 5");
        artisanArray.update(5, 55);
        artisanArray.print();
        System.out.println("GET... INDEX = 5");
        System.out.println(artisanArray.get(5));
        System.out.println("DELETE... INDEX = 5");
        artisanArray.delete(5);
        artisanArray.print();
    }
    public void print() {
        System.out.println("数组容量capacity：" + arr.length + " ,数组当前数据量size=" + size);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println();
    }
}

引导案例参考答案

再来看下我们的这个问题

分析：

----> 年龄范围 0~180 , 是不是开辟一个容量为181的数组就够了？

----> 统计每一个年龄有多少人—> 每个年龄就是对应的数组下标，碰到一个逐个加一，是不是就解决了？

Code

import java.io.*;
import java.util.Random;
/**
 * @author 小工匠
 * @version v1.0
 * @create 2019-12-28 16:54
 * @motto show me the code ,change the word
 * @blog https://artisan.blog.csdn.net/
 * @description
 **/
public class AgeCount {
    public static void main(String[] args) throws IOException {
        // 模拟文件
        simulatorAgeFile();
        String fileName = "D:\\age.txt";
        long start = System.currentTimeMillis();
        // 读取文件  逐行读取
        InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(fileName),"utf-8");
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        int[] age = new int[500];
        int total = 0 ;
        String line = null;
        while( (line = bufferedReader.readLine()) != null){  // 时间复杂度  O(n)
            int index = Integer.valueOf(line) ;
            age[index]++ ; // 年龄累加
            total++ ; // 总量累加
        }
        //估算下时间： O(n) 14亿数据. 最差的CPU也得 100万/秒 *1000 = 10亿 100~1000s之间 => 500s以下 60*8=480s
        System.out.println("总共的数据大小: " + total);
        for(int i = 0 ; i < 200 ; i ++){//下标从0开始的
            System.out.println(i + ":" + age[i]);
        }
        //124306ms => 124秒
        System.out.println("计算花费的时间为:" + (System.currentTimeMillis() - start) + "ms");
    }
    public static void simulatorAgeFile() throws IOException {
        final String fileName = "d:\\age.txt";
        final Random random = new Random();
        BufferedWriter objWriter = null;
        objWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName)));
        for (int i = 0; i < 1400000000; i++) {
            // 0 - 200 随机整数
            int age = (int) (Math.random() * 100 * 2);
            objWriter.write(age + "\r\n");
        }
        objWriter.flush();
        objWriter.close();
    }
}

14亿， 125秒统计完毕

Algorithms_基础数据结构(01)_线性表之数组&数组的应用案例分析

大纲图