《算法（第4版）》第一章读书笔记：基础编程模型

发表于 分类于 ， 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 17 分钟

本篇博客为《算法（第4版）》的读书笔记第一部分，主题是：基础编程模型。

算法是一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。

Java 程序的基本结构

一段 Java 程序（类）是一个静态方法库（函数）或者一个数据类型定义。为了创建静态方法库和定义数据类型，会用到以下组成部分：

  • 原始数据类型
  • 语句
  • 数组
  • 静态方法
  • 字符串
  • 输入输出
  • 数据抽象

我们将在本节学习前六种语法，数据抽象在下一篇介绍。

原始数据类型和表达式

数据类型就是一组数据和对其所能进行的操作的集合。Java 语言最基本的原始数据类型包括：

  • 整型（int）
  • 浮点型（double）
  • 布尔型（boolean）
  • 字符型（char）

Java 操作的是用标识符命名的变量。标识符是由字母、数字、下划线和 $ 组成的字符串，首字符不能是数字。每个变量都有自己的类型并存储了一个合法的值。我们用类似数学表达式的表达式来实现对各种类型的操作。

只要能够制定值域和在此值域上的操作，就能够定义一个数据类型，如下表所示：

需要注意的是算术运算符是经过重载的——根据上下文，同样的运算符对不同类型会执行不同的操作。这些初级运算的关键性质是运算所产生数据的数据类型和参与运算的数据的数据类型是相同的，这意味着我们经常需要处理近似值（例如 5/3 的值是 1）。

表达式

Java 使用的是中缀表达式：一个字面量（或表达式）紧接着一个运算符，再接着是另一个字面量（表达式）。字面量即值在源代码中的表示（表达式的结果）。

当一个表达式包含多个运算符时，运算符的作用顺序非常重要，Java 规定的运算符优先级如下： + 对于算术运算符，* 和 / （以及 %）的优先级高于 + 和 - + 对于逻辑运算符，! 优先级最高，之后是 && ，接下来是 ||

与算术表达式一样，使用括号能够改变这些规则。为了避免错误，建议多使用括号。

类型转换

如果不会损失信息，数字会被自动提升为高级的数据类型，如表达式 1+2.5 中，1 会被转换为浮点数 1.0，表达式的值为 double 值 3.5。

转换指的是在表达式中把类型名放在括号里将其后的值转换为括号中的类型，如 (int)3.7 的值是 3。 注意浮点型转换为整型将会截断小数部分而非四舍五入。

比较

下列运算符能够比较相同数据类型的两个值并产生一个布尔值： + 相等（==） + 不等（!=） + 小于（<） + 小于等于（<=） + 大于（>） + 大于等于（>=）

这些运算符被称为混合类型运算符，因为它们的结果是布尔型，而不是参与比较的数据类型。结果是布尔型的表达式被称为布尔表达式

其他原始类型

Java 的整型是 32 位，浮点型是 64 位。为了提供更大的灵活性，Java 还提供了其他四种原始数据类型：

  • 64位整数（long）
  • 16位整数（short）
  • 8位整数（byte）
  • 32位单精度实数（float）

语句

Java 程序是由语句组成的。语句能够通过创建和操作变量，对变量赋值并控制这些操作的执行流程来描述运算。

Java 语句一般包含以下几种：

声明语句

声明语句用于创建某种类型的变量并用标识符为其命名。由于 Java 是一种强类型的语言（Java 编译器会检查类型的一致性），所以我们需要用声明语句来指定变量的名称和类型。变量的作用域就是定义它的地方，一般由相同代码段中声明之后的所有语句组成。

赋值语句

赋值语句将某个数据类型的值（由一个表达式定义）和一个变量关联起来。为了简洁，一般可以将声明语句和赋值语句结合起来，在声明一个变量的同时将它初始化，例如 int i = 1;。

