994
《数据结构与抽象：Java语言描述（原书第4版）》一练习
本节书摘来华章计算机《数据结构与抽象：Java语言描述（原书第4版）》一书中的第2章 ，［美］弗兰克M.卡拉诺（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 着 罗得岛大学 新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
练习
1.为什么类ArrayBag中的方法getIndexOf和removeEntry是私有的而不是公有的？
2.为ADT包实现方法replace，用一个给定对象替换当前包中的对象，并返回原始对象。
3.修改2.1.7节中给出的方法clear的定义，以便更有效率且仅调用checkInitialization方法。
4.修改2.1.7节的避免重复工作中给出的方法remove，以便从包中删除一个随机项。这个修改会影响到类ArrayBag中的其他方法吗？
5.为类ArrayBag定义方法removeEvery，从包中删除给定项的所有出现。
6.类ArrayBag的实例有固定大小，而ResizableArrayBag的实例则没有。给出一些例子，如果包的大小是
a.固定的
b.可变的
则包是合适的。
7.假定想定义类PileOfBooks来实现前一章项目2中描述的接口。包是表示一堆书的合理集合吗？解释之。
8.考虑2.2.2节中讨论的类ResizableArrayBag的实例myBag。假定myBag的初始容量是10。
a.向myBag中添加了145项后
b.向myBag中添加20项后
数组bag的长度是多少？
9.在客户层定义一个方法，其参数是类ArrayBag的实例，并返回类ResizableArrayBag的实例，其中含有与参数所给包中相同的项。
10.假定包中含有Comparable对象，例如字符串。一个Comparable对象属于实现了标准接口Comparable的一个类，所以有方法compareTo。为类ArrayBag实现下列方法：
- 返回包中最小对象的方法getMin
- 返回包中最大对象的方法getMax
- 删除并返回包中最小对象的方法removeMin
- 删除并返回包中最大对象的方法removeMax
11.假定包中含有Comparable对象，如前一个练习中所描述的那样。为类ArrayBag定义一个方法，返回由小于某个给定项的项组成的新包。方法的头可以如下所示：
确保你的方法不会影响原始包的状态。
12.为类ArrayBag定义equals方法，当两个包的内容相同时返回真。注意，两个相等的包应含有相同个数的项，每个项出现在每个包中的个数应相等。每个数组中的项的次序是无关的。
13.类ResizableArrayBag有一个数组，当向包中添加对象时其大小增大。修改这个类，使得当从包中删除对象时，它的数组还可以缩小。完成这个任务需要两个新的私有方法，如下所示：
第一个新方法检查是否应该减小数组的大小：
如果包中的项数小于数组大小的一半且数组的大小大于20，这个方法返回真。
第二个新方法创建一个新数组，其大小是当前数组大小的3/4，且数组的大小大于20。
实现这两个方法，然后使用它们来定义两个remove方法。
14.考虑前一个练习中描述的两个私有方法。
a. 方法isTooBig需要数组的大小大于20。如果没有这个要求可能会发生什么问题？
b. 方法reduceArray与方法doubleCapacity并不相同，它没有让数组的大小减小一半。如果数组的大小减到一半而不是3/4，可能会出现什么问题？
15.为类ResizableArrayBag定义前一章练习5描述的方法union。
16.为类ResizableArrayBag定义前一章练习6描述的方法intersection。
17.为类ResizableArrayBag定义前一章练习7描述的方法difference。
项目
1.设计并实现单人猜谜游戏，选择n个1～m之间的随机整数，要求用户来猜它们。同一个整数可能被选中多次。例如，游戏可能选中1～10之间的以下4个整数：4,6,1,6。用户和游戏之间的交互可能是：
输入你猜测的1～10之间选中的4个整数：
1 2 3 4
你猜的2是正确的，再猜。
输入你猜测的1～10之间选中的4个整数：
2 4 6 8
你猜的2是正确的，再猜。
1 4 6 6
正确！再玩一次？不
再见！
设计作为ADT的游戏。使用包来保存游戏选择的整数。整数m和n由客户指定。
2.定义一个表示1.5节描述的集合（set）并实现接口的类ArraySet。在实现中使用类ResizableArrayBag。然后写一个程序，充分论证你的实现。
3.重复前一个项目，使用可变大小的数组而不是使用类ResizableArrayBag。
4.定义类PileOfBooks，实现前一章项目2中描述的接口。在实现中使用可变大小的数组。然后写一个程序，充分论证你的实现。
5.定义类Ring，实现前一章项目3描述的接口。在实现中使用可变大小的数组。然后写一个程序，充分论证你的实现。
6.可以写一个集合或一个包，创建拼写检查器。集合或包用作字典，且含有一组正确拼写的字。要看一个字是否拼写正确，可以看它是否含在字典中。使用这种方法对外部文件中保存的字创建拼写检查器。为简化任务，限制字典的规模。
7.重做前一个项目，创建拼写检查器，但是将你要检查拼写的字放入包中。字典（含有正确拼写字的集合或包）与要检查的字的包之间的差，是拼写错误的字的包。
自测题答案
1.学生仍然在连续编号的椅子上。不需要记录空椅子的位置。
2.不移动学生从而节省时间。
3.最大编号椅子中的学生。
4.不相等。仅当包满时两个值才相等。
5.如果客户含有如下的一条语句
则myBag.getCurrentSize()将是数组bagContents中项的个数。根据设计，bagContents.length可以大于包中项的个数。
6.该语句将包的第一个元素设置为null。numberOfEntries的值不改变，所以它是5。
7.
8.包aBag为空。当调用displayBag时，执行语句
当调用toArray时，执行语句
因为aBag为空，所以numberOfEntries是0。因此新数组result是空的。跳过toArray中的循环，返回空数组且赋给bagArray。因为bagArray.length是0，所以跳过displayBag中的循环。调用displayBag(aBag)的结果是简单的一行：
9.优点：这个定义易写，所以可能少犯错误。
缺点：这个定义要花更多的执行时间，如果anEntry在包中出现多次时。注意，方法getFrequencyOf中的循环对包中的所有项重复，而2.1.6节中所给的方法contains中的循环一旦找到所需的项立即结束。
10.
11.虽然对于客户的方法和ArrayBag中的其他方法，包会变为空的，但被删除对象的引用仍保留在数组bag中。即使客户不保留指向这些对象的引用，与它们相关的内存也没被释放。
12.设置bag[numberOfEntries]为null，该方法使得分配给被删项的内存被回收，除非客户还有另一个指向这个项的引用。
13.数组bag中不是最后一项的项设置为null。其余的项不再位于数组的连续元素中。可以重新安排项来去掉null项，或者修改其他方法跳过null项。
14. a.不能。如果result是null（且这十分可能），则将出现NullPointerException。
b.能。
15.在包中找到"B"后，remove方法将它替换为数组bag中的最后项，即"C"。然后将最后项替换为null。虽然可以定义remove来得到问题中所给出的两个其他可能的结果，但每个结果都是不好的。例如，要得到"A"，"A"，"A"，"C"，null，remove应该移动数组元素，需要更多的运行时间。在数组中留下空隙，如"A"，"A"，null，"A"，"C"，对remove来说容易办到，但对其他方法逻辑就复杂了。
16.
17.
或者
18.
或者
19.
20.
21.简单的赋值语句可能不是好的选择，因为客户可能使用指向作为参数传给构造方法的数组的引用来破坏包的数据。复制参数数组到数组bag中是必需的，以保护包数据的完整性。
22.优点：如果你知道下标，可以直接访问任意数组位置。
缺点：数组有固定的大小，所以或者浪费空间或者超界。调整数组大小可以避免后一个缺点，但需要将原始数组的内容复制到更大的数组中。
最后更新：2017-06-26 18:02:21