数据结构与算法笔记-数据结构-数组

原创
2020/09/11 14:13
阅读数 100

[TOC]

数据结构与算法笔记-数据结构-数组

数组(array)

数组代码-gitee

数组代码-github

关键词

  • 数组是线性表
  • 数组是连续的内存空间和相同类型的数据
  • 基本上所有语言都会有数组这种数据类型
  • 数组不光是编程语言中的数据类型,还是一种数据结构
  • 数组本身在定义的时候需要预先指定大小,需要分配连续的内存空间.
  • 如果申请了大小为 10 的数组,当第 11 个数据需要存储到数组中时,就要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入.此之谓动态扩容
  • 数组的插入和删除比较低效,但是数组支持随机访问,根据下标随机访问的时间复杂度为 O(1).
  • 数组插入和删除的最佳时间复杂度时O(1),最差时间复杂度时O(n),平均时间复杂度是(1+2+3...n)/n=O(n).

什么是数组

数组(array),是一种线性表数据结构. 用一组连续的内存空间,来存储一组具有相同类型的数据

线性表

线性表就是将数据排成一条线一样的数据结构,每个线性表上的数据最多只有两个方向.

除了数组,链表,队列,栈,等也是线性表结构

而与线性表相对立的时非线性表,比如: 二叉树,堆,图,等. 之所以成为非线性,是因为在非线性表中数据之间并不是简单的前后关系.

线性表图例

img

非线性表图例

img

连续的内存空间和相同类型的数据

有了这两个限制,数组实现了一个撒手锏特性:随机访问

但是,这两个限制也导致数组很多操作非常低效,比如: 删除和插入数据, 为了保证连续性,需要对数组进行大量的搬运工作.

数组根据下标随机访问数组元素的

举例:

​ 一个长度为10的int型数组, int[] a= new int[10]

​ 如下图,计算机为数组a[10]分配了一块连续的内存空间1000-1039,其中内存块的首地址为base_address = 1000.

img

计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据.

当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素,存储的内存地址:

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).

低效的插入和删除

数组为了保持内存数据的连续性,会导致插入和删除比较低效.

插入

举例:

  1. 假设数组长度为n,如果我们将一个数据插入到数组中的第 k 个位置.
  2. 为了将第k个位置让出来,需要将k~n的元素全部按照顺序向后挪一位.

分析这个流程的时间复杂度:

  1. 如果在数组末尾插入,就不必挪任何元素.此时时间复杂度也就是最佳复杂度为O(1)
  2. 如果在数组开头插入,所有数据都要向后挪一位,此时时间复杂度也就是最坏复杂度为O(n)
  3. 而在每个位置插入元素的概率是一样的,所以平均时间复杂度为(1+2+3...n)/n=O(n)

注意,乱序数组的插入操作

如果数据是有序的,想要插入数据到第k个位置,只要按照刚才说的,直接将k之后的数据搬运一位即可.

但是如果数组是无序的,没有任何规律,数组只是被当做存储数据的集合,此时如果想要在第k个位置插入数据,

为了避免大量的数据搬移,有一个简单的方法,直接将第k个元素挪到最后,然后将新的元素插入到第k个位置

举例:

假设数组a[10]中存储了5个元素:a,b,c,d,e.

现在我们将元素x插入到第三个位置,只需要:

  1. 将c放入到a[5]
  2. 将a[2]赋值为x即可
  3. 最后数组中的元素: a,b,x,d,ec

这个技巧在特定情况下,第k个位置插入一个元素的时间复杂度就会降为O(1).(快排也有这个思想)

如图:

img

删除

删除和插入类似

  1. 如果要删除第k个位置的元素,为了内存的连续性,也需要搬运数据,否则中奖会出现空洞,内存就不连续了.
  2. 如果删除数组末尾的数据,则为最佳时间复杂度是O(1).
  3. 如果删除开头的数据,则为最坏时间复杂度是O(n).
  4. 平均时间复杂度也是O(n).

在某些特殊场景下,并非一定要追求数组中数据的连续性,如果将多次删除集中在一起操作,删除的效率会提升不少.

例子:

数组a[10]中存储了8个元素: a,b,c,d,e,f,g,h. 现在要逐个删除a,b,c.三个元素

  1. 为了避免d,e,f,g,h.这几个元素被搬运三次,可以先记录下已删除的数据.

  2. 每次的删除操作并非是真正的搬移数据,只是记录一下数据被删除,需要搬运.

  3. 当数组中已经没有更多空间存储数据时,再触发执行一次真正的删除动作,可以大大减少删除导致的数据搬移操作

据称,"就是 JVM 标记清除垃圾回收算法的核心思想";

img

警惕数组的访问越界

代码分析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时就指定数据的大小.

什么时候用数组:

  1. 如果关注性能或者想用基础类型
  2. 事先已知晓数据大小并对数据的操作比较简单

业务开发直接上容器,省时省力.

底层开发,比如网络框架,性能优化要做大极致,显然要用数组.

数组编号为什么从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).

平时开发中,可以直接用编程语言提供的容器,如果是底层开发直接用数组更合适.

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部