基础编程模型

描述和实现算法所用到的语言特性、软件库和操作系统称为基础编程模型

Java 程序的基本结构

• 原始数据类型：在计算机程序中精确地定义整数、浮点数和布尔值等。其定义包括取值范围和能够对相应的值进行的操作。
• 语句：声明、赋值、条件、循环、调用和返回。
• 数组：多个数据类型的值的集合
• 静态方法：可以封装并重用代码，使我们可以用独立的模块开发程序
• 字符串
• 标准输入/输出：是程序与外面联系的桥梁
• 数据抽象：数据抽象封装和重用代码，使我们可以定义非原始数据类型，进而支持面向对象编程

原始数据类型和表达式

四种 Java 语言最基本的原始数据类型：

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

Java 程序控制用 标识符 命名 变量；用 表达式 实现对各种类型的操作；用运算符来指定操作；用字面量来表示具体的值。

Java程序的基本组成

原始数据类型

下表总结了 Java 的int、double、bolean和char类型的相关信息。

+、-、*、/ 运算符都是被 重载 过的，同样的运算符对不同的数据类型会执行不同的操作。例如，5/3 的值是1 而 5.0/3.0 的值是1.66666666666667，两者都很接近但是并不准确地等于5/3。

Java中的原始数据类型

Java中的原始数据类型（续）

表达式

当一个表达式包含一个以上运算符时，运算符优先级：

• 算数运算符中， * / % > + -
• 逻辑运算符中，! > && > ||
• 括号可以改变优先级

类型转换

• 自动类型提升
  如果不会损失信息，数值会被自动提升为高级的数据类型。
  例如：在表达式 1 + 2.5 中， 1 会被转换为浮点数 1.0 ，表达式的值为 double 值 3.5
• 强制类型转换
  表达式把类型名放在括号里将其后的值转换为括号中的类型。
  例如：(int)3.7 的值是3 而(double)3 的值是3.0
  注意：将浮点型转换为整型会截断小数部分而非四舍五入。

比较运算符

比较运算符：相等( == )、不等( != )、小于( < )、小于等于( > )、大于( >= )、大于等于( <= )。

其他数据类型

64位整数 - long
16位整数 - short
16位字符 - char
8位整数 - byte
32位单精度实数 - float

语句

声明语句

声明语句将一个变量名和一个类型在编译时关联起来。Java是 强类型 语言，编译器会检查类型的一致性。

赋值语句

赋值语句将（由一个表达式定义的）某个数据类型的值和一个变量关联起来。

• 隐式赋值：
  ++i 等价于 i = i +1 ,且表达式值为 i+1
  --i 等价于 i = i -1 ,且表达式值为 i+1
  i++ 等价于 i = i +1 ,且表达式值为 i
  i-- 等价于 i = i -1 ,且表达式值为 i

条件语句

• if 语句：if (<boolean expression>) { <block statements>}
• if-else 语句

循环语句

• while 循环：while (<boolean expression>) { <block statements>}

• for 循环：

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

等价于：

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

单语句代码段：如果条件或循环的代码段只有一条语句，代码段的花括号可以省略。

调用和返回语句

• 调用语句：调用方法。
  int key = StdIn.readInt();
• 返回语句：从方法中返回。
  return false;

break 和 continue 语句

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

数组

数组能够顺序存储相同类型的多个数据。除了存储数据，我们也希望能够访问数据。访问数据的某个元素的方法是将其编号然后索引。

创建并初始化数组

创建数组的三步：

• 声明数组的名字和类型。
• 创建数组。

• 初始化数组元素。

  
  
  声明、创建并初始化一个数组

使用数组

• 在声明和创建数组a[]之后，在代码的任何地方都能通过a[i]来访问其中索引为 i 的元素。
• 数组一经创建，它的大小就是固定的。
• 程序能够通过 a.length获取数组a[]的长度，而它的最后一个元素总是a[a.length-1]。
• Java会自动进行边界检查，如果你创建了一个大小为N的数组，但使用了一个<0或者>N-1的索引访问它，程序会因为运行时抛出 ArrayOutOfBoundsException 异常而终止。

