【Algo】数组 Array
Backto Algo Index
定义
数组Array
是一种线性表存储结构,它用一组连续的内存空间来存储一组具有相同类型的数据。
-
线性表(Linear List)
:内存是连续地址一条生产线,线性表就是上面一个坑一个坑的放数据,所有的元素最多有前
和后
两个方向。常见的线性表结构有 array,list,stack,queue 等。常用的非线性表,有 tree 和 graph 等 - 连续内存空间存储。这个是 array 最重要的特点,也就是说n个元素的array中的数据是依次在 0号坑,1号坑,。。。,n-1 号坑存储的。这决定了array 的最重要特性:依下标随机访问。当然随之而来的还有限制,为保证连续性,insert 和 delete 就要做大量的数据搬移工作。
- 相同的数据类型。保证统一性。
数据的存储与访问
我一个指令,
int a[] = new int[10];
计算机为我分配空间
寻址公式
也就是 , 也就是图中的地址 1000
.
对于二维数组,比如图像,行存储形式, 按下标访问第行列就是
常用操作的时间复杂度分析
-
Access
: 支持依下标的随机访问,复杂度 ,完美 -
Search
: best - , worst - , average - -
Insertion
: best - , worst - , average - -
Deletion
: best - , worst - , average -
优化思路
语言实现和特点
- C :原生数组
- C++ : 原生数组 + STL封装 vector
- Java : 原生数组 + 高级封装 ArrayList
- Python : 没有数组,有 List,Tuple, Dictionary 等,支持负数下标
- Matlab :特立独行 ,数组下标从 1 开始, 多维数组列存储
最佳实践 Best Practice
- 超级注重性能的,比如图像开发,网络服务器等,或业务逻辑超级简单的,数据类型固定,操作简单固定,用原生数组。其他一般的业务逻辑用高级封装容器实现。
- 即使用高级容器封装,也应该尽量给出更多的底层信息。比如如果事先知道数据规模的,就要给定容器的容量。