《数据结构与抽象:Java语言描述(原书第4版)》一2.1.3 实现核心方法-阿里云开发者社区

开发者社区> 华章出版社> 正文
登录阅读全文

《数据结构与抽象:Java语言描述(原书第4版)》一2.1.3 实现核心方法

简介:

本节书摘来华章计算机《数据结构与抽象:Java语言描述(原书第4版)》一书中的第2章 ,第2.1.3节,[美]弗兰克M.卡拉诺(Frank M. Carrano) 蒂莫西M.亨利(Timothy M. Henry) 著 罗得岛大学  新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.1.3 实现核心方法

数据域。在定义任何核心方法之前,需要考虑类的数据域。因为包要保存一组对象,所以一个域是这些对象的数组。数组的长度定义了包的容量。可以让客户指定这个容量,我们也可以提供一个默认容量。另外,我们想跟踪包中当前项的个数。所以可以为我们的类定义如下的数据域:
image

并将它们加到图1-2中类的UML表示中。得到的表示如图2-2所示。
image

程序设计技巧:终态数组
通过声明数组bag是类ArrayBag的一个终态数据成员,可知变量bag中的引用不能改变。虽然以这种方式声明数组是一种好的做法,但数组元素bag[0],bag[1],…的值还是可以改变的。这样的改变是需要的,但必须阻止客户从bag中得到对数组的引用。这种情况会让数组的内容易受恶意毁坏。当在后面定义方法toArray时会进一步讨论。

关于构造方法。这个类的构造方法必须创建数组bag。注意,在前面的数据域bag的声明中没有创建数组。在构造方法中忘记创建数组是一个常见错误。为创建数组,构造方法必须指定数组的长度,这是包的容量。因为我们已经创建了一个空包,所以构造方法还应该将域numberOfEntries初始化为0。
决定在数组bag的声明中使用泛型,影响到我们在构造方法中如何分配这个数组。如下的语句
image

在语法上是不正确的。当分配数组时不能使用泛型。相反,我们可以分配对象是Object类型的数组,如下所示:
image

但是,当试图将这个数组赋给数据域bag时问题就出现了。语句
image

产生语法错误,因为不能将Object[]类型的数组赋给T[]类型的数组,即两个数组的类型不兼容。
转型是必需的,但也会带来它自己的问题。语句
image

会出现编译警告
image

如果再次编译这个类,且使用选项-Xlint,则会有更详细的信息,信息的开头如下:
image

编译程序想让你保证将数组中的每项从类型Object转型为泛型T都是安全的。因为数组刚刚分配,所以它含有null项。因此,转型是安全的,故我们在有问题的语句之前写如下的注释可让编译程序忽略这个警告:
image

这条给编译程序的命令只能放在方法定义或变量声明之前。因为赋值
image

没有声明bag(bag已经声明过了),故我们将它修改为
image

注:禁止编译警告

要禁止编译程序给出的未检查转型警告,可以在标记的语句之前写如下的语句

注意,这条命令只能放在方法定义或变量声明之前。应该包含一条注释,对你禁止编译程序的警告做出解释。

构造方法。下列构造方法执行前面的步骤,使用参数所给出的容量:
image

默认构造方法可以调用前一个,将默认容量作为参数传给它,如下所示。
image

我们知道,构造方法可以使用关键字this作为方法名来调用同一个类中的另一个构造方法。
类的框架。让我们来看看到目前为止所定义的类。在完成了类的初始部分(即头、数据域和构造方法)后,可以为公有方法添加注释和头,从BagInterface中将这些内容复制过来即可。然后在这些方法头的后面写空方法。程序清单2-1显示了这些步骤之后的结果。下一个任务是实现这三个核心方法。
程序清单2-1 类ArrayBag的框架
image
image

程序设计技巧:当定义实现接口的类时,从接口中复制它们来添加类中公有方法的注释和头。使用这种方式,方便你在实现时检查每个方法的规格说明。另外,以后维护代码的人也容易访问这些规格说明。
设计决策:当数组bag中装了一部分数据时,包的项应该放在数组的哪些元素中?