典型的数组处理代码：

1. 找出数组中最大的元素：

double max = a[0];
for (int i = 0; i < a.length; i++)
  if (a[i] > a[0]) max = a[i];

2. 计算数组元素的平均值

int N = a.length;
double sum = 0.0;
for (int i = 0; i < N; i++)
  sum += a[i];
double average = sum / N;

3. 复制数组

int N = a.length;
double[] b = new double[N];
for (int i = 0; i < N; i++)
  b[i] = a[i];

4. 颠倒数组元素的顺序

int N = a.length
for (int i = 0; i < N; i++)
{
  double temp = a[i];
  a[i] = a[N-1-i];
  a[N-1-i] = temp;
}

5. 矩阵相乘a[][]*b[][]=c[][]

int N = a.length;
double[][] c = new c[N][N];
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
  {
    for (int k = 0; k < N; k++)
      c[i][j] = a[i][k] * b[k][j];
  }

起别名

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

int[] a = new int[N];
a[i] = 1234;
int[] b = new a;
b[i] = 5678; // a[i] 的值也会变成 5678

这种情况叫做起别名。如果你想将数组复制一份，应该声明、创建并初始化一个新数组，然后将原数组中的元素挨个赋值给新数组。

二维数组

• 在java中二维数组就是一维数组的数组。创建二维数组：double[][] a = new double[M][N]
• 二维数组 a[][] 的第 i 行第 j 列的元素可以写作 a[i][j]。

静态方法

静态方法封装了由一系列语句所描述的运算。方法需要参数（某种数据类型的值）并根据参数计算出某种数据类型的返回值（例如数学函数的结果）或者产生某种副作用（例如打印一个值）。静态方法与实例方法的区别是静态方法有static修饰符。

静态方法解析

典型的静态方法的实现：

1. 计算一个整数的的绝对值：

public static int abs()
{
  if (x < 0) return -x;
  else return x;
}

2. 计算一个浮点数的绝对值

public static double abs(double x)
{
  if (x < 0.0) return -x;
  else return x;
}

3. 判断一个数是否是素数

public static boolean isPrime(int N)
{
  if (N < 2) return false;
  for (i = 0; i*i <= N; i++)
    if (N % i == 0) return false;
  return true;
}

4. 计算平方根（牛顿迭代法）

public static double sqrt(double c)
{
  if (c < 0) return Double.NaN;
  double err = 1e-15;
  double t = c;
  while (Math.abs(t - c/t) > err * t)
    t = (c/t + t) / 2.0;
  return t;
}

5. 计算直角三角形的斜边

public static double hypothenuse(double a, double b)
{
  return Math.sqrt(a*a + b*b);
}

6. 计算调和级数

public static double H(int N)
{
  double sum = 0.0;
  for (int i = 1; i <= N; i++)
    sum += 1.0 / i;
  return sum;
}

方法的性质

• 方法的参数按值传递：方法中使用参数变量能够引用调用者的数组并改变其内容，但是不能改变数组变量本身。
• 方法名可以被重载：重载的常见用法是定义参数不同的同名函数。
• 方法只能返回一个值，但可以包含多个返回语句。
• 方法可以产生副作用：接受输入、产生输出、修改数组或改变系统状态。例如，静态方法 main() 的返回值就是 void，因为它的作用是向外输出。

递归

递归就是方法调用自己。编写递归代码最重要有以下三点：

1. 递归总有一个最简单的情况 —— 方法的第一条语句总是包含return的条件语句。
2. 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能手链到最简单的情况。在下面的代码中，第四个参数和第三个参数的差值一直在缩小。
3. 递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中，两个子问题各自操作的数组部分是不同的。

二分查找的递归实现：

