在每一种编程语言中,基本都会有数组这种数据类型,不过它不仅仅存在于编程语言中,还是一种基础数据结构。
数组定义:
数组(Array)是一种线性表数据结构,它用一组连续的内存空间,储存一组具有相同类型的数据。
定义里面有几个关键点:线性表、连续内存空间、相同类型的数据
线性表
顾名思义,线性表就是数据排成像一条线一样的结构。线性表上的每条数据最多只有前和后两个方向,数组、链表、队列、栈等等都是线性表结构。
与之相对的,是非线性表结构,例如二叉树、堆、图等。非线性表中,数据并不是简单的前后关系。
连续内存空间和相同数据类型
这个很好理解,在硬件结构上,数组内所有元素存储在一块连续的内存空间上,每个元素所占的的空间大小相同。
随机访问
因为数组具有“连续内存空间和相同数据类型”的储存特性,使得数组结构的随机访问变得简单。当程序需要随机访问数组内的某个元素时,计算机根据数组头地址、元素下标和数据大小可以快速找到需要的元素。
寻址公式:
a[i]_address = base_address + i * data_type_size
低效的插入和删除
因为数组结构的空间是连续的,所以在它的某个位置插入新元素或者删除某个元素时,后面的元素位置都需要移动,效率比较低。
问题:为什么很多编程语言中的数组下标都是从零开始的?有什么优势吗?
前面我们提到,因为数组的存储结构是一组 连续的内存空间 ,所以数组具有“快速查找”的特性,支持 随机访问 。
数组根据首地址和下标,实现对元素内存的随机访问。
寻址公式:
a[i]_address = base_address + i * data_type_size
现在回答上面的问题:
从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移”,如果用 a 来表示数组的首地址,a[0] 就是偏移为 0 的位置,也就是首地址,a[k] 就表示偏移 k 个 type_size 的位置,所以计算 a[k] 的内存地址只需要用这个公式:
a[k]_address = base_address + k * type_size
但是,如果数组从 1 开始计数,那我们计算数组元素 a[k] 的内存地址就会变为:
a[k]_address = base_address + (k-1)*type_size
对比两个公式,我们不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。
如果要说数组下标从零开始计数,有什么优势的话,这应该算一个吧。
链接
王争《数据结构与算法之美 数组:为什么很多编程语言中数组都从0开始编号?》-极客时间
为什么有些编程语言的数组要从零开始算? - 知乎