算法之程序模型
我们对算法的研究是基于将它们实现为用Java编程语言编写的程序。 我们这样做有几个原因：
- 我们的程序是简洁，优雅，完整的算法描述。
- 您可以运行程序来研究算法的属性。
- 您可以立即在应用程序中使用算法。
原始数据类型和表达式
数据类型 是一组值和一组对这些值的操作。以下四种基本数据类型是Java语言的基础：- 整数，带算术运算（int）
- 实数，再次与算术运算(double)
- 布尔值，带有逻辑运算符的值{true，false}的集合（布尔）
- 字符，您键入的字母数字字符和符号（char）
下表总结了对于Java的int，double，boolean和char数据类型的值的集合和最常见的操作。
- 表达式。 典型的表达式是中缀。 当表达式包含多个运算符时，优先级顺序指定它们的应用顺序：运算符*和/（和％）的优先级高于（应用于）+和 - 运算符; 在逻辑运算符之间！ 是最高优先级，后跟&&和然后||。 通常，相同优先级的运算符是左关联的（从左到右应用）。 您可以使用括号来覆盖这些规则。
- 类型转换。 如果没有丢失信息，则数字将自动提升为更具包容性的类型。例如，在表达式1 + 2.5中，1被提升为双精度值1.0，表达式的值为双精度值3.5。 转换是将一个类型的值转换为另一个类型的值的指令。 例如（int）3.7是3.将double转换为int将截断到零。
- 比较。 以下混合类型运算符比较相同类型的两个值并生成布尔值：
- 相等 (==)
- 不等 (!=)
- 小于 (<)
- 小于等于 (<=)
- 大于 (>)
- 大于等于 (>=)
- 其他原语类型。
Java的int有一个32位的表示; Java的double类型具有64位表示。 Java有五种额外的原始数据类型：
- 64位整数，带算术运算（长整型）
- 16位整数，带算术运算（短）
- 16位字符，带算术运算（char）
- 8位整数，带算术运算（字节）
- 32位单精度实数，带算术运算（float）
语句
Java程序由语句组成，语句通过创建和操作变量，为其分配数据类型值以及控制这些操作的执行流程来定义计算。- 声明创建指定类型的变量，并用标识符命名它们。 Java是一种强类型语言，因为Java编译器检查一致性。 变量的范围是定义它的程序的一部分。
- 分配将数据类型值（由表达式定义）与变量关联。
- 初始化声明将声明与赋值相结合，以便在声明变量的同时初始化变量。
- 隐式分配。 当我们的目的是修改变量相对于当前值的值时，可以使用以下快捷键：
- 递增/递减运算符：代码i ++是i = i + 1的缩写。除了表达式值是在递增/递减之后，而不是之前，代码++ i是相同的。
- 其他复合运算符：代码i / = 2是i = i / 2的缩写。
- 条件提供了执行流程的简单改变 - 根据指定的条件，在两个块中的一个块中执行语句。
- 循环提供了执行流程中更深刻的变化 - 只要给定条件为真，就执行块中的语句。 我们将循环中的块中的语句称为循环体。
- break和continue。 Java支持在while循环中使用两个附加语句：
- break语句，它立即退出循环
- continue语句，它立即开始循环的下一次迭代
- 符号。 许多循环遵循这个方案：将索引变量初始化为某个值，然后使用while循环测试涉及索引变量的循环继续条件，其中while循环中的最后一个语句增加索引变量。 你可以用Java的表示法来表达这样的循环。
- 单语句块。 如果条件或循环中的语句块只有一个语句，则可以省略花括号。
数组。
数组存储所有相同类型的值序列。 如果我们有N个值，我们可以使用符号a [i]来指代从0到N-1的i的任何值的第i个值。- 创建和初始化数组。 在Java程序中创建数组涉及三个不同的步骤：
- 声明数组的类型和名称
- 创建数组
- 初始化数组的值
- 默认数组初始化。 对于代码更简洁，我们经常利用Java的默认数组初始化约定，并将所有三个步骤组合成一个语句。 对于数字类型，默认初始值为零，对于类型布尔值为false。
- 初始化声明。 我们可以在编译时指定初始化值，方法是在花括号之间列出文字值，用逗号分隔。
- 使用数组。 一旦我们创建一个数组，它的大小是固定的。 程序可以使用代码a.length引用数组a []的长度。 Java执行自动边界检查 - 如果你访问一个非法索引的数组，你的程序将终止ArrayIndexOutOfBoundsException。
- 别名。 数组名称引用整个数组 - 如果我们将一个数组名称指定给另一个数组名称，那么它们都引用相同的数组，如下面的代码片段所示。
这种情况被称为混叠，并且可能导致微妙的错误。
1 2 3 4 5 6 7
int[] a = new int[N]; ... a[i] = 1234; ... int[] b = a; ... b[i] = 5678; // a[i] is now 5678. - 二维数组。 Java中的二维数组是一维数组的数组。 二维阵列可以是粗糙的（其阵列可以都具有不同的长度），但是我们最常使用（对于适当的参数M和N）M乘N的二维阵列。 为了引用二维数组a [] []的行i和列j中的条目，我们使用符号a [i] [j]。
静态方法。
静态方法在许多编程语言中被称为函数，因为它们可以表现得像数学函数。 每个静态方法是一系列语句，它们在调用静态方法时一个接一个执行。- 定义静态方法。 方法封装被定义为语句序列的计算。 方法接受参数（给定数据类型的值），并计算一些数据类型的返回值或导致副作用。 每个静态方法由签名和主体组成。
- 调用静态方法。 对静态方法的调用是其名称，后跟表达式，指定括号中的参数值，用逗号分隔。 当一个方法被调用时，它的参数变量用调用中相应表达式的值初始化。 返回语句终止静态方法，将控制权返回给调用者。 如果静态方法是计算值，则必须在return语句中指定该值。
- 方法的属性。 Java方法具有以下特性：
- 参数通过值传递。 调用函数时，参数值将完全求值，并将结果值复制到参数变量中。 这称为值传递。 数组（和其他对象）引用也通过值传递：方法不能更改引用，但它可以更改数组中的条目（或对象的值）。
- 方法名称可以重载。 类中的方法可以具有相同的名称，只要它们具有不同的签名。 此功能称为重载。
- 方法具有单个返回值，但可能有多个返回语句。 Java方法只能提供一个返回值。 一旦达到第一个return语句，控制就返回调用程序。
- 一种方法可能有副作用。 方法可以使用关键字void作为其返回类型，以指示它没有返回值，并产生副作用（消耗输入，产生输出，改变数组中的条目，或以其它方式改变系统的状态）。
- 递归。 递归方法是直接或间接调用自身的方法。 开发递归程序有三个重要的经验法则：
- 递归具有基本案例。
- 递归调用必须解决在某种意义上较小的子问题，因此递归调用会收敛到基本情况。
- 递归调用不应解决重叠的子问题。
- 基本编程模型。 静态方法库是一组在Java类中定义的静态方法。 Java编程的基本模型是开发一个程序，通过创建一个静态方法库，其中一个名为main（），来解决特定的计算任务。
- 模块化编程。 静态方法的库允许模块化编程，其中一个库中的静态方法可以调用其他库中定义的静态方法。 这种方法有许多重要的优点。
- 使用合理大小的模块
- 共享和重用代码，而不必重新实现它
- 替代改进的实现
- 为解决编程问题开发适当的抽象模型
- 本地化调试
- 单元测试。 Java编程的最佳实践是在每个测试库中的方法的静态方法库中包含一个main（）。
- 外部库。 我们使用来自四种不同类型库的静态方法，每种都需要（略）不同的代码重用程序。
- java.lang中的标准系统库，包括java.lang.Math，java.lang.Integer和java.lang.Double。
- 导入的系统库，如java.util.Arrays。 在程序开始时需要一个import语句来使用这样的库。
- 我们开发用的标准库。 要使用这样的程序，请将源码下载到您的工作目录中，或按照以下说明将stdlib.jar添加到类路径中。
字符串
- 串联
- 转换
- 自动转换。
- 命令行参数。
输入与输出
- 命令和参数。
- 标准输出
- 格式化输出
- 标准输入
- 重定向和管道。
- 从文件输入和输出。
- 标准绘图
二进制搜索。
下面是一个完整的Java程序BinarySearch.java，它说明了我们的编程模型的许多基本特性。 它实现了一种称为二进制搜索的经典算法，并针对称为白名单过滤的应用程序对其进行测试。
静态方法rank（）使用整数键和int值的排序数组作为参数，并返回键的索引（如果它存在于数组中），否则为-1。 它通过维护变量lo和hi来完成这个任务，使得如果在数组中，则密钥在[lo..hi]中，然后进入测试间隔中的中间条目（在索引mid）的循环。 如果键等于[mid]，返回值为mid; 否则，该方法将大约一半的间隔大小，如果该键小于a [mid]，则查看左半部分，如果该键大于[mid]，则查看右半部分。 当找到键或间隔为空时，进程终止。
- 开发客户端
- 白名单
- 性能
输入和输出库。 这里是一个输入和输出库的列表.
标准输入和标准输出。 StdIn.java和StdOut.java是用于从标准输入中读取数字和文本以及将数字和文本打印到标准输出的库。 我们的版本有一个比相应的Java接口更简单的接口（并提供一些技术改进）。 RandomSeq.java生成给定范围内的随机数。 Average.java从标准输入读取一系列实数，并在标准输出上打印它们的平均值。
1 2 3 4 5 | |
标准绘制。 StdDraw.java是一个易于使用的库，用于绘制几何形状，如点，线和圆。 RightTriangle.java绘制一个直角三角形和一个外接圆。 Draw.java是一个面向对象的版本，支持在多个窗口中绘制。
标准音频。 StdAudio.java是一个易于使用的库合成声音。 Tone.java从命令行读取频率和持续时间，并且在给定持续时间内声化给定频率的正弦波。
1
| |
图像处理。 Picture.java是一个易于使用的图像处理库。 Scale.java使用图片文件的名称和两个整数（width w和height h）作为命令行参数，并将图像缩放为w-by-h。