《数据结构与抽象——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 + " $" + 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: $" + 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() |