隐性赋值：当希望一个变量的值相对于其当前的值变化时，可以使用一些简便的写法。

  • 递增/递减操作符：++i 等价于 i=i+1，且表达式为 i+1，i++ 意思相同只是表达式为 i 的值
  • 其他复合运算符：在赋值语句中将一个二元运算符写在等号之前。i/=2 等价于 i=i/2

条件语句

条件语句能够简单地改变执行流程，根据指定的条件执行两个代码段之一。其基本格式如下：

if (<boolean expression>) { <block statements> } 
else                      { <block statements> }

如果只有一条语句，代码的花括号可以省略（下同）。

循环语句

循环语句可以更彻底地改变执行流程，只要条件为真就不断地反复执行代码段中的语句。其基本格式如下：

while (<boolean expression>) { <block statements> }

我们将循环语句中的代码段称为循环体。

有时候，很多循环的模式都是：初始化一个索引变量，然后使用 while 循环并将包含索引变量的表达式作为循环条件，while 循环的最后一条语句会将索引变量加 1（或其他操作）。对于这种情况，使用 for 语句可以更紧凑地表达这种初始化—递增循环：

for (<initialize>; <boolean expression>; <increment>)
{
    <block statements>
}

break 和 continue 语句

有些情况下我们需要比基本的条件和循环语句更加复杂的流出控制。Java 支持在循环中使用另外两条语句：

  • break 语句：立即从循环中跳出
  • continue 语句：立即开始下一轮循环

调用和返回语句

调用和返回语句与静态方法有关，是改变执行流程和代码组织的另一种方式。请参见第五节。

下表对不同种类的 Java 语句进行了总结：

数组

数组能够顺序存储相同类型的多个数据。访问数组中的某个元素的方法是将其编号然后索引。如果我们有 N 个值，对于 0 到 \(N-1\) 之间的任意的 i，我们就能够使用 a[i] 唯一的表示第 i+1 个元素的值（针对一维数组）。

创建并初始化数组

在 Java 中创建一个数组需要三步： + 声明数组的名字和类型 + 创建数组 + 初始化数组元素

简化写法

为了精简代码，我们常常会利用 Java 对数组默认的初始化来将三个步骤合为一条语句。数值类型的默认初始值是 0，布尔型的默认初始值是 false。

如果想要不同的初始值，可以使用 for 循环或通过花括号将一列由逗号分隔的值在编译时将数组初始化。下图给出了完整模式和简化模式下的数组声明、创建和初始化。

使用数组

在使用数组时要注意：数组一经创建，其大小就是固定的。程序能够通过 a.length 获取数组 a[] 的长度。Java 会自动进行边界检查，访问超出边界的位置时会抛出异常。

别名

数组名表示的是整个数组。如果我们将一个数组变量赋予另一个变量，那么两个变量将会指向同一个数组：

int[] a = new int[N];
...
a[i] = 1234;
...
int[] b = a;
...
b[i] = 5678;   // a[i] is now 5678.

这种情况叫做别名，有时可能会导致难以察觉的问题（可变性的锅）。如果想复制数组，应该声明、创建并初始化一个数组，然后将原数组中的元素挨个复制到新数组。

二维数组

在 Java 中二维数组就是一维数组的数组。二维数组可以是参差不齐的（即元素数组的长度可以不一致），但大多数情况下我们都会使用 \(M\times N\)，即 M 行长度为 N 的数组的二维数组。创建二维数组的简化模式如下：

double[][] a = new double[M][N];

在 Java 中访问二维数组 a[][] 的第 i 行第 j 列的元素可以写作 a[i][j]。

静态方法

静态方法是一组在调用时会被顺序执行的语句。在许多语言中，静态方法被称为函数，因为它们和数学函数的性质类似。

定义静态方法

方法封装了一系列语句所描述的运算。方法需要参数（某种类型的值）并根据参数计算出某种数据类型的返回值或者产生某种副作用。

每个静态方法都是由签名和函数体组成的：

调用静态方法

调用静态方法的方法是写出方法名并在后面的括号中列出参数值，用逗号分隔。调用方法时，它的参数变量将被初始化为调用时所给出的相应表达式的值。返回语句将结束静态方法并将控制权交还给调用者。如果静态方法的目的是计算某个值，返回语句应该指定这个值。

