数组

作者: 觥筹啊觥筹 | 来源:发表于2019-04-20 19:37 被阅读0次

数组结构

一. 内存 特征 原理

1. 数组的内存空间

int[] arr = new int[5];
  • 每个 int 元素占4个 字节 (在不同机器上,如单片机,32/64位操作系统中,int占用大小不同) ,在java中int占用4个字节,
数组内存示意.png
_address:某一具体数组内存空间的地址
base_address:内存块的首地址
data_type_size:数据类型大小;int占用4个字节,double为8个;


arr[i]_address = base_address + i * data_type_size

2. 若数组下标从1开始

arr[i]_address = base_address + (i-1)*data_type_size
  • 每次寻址过程中,CPU都要多进行一次减法指针运算

内存结构如图

特征:数组其元素空间大小根据由数组类型决定

原理:arr[i]_address = base_address + i * data_type_size

二. 时间复杂度

1. 查询/修改

数组根据下标来查询 公式为

arr[i]_address = base_address + i * data_type_size
  • base_address : 由内存提供精确值
  • data_type_size : 由数组类型提供精确值
  • 所以:arr[i]_address(第i个元素的内存地址)可以确定

其中,未知的元素只有 i 公式中的其他元素都为常数 并且i也是一个精确的数字,即常数,所以查询操作的时间复杂度为:
T(n)=O(1)

2. 插入/删除

  • 数组的长度为k,要插入元素的位置为n,如果 n>=k,则只进行一次插入操作,最好时间复杂度为T(n)=O(1)

  • 如果n<=k,数组需要将n~k内的元素全都往后移一位,其复杂度为T(n)=O(k-n)=O(n)

  • 因为n<=k,并且出现在每个位置的概率都相同,n插入的位置最多有k种情况,

    n=1时,要操作k-1次,n=2时要操作k-2次,要操作的次数总和=k-n

    平均时间复杂度为T(n)=o(f(\frac{(k-1)+(k-2)+...+(k-n)}{k-n}))=O(f(\frac{nk(1+2+3+...+n)}{k-n}))=O(n)

三.ArrayList

