为什么数组从0开始编号

发布时间:2022-07-05 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了为什么数组从0开始编号脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

为什么数组从0开始编号

数组对一个程序员来说再熟悉不过了,几乎所有的编程语言都有数组,它是最基本的数据结构之一。

刚开始学数组的时候,总是很纳闷,为什么它从0开始编号,而不是从更符合我们思维习惯的1开始呢?带着这个问题往下看。

什么是数组

在编程的过程中,我们经常要用到数组,但是你能够用专业的词汇来描述什么是数组吗?

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

线性表

线性表(linear list)是指具有n个相同特性的数据元素组成的有限序列,你可以理解为“把所有数据用一根线串起来,再存储到物理空间中”,从图中可以明显的看出它最多只有前和后两个方向(节点)。

为什么数组从0开始编号

 

除了数组,链表、队列和栈也是线性表结构(线性表既可以顺序存储,也可以链式存储)

非线性表

与线性表对应,非线性表是指一个节点元素可能有多个直接前驱和多个直接后继,比如树和图

为什么数组从0开始编号

 

连续的内存空间和相同的数据类型

同一个数组中的数据类型都是一样的,并且它们连续存储在内存中,所以我们可以对数组内容进行随机访问。随机访问这个过程是怎么实现的呢?

计算机会给每个内存单元分配一个地址,通过地址来访问内存中的数据。当它需要随机访问数组中的某个元素时,首先会通过寻址公式,计算出该元素存储的内存地址,然后对其进行读取操作,寻址公式为

    a[i]_address = base_address + i * data_tyPE_size    //其中i表示数组中第几个元素

我们拿一个长度为 10 的 int 类型的数组 int[] a = new int[10]来举例。在这个图中,计算机给数组 a[10]分配了一块连续内存空间 1000~1039,其中,内存块的首地址为 base_address = 1000,因为存储的是整数,所以data_type_size = 4。根据公式,我们很容易就能得到这个数组中某个元素在内存中的地址。

为什么数组从0开始编号

 

从内存上看,我们可以理解为什么大部分编程语言中的数组下标是0开始,更准确的讲它不是下标而是代表偏移(offset)。如果用a来表示数组的首地址,a[0]是它偏移0的位置(就是首地址),a[2]代表是偏移2 * data_type_size的位置,也就是第三个元素的地址,a[i]就表示偏移i * data_type_size的位置。如果从1开始编号的话,那么计算数组a[i]的内存地址公式就会变为

    a[i]_address = base_address + (i-1) * data_type_size

对于CPU来说,多做了一次减法指令。

还有一个原因就是历史遗留问题,因为c语言使用0开始计数数组下标,后面的Java、C#等语言也都效仿了C语言,继续沿用该习惯.但现在有的语言也不是从0开始计数,比如Lua,Matlab等.(部分内容及图片参考王争老师的数据结构与算法之美)

数组的增删查操作

查找

前面已经讲过,可以通过下标访问数组中的元素,由于它是连续存储的,访问的@R_147_1304@是O(1).

添加

假设我们有一个数组,长度为n,要在它第k个位置上插入数据,要进行什么操作呢?为了空出第k个位置给新插入的数据,k~n这部分的数据都需要往后挪一位,那么它的平均时间复杂度为O(n).

为什么数组从0开始编号

 

删除

删除操作于添加类似,为了保持内存的连续,不出现空洞,需要将删除元素后面的元素向前移,平均时间复杂度也为O(n)

为什么数组从0开始编号

如果对时间复杂度的概念不了解,可以查看算法复杂度分析

总结

 

@H_406_269@

 

脚本宝典总结

以上是脚本宝典为你收集整理的为什么数组从0开始编号全部内容,希望文章能够帮你解决为什么数组从0开始编号所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。