不完全类型和抽象数据类型的定义

立功教授数年之心血之作《程序设计与数据结构》以及《面向AMetal框架与接口的编程（上）》，书本内容公开后，在电子行业掀起一片学习热潮。经周立功教授授权，本公众号特对《程序设计与数据结构》一书内容进行连载，愿共勉之。

第二章为程序设计技术，本文为2.4.1 不完全类型和2.4.2 抽象数据类型。

>>> 2.4.1 不完全类型

不完全类型是指"函数之外、类型的大小不能被确定的类型"，结构体标记的声明就是一个不完全类型的典型示例。比如：

此时，struct _TypeA和struct _TypeB是互相引用的，虽然无论先声明哪一边都很麻烦，但可以先通过声明结构体标记回避以上问题。比如：

当使用typedef声明结构体类型时，比如：

由于TypeB类型的标记被声明时，还不知道它的内容，因此无法确定它的大小，这样的类型就被称为不完全类型。因为不能确定大小，所以不能将不完全类型变成数组，也不能将其作为结构体的成员，或声明为变量。但如果声明为指针，则可以使用不完全类型。在后续定义struct _TypeB的内容时，TypeB就不是不完全类型了。

通常在".h"头文件中声明不包含任何实现细节的结构体，然后在".c"实现文件中定义与数据结构的特定实现配合使用的函数。数据结构的用户可以看到声明和函数原型，但实现会隐藏在".c"文件中。只有使用数据结构所需要的信息会对用户可见，如果太多的内部信息可见，用户可能会使用这些信息从而产生依赖。一旦内部结构发生变化，则用户代码可能就会失效。不完全类型是因为编译器看不见".c"文件中的实际定义，它只能看到_demoB结构体的类型定义，而看不见结构体的实现细节。

下面将以数组为例介绍不完全类型的使用，尽管可以使用数组保存元素，由于数组的大小是固定的，因此数组并不会存储它的大小，而且也不会检查下标是否越界。通常用一个指向数组的指针pBuffer和记录数组元素个数的值count代替数组。其实现如下（IA_array.c）：

为了防止用户直接访问结构体的成员，通常将结构体移到实现代码中（IA_array.c）隐藏起来，然后使用不完全的类型在接口中（IA_array.h）声明一个IntArray处理相应的数据。虽然不完全类型描述了对象，但缺少对象大小所需的信息。比如：

其告诉编译器_IntArray是一个结构体标记，却没有描述结构体的成员，因此编译器没有足够的信息确定结构体的大小，其意图是不完全类型将会在程序的其它地方将信息补充完整。不完全类型的使用是受限的，因为编译器不知道它的大小，所以不能在接口中用它声明变量：

但可以在接口中（IA_array.h）定义一个指针类型引用不完全类型：

在这里，仅仅声明了它的存在，而没有做别的任何事情。对于用户来说，看到的只是IA_array.h，而对_IntArray的构造或实现却一无所知。

当将IntArray定义为一个指向struct _IntArray结构体类型时，即可声明IntArray*类型的变量，将其作为函数参数进行传递。即：

尽管此时还没有定义IntArray，但指针的大小始终相同，且不依赖于它指向的对象。即便在不知道结构体本身细节的前提下，编译器同样允许处理指向结构体的指针，这就解释了为什么C允许这种行为。虽然这个结构体是一个不完全类型，但在实现代码中信息变得完整，因此该结构体的成员依赖于实现方法。

虽然数组和指针有区别，但C语言不会区分它们，C对数组提供的支持只是为了便于内存管理和指针运算，最好的证明莫过于括号运算符居然有交换性。当在结构体内创建一个数组时，为了避免直接对数据进行访问，将通过接口函数和对象交互，详见程序清单 2.30。

程序清单 2.30 访问数组元素和大小接口（IntArray.h）

为了说明这些函数构成了IntArray对象的接口，并防止函数名和其它对象的接口冲突，于是在每个函数名前使用了前缀IA_，且每个函数都有一个IntArray*型的对象作为参数，这个参数就是函数将要操作的对象。

IA_init()初始化使数组处于空元素的状态，IA_cleanup()释放在数组生存期中分配给用户的内存。剩余的函数是控制对数组中数据的访问，IA_setSize()设置了数组中的元素个数，且为这些元素分配存储空间，IA_getSize()返回当前数组中的元素个数。IA_setElem()和IA_getElem()用于访问单个数据元素，其具体实现详见程序清单 2.31。

程序清单 2.31  访问数组元素和大小接口的实现（IntArray.c）

其中，IA_setSize()用于改变数组大小，首先释放原有的元素，然后保存新的元素，且为新元素分配存储空间。当然，也可以优化进一步代