DSA_03：数组

数组，相信大家再熟悉不过。

 

这里还是对其进行简单总结，最重要的是，给出一维数组、多维数组的内存模型和寻址公式，这是很多新手甚至有一定基础的同学任然搞不懂的地方。

　　1. 数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

　　2. 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

　　3. 非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系

　　4. 连续的内存空间和相同类型的数据：正是因为这两个限制，数组才有了一个堪称“杀手锏”的特性：随机访问

　　5. 说：数组适合查找，查找时间复杂度为o(1)，这句话准确吗？

　　　　答：有序数组用二分法查找复杂度是 o(logn)，因此自然这句话并不准确。应该说：数组支持随机访问，根据下标随机访问的时间复杂度为o(1)

 

一维数组内存模型和寻址公式：

　　有一个 int arr[7] 的数组，其内存模型如图：

　　　　　　

　　a[n] 寻址公式：a[i]_address = base_address + i * data_type_size，其中 base_address 是数组第一个元素所在地址。

 

二维数组内存模型和寻址公式：

　　这对于很多人来说，是一直没弄懂的，相信看完该图能够让你足够清晰。

　　int arr[3][3] 的内存模型为：

　　　　　　

　　ok，有了内存模型，不妨自己推导一下二维数组的寻址公式再继续往下看。

　　a[m][n] 寻址公式：a[i][j]_address = base_address + (i * n + j) * data_type_size，其中 base_address 是数组第一个元素所在地址。

　　data_type_size 代表数据类型所占字节

 

需要注意，数组的查找和删除，为了保证数据的连续性，需要将后面的元素整体搬移。

数组 插入、删除、查找 的性能就不再啰嗦了，与链表的性能对比，应用场合等也不再过多说明。

 

最后，容器能否完全替代数组？

如 java 中的 arraylist，c++ 中的 vector 等，能否完全代替数组呢？

　　前者：最大的优势就是可以将很多数组操作的细节封装起来，支持动态扩容。

　　后者：数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。

　　对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发， 比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。