《计算思维与算法入门》 —2.2 常见的数据结构

2.2    常见的数据结构

不同种类的数据结构适用于不同种类的程序应用，选择适当的数据结构是让算法发挥最大性能的主要因素，精心选择的数据结构可以给设计的程序带来更高效率的算法。然而，无论是哪种情况，数据结构的选择都是至关重要的。接下来我们将介绍一些常见的数据结构。

数组

“数组”结构其实就是一排紧密相邻的可数内存，并提供一个能够直接访问单个数据内容的计算方法。我们可以想象一下自家的信箱，每个信箱都有住址，其中路名就是名称，而信箱号码就是数组的下标（也称为“索引”），如图2-8所示。

图2-8  数组结构与邮递信箱系统类似

邮递员可以按照信件上的住址把信件直接投递到指定的信箱中，这就好比程序设计语言中数组的名称表示一块紧密相邻的内存的起始位置，而数组的下标（或索引）则用来表示从此内存起始位置开始后的第几个内存区块。

数组类型是一种典型的静态数据结构，它使用连续分配的内存空间（Contiguous Allocation）来存储有序表中的数据。静态数据结构是在编译时就给相关的变量分配好内存空间。在建立静态数据结构的初期，必须事先声明最大可能要占用的固定内存空间，因此容易造成内存的浪费。优点是设计时相当简单，而且读取与修改数组中任意一个元素的时间都是固定的，缺点则是删除或加入数据时，需要移动大量的数据。

数组是一组具有相同名称和数据类型的变量的集合，并且它们在内存中占有一块连续的内存空间。数组可以分为一维数组、二维数组与多维数组等，它们的基本工作原理都相同。如果想要存取数组中的数据，需要配合下标值（index，或称为索引值）找到数组中指定位置的值。在图2-9中的Array_Name是一维数组，它是拥有5个相同数据类型数值的数组。通过名称Array_Name与下标值即可方便地存取这5个数据。

图2-9  数组中数据存储的示意图

二维数组（Two-Dimension Array）可视为一维数组的扩展，都是用于处理数据类型相同的数据，差别只在于维数的声明。例如，一个含有m × n个元素的二维数组A(1:m, 1:n)，m代表行数，n代表列数，A[4][4]数组中各个元素在直观平面上的具体排列方式可参考图2-10。

图2-10  4 × 4的数组在直观平面上的排列方式

三维数组的表示法和二维数组一样，都可视为是一维数组的扩展或延伸，如果数组为三维数组，可以看作一个立方体。将arr[2][3][4]三维数组想象成空间上的立方体，如图2-11所示。

图2-11  三维数组可以看成一个立方体