[TOC]
数据结构与算法笔记-数据结构-数组
数组(array)
关键词
- 数组是线性表
- 数组是连续的内存空间和相同类型的数据
- 基本上所有语言都会有数组这种数据类型
- 数组不光是编程语言中的数据类型,还是一种数据结构
- 数组本身在定义的时候需要预先指定大小,需要分配连续的内存空间.
- 如果申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,就要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入.此之谓动态扩容
- 数组的插入和删除比较低效,但是数组支持随机访问,根据下标随机访问的时间复杂度为
O(1). - 数组插入和删除的最佳时间复杂度时
O(1),最差时间复杂度时O(n),平均时间复杂度是(1+2+3...n)/n=O(n).
什么是数组
数组(array),是一种线性表数据结构. 用一组连续的内存空间,来存储一组具有相同类型的数据
线性表
线性表就是将数据排成一条线一样的数据结构,每个线性表上的数据最多只有两个方向.
除了数组,链表,队列,栈,等也是线性表结构
而与线性表相对立的时非线性表,比如: 二叉树,堆,图,等. 之所以成为非线性,是因为在非线性表中数据之间并不是简单的前后关系.
线性表图例
非线性表图例
连续的内存空间和相同类型的数据
有了这两个限制,数组实现了一个撒手锏特性:随机访问
但是,这两个限制也导致数组很多操作非常低效,比如: 删除和插入数据, 为了保证连续性,需要对数组进行大量的搬运工作.
数组根据下标随机访问数组元素的
举例:
一个长度为10的int型数组, int[] a= new int[10]
如下图,计算机为数组a[10]分配了一块连续的内存空间1000-1039,其中内存块的首地址为base_address = 1000.
计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据.
当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素,存储的内存地址:
a[i]_address = base_address + i * data_type_size
- data_type_size 表示数组中每个元素的大小
- 数组中存储的是 int 类型数据,所以 data_type_size 就为 4 个字节
数组和链表的区别
很多人会说: 链表适合插入,删除,时间复杂度 O(1).数组适合查找,查找时间复杂度为 O(1).
数组是适合查找操作,但查找的时间复杂度并不是 O(1).
即便是排好序的数组,使用二分查找,时间复杂度也是 O(logn).
所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1).
低效的插入和删除
数组为了保持内存数据的连续性,会导致插入和删除比较低效.
插入
举例:
- 假设数组长度为n,如果我们将一个数据插入到数组中的第 k 个位置.
- 为了将第k个位置让出来,需要将k~n的元素全部按照顺序向后挪一位.
分析这个流程的时间复杂度:
- 如果在数组末尾插入,就不必挪任何元素.此时时间复杂度也就是最佳复杂度为
O(1) - 如果在数组开头插入,所有数据都要向后挪一位,此时时间复杂度也就是最坏复杂度为
O(n) - 而在每个位置插入元素的概率是一样的,所以平均时间复杂度为
(1+2+3...n)/n=O(n)
注意,乱序数组的插入操作
如果数据是有序的,想要插入数据到第k个位置,只要按照刚才说的,直接将k之后的数据搬运一位即可.
但是如果数组是无序的,没有任何规律,数组只是被当做存储数据的集合,此时如果想要在第k个位置插入数据,
为了避免大量的数据搬移,有一个简单的方法,直接将第k个元素挪到最后,然后将新的元素插入到第k个位置
举例:
假设数组a[10]中存储了5个元素:a,b,c,d,e.
现在我们将元素x插入到第三个位置,只需要:
- 将c放入到a[5]
- 将a[2]赋值为x即可
- 最后数组中的元素: a,b,x,d,ec
这个技巧在特定情况下,第k个位置插入一个元素的时间复杂度就会降为O(1).(快排也有这个思想)
如图:
删除
删除和插入类似
- 如果要删除第k个位置的元素,为了内存的连续性,也需要搬运数据,否则中奖会出现空洞,内存就不连续了.
- 如果删除数组末尾的数据,则为最佳时间复杂度是
O(1). - 如果删除开头的数据,则为最坏时间复杂度是
O(n). - 平均时间复杂度也是O(n).
在某些特殊场景下,并非一定要追求数组中数据的连续性,如果将多次删除集中在一起操作,删除的效率会提升不少.
例子:
数组a[10]中存储了8个元素: a,b,c,d,e,f,g,h. 现在要逐个删除a,b,c.三个元素
-
为了避免d,e,f,g,h.这几个元素被搬运三次,可以先记录下已删除的数据.
-
每次的删除操作并非是真正的搬移数据,只是记录一下数据被删除,需要搬运.
-
当数组中已经没有更多空间存储数据时,再触发执行一次真正的删除动作,可以大大减少删除导致的数据搬移操作
据称,"就是 JVM 标记清除垃圾回收算法的核心思想";
警惕数组的访问越界
代码分析3-1:
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){//但是很显然会遍历0,1,2,3,四次,第四次导致数组越界,C语言中,这里会成为死循环
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
上面的代码,并非是打印三次,而是会陷入到死循环中.
因为数组的大小虽然为3个元素,但是for循环时书写错误了.
导致 for 循环的结束条件错写为了 i<=3 而非 i<3,所以当i=3时,数组a[3]访问越界.
在C语言中,非受限内存之外的所有内存空间都是可以自由访问的,
根据前面讲的数组寻址公式,a[3]也会被定位到某块不属于数组的内存地址上,
而这个地址正好是用来存储遍历i的内存地址,那么a[3]=0就相当于i=0,所以代码无限循环.
数组越界在C语言中是一种未决行为,C语言没有规定数组访问越界时编译器该如何处理.
因为,访问数组本身就是在访问一段连续的内存,只要数组通过偏移计算得到的内存是可用的,程序就不会报错.
这就会导致程序出现莫名其妙的逻辑问题,而且很难debug.
很多病毒正是利用了数组越界可用访问非法地址的漏洞来共计系统,所以写代码时一定要特别注意这一块
不过并不是所有语言都像C语言一样,把数组检查越界的工作丢给程序员,比如PHP和Java等语言本身就会做越界检查.
容器能否完全替代数组
什么时候用数组,什么时候用容器?
很多语言都提供了容器类,比如: 比如 Java 中的ArrayList,C++ STL中的vector.
据称Java的ArrayList可以将很多数组操作的细节封装起来,比如上面说的,插入,删除时需要搬运其他数据,而且ArrayList支持动态扩容.
使用ArrayList完全不用关心底层的扩容逻辑,每次空间不足,都会自动扩容1.5倍.
因为扩容要设计到数据搬运和申请,有点费时,最好在创建ArrayList时就指定数据的大小.
什么时候用数组:
- 如果关注性能或者想用基础类型
- 事先已知晓数据大小并对数据的操作比较简单
业务开发直接上容器,省时省力.
底层开发,比如网络框架,性能优化要做大极致,显然要用数组.
数组编号为什么从0开始
数组编号为什么从0开始而不是从1开始,毕竟1更符合人类的习惯
从数组存储的模型上看,下标应该叫做偏移量(offset),如果用a表示数组的首地址,a[0]就是便宜量为0的位置,也就是首地址.
a[k]表示偏移k个type_size的位置,所以a[k]的内存地址公式为:
a[k]_address = base_address + k * type_size
但是如果编号从1开始,公式就编程了这样:
a[k]_address = base_address + (k-1)*type_size
也就是说,如果从1开始,每次访问数组元素就多了一次减法运算,CPU也就多了一次减法指令.
数组作为非常基础的数据结构,通过下标访问更是非常的普遍操作,效率的优化就要做大极致.
为了减少一次减法运算,所以下标就从0开始了,而不是从1开始.
其实更多的可能是历史问题,因为C用0开始做下标,之后的JAVA什么的也都用了0.
不过并非所有语言的下标都是从0开始,比如Matlab.而Python更是支持了负数下标.
小结
数组是最基础最简单的数据结构.
数组用连续的内存空间来存储相同类型的一组数据,最大的特点就是支持随机访问.
但是插入和删除操作变得比较低效,平均情况时间复杂度为O(n).
平时开发中,可以直接用编程语言提供的容器,如果是底层开发直接用数组更合适.