1.add()

    //元素数据,他就是ArrayList底层的数组
    private transient Object[] elementData;

    public boolean add(E e) {
        //size+1 当前数组长度+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将新元素添加到数组中(该数组可能被扩容了,也可能没有)
        elementData[size++] = e;
        return true;
    }



    private void ensureCapacityInternal(int minCapacity) {
        //判定数组是否为空
        if (elementData == EMPTY_ELEMENTDATA) {
            //和默认长度10比较,返回较大的
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //传入将要添加的元素的下标
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        //该段对象的总操作次数+1
        modCount++;

        // overflow-conscious code
        //如果当前数组没有空闲空间了
        if (minCapacity - elementData.length > 0)
            //扩容方法
            grow(minCapacity);
    }


    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新的数组容量 = 旧的数组容量+旧的数组容量的一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2.get()

    public E get(int index) {
        //检查下表长度
        rangeCheck(index);
        //获取元素
        return elementData(index);
    }

    private void rangeCheck(int index) {
        //若下标不存在,则抛出索引越界异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

四. 手写数组封装类

package aritch;

/**
 * create by lyuweigh
 * date 2019 2019/4/20 21:26
 * description <>
 */

import java.util.Arrays;

/**
 * 功能分析:
 * 1. 插入数据
 *    在指定位置插入数据
 *
 * 2. 删除指定位置的数据
 *
 * 3. 查询数据
 *    查询指定位置的数据
 *    打印所有数据
 *
 *    数组有  长度, 数据, 数组包装类有元素个数
 */
public class ArrayDemo<E> {

    //1. 定义一个默认长度 初始化容量
    private int initCapacity = 10;

    //2. 定义一个数组容器,用于存放数据
    private Object element[];

    //3.保存元素的个数
    private int size;

    @Override
    public String toString() {
        return "Arraydemo{" +
                "element=" + Arrays.toString(element) +
                '}';
    }

    public int getSize() {
        return size;
    }

    //默认初始化
    public  ArrayDemo() {
        element = new Object[initCapacity];
    }

    //创建指定长度的数组
    public  ArrayDemo(int initCapacity) {
        this.initCapacity = initCapacity;
        element = new Object[initCapacity];
    }


    /**
     * 插入元素,默认在末尾
     * @param data
     * @return
     */
    public int add(E data) {
        //1.检查数组长度够不够
        checkElementSize(size+1);
        System.out.println("插入");
        add(size, data);
        return size;
    }


    /**
     * 插入元素到指定的位置中
     * @param index
     * @param data
     * @return
     */
    public int add(int index, E data) {

        //检查要插入的位置是否在数组的承受范围内
        checkIndexBoundary(index);
        element[index] = data;
        System.out.println("指定插入");
        return size++;
    }


    /**
     * 删除元素,返回被删除的元素
     * @param index
     * @return
     */
    public E remove(int index) {
        checkIndexBoundary(index);
        E old = (E) element[index];

        //要移动元素的个数 -1 指令因为数组后面减少了一个
        int numMoved = element.length - index - 1;

        /**
         * 从即将要被删除的元素的后一个位置开始复制
         * 复制到被删除的元素的位置上(就是位移操作了),位移所有要移动的元素的个数
         */
        System.arraycopy(element, index + 1, element, index, numMoved);
        System.out.println("删除元素");
        return old;

    }


    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    public E get(int index) {
        //检查这个index在不在数组中
        checkIndexBoundary(index);
        System.out.println("获取元素");
        return (E) element[index];
    }






    /**
     * 检查要操作的下标是否在当前数组边界中
     * @param index
     */
    private void checkIndexBoundary(int index) {
        if (index > element.length) {
            throw new IndexOutOfBoundsException();
        }
    }


    /**
     * 检查数组长度够不够,不够就自动扩容一倍
     * @param i
     */
    private void checkElementSize(int i) {
        if (i - element.length > 0) {
            moreCoarse();
        }
    }


    /**
     * 数组扩容方法
     */
    private void moreCoarse() {
        int oldCapacity= element.length;
        //比较好看的除以2操作 >>
        int newCapacity = element.length +(element.length>>1);
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(element, 0, newArray, 0, element.length);
        element = newArray;
        System.out.println("扩容");
    }
}

相关文章

  • 数组

    数组数组数组数组数组数组数组数组数组

  • JavaScript - 5.数组<增删改查>

    数组 Array 数组 - 增 数组 - 删 / 改 数组 - 查 数组 - 自动 toString() 数组 -...

  • PHP数组使用

    数组定义 数组增、删、改 数组查询 数组排序 数组合并、分割 数组比较、去重复 数组长度 数组遍历 数组转换 其他...

  • 》》》PHP初入---(三)

    数组定义 1.索引数组:数组下标是整型的 声明数组: 访问数组: count(数组)--获取数组长度 查看数组所有...

  • JavaScript中数组的常用操作

    数组的遍历 数组的映射 数组的简化 数组的连接 获取数组的片段 数组的拷贝 查找数组 数组去重

  • JavaSE之数组

    六、数组 目录:数组概述、数组声明创建、数组使用、多维数组、Array类、稀疏数组 1.什么是数组 数组的定义:数...

  • Shell数组、关联数组

    数组 定义数组 获取数组 关联数组 定义关联数组 获取关联数组

  • 学习Java第五天

    数组是多个数据的集合 数组的语法 数组元素类型【】 数组名; 多维数组: 数组元素类型【】【】 数组名; 多维数组...

  • php基础精粹

    PHP php数组 php数组之索引数组初始化 PHP数组之索引数组赋值 PHP数组之访问索引数组内容 PHP数组...

  • C语言的惯用集

    数组部分 数组部分 清空数组a 把数据读进数组a 对数组a求和

网友评论

      本文标题:数组

      本文链接:https://www.haomeiwen.com/subject/cfnlgqtx.html