美文网首页数据结构和算法分析极客时间:数据结构与算法之美笔记
数组:为什么很多编程语言中数组都从0开始编号?

数组:为什么很多编程语言中数组都从0开始编号?

作者: 红酥手黄藤酒丶 | 来源:发表于2018-12-22 18:36 被阅读1次

    数组:为什么很多编程语言中数组都从0开始编号?

    1. 数组的定义

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

    2. 什么是 线性表

    线性表就是数据排成像一条线一样的结构。每个线性表的数据最多只有前和后两个方向。
    数组、链表、队列、栈等都是线性表结构。

    image

    3. 什么是 非线性表

    在非线性表中,数据不是简单的前后关系。
    二叉树、堆、图等都是非线性表。


    image

    4. 什么叫是 连续的内存空间

    数组中每个元素的存储地址都是相邻的。


    image

    因为数组是在一段连续的内存空间,存储相同类型的数据,使得数组具有一个非常nb的特性:随机访问。

    5. 什么是 随机访问

    只要给我 下标 我就能直接根据索引获得元素值。
    计算机会给每个内存单元分配一个地址,计算机通过地址访问内存中的数据。当计算机需要访问数组中的某个元素时,会先通过下面的寻址公式计算出该元素存储的内存地址:


    image

    这样主要有了下标,就可以直接访问到该元素,因为数组支持 随机访问,才使得 数组适合查找
    数组查找的时间复杂度要根据所使用的算法来计算。

    • 正常的 for 循环直接判断是否相等来查找,那么复杂度就为:○(n)
    • 对一个已经排好序的数组,使用二分查找,那么复杂度就为:○(㏒n)
    • 还有一种表述方式:数组根据下标随机访问的时间复杂度为 ○(1)

    注:访问和查找是两回事,访问只是取出值就可以了,查找是要判断有没有,在哪里。

    6. 低效的 插入删除

    数组为了保持内存数据的连续性(就是元素要一个挨着一个,无间隙),会导致 插入删除 这两个操作比较低效。

    为什么?

    image image

    7. 如何优化呢?

    优化插入

    image

    优化删除

    为了避免在插入或删除时,数据被多次迁移(插入一个,就迁移一堆),我们可以先记录下要删除的数据(每次执行删除时,并没有真正的删除数据,而是给数据一个状态,记录标识其不可用,属于已删除状态)。当数组没有更多空间存储数据时,再一次性触发真正的删除操作,此举可大大减少删除操作导致的数据迁移。

    8. 数组的越界问题

    分析下面这段 c 语言代码的运行结果:

    int main(int argc, char* argv[]){
        int i = 0;
        int arr[3] = {0};
        for(; i<=3; i++){
            arr[i] = 0;
            printf("hello world\n");
        }
        return 0;
    }
    

    我还没有好好系统的学习过 c ,所以对上段代码不是很了解,不过在看懂下面文字后也明白了大致意思:在 c 语言中,对数组越界的界定与处理是交给程序员来做的。

    image

    9. 容器能否完全代替数组

    对于 Java 程序员经常用到的 ArrayList 来说,其最大的优势就是 可以将很多数组操作的细节封装起来。 例如数组的插入、删除时的迁移过程。而且,ArrayList 还支持动态扩容。

    如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定数据大小,这样可以省去很多次 内存申请数据迁移 的过程。

    那么合适时候数组会好一些呢?

    1. 因为 ArrayList 无法存储基本数据类型,只能存储包装类型,此时就涉及到 自动装箱/拆箱 的过程,如果特别关注性能,或者想使用基本数据类型,此时可以使用数组。
    2. 如果数据大小事先已知,并且对数据的操作非常简单,可以直接使用数组。
    3. 一般情况下,在处理多维数据时,使用多维数组会比 ArrayList<ArrayList> 更直观。

    对于业务开发而言,直接使用容器就够了,完全不会影响系统的性能。

    10. 为什么很多编程语言中数组都从0开始编号?

    根据第 4、5 小节的示例,如果用 a 来表示数组的首地址,那么 a[0] 就是偏移为 0 的位置,也就是首地址,a[k] 就表示偏移 k 个 type_size 的位置:

    a[k]_address = base_address + k * type_size
    

    但是如果数组从 1 开始计算,我们计算元素 a[k] 的内存地址就会变为:

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

    相关文章

      网友评论

        本文标题:数组:为什么很多编程语言中数组都从0开始编号?

        本文链接:https://www.haomeiwen.com/subject/udhwkqtx.html