CodeSnippet.Cn
代码片段
Csharp
架构设计
.NetCore
西班牙语
kubernetes
MySql
Redis
Algorithm
Ubuntu
Linux
Other
.NetMvc
VisualStudio
Git
pm
Python
WPF
java
Plug-In
分布式
CSS
微服务架构
JavaScript
DataStructure
Shared
为什么数组从0开始编号
0
Csharp
小笨蛋
发布于：2021年10月28日
更新于：2021年10月28日
161
#custom-toc-container
数组对一个程序员来说再熟悉不过了，几乎所有的编程语言中都有数组，它是最基本的数据结构之一。 刚开始学数组的时候，总是很纳闷，为什么它从0开始编号，而不是从更符合我们思维习惯的1开始呢？带着这个问题往下看。 ### 什么是数组 在编程的过程中，我们经常要用到数组，但是你能够用专业的词汇来描述什么是数组吗？ ** 数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。 ** ### 线性表 线性表`（linear list）`是指具有n个相同特性的数据元素组成的有限序列，你可以理解为“把所有数据用一根线串起来，再存储到物理空间中”，从图中可以明显的看出它最多只有前和后两个方向（节点）。  除了数组，链表、队列和栈也是线性表结构（线性表既可以顺序存储，也可以链式存储） ### 非线性表 与线性表对应，非线性表是指一个节点元素可能有多个直接前驱和多个直接后继，比如树和图  ### 连续的内存空间和相同的数据类型 同一个数组中的数据类型都是一样的，并且它们连续存储在内存中，所以我们可以对数组内容进行随机访问。随机访问这个过程是怎么实现的呢？ 计算机会给每个内存单元分配一个地址，通过地址来访问内存中的数据。当它需要随机访问数组中的某个元素时，首先会通过寻址公式，计算出该元素存储的内存地址，然后对其进行读取操作，寻址公式为 `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开始，更准确的讲它不是下标而是代表偏移(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等. ### 数组的增删查操作 #### 查找 前面已经讲过,可以通过下标访问数组中的元素,由于它是连续存储的,访问的时间复杂度是O(1). #### 添加 假设我们有一个数组,长度为n,要在它第k个位置上插入数据,要进行什么操作呢?为了空出第k个位置给新插入的数据,k~n这部分的数据都需要往后挪一位,那么它的平均时间复杂度为O(n).  #### 删除 删除操作于添加类似,为了保持内存的连续,不出现空洞,需要将删除元素后面的元素向前移,平均时间复杂度也为O(n)  ### 总结 
这里⇓感觉得写点什么，要不显得有点空，但还没想好写什么...
返回顶部
About
京ICP备13038605号
© 代码片段 2024
Csharp
小笨蛋
发布于：2021年10月28日
更新于：2021年10月28日
161