数组索引为何从0开始

本文最后更新于：2019年11月28日 晚上

在大部分编程语言中，为什么数组都是从 0 开始编号，而不是从1开始呢？

  • 因为，从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要：
  • 但是，如果数组从 1 开始计数，数组元素 a[k] 的内存地址就会变为：
  • 显然，从0开始计数，不需要减法运算，更高效一些。
  • 但最可能可能还是历史原因吧。C语言起始，JAVA等语言模仿；但有些语言数组并不是从0开始计数的，比如Matlab，甚至还有一些语言支持负数下标（从后往前数），比如Python

什么是数组

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

  • 线性表（Linear List）：数据排成像一条线一样的结构，每个线性表上的数据最多只有前后两个方向。（非线性表中并不是简单的前后关系）

  • 连续的内存空间和相同类型的数据：使数组支持随机访问，但也使插入和删除非常低效（需要进行大量的数据迁移）。假设计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。当计算机需要随机访问某个元素时，可以通过获得下列公式计算得到该元素的存储地址：

    说“数组适合查找，查找时间复杂度为$O(1)$“是不准确的，只有数组按下标进行随机访问时，时间复杂度才是$O(1)$；否则，已排好序，二分法查找时，时间复杂度为$O(n)$

插入和删除

  • 如果要将某个元素插入到数组的第 k 个位置，为了避免大规模的数据搬移，一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。（类比快速排序）
  • 将多次删除操作集中在一起运行时，可以提高执行效率
    • 比如数组 a[10] 中存储了 8 个元素：a，b，c，d，e，f，g，h，我们需要依次删除 a，b，c 三个元素删除，为了避免d，e，f，g，h被多次搬移，可以先将数据标记为已删除数据，当数组没有更多空间存储数据时，再统一执行一次真正的删除操作（类比垃圾桶）。
    • 教程中提到了JAVA的JVM，暂时没了解过。

数组越界问题

有的语言会自己进行数组越界检查，有的不会，也和编译器有一定关系。比如下面这段C代码，由于a[3]访问越界，其会被定位到某块不属于数组的内存地址上，即变量i的内存地址。那么a[3]=0, i=0,代码无限循环输出“hello world”

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