public static int rank(int key, int[] a)
{
  rank(key, a, 0, a.length -1)
}
public static int rank(int key, int[] a, int lo, int hi)
{
  if (lo > hi) return -1;
  int mid = lo + (hi - lo) / 2;
  if (key < a[mid]) return rank(key, a, lo, mid - 1);
  else if (key > a[mid]) return rank(key, a, mid + 1,hi);
  else return mid;
}

违背以上三条的任意一条都可能得到错误的结果或是低效的代码。而坚持这些原则则能写出清晰、正确容易评估性能的程序。

基础编程模型

静态方法库 是定义一个 Java 类中的一组静态方法。类的声明是public class加上类名，以及用花括号包含的静态方法。存放类的文件的文件名和类名相同，扩展名是.java。Java开发的基本模式是编写一个静态方法库（包含一个main()方法）来完成一个任务。控制台输入 java 库名 参数就能调用库类中的main()方法，其参数为由输入的字符串组成的一个数组。

模块化编程

基础编程模型的最重要之处在于通过静态方法实现了模块化编程。我们可以构造许多个静态方法库，一个库中的静态方法也能够调用另一个库中定义的静态方法。
好处：

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

单元测试

Java编程的最佳实践之一就是每个静态方法库中都包含一个main()函数来测试库中所有的方法。（有些编程语言不支持多个main()方法，因此不支持这种方式）。
main() 方法可以用来：

• 开发用例：在开发过程中用它来测试更多的细节
• 测试用例：用来所有代码进行全面测试。
  （用例指代调用另一个库中的方法的程序。）

外部库

• 系统标准库 java.lang.*：包括 Math 库，实现了常用的数学函数；Interger 和 Double 库，能够将字符串转换为 int 和 double 值；String 和 StringBuilder 库等。无需导入。
• 导入的系统库：例如 java.util.Arrays。要在程序的开头 import 语句导入使用这些库。

• 我们的标准库：例如，其他程序也可以使用 BinarySearch的rank()方法。要使用这些库需要将源代码放入工作目录，或者使用 import 语句引用该程序的 jar 包。

  
  
  《算法（第四版）中使用的含有静态方法的库》

API

模块化编程的重要组成部分就是记录库方法的用法并供他人参考的文档。我们会统一的使用应用程序编程接口（API）的方式列出书中使用的每个库方法名称、签名和简短的描述。

java.lang 中 Math 库 的 API

Java的数学函数库的API

Java 库

Arrays 库不在 java.lang 中，因此我们需要用 import 语句导入后才能使用它。

Java 的 Arrays 库节选（java.util.Arrays）

书中的标准库

《算法（第四版）》一书中提供了以下库来提供一些使用的功能，大多数用于处理输入输出，还有以下两个库用来测试和分析我们的实现：

1. StdRandom 库扩展了Math.random()的方法。

   
   
   随机数静态方法库的 API
   
   

   StdRandom 的 initialize() 方法为随机数生成器提供种子，这样我们，这样我们就可以重复和随机数有关的实验。

2. 各种统计计算的库。

   
   
   数据分析的静态方法库的 API

设计良好的方法库的好处：

• 这些方法所实现的抽象层有助于我们将精力集中在实现和测试算法，而非生成随机数或是统计计算。
• 方法库会经过大量测试，覆盖极端和罕见的情况，是我们可以信任的。这样的实现需要大量的代码。例如，Java 的 Arrays 库针对不同数据类型对sort()进行了多次重载。

StdRandom库的静态方法的实现：

1. 随机返回[a,b)之间的一个double值：

public static double uniform(double a, double b)
{
  return a + StdRandom.random() * (b-a);
}

2. 随机返回[0, N)之间的一个int值：

public static double uniform(int N)
{
  return (int) (StdRandom.random() * N);
}

3. 随机返回[lo, hi) 之间的一个int值：

public static int uniform(lo, hi)
{
  return lo + StdRandom.unifom(hi - lo);
}

4. 根据离散概率随机返回的int值（出现 i 的概率为a[i]）

public static int discrete(double[] a)
{
  double r = StdRandom.random();
  double sum = 0.0;
  for (int i = 0； i < a.length; i++)
  {
    sum = sum + a[i];
    if (sum >= r) return i;
  }
  return -1;
}

5. 将 double 数组中的元素打乱

public static void shuffle(double[] a)
{
  int N = a.length;
  for (int i = 0; i < N; i++)
  {
    int r = i + StdRandom.uniform(N-i);
    double temp = a[i];
    a[i] = a[r];
    a[r] = temp;
  }
}

自己编写的库

我们应该将自己编写的每一个程序都当做一个日后可以重用的库。

• 编写用例，在实现中将计算过程分解成可控的部分。
• 明确静态方法库和与之对应的 API
• 实现 API 和一个能够对方法进行独立测试的 main() 函数。
  这不仅能帮助我们实现可重用的代码，而且能够教会我们如何运用模块化编程来解决一个复杂的问题。
  API的目的是将调用和实现分离。API使我们能够广泛的重用代码。使我们可以将老算法替换为更新更好的实现。

字符串

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

字符串拼接

使用 + 运算符进行拼接。

类型转换

字符串的两个主要用途是将用户从键盘输入的内容转换成相应数据类型的值以及将各种数据类型的值转化成能够在屏幕上显示的内容。Java 的 String 类型为这些操作内置了相应的方法。

String 值和数字之间相互转换的 API

自动转换

如果加号的一个参数是字符串，那么Java会自动将其他类型都转换为字符串。

命令行参数

在 Java 中字符串的一个重要用途就是使程序能够接收从命令行传递来的信息。当输入在控制台命令java 库名 字符串1 字符串2 ...时，Java系统会调用库类中的main()方法将字符串1，字符串2等一系列字符串变成一个数组作为参数传递给main方法。我们在代码中常见的用法是当命令行参数表示的是数字的时候，用parseInt()和paseDouble()方法将其分别转换为整数和浮点数。
字符串的用法是现代程序的重要部分。

输入输出

命令和参数

Java类中都会包含一个静态方法 main()，它有一个String数组类型的参数 args[]。这个数组的内容就是我们输入的命令行参数，操作系统会将它传递给 Java。Java 和操作系统默认参数为字符串。如果我们需要某个参数是数字，我们会使用类似 Interger.parseInt() 的方法将其转换为适当的数据类型的值。

操作系统常用命令

标准输出

《算法（第四版）》一书中将标准输入输出封装为StdIn和StdOut库。

StdOut库

我们来看看这个StdOut标准输出库的代码实现：

package edu.princeton.cs.algs4;

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;

public final class StdOut {

    // force Unicode UTF-8 encoding; otherwise it's system dependent
    private static final String CHARSET_NAME = "UTF-8";

    // assume language = English, country = US for consistency with StdIn
    private static final Locale LOCALE = Locale.US;

    private static PrintWriter out;

    // this is called before invoking any methods
    static {
        try {
            out = new PrintWriter(new OutputStreamWriter(System.out, CHARSET_NAME), true);
        }
        catch (UnsupportedEncodingException e) {
            System.out.println(e);
        }
    }

    // don't instantiate
    private StdOut() { }

    public static void println() {
        out.println();
    }

    public static void println(Object x) {
        out.println(x);
    }

    public static void println(boolean x) {
        out.println(x);
    }

    public static void println(char x) {
        out.println(x);
    }

    public static void println(double x) {
        out.println(x);
    }

    public static void println(float x) {
        out.println(x);
    }

    public static void println(int x) {
        out.println(x);
    }

    public static void println(long x) {
        out.println(x);
    }

    public static void println(short x) {
        out.println(x);
    }

    public static void println(byte x) {
        out.println(x);
    }

