《 C语言接口与实现: 创建可重用软件的技术》一2.3抽象数据类型

本节的摘录来自异步社区“社区”公共帐户视图中的“ C语言接口和实现: 创建可重用软件的技术”一书的第2章，第2.3章

抽象数据类型是定义数据类型以及对该类型的值执行的操作的接口. 数据类型是值的集合. 在C语言中，内置数据类型包括字符，整数，浮点数等. 结构本身也可以定义新类型，因此可以用于创建更高级的类型c语言接口与实现:创建可重用软件的技术，例如列表，树，查找表，等等.

高级类型是抽象的，因为它们的接口隐藏了相关的呈现细节，并且仅对类型的值指定合法的操作. 理想情况下，这些操作将不会公开演示文稿详细信息的类型，因为这可能会使客户端程序隐式依赖于特定的演示文稿. 抽象数据类型或ADT的标准示例是堆栈. 其接口定义了堆栈类型及其5个操作:

〈initial version of stack.h〉≡ 
　#ifndef STACK_INCLUDED 
　#define STACK_INCLUDED 
　typedef struct Stack_T *Stack_T; 
　extern Stack_T Stack_new　(void); 
　extern int　　 Stack_empty(Stack_T stk); 
　extern void　　Stack_push (Stack_T stk, void *x); 
　extern void　 *Stack_pop　(Stack_T stk); 
　extern void　　Stack_free (Stack_T *stk); 
　#endif

上面的typedef定义了Stack_T类型，它是指向具有相同名称的结构的指针. 此定义是合法的，因为结构，联合和枚举的名称（标记）占据一个名称空间，该名称空间不同于用于变量，函数和类型名称的名称空间. 在本书中都使用了这种习语. 类型名称Stack_T是我们在此接口中关注的名称. 仅对于实现而言，结构名称更为重要. 使用相同的名称可以避免过多的稀有名称污染代码.

宏STACK_INCLUDED也会污染名称空间，但是_INCLUDED后缀有助于避免冲突. 另一个常见的约定是在此类名称前加上下划线，例如_STACK或_STACK_INCLUDED. 但是Standard C为实施者和将来的扩展保留了下划线前缀，因此避免使用下划线前缀似乎是明智的.

该接口显示堆栈由指向结构的指针表示，但未提供有关该结构的任何信息. 因此，Stack_T是不透明的指针类型. 客户端程序可以自由地操纵该指针，但是不能取消引用不透明的指针，即它不能查看该指针指向的结构的内部信息. 只有接口的实现才具有此特权.

不透明的指针隐藏了演示文稿的详细信息，并有助于捕获错误. 只能将Stack_T类型的值传递给上述函数. 尝试传递另一个指针（例如指向另一个结构的指针）将导致编译错误. 唯一的例外是参数中的void指针c语言接口与实现:创建可重用软件的技术，可以将其传递给任何类型的指针.

定义STACK_INCLUDED make stack.h的条件编译指令#ifdef和#endif和#define可以被多次包含，当接口导入其他接口时可能会发生. 如果没有这种保护，由于在typedef中重新定义了Stack_T，第二和后续的include操作将导致编译错误.

在少数可用的替代方案中，此约定似乎是最适度的. 禁止该接口包含其他接口可以完全避免重复包含，但是这迫使该接口指定必须以其他方式（例如注释）导入的其他接口，并且还迫使程序员提供包含指令. 将条件编译指令放在客户端程序而不是接口中可以避免在编译过程中不必要地读取接口文件，但是代价是很多地方都需要派生许多混乱的条件编译指令，这不像将其放入程序库中那样干净. 接口. 上面解释的约定要求编译器完成所谓的“肮脏工作”.

根据约定，ADT接口X可以命名为ADT类型X_T. 本书中的接口使该约定更进一步，使用接口内的宏将X_T缩写为T. 使用此约定时，stack.h如下:

〈stack.h〉≡ 
　#ifndef STACK_INCLUDED 
　#define STACK_INCLUDED 
　#define T Stack_T 
　typedef struct T *T; 
　extern T　　 Stack_new　(void); 
　extern int　 Stack_empty(T stk); 
　extern void　Stack_push (T stk, void *x); 
　extern void *Stack_pop　(T stk); 
　extern void　Stack_free (T *stk); 
　#undef T 
　#endif

该接口在语义上与上一个等效. 缩写只是语法糖，使界面更易于阅读. T是接口中的主要类型. 但是客户端程序必须使用Stack_T，因为stack.h末尾的#undef指令会删除上面提到的缩写.

该接口提供了无限的指针堆栈，可用于任何指针. Stack_new创建一个新的堆栈，该堆栈返回类型T的值，该值可以作为参数传递给其他四个函数. Stack_push将指针推到堆栈的顶部. Stack_pop删除堆栈顶部的指针并返回该指针. 如果堆栈为空，则Stack_empty返回1，否则返回0. Stack_free将指向T的指针作为参数，释放该指针指向的堆栈，并将类型T的变量设置为NULL指针. 这种设计有助于避免悬空的指针指向已释放的内存. 例如，如果名称是通过以下代码定义和初始化的:

include "stack.h" 
Stack_T names = Stack_new();

以下声明

Stack_free(&names);

释放名称所指向的堆栈，并将名称设置为NULL指针.

当ADT由不透明指针表示时，派生类型是指针类型，这就是为什么Stack_T被定义为通过typedef指向结构Stack_T的指针的原因. 本书中的大多数ADT使用类似的typedef. 当ADT公开其表示的详细信息并导出一个接受并返回相应结构值的函数时，该接口会将结构类型定义为导出类型. 第16章中的Text接口说明了此约定，该约定将Text_T声明为struct Text_T的typedef. 无论如何，界面中的主要类型总是缩写为T.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-216353-1.html