1.4.1  设计ADT（1）

设计ADT

在问题求解的过程中，抽象数据类型的设计很自然地会演变。为了说明这个过程是如何进行的，假定想要判断给定年份所有节假日的日期。完成这一任务的方法之一是查阅日历。也就是说，可以考虑某个年份中的所有日期，并检测某天是否为节假日。下面的伪代码是这个问题可能的解决方案之一：
 

// Displays the dates of all holidays in a given year.  
listHolidays(year)  
datedate = date of first day of year  
while (date is before the first day of year + 1)  
{  
if (date is a holiday )  
write (date," is a holiday")  
datedate = date of next day  
}  

在此涉及哪些数据？很显然，这个问题需要操作日期，而日期由年月日组成。为了解决节假日问题需要执行什么操作？ADT必须指明并限定关于日期的合法操作，就像基本数据类型int限定类似于加法操作以及比较操作一样。从前面的伪代码中可以看出，必须：

判断给定年份的第一天的日期

判断某个日期是否在另一日期之前

判断某个日期是否为节假日

判断给定日期之后一天的日期

注释：某问题需要哪些数据

某问题需要哪些操作

因此，可以使用统一建模语言(UML)标记的伪代码为ADT日期指明下面的操作，UML在附录C中讲述：
 

// Returns the date of the first day of a given year.  
+getFirstDay(year: integer): Date  
// Returns true if this date is before the given date; otherwise returns false.  
+isBefore(otherDate: Date): boolean  
// Returns true if this date is a holiday; otherwise returns false.  
+isHoliday(): boolean  
// Returns the date of the day after this date.  
+getNextDay(): Date  

listHolidays伪代码现在如下所示：
 

// Displays the dates of all holidays in a given year.  
listHolidays(year: integer): void  
date = getFirstDay(year)  
while (date.isBefore(getFirstDay(year + 1)))  
{  
if (date.isHoliday())  
write (date," is a holiday ")  
datedate = date.getNextDay()  
}  

这样，通过确定数据以及选择适合于问题的操作设计了ADT。当指明了操作之后，就可以用这些操作解决问题，而不依赖于ADT的实现细节。

预约簿  作为ADT设计的另一个示例，假定您想要创建一个跨度为一年的预约簿。假设只想在上午8点到下午5点之间的整点和半点做记录，并且想要系统用简短的记号存储约会的类型以及日期和时间。

为了解决这个问题，可以定义一个ADT预约簿。ADT中的数据项是约会，某个约会由日期、时间以及目的组成。有什么操作呢？有两个明显的操作：

根据日期、时间、目的创建一个约会(要小心，不要在已经被占用的时间内创建约会)

取消某个日期和时间的约会

除了这些操作之外，您或许还想：

查询在给定的时间内是否有约会

获取给定时间内约会的目的

最后，我们假定ADT通常具有初始化以及销毁操作，但是在此阶段并不指定这一内容。

这样，ADT预约簿将具有如下操作：
 

// Returns true if an appointment exists for the date and time specified,  
// false otherwise.  
+isAppointment(apptDate: Date, apptTime: Time): boolean  
// Inserts the appointment for the date, time, and purpose specified as long as  
// it does not conflict with an existing appointment.  
// Returns true if successful, false otherwise.  
+makeAppointment(apptDate: Date, apptTime: Time,  
apptPurpose: string): boolean  
// Deletes the appointment for the date and time specified.  
// Returns true if successful, false otherwise.  
+cancelAppointment(apptDate: Date, apptTime: Time): boolean  
// Gets the purpose of the appointment at the given date and time, if one exists.  
// Otherwise returns an empty string.  
+getAppointmentPurpose(apptDate: Date, apptTime: Time): string