    public static void print() {
        out.flush();
    }

    public static void print(Object x) {
        out.print(x);
        out.flush();
    }

    public static void print(boolean x) {
        out.print(x);
        out.flush();
    }

    public static void print(char x) {
        out.print(x);
        out.flush();
    }

    public static void print(double x) {
        out.print(x);
        out.flush();
    }

    public static void print(float x) {
        out.print(x);
        out.flush();
    }

    public static void print(int x) {
        out.print(x);
        out.flush();
    }

    public static void print(long x) {
        out.print(x);
        out.flush();
    }

    public static void print(short x) {
        out.print(x);
        out.flush();
    }

    public static void print(byte x) {
        out.print(x);
        out.flush();
    }

    public static void printf(String format, Object... args) {
        out.printf(LOCALE, format, args);
        out.flush();
    }

    public static void printf(Locale locale, String format, Object... args) {
        out.printf(locale, format, args);
        out.flush();
    }

    public static void main(String[] args) {
        // write to stdout
        StdOut.println("Test");
        StdOut.println(17);
        StdOut.println(true);
        StdOut.printf("%.6f\n", 1.0/7.0);
    }

}

• 在StdOut的类中我们在静态代码块中创建PrintWriter对象，创建一个基于字符的输出流。
  静态代码块的特点：随着类的加载而执行，而且只加载一次。
  静态代码块的执行优先级优于非静态的初始化块，它会在类初始化的时候执行一次，执行完成便销毁。
• flush()方法解释：参考博客

在冯诺依曼体系结构中，计算机由控制器、运算器、存储器、输入设备、输出设备五部分组成。其中运算器、控制器（还有一些寄存器）是CPU的组成成分。存储器则分为内存储器（内存）和外存储器（外存）。输入输出设备主要用来完成系统的I/O操作。I/O操作主要对硬盘的数据进行读和取。CPU不能直接访问外存（硬盘），而需要借助内存来完成对硬盘数据的读/取操作。由于CPU的运算速度远远大于I/O操作，因此当一个进程需要产生许多I/O操作时，会耗费许多系统资源，同时也不利于进程之间的资源竞争，导致系统资源利用率下降。

JAVA中的输入/输出流在默认的情况下是不被缓存区缓存的，因此，每发生一次read()方法和write()方法都需要请求操作系统再分发/接收一个字节，这样程序的运行效率必然会降低，相比之下，请求一个数据块并将其置于缓冲区中会显得更加高效。我们考虑可以将硬盘中的数据事先添加到预定义范围（大小合适）的缓冲池中来预存数据，待CPU产生I/O操作时，可以从这个缓存池中来读取数据，这样便减少了CPU的I/O的次数，提高了程序的运行效率。事实上JAVA也正是采取这种方式，通过为基本流添加处理流（缓冲机制）来减少I/O操作的次数。

read()方法和write()方法是线程阻塞的，也就是说，当某个线程试图向另一端网络节点读取或写入数据时，有可能会发生网络连接异常或者是服务器短期没有响应，同样的，在无数据状态进行读取，数据已满进行写操作时，同样会发生阻塞，这时，其他线程抢占资源后继续执行。如果出现此现状，读取到缓冲池中的数据不能够及时的发送到另一端的网络节点，需要该线程再次竞争到CPU资源才可正常发送。

还有一种情况，当我们将数据预存到缓冲池中时，当数据的长度满足缓冲池中的大小后，才会将缓冲池中的数据成块的发送，若数据的长度不满足缓冲池中的大小，最终导致这部分的数据停留在缓冲池无法发送。

这时，就需要我们在write()方法后，手动调用flush()方法，强制刷出缓冲池中的数据（即使数据长度不满足缓冲池的大小）从而保证数据的正常发送。当然，当我们调用流的close()方法后，系统也会自动将缓冲区的数据刷出，同时可保证流的物理资源被回收。

OutputStream抽象基类中的方法