第 1章基础 本书的目的是研究多种重要而实用的算法，即适合用计算机实现的解决问题的方法。和算法关系最紧密的是数据结构，即便于算法操作的组织数据的方法。本章介绍的就是学习算法和数据结构所需要的基本工具。 首先要介绍的是我们的基础编程模型。本书中的程序只用到了 Java语言的一小部分，以及我们自己编写的用于封装输入输出以及统计的一些库。 1.1节总结了相关的语法、语言特性和书中将会用到的库。 接下来我们的重点是数据抽象并定义抽象数据类型（ADT）以进行模块化编程。在 1.2节中我们介绍了用 Java实现抽象数据类型的过程，包括定义它的应用程序编程接口（API）然后通过 Java的类机制来实现它以供各种用例使用。 之后，作为重要而实用的例子，我们将学习三种基础的抽象数据类型：背包、队列和栈。1.3节用数组、变长数组和链表实现了背包、队列和栈的 API，它们是全书算法实现的起点和样板。性能是算法研究的一个核心问题。 1.4节描述了分析算法性能的方法。我们的基本做法是科学式的，即先对性能提出假设，建立数学模型，然后用多种实验验证它们，必要时重复这个过程。我们用一个连通性问题作为例子结束本章，它的解法所用到的算法和数据结构可以实现经典的 ~ 1 3 union-find抽象数据结构。 算法 编写一段计算机程序一般都是实现一种已有的方法来解决某个问题。这种方法大多和使用的编程语言无关——它适用于各种计算机以及编程语言。是这种方法而非计算机程序本身描述了解决问题的步骤。在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。算法是计算机科学的基础，是这个领域研究的核心。 要定义一个算法，我们可以用自然语言描述解决某个问题的过程或是编写一段程序来实现这个过程。如发明于 2300多年前的欧几里德算法所示，其目的是找到两个数的最大公约数： 自然语言描述 计算两个非负整数 p和 q的最大公约数：若 q是 0，则最大公约数为 p。否则，将 p除以 q得到余数 r，p和 q的最大公约数即为 q和 r的最大公约数。 Java语言描述 Public static int gcd(int p, int q) { if (q == 0) return p; int r = p %q; return gcd(q, r); } 欧几里德算法 第 1章 基 础 如果你不熟悉欧几里德算法，那么你应该在学习了 1.1节之后完成练习 1.1.24和练习 1.1.25。在本书中，我们将用计算机程序来描述算法。这样做的重要原因之一是可以更容易地验证它们是否如所要求的那样有限、确定和有效。但你还应该意识到用某种特定语言写出一段程序只是表达一个算法的一种方法。数十年来本书中许多算法都曾被表达为多种编程语言的程序，这正说明每种算法都是适合于在任何计算机上用任何编程语言实现的方法。 我们关注的大多数算法都需要适当地组织数据，而为了组织数据就产生了数据结构，数据结构也是计算机科学研究的核心对象，它和算法的关系非常密切。在本书中，我们的观点是数据结构是算法的副产品或是结果，因此要理解算法必须学习数据结构。简单的算法也会产生复杂的数据结构，相应地，复杂的算法也许只需要简单的数据结构。本书中我们将会研讨许多数据结构的性质，也许 4 本书就应该叫《算法与数据结构》。当用计算机解决一个问题时，一般都存在多种不同的方法。对于小型问题，只要管用，方法的不同并没有什么关系。但是对于大型问题（或者是需要解决大量小型问题的应用），我们就需要设计能够有效利用时间和空间的方法了。学习算法的主要原因是它们能节约非常多的资源，甚至能够让我们完成一些本不可能完成的任务。在某些需要处理上百万个对象的应用程序中，设计优良的算法甚至可以将程序运行的速度提高数百万倍。在本书中我们将在多个场景中看到这样的例子。与此相反，花费金钱和时间去购置新的硬件可能只能将速度提高十倍或是百倍。无论在任何应用领域，精心设计的算法都是解决大型问题最有效的方法。在编写庞大或者复杂的程序时，理解和定义问题、控制问题的复杂度和将其分解为更容易解决的子问题需要大量的工作。很多时候，分解后的子问题所需的算法实现起来都比较简单。但是在大多数情况下，某些算法的选择是非常关键的，因为大多数系统资源都会消耗在它们身上。本书的焦点就是这类算法。我们所研究的基础算法在许多应用领域都是解决困难问题的有效方法。计算机程序的共享已经变得越来越广泛，尽管书中涉及了许多算法，我们也只实现了其中的一小部分。例如， Java库包含了许多重要算法的实现。但是，实现这些基础算法的简化版本有助于我们更好地理解、使用和优化它们在库中的高级版本。更重要的是，我们经常需要重新实现这些基础算法，因为在全新的环境中（无论是硬件的还是软件的），原有的实现无法将新环境的优势完全发挥出来。在本书中，我们的重点是用最简洁的方式实现优秀的算法。我们会仔细地实现算法的关键部分，并尽最大努力揭示如何进行有效的底层优化工作。 5 为一项任务选择最合适的算法是困难的，这可能会需要复杂的数学分析。计算机科学中研究这种问题的分支叫做算法分析。通过分析，我们将要学习的许多算法都有着优秀的理论性能；而另一些我们则只是根据经验知道它们是可用的。我们的主要目标是学习典型问题的各种有效算法，但也会注意比较不同算法之间的性能差异。不应该使用资源消耗情况未知的算法，因此我们会时刻关注算法的期望性能。 本书框架 接下来概述一下全书的主要内容，给出涉及的主题以及本书大致的组织结构。这组主题触及了尽可能多的基础算法，其中的某些领域是计算机科学的核心内容，通过对这些领域的深入研究，我们找出了应用广泛的基本算法，而另一些算法则来自计算机科学和相关领域比较前沿的研究成果。总之，本书讨论的算法都是数十年来研发的重要成果，它们将继续在快速发展的计算机应用中扮演重要角色。 第 1章 基 础 第 1章 基 础 1.1 基础编程模型 我们学习算法的方法是用 Java编程语言编写的程序来实现算法。这样做是出于以下原因： 程序是对算法精确、优雅和完全的描述； 可以通过运行程序来学习算法的各种性质； 可以在应用程序中直接使用这些算法。相比用自然语言描述算法，这些是重要而巨大的优势。这样做的一个缺点是我们要使用特定的编程语言，这会使分离算法的思想和实现细节变得困难。 我们在实现算法时考虑到了这一点，只使用了大多数现代编程语言都具有且能够充分描述算法所必需的语法。 我们仅使用了 Java的一个子集。尽管我们没有明确地说明这个子集的范围，但你也会看到我们只使用了很少的 Java特性，而且会优先使用大多数现代编程语言所共有的语法。我们的代码是完整的，因此希望你能下载这些代码并用我们的测试数据或是你自己的来运行它们。 我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。本节以及 1.2节会详细说明这个模型，相关内容自成一体，主要是作为文档供读者查阅，以便理解本书的代码。我们的另一本入门级的书籍 An Introduction to Programming in Java: An Interdisciplinary Approach也使用了这个模型。 作为参考，图 1.1.1所示的是一个完整的 Java程序。它说明了我们的基础编程模型的许多基本特点。在讨论语言特性时我们会用这段代码作为例子，但可以先不用考虑代码的实际意义（它实现了经典的二分查找算法，并在白名单过滤应用中对算法进行了检验，请见 1.1.10节）。我们假设你具备某种主流语言编程的经验，因此你应该知道这段代码中的大多数要点。图中的注释应该能够解答你的任何疑问。因为图中的代码某种程度上反映了本书代码的风格，而且对各种 Java编程惯例和语言构造，在用法上我们都力求一致，所以即使是经验丰富的 Java程序员也应该看一看。 1.1.1 Java程序的基本结构 一段 Java程序（类）或者是一个静态方法（函数）库，或者定义了一个数据类型。要创建静态方法库和定义数据类型，会用到下面五种语法，它们是 Java语言的基础，也是大多数现代语言所共有的。 原始数据类型：它们在计算机程序中精确地定义整数、浮点数和布尔值等。它们的定义包括取值范围和能够对相应的值进行的操作，它们能够被组合为类似于数学公式定义的表达式。 语句：语句通过创建变量并对其赋值、控制运行流程或者引发副作用来进行计算。我们会使用六种语句：声明、赋值、条件、循环、调用和返回。 数组：数组是多个同种数据类型的值的集合。 静态方法：静态方法可以封装并重用代码，使我们可以用独立的模块开发程序。 字符串：字符串是一连串的字符， Java内置了对它们的一些操作。 标准输入 /输出：标准输入输出是程序与外界联系的桥梁。 数据抽象：数据抽象封装和重用代码，使我们可以定义非原始数据类型，进而支持面向对象编程。我们将在本节学习前五种语法，数据抽象是下一节的主题。运行 Java程序需要和操作系统或开发环境打交道。为了清晰和简洁，我们把这种输入命令执行 程序的环境称为虚拟终端。请登录本书的网站去了解如何使用虚拟终端，或是现代系统中许多其他高级的编程开发环境的使用方法。在例子中， BinarySearch类有两个静态方法 rank()和 main()。第一个方法 rank()含有四条语句：两条声明语句，一条循环语句（该语句中又有一条赋值语句和两条条件语句）和一条返回语句。 1.1 基础编程模型 第二个方法 main()包含三条语句：一条声明语句、一条调用语句和一个循环语句（该语句中又包含一条赋值语句和一条条件语句）。 要执行一个 Java程序，首先需要用 javac命令编译它，然后再用 java命令运行它。例如，要运行 BinarySearch，首先要输入 javac BinarySearch.java（这将生成一个叫 BinarySearch.class的文件，其中含有这个程序的 Java字节码）；然后再输入 java BinarySearch（接着是一个白名单文件名）把控制权移交给这段字节码程序。为了理解这段程序，我们接下来要详细介绍原始数据类型和表达式，各种 Java语句、数组、静态方法、字符串和输入输出。 导入一个Java库（请见1.1.6.8节）import java.util.Arrays; 代码文件名必须是BinarySearch.java（请见1.1.6.5节） public class BinarySearch 参数变量 { 静态方法（请见1.1.6.1节） 初始化声明语句（请见1.1.4.1节） 循环语句（请见1.1.3.4节） 条件语句（请见1.1.3.3节） } 命令行（请见1.1.9.1节）文件名，即args[0] StdOut的输出（请见1.1.9.2节） 9 图 1.1. 1 Java程序及其命令行的调用 10 ~ 第 1章 基 础 1.1.2 原始数据类型与表达式 数据类型就是一组数据和对其所能进行的操作的集合。首先考虑以下 4种 Java语言最基本的原始数据类型： 整型，及其算术运算符（int）； 浮点型，及其算术运算符（double）； 布尔型，它的值 {true, false}及其逻辑操作（boolean）； 字符型，它的值是你能够输入的英文字母数字字符和符号（char）。接下来我们看看如何指明这些类型的值和对这些类型的操作。 Java程序控制的是用标识符命名的变量。每个变量都有自己的类型并存储了一个合法的值。在 Java代码中，我们用类似数学表达式的表达式来实现对各种类型的操作。对于原始类型来说，我们用标识符来引用变量，用 +、-、*、/等运算符来指定操作，用字面量，例如 1或者 3.14来表示值，用形如 (x+2.236)/2的表达式来表示对值的操作。表达式的目的就是计算某种数据类型的值。表 1.1.1对这些基本内容进行了说明。 表 1.1.1 Java程序的基本组成 只要能够指定值域和在此值域上的操作，就能定义一个数据类型。表 1.1.2总结了 Java的 int、double、boolean和 char类型的相关信息。许多现代编程语言中的基本数据类型和它们都很相似。对于 int和 double来说，这些操作是我们熟悉的算数运算；对于 boolean来说则是逻辑运算。需要注意的重要一点是， +、-、 *、/都是被重载过的——根据上下文，同样的运算符对不同类型会执行不同的操作。这些初级运算的关键性质是运算产生的数据的数据类型和参与运算的数据的数据类型是相同的。这也意味着我们经常需要处理近似值，因为很多情况下由表达式定义的准确值并非参与表达式运算的值。例如， 5/3的值是 1而 5.0/3.0的值是 1.66666666666667，两者都很接近但并不准确地等于 5/3。下表并不完整，我们会在本节最后的答疑部分中讨论更多运算符和偶尔需要考虑到的各种异常情况。 表 1.1.2 Java中的原始数据类型 1.1 基础编程模型 （续） 1.1.2.1表达式 如表 1.1.2所示， Java使用的是中缀表达式：一个字面量（或是一个表达式），紧接着是一个运算符，再接着是另一个字面量（或者另一个表达式）。当一个表达式包含一个以上的运算符时，运算符的作用顺序非常重要，因此 Java语言规范约定了如下的运算符优先级：运算符 *和 /（以及 %）的优先级高于 +和 -（优先级越高，越早运算）；在逻辑运算符中， !拥有最高优先级，之后是 &&，接下来是 ||。一般来说，相同优先级的运算符的运算顺序是从左至右。与在正常的算数表达式中一样，使用括号能够改变这些规则。因为不同语言中的优先级规则会有些许不同，我们在代码中会使用括号并用各种方法努力消除对优先级规则的依赖。 1.1.2.2类型转换 如果不会损失信息，数值会被自动提升为高级的数据类型。例如，在表达式 1+2.5中， 1会被转换为浮点数 1.0，表达式的值也为 double值 3.5。转换指的是在表达式中把类型名放在括号里将其后的值转换为括号中的类型。例如， (int)3.7的值是 3而 (double)3的值是 3.0。需要注意的是将浮点型转换为整型将会截断小数部分而非四舍五入，在复杂的表达式中的类型转换可能会很复杂，应该小心并尽量少使用类型转换，最好是在表达式中只使用同一类型的字面量和变量。 1.1.2.3比较 下列运算符能够比较相同数据类型的两个值并产生一个布尔值：相等（==）、不等（!=）、小于（<）、小于等于（<=）、大于（>）和大于等于（>=）。这些运算符被称为混合类型运算符，因为它们的结果是布尔型，而不是参与比较的数据类型。结果是布尔型的表达式被称为布尔表达式。我们将会看到这种表达式是条件语句和循环语句的重要组成部分。 1.1.2.4其他原始类型 Java的整型能够表示 232个不同的值，用一个 32位二进制即可表示（虽然现在的许多计算机有 64位二进制，但整型仍然是 32位）。与此相似，浮点型的标准规定为 64位。这些大小对于一般应用程序中使用的整数和实数已经足够了。为了提供更大的灵活性， Java还提供了其他五种原始数据类型： 64位整数，及其算术运算符 (long)； 16位整数，及其算术运算符 (short)； 16位字符，及其算术运算符 (char)； 8位整数，及其算术运算符 (byte)； 32位单精度实数，及其算术运算符 (float)。 第 1章 基 础 13 在本书中我们大多使用 int和 double进行算术运算，因此我们在此不会再详细讨论其他类似的数据类型。 1.1.3语句 Java程序是由语句组成的。语句能够通过创建和操作变量、对变量赋值并控制这些操作的执行流程来描述运算。语句通常会被组织成代码段，即花括号中的一系列语句。 声明语句：创建某种类型的变量并用标识符为其命名。 赋值语句：将（由表达式产生的）某种类型的数值赋予一个变量。 Java还有一些隐式赋值的语法可以使某个变量的值相对于当前值发生变化，例如将一个整型值加 1。 条件语句：能够简单地改变执行流程根据指定的条件执行两个代码段之一。 循环语句：更彻底地改变执行流程只要条件为真就不断地反复执行代码段中的语句。 调用和返回语句：和静态方法有关（见 1.1.6节），是改变执行流程和代码组织的另一种方式。 程序就是由一系列声明、赋值、条件、循环、调用和返回语句组成的。一般来说代码的结构都是嵌套的：一个条件语句或循环语句的代码段中也能包含条件语句或是循环语句。例如， rank()中的 while循环就包含一个 if语句。接下来，我们逐个说明各种类型的语句。 1.1.3.1声明语句 声明语句将一个变量名和一个类型在编译时关联起来。 Java需要我们用声明语句指定变量的名称和类型。这样，我们就清楚地指明了能够对其进行的操作。 Java是一种强类型的语言，因为 Java编译器会检查类型的一致性（例如，它不会允许将布尔类型和浮点类型的变量相乘）。变量可以声明在第一次使用之前的任何地方——一般我们都在首次使用该变量的时候声明它。变量的作用域就是定义它的地方，一般由相同代码段中声明之后的所有语句组成。 1.1.3.2赋值语句 赋值语句将（由一个表达式定义的）某个数据类型的值和一个变量关联起来。在 Java中，当我们写下 c=a+b时，我们表达的不是数学等式，而是一个操作，即令变量 c的值等于变量 a的值与变量 b的值之和。当然，在赋值语句执行后，从数学上来说 c的值必然会等于 a+b，但语句的目的是改变 c的值（如果需要的话）。赋值语句的左侧必须是单个变量，右侧可以是能够得到相应类型的 14 值的任意表达式。 1.1.3.3条件语句 大多数运算都需要用不同的操作来处理不同的输入。在 Java中表达这种差异的一种方法是 if语句： if (<boolean expression>) { <block statements> } 这种描述方式是一种叫做模板的形式记法，我们偶尔会使用这种格式来表示 Java的语法。尖括号（<>）中的是我们已经定义过的语法，这表示我们可以在指定的位置使用该语法的任意实例。在这里， <boolean expression>表示一个布尔表达式，例如一个比较操作。 <block statements>表示一段 Java语句。我们也可以给出 <boolean expression>和 <block statements>的形式定义，不过我们不想深入这些细节。 if语句的意义不言自明：当且仅当布尔表达式的值为真 (true)时代码段中的语句才会被执行。以下 if-else语句能够在两个代码段之间作出选择： if (<boolean expression>) { <block statements> } else { <block statements> } 1.1 基础编程模型 1.1.3.4循环语句 许多运算都需要重复。 Java语言中处理这种计算的基本语句的格式是： while (<boolean expression>) { <block statements> } while语句和 if语句的形式相似（只是用 while代替了 if），但意义大有不同。当布尔表达式的值为假（ false）时，代码什么也不做；当布尔表达式的值为真（ true）时，执行代码段（和 if一样），然后再次检查布尔表达式的值，如果仍然为真，再次执行代码段。如此这般，只要布尔表达式的值为真，就继续执行代码段。我们将循环语句中的代码段称为循环体。 1.1.3.5 break与 continue语句 有些情况下我们也会需要比基本的 if和 while语句更加复杂的流程控制。相应地， Java支持在 while循环中使用另外两条语句： break语句，立即从循环中退出； continue语句，立即开始下一轮循环。 本书很少在代码中使用它们（许多程序员从来都不用），但在某些情况下它们的确能够大大简化代码。 1.1.4简便记法 程序有很多种写法，我们追求清晰、优雅和高效的代码。这样的代码经常会使用以下这些广为流传的简便写法（不仅仅是 Java，许多语言都支持它们）。 1.1.4.1声明并初始化 可以将声明语句和赋值语句结合起来，在声明（创建）一个变量的同时将它初始化。例如， int i = 1;创建了名为 i的变量并赋予其初始值 1。最好在接近首次使用变量的地方声明它并将其初始化（为了限制它的作用域）。 1.1.4.2隐式赋值 当希望一个变量的值相对于其当前值变化时，可以使用一些简便的写法。 递增 /递减运算符， ++i;等价于 i=i+1;且表达式为 i+1;。类似地， --i;等价于 i=i¬1;i++;。和 i--;的意思相同，只是表达式的值为 i的值。 其他复合运算符，在赋值语句中将一个二元运算符写在等号之前，等价于将左边的变量放在等号右边并作为第一个操作数。例如， i/=2;等价于 i=i/2;。注意， i += 1;等价于 i= i + 1;（以及 ++i;）。 1.1.4.3单语句代码段 如果条件或循环语句的代码段只有一条语句，代码段的花括号可以省略。 1.1.4.4 for语句 很多循环的模式都是这样的：初始化一个索引变量，然后使用 while循环并将包含索引变量的表达式作为循环的条件， while循环的最后一条语句会将索引变量加 1。使用 Java的 for语句可以更紧凑地表达这种循环： for (<initialize>; <boolean expression>; <increment>) { <block statements> } 除了几种特殊情况之外，这段代码都等价于： 第 1章 基 础 <initialize>; while (<boolean expression>) { <block statements> <increment>; } 我们将使用 for语句来表示对这种初始化—递增循环用法的支持。表 1.1.3总结了各种 Java语句及其示例与定义。 表 1.1.3 Java语句 1.1.5数组 数组能够顺序存储相同类型的多个数据。除了存储数据，我们也希望能够访问数据。访问数组中的某个元素的方法是将其编号然后索引。如果我们有 N个值，它们的编号则为 0至 N-1。这样对于 0到 N-1之间任意的 i，我们就能够在 Java代码中用 a[i]唯一地表示第 i个元素的值。在 Java中这种数组被称为一维数组。 1.1.5.1创建并初始化数组 在 Java程序中创建一个数组需要三步： 声明数组的名字和类型； 创建数组； 初始化数组元素。 在声明数组时，需要指定数组的名称和它含有的数据的类型。在创建数组时，需要指定数组的长度（元素的个数）。例如，在以下代码中，完整模式部分创建了一个有 N个元素的 double数组， 1.1 基础编程模型 所有的元素的初始值都是 0.0。第一条语句是数组的完整模式 声明数组声明，它和声明一个相应类型的原始数据类型变量double[] a; 创建数组 a = new double[N]; 十分相似，只有类型名之后的方括号说明我们声明for (int i = 0; i < N; i++) 的是一个数组。第二条语句中的关键字 new使 Javaa[i] = 0.0; 创建了这个数组。我们需要在运行时明确地创建数简化写法 初始化数组 组的原因是 Java编译器在编译时无法知道应该为数double[] a = new double[N];组预留多少空间（对于原始类型则可以）。 for语句初始化了数组的 N个元素，将它们的值置为 0.0。声明初始化在代码中使用数组时，一定要依次声明、创建并初int[] a = { 1, 1, 2, 3, 5, 8 };始化数组。忽略了其中的任何一步都是很常见的编声明、创建并初始化一个数组程错误。 1.1.5.2简化写法 为了精简代码，我们常常会利用 Java对数组默认的初始化来将三个步骤合为一条语句，即上例中的简化写法。等号的左侧声明了数组，等号的右侧创建了数组。这种写法不需要 for循环，因为在一个 Java数组中 double类型的变量的默认初始值都是 0.0，但如果你想使用不同的初始值，那么就需要使用 for循环了。数值类型的默认初始值是 0，布尔型的默认初始值是 false。例子中的第三种方式用花括号将一列由逗号分隔的值在编译时将数组初始化。 1.1.5.3使用数组 典型的数组处理代码请见表 1.1.4。在声明并创建数组之后，在代码的任何地方都能通过数组名之后的方括号中的索引来访问其中的元素。数组一经创建，它的大小就是固定的。程序能够通过 a.length获取数组 a[]的长度，而它的最后一个元素总是 a[a.length – 1]。Java会自动进行边界检查——如果你创建了一个大小为 N的数组，但使用了一个小于 0或者大于 N-1的索引访问它，程序会因为运行时抛出 ArrayOutOfBoundsException异常而终止。 表 1.1.4典型的数组处理代码 第 1章 基 础 （续） 任 务实现（代码片段） 矩阵相乘（方阵） int N = a.length; a[][] * b[][] = c[][] double[][] c = new double[N][N]; for (inti =0;i < N; i++) for (intj = 0; j< N; j++) { //计算行 i和列 j的点乘 for(int k =0;k <N;k++) c[i][j] += a[i][k]*b[k][j]; } 1.1.5.4起别名 请注意，数组名表示的是整个数组——如果我们将一个数组变量赋予另一个变量，那么两个变量将会指向同一个数组。例如以下这段代码： int[] a = new int[N]; ... a[i] = 1234; ... int[] b = a; ... b[i] = 5678; // a[i]的值也会变成 5678 这种情况叫做起别名，有时可能会导致难以察觉的问题。如果你是想将数组复制一份，那么应该声明、创建并初始化一个新的数组，然后将原数组中的元素值挨个复制到新数组，如表 1.1.4的第三个例子所示。 1.1.5.5二维数组 在 Java中二维数组就是一维数组的数组。二维数组可以是参差不齐的（元素数组的长度可以不一致），但大多数情况下（根据合适的参数 M和 N）我们都会使用 M×N，即 M行长度为 N的数组的二维数组（也可以称数组含有 N列）。在 Java中访问二维数组也很简单。二维数组 a[][]的第 i行第 j列的元素可以写作 a[i][j]。声明二维数组需要两对方括号。创建二维数组时要在类型名之后分别在方括号中指定行数以及列数，例如： double[][] a = new double[M][N]; 我们将这样的数组称为 M×N的数组。我们约定，第一维是行数，第二维是列数。和一维数组一样， Java会将数值类型的数组元素初始化为 0，将布尔型的数组元素初始化为 false。默认的初始化对二维数组更有用，因为可以节约更多的代码。下面这段代码和刚才只用一行就完成创建和初始化的语句是等价的： double[][] a; a = new double[M][N]; for (int i= 0; i< M; i++) for(int j= 0; j <N;j++) a[i][j] = 0.0; 19 在将二维数组初始化为 0时这段代码是多余的，但是如果想要初始化为其他值，我们就需要嵌21 套的 for循环了。 1.1.6静态方法 本书中的所有 Java程序要么是数据类型的定义（详见 1.2节），要么是一个静态方法库。在许多语言中，静态方法被称为函数，因为它们和数学函数的性质类似。静态方法是一组在被调用时会 ~ 1.1 基础编程模型 被顺序执行的语句。修饰符 static将这类方法和 1.2节的实例方法区别开来。当讨论两类方法共有的属性时我们会使用不加定语的方法一词。 1.1.6.1静态方法 方法封装了由一系列语句所描述的运签名算。方法需要参数（某种数据类型的值）并 返回值类型方法名参数类型参数变量根据参数计算出某种数据类型的返回值（例如数学函数的结果）或者产生某种副作用（例{ 如打印一个值）。 BinarySearch中的静态函局部数 rank()是前者的一个例子； main()则是变量后者的一个例子。每个静态方法都是由签名函数体 （关键字 public static以及函数的返回值，方法名以及一串各种类型的参数）和函数体}返回语句调用另一个方法 （即包含在花括号中的代码）组成的，如图 1.1.2所示。静态函数的例子请见表 1.1.5。图 1.1.2静态方法解析 表 1.1.5典型静态方法的实现 第 1章 基 础 ~ 1.1.6.2调用静态方法 调用静态方法的方法是写出方法名并在后面的括号中列出参数值，用逗号分隔。当调用是表达式的一部分时，方法的返回值将会替代表达式中的方法调用。例如， BinarySearch中调用 rank()返回了一个 int值。仅由一个方法调用和一个分号组成的语句一般用于产生副作用。例如， BinarySearch的 main()函数中对系统方法 Arrays.sort()的调用产生的副作用，是将数组中的所有条目有序地排列。调用方法时，它的参数变量将被初始化为调用时所给出的相应表达式的值。返22 回语句将结束静态方法并将控制权交还给调用者。如果静态方法的目的是计算某个值，返回语句应23 该指定这个值（如果这样的静态方法在执行完所有的语句之后都没有返回语句，编译器会报错）。 1.1.6.3方法的性质 对方法所有性质的完整描述超出了本书的范畴，但以下几点值得一提。 方法的参数按值传递：在方法中参数变量的使用方法和局部变量相同，唯一不同的是参数变量的初始值是由调用方提供的。方法处理的是参数的值，而非参数本身。这种方式产生的结果是在静态方法中改变一个参数变量的值对调用者没有影响。本书中我们一般不会修改参数变量。值传递也意味着数组参数将会是原数组的别名（见 1.1.5.4节）——方法中使用的参数变量能够引用调用者的数组并改变其内容（只是不能改变原数组变量本身）。例如， Arrays.sort()将能够改变通过参数传递的数组的内容，将其排序。 方法名可以被重载：例如， Java的 Math包使用这种方法为所有的原始数值类型实现了 Math.abs()、Math.min()和 Math.max()函数。重载的另一种常见用法是为函数定义两个版本，其中一个需要一个参数而另一个则为该参数提供一个默认值。 方法只能返回一个值，但可以包含多个返回语句：一个 Java方法只能返回一个值，它的类型是方法签名中声明的类型。静态方法第一次执行到一条返回语句时控制权将会回到调用代码中。尽管可能存在多条返回语句，任何静态方法每次都只会返回一个值，即被执行的第一条返回语句的参数。 方法可以产生副作用：方法的返回值可以是 void，这表示该方法没有返回值。返回值为 void的静态函数不需要明确的返回语句，方法的最后一条语句执行完毕后控制权将会返回给调用方。我们称 void类型的静态方法会产生副作用（接受输入、产生输出、修改数组或者改变系统状态）。例如，我们的程序中的静态方法 main()的返回值就是 void，因为它 24 的作用是向外输出。技术上来说，数学方法的返回值都不会是 void（Math.random()虽然不接受参数但也有返回值）。 2.1节所述的实例方法也拥有这些性质，尽管两者在副作用方面大为不同。 1.1.6.4递归 方法可以调用自己（如果你对递归概念感到奇怪，请完成练习 1.1.16到练习 1.1.22）。例如，下面给出了 BinarySearch的 rank()方法的另一种实现。我们会经常使用递归，因为递归代码比相应的非递归代码更加简洁优雅、易懂。下面这种实现中的注释就言简意赅地说明了代码的作用。我们可以用数学归纳法证明这段注释所解释的算法的正确性。我们会在 3.1节中展开这个话题并为二分查找提供一个这样的证明。 编写递归代码时最重要的有以下三点。 递归总有一个最简单的情况方法的第一条语句总是一个包含 return的条件语句。 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在下面的代码中，第四个参数和第三个参数的差值一直在缩小。 1.1 基础编程模型 递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中，两个子问题各自操作的数组部分是不同的。 违背其中任意一条都可能得到错误的结果或是低效的代码（见练习 1.1.19和练习 1.1.27），而坚持这些原则能写出清晰、正确且容易评估性能的程序。使用递归的另一个原因是我们可以使用数学模型的来估计程序的性能。我们会在 3.2节的二分查找以及其他几个地方分析这个问题。 1.1.6.5基础编程模型 静态方法库是定义在一个 Java类中的一组静态方法。类的声明是 public class加上类名，以及用花括号包含的静态方法。存放类的文件的文件名和类名相同，扩展名是 .java。Java开发的基本模式是编写一个静态方法库（包含一个 main()方法）来完成一个任务。输入 java和类名以及一系列字符串就能调用类中的 main()方法，其参数为由输入的字符串组成的一个数组。 main()的最后一条语句执行完毕之后程序终止。在本书中，当我们提到用于执行一项任务的 Java程序时，我们指的是用这种模式开发的代码（可能还包括对数据类型的定义，如 1.2节所示）。例如， BinarySearch就是一个由两个静态方法 rank()和 main()组成的 Java程序，它的作用是将输入中所有不在通过命令行指定的白名单中的数字打印出来。 1.1.6.6模块化编程 这个模型的最重要之处在于通过静态方法库实现了模块化编程。我们可以构造许多个静态方法库（模块），一个库中的静态方法也能够调用另一个库中定义的静态方法。这能够带来许多好处： 程序整体的代码量很大时，每次处理的模块大小仍然适中； 可以共享和重用代码而无需重新实现； 很容易用改进的实现替换老的实现； 可以为解决编程问题建立合适的抽象模型； 缩小调试范围（请见 1.1.6.7节关于单元测试的讨论）。 例如， BinarySearch用到了三个独立的库，即我们的 StdOut和 StdIn以及 Java的 Arrays，而这三个库又分别用到了其他的库。 1.1.6.7单元测试 Java编程的最佳实践之一就是每个静态方法库中都包含一个 main()函数来测试库中的所有方法（有些编程语言不支持多个 main()方法，因此不支持这种方式）。恰当的单元测试本身也是很有挑战性的编程任务。每个模块的 main()方法至少应该调用模块中的其他代码并在某种程度上保 第 1章 基 础 证它的正确性。随着模块的成熟，我们可以将 main()方法作为一个开发用例，在开发过程中用它来测试更多的细节；也可以把它编成一个测试用例来对所有代码进行全面的测试。当用例越来越复杂时，我们可能会将它独立成一个模块。在本书中，我们用 main()来说明模块的功能并将测试用 26 例留做练习。 1.1.6.8外部库 我们会使用来自 4个不同类型的库中的静态方法，重用每种库代码的方式都稍有不同。它们大多都是静态方法库，但也有部分是数据类型的定义并包含了一些静态方法。 系统标准库 java.lang.*：这其中包括 Math库，实现了常用的数学函数； Integer和 Double库，能够将字符串转化为 int和 double值； String和 StringBuilder库，我们稍后会在本节和第 5章中详细讨论；以及其他一些我们没有用到的库。 导入的系统库，例如 java.utils.Arrays：每个标准的 Java版本中都含有上千个这种类型的库，不过本书中我们用到的并不多。要在程序的开头使用 import语句导入才能使用这些库（我们也是这样做的）。 本书中的其他库：例如，其他程序也可以使用 BinarySearch的 rank()方法。要使用这些库，请在本书的网站上下载它们的源代码并放入你的工作目录中。 我们为本书（以及我们的另一本入门教材 An Introduction 系统标准库 to programming in Java: An Interdisciplinary Approach）开Math Integer† 发的标准库 Std*：我们会在下面简要地介绍这些库，它Double† 们的源代码和使用方法都能够在本书的网站上找到。String† 要调用另一个库中的方法（存放在相同或者指定的目录中，StringBuilder System或是一个系统标准库，或是在类定义前用 import语句导入的导入的系统库 库），我们需要在方法前指定库的名称。例如， BinarySearch的 java.util.Arrays 我们的标准库 main()方法调用了系统库 java.utils.Arrays的 sort()方法，我StdIn StdOut 们的库 StdIn中的 readInts()方法和 StdOut库中的 println()StdDraw 方法。StdRandom 我们自己及他人使用模块化方式编写的方法库能够极大地扩StdStats 展我们的编程模型。除了在 Java的标准版本中可用的所有库之外，In† Out† 网上还有成千上万各种用途的代码库。为了将我们的编程模型限†含有静态方法的数据类型的定义27 制在一个可控范围之内，以将精力集中在算法上，我们只会使用本书使用的含有静态方法的库 以下所示的方法库，并在 1.1.7节中列出了其中的部分方法。
