《数据结构与抽象——Java语言描述》第一章学习笔记
感想：以前学数据结构关注于方法及实现，为了完成作业和手写代码，没有从设计层面考虑过，第一章设计一个bag ADT，借助于Java interface实现ADT的规范说明，然后在实现之前通过Java语句来确认或者修改方法的设计决策及相关文档，且这些代码可以作为后续测试实现。
Points:
- 对要讨论的类，要在实现它们之前使用类似CRC卡和UML这样的工具仔细说明方法；
- 设计了ADT草稿后，通过写使用ADT的伪代码，确认你理解了操作及它们的设计；
- 应该说明遇到特殊情况时方法应该采取的动作；
- 组织ADT规格说明的一种方式是写一个Java接口；
- 在定义类之前写一个测试它的程序，看看你是否完全理解并满意类中方法的规格说明。
将包（bag）视为一种集合，定义该集合的操作。
- 说明一个包
描述它的数据，并详细说明对应于包行为的方法。（命名方法，选择它们的参数，确定它们的返回值类型，写出注释充分描述它们对包数据的影响）---> Java头和注释
1.1 UML描述
返回包中当前的项数：+getCurrentSize(): Integer
判断是否为空：+isEmpty(): Boolean
注：通过getCurrentSize是否为0就可判断是否为空，并不是真的需要操作isEmpty，但是它是所谓的便利方法（convenience method）
添加给定的对象：+add(newEntry: T): boolean
删除包中所有项：+clear(): void
删除一项：+remove(): T
删除特定项：+remove(anEntry: T): Boolean(或者返回T)
统计某个对象的次数：+getFrequencyOf(anEntry: T): integer
包中是否含有某对象：+contains(anEntry: T): boolean
返回数组：+toArray(): T[]（定义一个方法返回保存这些项的数组，通常定义一个新的数组来返回）
1.2 设计决策（特殊条件）
类的设计者，必须要做出决定如何处理特殊条件，并将这些决策包含在规格说明中。ADT包的文档应该反映这些决策和前面的细节。
- 假定无效的情形不能发生： 方法可以声明一种假设（即前置条件），这是客户必须遵守的限制。由客户检查在方法调用前这个前置条件是否满足。
- 忽略无效情形：给出无效数据时方法可能什么也不做。客户也不知道发生了什么。
- 猜测客户的意图：同上，可能给客户带来麻烦。
- 返回一个表示问题的值：for example，若客户试图从空包中remove一项时，remove方法应该返回null。返回的值必须是不在包中的值。
- 返回一个布尔值，表示操作的成功或失败。
- 抛出一个异常。
注1：抛出异常经常是Java方法运行期间处理遇到的特殊事件的理想方法。
注2：ADT规格说明的草稿写完大部分内容，可以专注这些异常情况做详细说明。
1.3 一个接口
在实现类之前写接口，可以让你以简洁的方式记录你的规格说明。然后可将接口中的代码用在具体类的框架中。接口为包提供数据类型，不依赖于具体类的实现，也可以做到，同一种接口不同实现。
BagInterface.java
/**
* An interface that describes the operations of a bag of objects.
* @author Administrator
*
*/
public interface BagInterface <T> {
/**
* Gets the current number of entries in this bag.
* @return: The integer number of entries currently in the bag.
*/
public int getCurrentSize(); /**
* Sees whether this bag is empty.
* @return: True if the bag is empty, or false if not.
*/
public boolean isEmpty(); /**
* Adds a new entry to this bag.
* @param newEntry: The object to be added as a new entry.
* @return: True if the addition is successful, or false if not.
*/
public boolean add(T newEntry); /**
* Removes one unspecified entry from this bag, if possible.
* @return: Either the removed entry, if the removel was successful, or null.
*/
public T remove(); /**
* Removes one occurrence of a given entry from this bag, if possible.
* @param anEntry: The entry to be removed.
* @return: True if the removal was successful, or false if not.
*/
public boolean remove(T anEntry); /**
* Removes all entries from this bag.
*/
public void clear(); /**
* Counts the number of times a given entry appears in this bag.
* @param anEntry: The entry to counted.
* @return: The number of times anEntry appears in the bag.
*/
public int getFrequencyOf(T anEntry); /**
* Tests whether this bag contains a given entry.
* @param anEntry: The entry to locate.
* @return: True if the bag contains anEntry, or false if not.
*/
public boolean contains(T anEntry); /**
* Retrieves all entries that are in this bag.
* @return: A newly allocated array of all the entries in the bag.
* Note: If the bag is empty, the returned array is empty.
*/
public T[] toArray(); } // end BagInterface
程序设计技巧：在实现一个类之前写测试程序
写Java语句来测试一个类的方法，将有助于完全理解方法的规格说明。在能正确实现方法之前必须理解它。如果你也是类的设计者，那么使用这个类可能有助于你对设计或对文档进行理想的修改。后面可以使用这些相同的Java语句来测试你的实现。
2. 使用ADT包
示例：在线购物（商品放入bag内，顺序不重要）
在线购物中购物袋的维护程序：
需要的Item.java
/**
* A class of items for sale.
* @author Administrator
*
*/
public class Item { private String description;
private int price; public Item(String productDescription, int productPrice) {
description = productDescription;
price = productPrice;
} // end constructor public String getDescription() {
return description;
} // end getDescription public int getPrice() {
return price;
} // end getPrice public String toString() {
return description + "\t$" + price / 100 + "." + price % 100;
} // end toString
} // end Item
OnlineShopper.java
/**
* A class that maintains a shopping cart for an online store.
* @author Administrator
*
*/
public class OnlineShopper { public static void main(String[] args) {
Item[] items = {
new Item("Bird feeder", 2050),
new Item("Squirrel guard", 1547),
new Item("Bird bath", 4499),
new Item("Sunflower seeds", 1295)
}; BagInterface<Item> shoppingCart = new Bag<>();
int totalCost = 0; // Statements that add selected items to the shopping cart:
for(int index = 0; index < items.length; index++) {
Item nextItem = items[index]; // Simulate getting item from shopper
shoppingCart.add(newEntry);
totalCost = totalCost + nextItem.getPrice();
} // end for // Simulate checkout
while(!shoppingCart.isEmpty()) {
System.out.println(shoppingCart.remove());
} System.out.println("Total cost: \t$" + totalCost / 100 + "." + totalCost % 100);
} // end main } // end OnlineShopper /*
output:
Sunflower seeds $12.95
Bird bath $44.99
Squirrel guard $15.47
Bird feeder $20.50
Total cost: $93.91 *
作为设计原则，抽象要求你关注于what而不是how。当你设计一个ADT并最终设计一个类时，使用数据抽象将关注焦点集中在你想对数据做什么，而不必担心如何完成这些任务。
3. ADT集合
集合（set）。不允许有重复项。所以包的add和remove方法需要修改，且不需要getFrequencyOf方法，因为总是1或0，可以使用contains方法。
接口SetInterface.java
/**
* An interface that describes the operations of a set of objects.
* @author Administrator
*
*/
public interface SetInterface<T> { public int getCurrentSize();
public boolean isEmpty(); /**
* Adds a new entry to this set, avoiding duplicates(副本).
* @param newRntry: The object to be added as a new entry.
* @return: True if the addtion is successful, or false if the item already is in the set.
*/
public boolean add(T newRntry); /**
* Removes a specific entry from this set, if possible.
* @param anEntry: The entry to be removed
* @return: True if the removal was successful, or false if not.
*/
public boolean remove(T anEntry); public T remove();
public void clear();
public boolean contains(T anEntry);
public T[] toArray();
} // end SetInterface
4. java类库：接口Set
java类库是类和接口的集合，这是程序员要学习的。Java集合框架（Java Collections Framework）是这个库的一个子库，它为我们提供了表示及处理集合的统一方式。我们将说明的Java类库中的大多数类和接口都是这个框架的一部分。
标准接口Set，属于java.util。遵循接口规范的集合（set）,不包含让x.equals(y)为真的对象对x和y。
Set中方法与SetInterface中对应方法的不同之处：
|
Public Boolean add(T newEntry) Public Boolean remove(Object anEntry) Public void clear() Public Boolean contains(Object anEntry) Public Boolean isEmpty() Public int size() Public Object[] toArray() |