当向数组添加第一个项时,一般将它放在数组的第一个元素中,即下标为0的元素。不过这样做也不是必需的,特别是对于实现集合的数组来说。例如,有些集合的实现受益于忽略下标为0的数组元素,而将下标1作为数组的第一个元素。有时你可能会想先使用数组尾端然后再使用数组头。对于包,我们没有理由不按常理做,所以包中的对象将从数组的下标0处开始。
另一个要考虑的问题是,包的对象是否应该保存在数组连续的元素中。要求add方法将对象连续放到数组bag中,肯定是合理的,但是为什么我们要关心这个问题?这真是一个值得关注的问题吗?关于计划中的实现方案,必须确定某些事实或断言,以便每个方法的动作不会对其他方法产生不利。例如,方法toArray必须“知道”add方法将包的项放在哪里。我们现在的决策会影响从包中删除一项时将发生什么。方法remove需要保证数组项保存在连续的元素中吗?它必须这样做,因为至少到现在,我们仍强调包项保存在连续的数组元素中。

方法add。如果包满了,则不能添加任何东西。这种情形下,方法add应该返回假。否则,仅需紧接在数组bag最后项的后面添加newEntry,语句如下:
image

如果向空包中添加项,则numberOfEntries是0,应该给bag[0]赋值。如果包中含有一个项,则添加的项应赋给bag[1],以此类推。每次向包中添加项后,要递增计数器numberOfEntries的值。这些步骤如图2-3所示,且由图后面的add方法的定义来完成。


image


image

注意,我们调用isArrayFull就好像它已经定义过一样。之前我们没有把isArrayFull作为核心方法,它的使用表明它应该在核心组内。

注:包中的项没有特定的次序。所以,方法add可以将新项放到数组bag中最方便的元素位置。在前面那个add的定义中,元素紧接在已用的最后元素之后。
注:通常,讨论中提到数组时就好像它真的含有对象一样。实际上,Java数组含有指向对象的引用,如图2-3所示的数组一样。

方法isArrayFull。当包中含有的对象数与数组bag能容纳的量相等时,包就满了。当numberOfEntries等于数组容量时就发生了这种情形。所以,isArrayFull有下列简单的定义:
image

方法toArray。在最初的核心组内,最后一个方法toArray是获取包中的项,并将它们返回到客户新分配的数组内。这个新数组的长度可以与包中项的个数(即numberOfEntries值)相等,而不是与数组bag的长度相等。但是,在分配数组时遇到了定义构造方法时遇到过的同样问题,所以采用与构造方法相同的处理步骤。
在toArray创建新数组后,使用简单的循环可以将数组bag中的引用复制到这个新数组中,然后返回这个数组。所以toArray的定义如下所示。
image

设计决策:方法toArray应该返回数组bag而不是复制吗?

假定我们如下定义toArray:
image

这个简单定义肯定能将包元素所在的数组返回给客户。例如,语句
image

能得到指向myBag中项的数组的引用。客户可以使用变量bagArray来显示myBag的内容。
但是,引用bagArray是数组bag自身,即bagArray是对象myBag中的私有实例变量bag的别名,所以它能让客户直接访问这个私有数据。因此客户不调用类的公有方法就能修改包的内容。例如,如果myBag是图2-3中所示的满包,语句
image

将把项Ted改为null。如果本意是想从包中删除Ted,虽然这个方法听上去很好,但这样做可能会破坏包的完整性。具体来说,数组bag中的项可能不再是连续的,且包中的项数也会出错。

安全说明:类不应该返回指向其私有数据域的数组的引用。

注:使用泛型,可以限制集合中的项的数据类型,因为

声明数据类型为Object的变量可以是任何数据类型对象的引用,但是有泛型数据类型的变量只能指向指定数据类型的对象。

由Object类型的变量指向的项的集合可以含有各种相关类的对象,但由泛型变量指向的项的集合只能含有由继承而相关的类的对象。

自测题4 在前面的toArray方法中,numberOfEntries的值一般等于bag.length吗?

自测题5 假定前面的toArray方法让新数组result的长度与数组bag相同。客户如何得到返回的数组中的项数?
自测题6 假定前面的toArray方法返回数据bag而不是返回像result这样的新数组。如果myBag是含5个项的包,则下列语句对数组bag和域numberOfEntries的影响是什么?
image

自测题7 如果调用方法Arrays.copyOf,则方法toArray的方法体中可以含有一个return语句。修改方法toArray。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: