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


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

数组定义:

数组(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
阅读 79 讨论 0 喜欢 3

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

4601 1243927
抢先体验

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

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

18年元旦立下的flag要集中突击一下了.....

人生是一场马拉松,起跑的优劣对于整段路途而言并没有那么重要,笑到最后的都是一直在跑的人,也就是一辈子都在学习的人。

角色是谁并不重要,重要的是会不会抢戏~

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.