08-抽象数据类型的描述

0.3.2　抽象数据类型的描述

抽象数据类型其实是根据数据结构的研究对象进行定义的，包含了数据对象、数据对象间的关系及其基本运算。本书把抽象数据类型分为两个部分来描述，即数据对象集合和基本操作集合。其中，数据对象集合部分描述了数据对象的定义及数据对象中元素之间的关系，基本操作集合部分描述了数据对象的运算。数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式如下。

基本操作名（参数表）：初始条件和操作结果描述。

例如，队列的抽象数据类型描述如下。

1．数据对象集合

队列的数据对象集合为{a₁, a₂,…, a_n}，每个数据元素都具有相同的数据类型。

队列中的数据元素之间是一对一的关系。除第一个元素a₁外，每一个元素有且只有一个直接前驱元素；除最后一个元素a_n外，每一个元素有且只有一个直接后继元素。

2．基本操作集合

（1）InitQueue(&Q)：初始化操作，建立一个空队列Q。这就像日常生活中医院新增一个挂号窗口，前来看病的人就可以排队在这里挂号。

（2）QueueEmpty(Q)：若Q为空队列，返回1；否则，返回0。这就像判断挂号窗口前是否还有人在排队挂号。

（3）EnQueue(&Q,e)：把元素e插入队列Q的队尾。这就像新来挂号的人都要到队列的最后排队挂号。

（4）DeQueue(&Q,&e)：删除Q的队首元素，并用e返回其值。这就像排在最前面的人挂完号离开队列。

（5）Gethead(Q,&e)：用e返回Q的队首元素。这就像询问当前排队挂号的人是谁一样。

（6）ClearQueue(&Q)：将队列Q清空。这就像所有排队的人都挂完号离开队列。