红谷滩园林建设集团网站,济南房产信息网站官网,网搜网,运动分类的网站设计论文2.1 数组
#xff08;1) 概述
定义
在计算机科学中#xff0c;数组是由一组元素#xff08;值或变量#xff09;组成的数据结构#xff0c;每个元素有至少一个索引或键来标识
因为数组内的元素是连续存储的#xff0c;所以数组中元素的地址#xff0c;可以通过其索引…2.1 数组
1) 概述
定义
在计算机科学中数组是由一组元素值或变量组成的数据结构每个元素有至少一个索引或键来标识
因为数组内的元素是连续存储的所以数组中元素的地址可以通过其索引计算出来例如
int[] array {1,2,3,4,5}知道了数组的数据起始地址 B a s e A d d r e s s BaseAddress BaseAddress就可以由公式 B a s e A d d r e s s i ∗ s i z e BaseAddress i * size BaseAddressi∗size 计算出索引 i i i 元素的地址 i i i 即索引在 Java、C 等语言都是从 0 开始 s i z e size size 是每个元素占用字节例如 i n t int int 占 4 4 4 d o u b l e double double 占 8 8 8
小测试
byte[] array {1,2,3,4,5}已知 array 的数据的起始地址是 0x7138f94c8那么元素 3 的地址是什么 答0x7138f94c8 2 * 1 0x7138f94ca 空间占用
Java 中数组结构为
8 字节 markword4 字节 class 指针压缩 class 指针的情况4 字节 数组大小决定了数组最大容量是 2 32 2^{32} 232数组元素 对齐字节java 中所有对象大小都是 8 字节的整数倍[^12]不足的要用对齐字节补足
例如
int[] array {1, 2, 3, 4, 5};的大小为 40 个字节组成如下
8 4 4 5*4 4(alignment)随机访问性能
即根据索引查找元素时间复杂度是 O ( 1 ) O(1) O(1)
2) 动态数组
java 版本
public class DynamicArray implements IterableInteger {private int size 0; // 逻辑大小private int capacity 8; // 容量private int[] array {};/*** 向最后位置 [size] 添加元素** param element 待添加元素*///在数组末尾添加元素public void addLast(int element) {add(size, element);}/*** 向 [0 .. size] 位置添加元素** param index 索引位置* param element 待添加元素*///在指定位置index添加元素public void add(int index, int element) {checkAndGrow();// 添加逻辑if (index 0 index size) {// 向后挪动, 空出待插入位置System.arraycopy(array, index,array, index 1, size - index);}array[index] element;size;}
//如果容量为0则创建一个初始容量为8的数组如果大小超过容量则进行容量的1.5倍扩容private void checkAndGrow() {// 容量检查if (size 0) {array new int[capacity];} else if (size capacity) {// 进行扩容, 1.5 1.618 2//移位运算符1即除以2然后再加上之前的容量即为1.5倍扩容capacity capacity 1;int[] newArray new int[capacity];//扩容逻辑先复制原本的数组里面的元素再创建一个新的数组容量为原数组的1.5倍//然后把复制的元素复制到新数组里面之后再进行元素的添加System.arraycopy(array, 0,newArray, 0, size);array newArray;}}/*** 从 [0 .. size) 范围删除元素** param index 索引位置* return 被删除元素*/public int remove(int index) { // [0..size)int removed array[index];//删除逻辑指定删除元素的索引1开始的元素以及后面的所有元素复制一遍把指定元素移除后//再将复制的元素放进来也就是后面的元素往前面移动一位if (index size - 1) {// 向前挪动System.arraycopy(array, index 1,array, index, size - index - 1);}size--;return removed;}/*** 查询元素** param index 索引位置, 在 [0..size) 区间内* return 该索引位置的元素*/public int get(int index) {//直接返回查询元素的索引return array[index];}/*** 遍历方法1** param consumer 遍历要执行的操作, 入参: 每个元素*///调用java的Consumer接口然后是包装的泛型整型public void foreach(ConsumerInteger consumer) {for (int i 0; i size; i) {// 提供 array[i]// 返回 voidconsumer.accept(array[i]);}}/*** 遍历方法2 - 迭代器遍历*/Override//调用java的迭代器遍历public IteratorInteger iterator() {return new IteratorInteger() {int i 0;Overridepublic boolean hasNext() { // 有没有下一个元素return i size;}Overridepublic Integer next() { // 返回当前元素,并移动到下一个元素return array[i];}};}/*** 遍历方法3 - stream 遍历** return stream 流*///调用java的stream流遍历public IntStream stream() {return IntStream.of(Arrays.copyOfRange(array, 0, size));}
}这些方法实现都简化了 index 的有效性判断假设输入的 index 都是合法的
测试代码时养成用断言assert去判断而不是将其打印出来
插入或删除性能
头部位置时间复杂度是 O ( n ) O(n) O(n)
中间位置时间复杂度是 O ( n ) O(n) O(n)
尾部位置时间复杂度是 O ( 1 ) O(1) O(1)均摊来说
