数组

数据结构的鼻祖——数组，作为数据结构中最基础的一个存储方式，是我们学习一切数据结构、算法的基石。大部分数据结构都可以用数组来实现。在每一门编程语言中，数组都是重要的数据结构，当然每种语言对数组的实现和处理也不相同，但是本质是都是用来存放数据的的结构。

数组(Array)

要用就要提前想好的数据结构——数组。要用就要提前想好？为什么？这其实是由数组的一个特点决定的，那就是对于数组这个数据结构，在用它之前必须提前想好它的长度；有了长度，才能知道该为这个存储结构开辟多少空间；而在决定了长度之后，不管我们最后往里面填充的数据够不够长，没有用到的空间也就都浪费了；如果我们想往这个数组中放入的数据超过了提前设定好的长度，那么是不可行的，因为空间只有这么大。

什么是数组

数组（Array），就是把有限个数据类型一样的元素按顺序放在一起，用一个变量命名，然后通过编号可以按顺序访问指定位置的元素的一个有序集合。 其实简单来说，就是为了方便而把这些元素放在一起。我们通过编号去获取每个元素，这个编号叫作下标或者索引（Index），一般的语言是从0开始的。

我们常说的数组一般指一维数组，当然还有多维数组，虽然多维数组并不常用。 多维的实现其实是数组的某些元素本身也是一个数组，这里以一个标准的二维数组为例进行介绍。其实，二维数组相当于每个元素的长度都一样的一个一维数组（也就是我们常说的数组）。可以想象一下矩阵，其实它和数学中的矩阵类似。

在很多弱语言中，并不要求每个元素的长度都一样，可以某些元素是数组（长度可以不一样），某些元素不是数组，甚至每个元素的数据类型都不同。这里讲的二维数组指的是标准的二维数组。 注：弱类型语言也叫作弱类型定义语言，简称弱语言。弱语言一般对语言的标准没有特别的要求。比如在JavaScript中用var声明变量，不会指定该变量是哪种类型。如果想更多地了解弱语言，则请参考JavaScript，该语言主要用于前端开发。强语言对编写规则比较有要求，所以不容易出现问题，很多开发工具都会帮助检查其基本规则。

数组的存储结构

在了解了什么是数组之后，我们来看下数组的存储结构。 首先我们来看下一维数组的存储结构

        num[n]数组结构

num[0] num[1] ... num[n-1]

其实，我们先要确定一个值，也就是数组的长度；然后，系统会根据我们声明的数据类型开辟一些空间（当然，每种数据类型需要开辟的空间也不一样）。这时，这些空间就归这个变量所有了。一般在编程语言的实现中，这些空间会默认对我们声明的数据类型赋值，比如整型值是0，布尔值是false，等等。

所以有以下几种情况。

• 只声明了指定长度的空间，没有初始化值（以整型为例，所有值都会默认为0，如下图）。

  例如num[5]，默认值都是0
  [0,0,0,0,0]
  

• 声明了指定长度的空间，初始化了部分值（以整型为例，未初始化的值都会默认为0，如下图）。

  例如num[5]，只初始化了前三个值，其余值自动初始化为0
  [0,1,2,0,0]
  

• 声明了指定长度的空间，初始化了全部的值

  例如num[5]，初始化了全部的值
  [1,2,3,4,5]
  

数组在编程语言中的初始化及操作

数组的特点

因为本身存储的方式，数组有如下特点。

• 定长 数组的长度是固定的，这是数组最重要的一个特点。 只要我们在声明时确定了数组的长度，在赋值时就算没有给数组的所有元素赋值，未赋值的元素也是有初始默认值的；而如果我们在赋值时发现数组的长度不够用，这时也没有什么好办法，因为数组的长度无法改变。要是想继续存放数据，就只能重新声明一个数组了。
• 按顺序访问 我们在访问一个数组中的某个元素时，必须从第1个元素开始按顺序访问，直到访问到指定位置的元素。 这里想说明一点，虽然我们在开发时可以直接通过下标访问指定位置的元素，但是实际上计算机在处理时也是按顺序访问的。

数组的适用场景

数组其实是一个非常简单的数据结构，用起来也比较简单。但是，数组是所有数据结构的基础，我们必须掌握好数组，才能更好地学习其他数据结构和算法。 数组适合在什么时候用，其实根据数组的特点我们就可以想到，由于数组的长度一般是固定的，所以在不会出现变化的业务上比较适合使用数组。

• 技能快捷键 不知道大家对RPG（ARPG）等类似的游戏了解多少，在这类游戏中会有一排快捷键技能格，比如F1～F9这样9个快捷键技能格，我们每个人可以把自己惯用的技能拖动到这些技能格上，这样就可以直接通过技能快捷键操控技能了。一般在这种设计中，一个游戏的快捷键格子会有固定的个数。于是，我们在程序里就可以通过数组来存储每个人的技能快捷键对应的技能（当然，肯定会通过一定的映射存到数据库之类的磁盘上）。

到这里，我们应该已经很清晰地认识到了数组的劣势，那就是在用之前必须提前确定数组的长度，而后不管我们的技能是否需要增加快捷键位，或者优酷首页从8+1变成了11+1，都会导致对程序进行一定的改动。这时我们就该认识一下数组的升级版——集合了。

数组的局限性

通过上面的代码，我们发现数组是能完成一个数据结构所有的功能的，而且实现起来也不难，那数据既然能完成所有的工作，我们实际应用中为啥不用它来进行所有的数据存储呢？那肯定是有原因呢。 数组的局限性分析：

• 插入快，对于无序数组，上面我们实现的数组就是无序的，即元素没有按照从大到小或者某个特定的顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但是有序数组却不一定了，它需要在指定的位置插入。
• 查找慢，当然如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，我们需要从数组第一个元素开始遍历，直到找到那个元素。有序数组通过特定的算法查找的速度会比无需数组快，后面我们会讲各种排序算法。
• 删除慢，根据元素值删除，我们要先找到该元素所处的位置，然后将元素后面的值整体向前面移动一个位置。也需要比较多的时间。
• 数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。

很显然，数组虽然插入快，但是查找和删除都比较慢，而且扩展性差，所以我们一般不会用数组来存储数据，那有没有什么数据结构插入、查找、删除都很快，而且还能动态扩展存储个数大小呢，答案是有的，但是这是建立在很复杂的算法基础上，后面我们也会详细讲解。