方法的性质

Java 方法拥有以下几个特点： + 方法的参数按值传递：当调用一个函数时，其参数对应的值将被拷贝至参数变量。这意味着数组参数将会是原数组的别名（原数组的内容可能会被改变） + 方法名可以被重载：一个类中的方法名称可以相同，只要签名不同即可 + 方法只能返回一个值，但可以包含多个返回句：一个 Java 方法只能返回一个值。第一次执行到一条返回语句时控制权将会回到调用代码中 + 方法可以产生副作用：方法的返回值可以是 void，这表示该方法没有返回值。void 类型的方法会产生副作用（接受输入、产生输出、修改数组或者改变系统状态）

递归

递归方法是一种直接或间接调用自己的方法，编写递归代码时最重要的有以下三点： + 递归总有一个最简单的情况 + 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况 + 递归调用尝试解决的子问题之间不应该有交集

违背其中任意一条都可能得到错误的结果或是低效的代码。

基础编程模型

静态方法库是定义在一个 Java 类中的一组静态方法。Java 开发的一个基本模型是通过创建一个静态方法库（包含一个 main() 方法）编写一个程序来完成一个特定的计算任务。

模块化编程

静态方法库实现了模块化编程。一个库中的静态方法也能够调用另一个库中定义的静态方法。模块化编程能够带来很多好处：

  • 处理的模块大小适中
  • 可以共享和重用代码而无需重新实现
  • 很容易用改进的实现替换老的实现
  • 可以为解决编程问题建立合适的抽象模型
  • 缩小调试范围

单元测试

Java 编程的最佳实践之一就是每个静态方法库中都包含一个 main 函数来测试库中的所有方法。每个模块的 main() 方法至少应该调用模块中的其他代码并在某种程度上保证它的正确性。

外部库

我们会使用来自 4 个不同类型的库中的静态方法，重用每种库代码的方式稍有不同。 + 系统标准库 java.lang：包括 java.lang.Math，java.lang.Integer 和 java.lang.Double + 导入的系统库，例如 java.utils.Arrays。需要在程序的开头使用 import 语句导入 + 本书中的其他库：需要下载并放入你的工作目录中（或下载 jar 包添加路径）。放入同一目录中不需要 import，添加路径需要 import + 本书提供的标准库：同上

要调用另一个库中的方法，需要在方法前指定库的名称，如 Math.sqrt()。

API

我们会统一使用应用程序编程接口（API）的方式来列出本书中使用的每个方法库名称、签名和简短的描述。

API 的目的是将调用和实现分离。我们用客户端（client）来指代调用另一个库中方法的程序，用实现（implementation）来描述实现了某个 API 方法的 Java 代码。

下面给出一个 API 的样例：

字符串

字符串是由一串字符组成的，一个 String 类型的字面量包括一对双引号和其中的字符。String 类型是 Java 的一个数据类型，但并不是原始数据类型。

字符串拼接

Java 内置了一个串联 String 类型字符串的运算符（+），拼接两个 String 类型的字符串将得到一个新的 String 值，其中第一个字符串在前，第二个字符串在后。

类型转换

字符串的两个主要用途分别是：

  • 将用户从键盘输入的内容转换成相应数据类型的值
  • 将各种数据类型的值转化成能够在屏幕上显示的内容

举例来说，Integer 和 Double 库包含了分别和 String 类型相互转化的方法：

自动转换

Java 在连接字符串的时候会自动将任意数据类型的值转换为字符串，我们能够通过一个空字符串将任意数据类型的值转换为字符串值。

命令行参数

在 Java 中字符串的一个重要的用途就是使程序能够接收到从命令行传递来的信息。当你输入命令 java 和一个库名以及一系列字符串后，Java 系统会调用库的 main 方法并将那一系列字符串变成一个数据作为参数传递给它：

输入输出

