|初学者指南：什么是算法？11行伪代码给你讲明白( 二 )

数组之于计算机，就像对象序列之于人类。数组是元素的有序序列，这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建一个保存n个元素的数组，可调用算法1-1第1行中的CreateArray算法。

本文插图

如果你熟悉数组，可能就会奇怪创建数组怎么还需要一个算法。但实际情况的确如此。为了获得保存数据的一块内存，你必须至少在计算机中搜索可用内存并标记它为数组所用。
CreateArray(n)调用做了所需的一切，它返回一个可容纳n个元素的数组，初始时其中没有元素，只有保存元素所需的空间。算法负责调用CreateArray(n)来将实际数据填充到数组中。
对数组A ，我们用A[i]表示其第i个元素，访问该元素也是用该符号。一个元素在数组中的位置，如A[i]中的i ，被称为索引（index）。一个n个元素的数组A包含元素A[0] ， A[1] ， … ， A[n-1] 。
这可能令你吃惊，因为其首元素是第0个，而尾元素是第n-1个，可能你的预期是第1个和第n个。但是，大多数计算机语言中的数组都是如此，你最好现在就熟悉这种机制。这非常常见，当遍历一个大小为n的数组时，我们是从位置0遍历到位置n-1 。
在我们的算法中，当我们说某个对象的取值是从数x到数y（假定x小于y）时，意思是从x到y（但不包含）的所有值，参见算法第2行。
我们假定无论i的值是什么，访问第i个元素都花费相同的时间。因此访问A[0]与访问A[n-1]需要相同的时间。这是数组的一个非常重要的特性：对元素的访问是一致的，都花费常量时间。当我们通过索引访问数组元素时，数组不需要搜索此元素。
关于算法描述中的符号表示，我们用小写字母表示算法中的变量。但当变量表示一个数据结构时，我们会使用大写字母来令其突出，如数组A 。但这并非必要。当我们希望给变量起一个包含很多单词的名字时，我们会使用下划线（_），如a_connector 。这是必要的，因为计算机不理解由一组空格分隔的单词构成单个变量名的方式。
算法1-1使用数组保存数值。数组可以保存任何类型的项，在我们的伪代码中每个数组只能保存单一类型的项。大多数程序设计语言中也都是如此。
例如，可以创建十进制数数组、分数数组、表示人的项的数组以及另一个表示地址的项的数组，但不可以创建一个既包含十进制数又包含表示人的项的数组。至于“表示人的项”会是什么，由编程所使用的语言所决定。所有程序设计语言都提供表示有意义的东西的方法。
一种特别有用的数组是字符数组。一个字符数组表示一个字符串（string），即一个字母序列、一个数序列、一个单词序列、一个句子序列等。与所有数组一样，我们可以用索引单独引用数组中的单个字符。如果我们有一个字符串s=“Hello ， World” ，则s[0]为字母“H”而s[11]为字母“d” 。

本文插图

总结一下，数组就是一个保存相同类型项的序列的数据结构。数组支持两种操作：