07-建立抽象

17.3.1　建立抽象

从根本上看，电影项目所需的是一个项链表。每一项包含电影名和评级。你所需的操作是把新项添加到链表的末尾和显示链表中的内容。我们把需要处理这些需求的抽象类型叫作链表。链表具有哪些属性？首先，链表应该能存储一系列的项。也就是说，链表能存储多个项，而且这些项以某种方式排列，这样才能描述链表的第1项、第2项或最后一项。其次，链表类型应该提供一些操作，如在链表中添加新项。下面是链表的一些有用的操作：

• 初始化一个空链表；
• 在链表末尾添加一个新项；
• 确定链表是否为空；
• 确定链表是否已满；
• 确定链表中的项数；
• 访问链表中的每一项执行某些操作，如显示该项。

对该电影项目而言，暂时不需要其他操作。但是一般的链表还应包含以下操作：

• 在链表的任意位置插入一个项；
• 移除链表中的一个项；
• 在链表中检索一个项（不改变链表）；
• 用另一个项替换链表中的一个项；
• 在链表中搜索一个项。

非正式但抽象的链表定义是：链表是一个能存储一系列项且可以对其进行所需操作的数据对象。该定义既未说明链表中可以存储什么项，也未指定是用数组、结构还是其他数据形式来存储项，而且并未规定用什么方法来实现操作（如，查找链表中元素的个数）。这些细节都留给实现完成。

为了让示例尽量简单，我们采用一种简化的链表作为抽象数据类型。它只包含电影项目中的所需属性。该类型总结如下：

类型名： 简单链表

类型属性： 可以存储一系列项

类型操作： 初始化链表为空

确定链表为空

确定链表已满

确定链表中的项数

在链表末尾添加项

遍历链表，处理链表中的项

清空链表

下一步是为简单链表ADT开发一个C接口。