在我们的模型中，Java 程序可以从命令行参数或者一个名为标准输入流的抽象字符流中获得输入，并将输出写入另一个名为标准输出流的字符流中：

命令和参数

终端窗口包含一个提示符，通过它我们能够向操作系统输入命令和参数。本书中会使用到如下几个命令：

标准输出

系统默认会将标准输出打印到终端窗口。本书将使用自己编写的 StdOut 库：

格式化输出

在最简单的情况下 printf 方法接收两个参数：

  • 第一个参数是一个格式字符串，描述第二个参数应该如何在输出中被转换为一个字符串
  • 第二个参数是待转换的数据

最简单的格式字符串的第一个字符是 % 并紧跟一个字符表示的转换代码。在 % 和转换代码之间可以插入一个整数来表示转换之后的值的宽度，在宽度之后还可以插入一个小数点以及数值来指定保留的小数位数或是字符串截取长度：

标准输入

我们的 StdIn 库从标准输入流中获取数据。这些数据可能为空，也可能是一系列由空白字符分隔的值（空格、制表符、换行符等）。输入流由 <ctrl-d> 或 <ctrl-z> 结束，取决于你的终端。标准输入流最重要的特点是这些值会在你的程序读取它们之后消失。

重定向与管道

只需要向启动程序的命令中加入一个简单的提示符，就可以将它的标准输出或输入重定向至一个文件。将一个程序的输出重定向为另一个程序的输入叫做管道。

基于文件的输入输出

我们的 In 和 Out 库提供了一些静态方法，来实现向文件中写入或从文件中读取一个原始数据类型（或 String 类型）的数组的抽象。借此我们可以在同一个程序中分别使用文件和标准输入输出达到两种不同的目的。

标准绘图库

我们使用 StrDraw 来绘制图像，其基本方法如下：

标准绘图库中还包含一些控制方法，用以改变画布大小、字体、颜色等：

二分查找

下面的程序实现了一个被称为二分查找的经典算法，并通过白名单过滤进行了测试：

算法是由静态方法 rank() 实现的。它接收一个整数键和一个已经有序的 int 数组作为参数，如果该键存在于数组中则返回它的索引，否则返回 -1。

算法使用两个变量 lo 和 hi，并保证如果键在数组中则它一定在 a[lo..hi] 中，然后方法进入一个循环：不断地将数组的中间键（索引为 mid）和被查找的键比较，如果被查找的键等于 a[mid] ，返回 mid；否则算法就将查找范围缩小一半，如果被查找的键小于 a[mid] 就继续在左半边查找，如果被查找的键大于 a[mid] 就继续在右半边查找。算法找到被查找的键或是查找范围为空时则该过程结束。

下图可视化了有序数组中的二分查找：

白名单过滤的过程如下：

  • 将客户的账号保存在一个文件中，我们称它为白名单
  • 从标准输入中得到每笔交易的账号
  • 使用这个测试用例在标准输出中打印所有与任何客户无关的账号，拒绝此类交易

练习

Sattolo 算法

Sattolo 算法是一种随机打乱算法，对于一个序列 0 1 2 … n-1，我们将序列的 index 看做节点，将其值看做其指向的节点，则该算法打乱的序列所构成的图必定只有一个环。

算法的基本思想是每次随机生成一个 index（不包括末尾），和序列末尾互换位置：

public class Sattolo{
  public static void cycle(Object[] a) {
    int n = a.length;
    for (int i = n; i > 1; i--) {
      // choose index uniformly in [0, i-1)
      int r = (int) (Math.random() * (i-1));
      Object swap = a[r];
      a[r] = a[i-1];
      a[i-1] = swap;
    }
  }
}

与该算法相似的算法是 Fisher-Yates 算法（Durstenfeld 版本），与 Sattolo 不同的是其允许元素与其自身互换（无偏差）。该版本可生成的组合为 n! 种，而 Sattolo 算法为 (n-1)! 种。该方法同样是一个原地算法（in-place），也可以改写为 inside-out 版本（不改变原数组）。

思维导图