数据结构 - > 数组篇
一）、数组的特点
特点：是一种线性表结构，具有连续的存储空间，存储相同的数据类型数据。
特点剖析：
线性表：数据之间具有前后顺序关系。
例如：1).数组、链表、队列、栈数据之间都具有前后关系。
2).非线性表，数据之间没有前后关系，例如: 树、图
连续的存储空间：数组具有连续的存储空间，根据寻址公式，实现数组元素的随机
访问。
存储相同的数据类型：声明一个数据时需要声明存储的数据类型，这样才能根据寻
址公式，实现数组的随机访问。
二）、数组的随机访问公式
a[i]_address = base_address + i * data_type_size;
1).base_address： 数组的首地址a[0];
2).data_type_size：数据类型的大小， 例：int类型，4个字节，data_type_size = 4.
3). i：数组的下标。
三）、为什么数组的下标是从0开始访问？
由数组的寻址公式 a[i]_address = base_address + i * data_type_size可知 i 代表偏移量，a[0]代表偏移量为0的位置，即首地址位置，当数组的下标是从1开始访问呢，则寻址公式就为 a[i]_address = base_address + (i -1) * data_type_size,此时计算机就要多做一次减法运算，为了优化计算效率，对数组从0开始编号。
四）、数组和链表的区别
1).链表适用于删除和插入，时间复杂度为O(1).
2).数组适用于随机访问，时间复杂度为O(1).
注： 数组适用用查找，时间复杂度为O(1)的说法是错的，数组进行查找的时间复杂度为O(n), 有顺序的二分查找，时间复杂度为O(logn).
五）、对数组的操作
1）、数组的插入
1.1).插入一个元素，数组的相对位置保持不变超，时间复杂度O(n)。
public T[] insertElement(T[] arr, int index, T e){
int size = arr.length;
//数组元素后移
for(int i = size - 1; i >= index; i--){
//数组后移
arr[i+1] = arr[i];
}
arr[index] = e;
//返回插入的值
return arr;
}
1.2).不需要保持数组元素的相对位置，时间复杂度O(1)。
/**
* @Author chenxuebing
* @Description 插入元素时如果不考虑元素的有序性，假如要在第K个元素进行插入，直接将第k个元素移到末尾，在第k个位置插入元素
* 针对引用型数据类型
* @Date 2019/12/25 14:18
* @Param [arr, index]
* @return
**/
public T[] insertElementUnOrder(T[] arr, int index, T e){
//直接在数组的末尾插入元素，时间复杂度O(1)
int flag = 0;
for(int i = 0; i < arr.length; i++){
flag++;
if(arr[i] == null){
break;
}
}
arr[flag] = arr[index];
arr[index] = e;
return arr;
}
2、数组的删除操作
2.1）.删除指定位置的元素，保持元素的相对位置,时间复杂度O(n)
/**
* @Author chenxuebing
* @Description 删除指定位置的元素
* @Date 2019/12/25 11:39
* @Param [arr, Index]
* @return
**/
public T deleteElement(T[] arr, int index){
//数组元素前移
int size = arr.length;
for(int i = index; i < size-1; i++){
arr[i] = arr[i+1];
}
return arr[index];
}
2.2). 删除指定位置的元素，不需要保持元素的相对位置,时间复杂度O(1)
技术要点：使用标记删除的做法，对要删除的元素不做删除操作，只进行标记，当数组的元素满的时候再进行操作，减少了数据的多次移动的操作。
/**
* @Author chenxuebing
* @Description 使用标记的方法删除数组的元素，即对指定位置的元素做标记删除操作，待数组的元素满了之后再进行删除操作
* 这样做的好处：对多次删除元素的移动缩减为一次移动
* @Date 2019/12/25 15:07
* @Param [arr, index]
* @return
**/
public T[] deleteElementFlag(T[] arr, int index){
return null;
}