程序员学数据结构

第2章　数组：基本数据集

很多时候，应用程序需要在运行时将多种用户数据或对象存进内存。一种方案是针对所需数据，分别在各个类中定义多个字段（属性）进行存储。遗憾的是，哪怕用于最简单的工作流，这种方案很快就会捉襟见肘：要么字段太多而无法处理，要么在编译阶段还无法预见到项目所有的动态需求。另一种方案是使用数组。数组是一种简单的数据集，实际上许多数据结构都是构建在数组之上的，因此它是日常编程中遇到的最为常用的数据结构之一。

数组是一种能够定量容纳特定类型数据项的容器。在C及其派生语言中，数组的大小在其创建之初便确定下来，且不再变化。数组中的每个数据项都称为一个元素（element），每个元素都可通过其索引进行访问。一般而言，数组是一个数据项的合集，这些数据项可通过程序运行时所确立的索引进行选择。

本章将涵盖以下主要内容：

• 数组的定义；
• 可变数组与不可变数组；
• 数组的示例程序；
• 线性查找；
• 原始数组；
• 对象数组；
• 混合数组；
• 多维数组；
• 不规则数组。

值得注意的是，在绝大多数语言中，数组都是零编号索引（zero-based index），即数组中第一个项目的编号为0，第二个项目的编号为1，依此类推，如图2-1所示。

当源代码试图访问的项目与实际所需要访问的项目编号差一时，会发生差一错误（off-by-one error）。初学者和编程老手一样，会经常犯这种错误，这通常是出现索引超出范围（index is out of range）或索引超出边界（index is out of bounds ...