数组Array 是一个线性表数据结构，它用一组连续的内存空间来存储相同类型的元素。
上述就是数组最重要的定义，理解这句话基本就理解了数组。
下面详述其特点
线性表
线性表中的数据最多有两个方向 前和后。
常见的线性表有 数组 链表 队列 栈等等
非线性表
树 图 这种并非只有简单的前后关系
连续的内存空间存储相同的数据
这个一特点实现了数组的下标访问
int a[10]
数组内存地址.jpg
寻址公式为 a[i] = 初始地址 + i * 数据类型大小
a[6] = 1000 + 6 * 4
a[6] = 1024
数组的相关操作
插入
k：插入的位置
有序 ：如果k位置有元素 则要将包括k位置元素后的所有元素依次搬移一个位置 时间复杂度为O(n)
无序：将k位置元素放到数组元素的最后 将k位置元素赋值为插入元素 时间复杂度为O(1)
删除
k：删除的位置
有序：与插入相同，如果k位置元素被删除k之后的所有数据都需要搬移 时间复杂度为O(n)
在删除时可以对删除元素标记为已删除，当已删除元素达到阈值统一删除，可避免频繁的搬移元素
无序：删除k元素后将数组中最后的元素填充到k位置 时间复杂度O(n)
查找
有序：使用二分查找 O(logn)
无序：顺序遍历O(n)
网友评论