+
+
Posts List
  1. 随机访问
  2. 低效的「插入」和「删除」
    1. 插入
    2. 删除
  3. C语言中的数组访问越界
  4. 容器
  5. 为什么数组从0开始编号呢

数据结构与算法之美:数组

随机访问

随机访问是指数组在内存中按顺序存放,可以通过下标直接定位到某一个元素存放的位置。

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

有几个关键词:

  • 线性表

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

    与线性表相对立的概念是非线性表,比如二叉树、堆、图等,之所以叫非线性,是因为在非线性表中,数据之间并不是简单的前后关系。

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

    因为具有内存空间和相同类型的数据,数组才具有「随机访问」的特性,这也导致数组的很多操作变得非常低效,比如删除/插入元素时,就要做大量的数据搬移工作。
    计算机给数组分配一块连续内存空间,然后通过地址访问内存中的数据,寻址公式如下:

    1
    a[i]_address = base_address + i * data_type_size
> 数组和链表的区别在于:数组支持随机访问,根据下标随机访问的时间复杂度为$O(1)$,而链表适合插入和删除,进行插入和删除的时间复杂度为$O(1)$。

低效的「插入」和「删除」

插入

如果在数组的末尾插入元素,时间复杂度为$O(1)$;但如果在数组开头插入元素,那所有的数组都需要依次往后移动一位,时间复杂度为$O(n)$。平均情况时间复杂度为$\frac{(1+2+3+…+n)}{n}=O(n)$。

而元素的插入位置和我们的需求有关。比如,当要求数组有序时,就必须经过「搬移」。而如果数组是无序的,我们完全可以在数组的末尾「插入」,或者当需要在无序数组的特定位置插入元素时,可以通过「替换」的方式——将目标元素与原占位元素替换,原占位元素插入到数组的末尾。

删除

与插入数据类似,为了内存的连续性,删除操作也需要搬移数据。那么当我们需要多次删除时,就不免进行元素的重复搬移,删除的效率低。

举个例子,我们要删除[a, b, c, d, e, f, g, h]中的abc三个元素。

为了避免数据的重复搬移,我们可以先记录下已经删除的数据,每次的删除操作并不实际进行数据搬移,而是记录数据被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。这和JVM(Java Virtual Machine)的垃圾回收机制不谋而合。

C语言中的数组访问越界

1
2
3
4
5
6
7
8
9
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0}; //声明一个长度为3的数组,元素全部初始化为0
for(; i<=3; i++){ //发生越界
arr[i] = 0;
printf("hello world\n");
}
return 0;
}

因为for循环的结束条件错写为了i<=3,导致越界访问了a[3],上面代码的运行结果并非是打印三行hello world,而是无限打印hello world

在C语言中,只要不是访问受限的内存,所有的内存空间都是可以自由访问的,因此a[3]会被定位到某块不属于数组的内存地址上。而这个地址恰好是存储i的内存地址时(此例中,涉及压栈相关知识,iarr在相邻地址且i的地址比arr大,所以arr越界后访问到i),a[3]=0的执行效果就变成了i=0,因此导致代码死循环。数组越界在C语言中是一种未决行为,C语言本身并未规定越界时编译器该如何处理。因为访问数组的本质是访问一段连续内存地址,当偏移计算后得到的内存地址可用时,程序就不会报错。因此,数组越界常常会导致一些莫名其妙的逻辑错误。

这一块设计到我的知识盲区了,有关C语言的内存分配以及计算机原理。

大概了解了一下,high addresslow address指的是内存地址的大小,地址大为高,反之为小。此例中iarr都存储在栈中,而栈是从高位到低位增长的,故存储顺序为:i->arr[2]->arr[1]->arr[0],因此arr[3]恰好就是i的位置。

容器

针对数组类型,很多语言都提供了容器类,比如Java中的ArrayList。

ArrayList最大的优势就是将很多数组操作的细节封装起来,比如插入和删除等。另外,ArrayList还支持动态扩容,当存储空间不够时,它会将空间自动扩容为之前的1.5倍大。虽然很智能,但扩容操作设计内存申请和数据搬移,还是会损失时间的。所以在特别关注性能的情况下,还是选用数组吧。但对于业务开发,直接使用容器就足够了,省时省力。

为什么数组从0开始编号呢

从0编号的偏移计算公式:

1
a[k]_address = base_address + k * type_size

从1编号的偏移计算公式:

1
a[k]_address = base_address + (k-1)*type_size

对比两个公式,不难发现,后者比前者多了一次减法运算,对于CPU来说,每次随机访问数组元素就多了一次减法指令。

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_4/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay