数组——最基本的数据结构之一 | 为什么很多编程语言中的数组下标都是从零开始的?有什么优势吗?


在每一种编程语言中,基本都会有数组这种数据类型,不过它不仅仅存在于编程语言中,还是一种基础数据结构。

数组定义:

数组(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开始编号?》-极客时间
为什么有些编程语言的数组要从零开始算? - 知乎

本文发表于2018年10月23日 17:45
阅读 4709 讨论 0 喜欢 4

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1