抽象数据类型 Data Abstraction

Programming in Java is largely based on building data types.

This style of programming is known as object-oriented programming, as it revolves around the concept of an object, an entity that holds a data type value.

数据类型：

一组值和一组对值操作的集合

1.2.1 使用数据类型

对象：

能够存储任意该数据类型的值的实体

对象有3大特性：

状态：数据类型中的值

标识：内存中的位置（区别一个对象和另一个）

行为：数据类型的操作，API

创建对象:

为对象分配内存空间

调用构造函数初始化对象中的值

返回该对象的引用

静态方法和非静态方法

静态方法调用的开头是类名，主要作用是实现函数

非静态方法/实例方法的开头是对象名，主要是实现数据类型的操作

赋值语句

引用类型变量的赋值会创建引用的副本

原始数据类型变量的赋值是真的复制的值

将对象作为参数传递

其实是传递对象的引用，函数能够改变对象的值

将对象作为返回值返回

虽然Java只能有一个返回值，但返回对象代码实际上就可以返回很多值

1.2.2 抽象数据类型举例

Point2D.java is a data type for points in the plane.

Interval1D.java is a data type for one-dimensional intervals.

Interval2D.java is a data type for two-dimensional intervals.

Information processing. Abstract data types provide a natural mechanism for organizing and processing information. the information

Date.java is a data type that represents the day, month, and year.

Transaction.java is a data type that represents a customer, a date, and an amount.

Accumulator. Accumulator.java defines an ADT that provides to clients the ability to maintain a running average of data values. For example, we use this data type frequently in this book to process experimental results. VisualAccumulator.java in an enhanced version that also plots the data (in gray) and the running average (in red).

Strings. Java's String data type in an important and useful ADT.

1.2.3 抽象数据类型的实现

实例变量，构造函数，实例方法 scope作用域

1.2.5 数据类型的设计

Encapsulation（封装）

 A hallmark of object-oriented programming is that it enables us to encapsulate data types within their implementations, to facilitate separate development of clients and data type implementations. Encapsulation enables modular programming.

Designing APIs

One of the most important and most challenging steps in building modern software is designing APIs. Ideally, an API would clearly articulate behavior for all possible inputs, including side effects, and then we would have software to check that implementations meet the specification.

Algorithms and ADT

Data abstraction is naturally suited to the study of algorithms, because it helps us provide a framework within which we can precisely specify both what an algorithm needs to accomplish and how a client can make use of an algorithm.

Interface inheritance

Java provides language support for defining relationships among objects, known as inheritance. The first inheritance mechanism that we consider is known as subtyping, which allows us to specify a relationship between otherwise unrelated classes by specifying in an interface a set of common methods that each implementing class must contain. We use interface inheritance for comparison and for iteration.

Implementation inheritance.

Java also supports another inheritance mechanism known as subclassing, which is a powerful technique that enables a programmer to change behavior and add functionality without rewriting an entire class from scratch. The idea is to define a new class (subclass) that inherits instance methods and instance variables from another class (superclass). We avoid subclassing in this book because it generally works against encapsulation. Certain vestiges of the approach are built in to Java and therefore unavoidable: specifically, every class is a subclass of Object.

Immutability. 

An immutable data type has the property that the value of an object never changes once constructed. By contrast, a mutable data type manipulates object values that are intended to change. Java's language support for helping to enforce immutability is the final modifier. When you declare a variable to be final, you are promising to assign it a value only once, either in an initializer or in the constructor. Code that could modify the value of a final variable leads to a compile-time error.

Vector.java is an immutable data type for vectors. In order to guarantee immutability, it defensively copies the mutable constructor argument.

---

Q + A.

Q. Are there any truly immutable classes in Java?

A. If you use reflection, you can access the private fields of any class and change them. Program MutableString.java demonstrates how to mutate a String. Program MutableInteger.java demonstrates that this is true even if the instance variable is final.

---

Exercises

Write a Point2D.java client that takes an integer value N from the command line, generates N random points in the unit square, and computes the distance separating the closest pair of points.

What does the following code fragment print?

String string1 = "hello";

String string2 = string1;

string1 = "world";

StdOut.println(string1);

StdOut.println(string2);

Solution:

world

hello

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular shifts of one another.

Solution: (s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)

What does the following recursive function return?

public static String mystery(String s) {

    int N = s.length();

    if (N <= 1) return s;

    String a = s.substring(0, N/2);

    String b = s.substring(N/2, N);

    return mystery(b) + mystery(a);

}

Solution: Reverse of the string.

Using our implementation of Date.java as a model, develop an implementation of Transaction.java.

Using our implementation of equals() in Date.java as a model, develop an implementation of equals() for Transaction.java.

Creative Problems

Rational numbers. Implement an immutable data type Rational.java for rational numbers that supports addition, subtraction, multiplication, and division.

You do not have to worry about testing for overflow, but use as instance variables two long values that represent the numerator and denominator to limit the possibility of overflow. Use Euclid's algorithm to ensure that the numerator and denominator never have any common factors. Include a test client that exercises all of your methods.

Sample variance for accumulator. Validate that the following code, which adds the methods var() and stddev() to Accumulator.java to compute the mean, sample variance, and sample standard deviation of the numbers presented as arguments to addDataValue().

Reference: Here is a good explanation of this one-pass method, that was first discovered by Welford in 1962. This approach can be applied to computing the skewness, kurtosis, regression coefficients, and Pearson's correlation coefficient.

Parsing. Develop the parse constructors for your Date.java and Transaction.java implementations that take a single String argument to specify the initialization values, using the formats given in the table below.