2021不良正能量免费网站,简单个人网页制作,网站设计资料,北票网站建设优质博文#xff1a;IT-BLOG-CN 一、简介
数组Array是一种线性表数据结构#xff0c;它用一组连续的内存空间#xff0c;存储一组具有相同类型的数据。 数组因具有连续的内存空间的特点#xff0c;数据拥有非常高效率的“随机访问”#xff0c;时间复杂度为O(1)。但因要保… 优质博文IT-BLOG-CN 一、简介
数组Array是一种线性表数据结构它用一组连续的内存空间存储一组具有相同类型的数据。 数组因具有连续的内存空间的特点数据拥有非常高效率的“随机访问”时间复杂度为O(1)。但因要保持这个连续的内存空间导致数组在删除或插入操作的时非常低效。因为数组为了保持连续性必然会涉及大量数据的迁移这个是非常消耗时间的平均时间复杂度为O(N)。
二、数组的随机访问
数组的随机访问是有个寻址公式的上问中我们提到过数组是用一组连续的内存空间存储数据元素的然而每个内存单元都有自己的地址(在计算机里面就是通过这个地址访问数据的)又加上每个内存单元的大小都是一样的这样就很容易得到一个公式了如下所示
a[i]_address base_address i * data_type_size
我们来简单解释一下上述公式其中data_type_size表示数组中每个元素的大小base_address表示内存块的首地址i表示数组下标。
三、数组的基本操作
【1】创建数组
public class MyArray { private int[] array; // 数组大小 private int size; public MyArray(int capacity) { this.size 0; this.array new int[capacity]; }
}【2】读取元素 我们知道数组在内存中是连续存储的所以根据上文的寻址公式可以知道我们可以根据数组下标i快速定位到对应的元素。
int[] array{1,2,3,4,5,6};
System.out.println(array[1]); // 输出的是2 因为数组的下标是从0开始的。【3】更新元素 我们可以根据数组下标快速查找到对应元素。那么同样道理我们可以根据数组下标i快速更新元素这中间涉及两个过程首先就是找到数组下标i对应的数据元素A然后将新的数据元素B赋值给A即完成更新。
int[] array{1,2,3,4,5,6};
System.out.println(array[1]); // 输出的是2
//更新数组下标为 1 的数组元素
array[1]7;
System.out.println(array[1]); // 输出的是7【3】插入元素相比读取、更新操作插入元素稍微复杂一些分为以下两种情况
尾部插入 首先我们看看尾部插入这种情况很简单在数组的最后新增一个新的元素此时对于原数组来说没有任何影响时间复杂度为0(1)。如下图所示 中间插入 如果在数组的中间位置插入元素的话此时会对插入元素位置之后的元素产生影响也就是这些数据需要向后依次挪动一个位置。如下图所示 /** * 插入元素* param index 待插入的位置 * param element 待插入的元素 */
public void insert(int index, int element){ if(index 0 || index size) { throw new IndexOutOfBoundsException(超过数组容量 ! 插入失败); } // 从左到右将元素向右移动一位 for (int i size-1; i index; i--) {array[i1] array[i];} // 此时index这个位置已经腾空了可以放进入element array[index]element; //数组中元素个数1 size;
}【4】删除元素 删除元素和插入元素类似如果我们删除第k个位置的数据为了内存的连续性同样会涉及数据的挪动。如下图所示 /** * 根据数组下标删除元素* param index 数组下标 * return */
public int delete(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(已经超过数组容量 ! 插入失败); } int deleteElement array[index]; // 从左到右将元素向左移动一位 for (int i index; i size - 1; i) { array[i] array[i 1]; } size--; return deleteElement;
}四、数组扩容
因为数组的长度在创建的时候已经确定了当插入元素的时候如果数组已经满了是没办法插入成功的。这个时候就要考虑数组扩容的问题了那么该如何实现扩容呢?
其实我们可以这样比如此时的数组是A, A已经满了我们再创建一个数组B且数组长度是A的2倍然后我们将数组A的元素全部放到数组B中这样就完成了数组扩容了。
/** 数组扩容为原数组的二倍 **/
public void resize(){ int[] newArray new int[array.length * 2]; System.arraycopy(array, 0, newArray, 0, array.length); // 把从索引0第一个0开始的array.length个数字复制到索引为0第二个0的位置上 array newArray;
}
