数据结构与算法系列--数组精讲

比眉伴天荒 2022-02-23 03:34 228阅读 0赞

在每种编程语言中，基本都会有数组这种数据类型，它不仅仅是一种编程语言的数据类型，还是一种最基础的数据结构。尽管数组看起来非常基础，简单，但是我估计很多人并没有理解这个基础的数据结构的精髓。  
  
现在我以问题导向讲解数组的精髓。  
什么是数组？数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。（专业定义）  
关键词：线性表，连续，相同类型

## 1，如何实现随机访问？ ##

数组有随机访问的特性，这个结论怎么来的?定义里并没有说和体现啊。这里就要说**数组的本质**机制。

int a[] = {0,1,2,3,4};
    int i,length;
    length = sizeof(a) / sizeof(int);
    printf("int has %d bytes\n",sizeof(int));
    
    for(i=0;i<length;i++){
        printf("a[%d]: %d-------memory address: %d\n",i,*(a+i),(a+i));
    }

运行结果：  
![在这里插入图片描述][20190406130945428.png]  
从上面结果能得出怎样的猜想（因为数据少并不足支持结论）—— **a\[i\] = a\[0\] + i\*4**  
没错，这就是随机存取（访问）的秘密。每个数组元素都可以通过下标i 来直接访问，即实现随机访问。如何实现随机访问？通过上面的表达式，根据i 来计算a\[i\]的地址，并访问里面的值。类似根据学号找学生。

## 2，低效的“插入”和“删除” ##

数组为了保持数据连续性，导致插入，删除这两个操作比较低效。（数据结构各有优劣，这个道理贯穿整个学科）  
插入操作： 时间复杂度O（n）  
删除操作：时间复杂度O（n）

而对比链表O（1）比较低效。在数据结构里O（n）复杂度就教高了。因为有时候对n个元素操作，复杂度就成了O（n^2）。

不能提高其插入删除的效率吗? 》 为什么低效 》 为了保持数组的连续性，所以这样设计。  
在某些特殊场景下，我们并不一定非要追求数组的数据连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会高很多呢？  
如果你了解JVM，你会发现，这就是JVM标记清除垃圾回收算法的核心思想。

## 3，警惕数组的访问越界问题 ##

通过上述数组的本质讲解，我们知道，数组的访问越界一般不会报错，因为它只是访问到了数组之外的地址，并不是错误。C语言把数组越界检查的工作丢给了程序员来做，而Java本身就会做越界检查，所以会抛出数组越界的异常。  
所以在写循环时或者用到数组时要注意加上限制条件，i<array.length

## 4，数组为什么从0开始编号，而不从1呢？ ##

从上面的数组的本质可知，a\[k\] = a\[0\] + i\*4（从0开始）；a\[k\] = a\[0\] + （i-1）\*4（从1开始）  
对比两个公式可知，从1开始要多一次减法运算，对CPU多一次减法指令。而数组作为底层数据结构，性能要做到极致。当然也可能是历史原因。

## 5，容器能否完全替代数组？ ##

Java中的ArrayList等，在项目开发中，什么时候适合用数组，什么时候适合用容器？

容器ArrayList和数组相比，最大的优势是可以将很多数据操作的细节封装起来，还有支持动态扩容。而数组本身定义时候需要指定大小，增删改和动态扩容这些操作都需要程序员自己写，而且要处理一些逻辑问题。  
ArrayList的缺点：Java ArrayList 无法存储基本数据类型，比如int,long需要封装成类。而且性能会有消耗。

总结一下：对于业务开发，直接用容器就够了，省时省力。虽然损耗了一点性能，但不会有大的影响。但如果做一些非常底层的开发，性能要求极高，那么数组就是首选。

[20190406130945428.png]: /images/20220223/6b75d62c5f6047d78e6df7584975a372.png