C语言之如何定义一个数据类型

本文介绍了如何设计和定义一个新的数据类型，具体包括建立抽象、建立接口和实现接口三个部分。总结这三步法：从思考“做什么”（抽象）到规定“怎么做才对”（接口），最后才是“怎么做到”（实现），这是编写健壮、清晰、可维护代码的基石。

---

引言

设计一种数据类型包括设计如何储存该数据类型（属性）和设计一系列管理该数据的函数（操作）。

计算机科学领域已开发了一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程。

1. 提供类型属性和相关操作的抽象描述。这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型（ADT）。
2. 开发一个实现 ADT 的编程接口。也就是说，指明如何储存数据和执行所需操作的函数。例如在C中，可以提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于作用于C基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程。
3. 编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。

抽象数据类型以面向问题而不是面向语言的方式，把解决问题的方法和数据表示结合起来。设计一个ADT后，可以在不同的环境中复用。理解ADT可以为将来学习面向对象程序设计（OOP）以及C++语言做好准备。

建立抽象

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

为了让示例尽量简单，一种简化的链表类型总结如下：

类型名： 简单链表

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

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

确定链表为空

确定链表已满

确定链表中的项数

在链表末尾添加项

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

清空链表

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

建立接口

这个简单链表的接口有两个部分。第1部分是描述如何表示数据，第2部分是描述实现ADT操作的函数。接口设计应尽量与ADT的描述保持一致。因此，应该用某种通用的Item类型而不是一些特殊类型，如 int 或 struct film 。可以用C的 typedef 功能来定义所需的Item类型：

#define TSIZE 45 /* 储存电影名的数组大小 */
struct film
{
    char title[TSIZE];
    int rating;
};
typedef struct film Item;

然后，就可以在定义的其余部分使用 Item 类型。如果以后需要其他数据形式的链表，可以重新定义Item类型，不必更改其余的接口定义。定义了 Item 之后，现在必须确定如何储存这种类型的项。实际上这一步属于实现步骤，但是现在决定好可以让示例更简单些。这里采用链节节点结构：

typedef struct node
{
    Item item;
    struct node * next;
} Node;
typedef Node * List;

在链表的实现中，每一个链节叫作节点（node）。每个节点包含形成链表内容的信息和指向下一个节点的指针。为了强调这个术语，我们把node作为节点结构的标记名，并使用typedef把Node作为struct node结构的类型名。最后，为了管理链表，还需要一个指向链表开始处的指针，我们使用typedef把List作为该类型的指针名。因此，下面的声明：

List movies;

创建了该链表所需类型的指针movies。 这是否是定义List类型的唯一方法？不是。例如，还可以添加一个变量记录项数，添加第2个指针储存链表的末尾：

typedef struct list
{
    Node * head; /* 指向链表头的指针 */
    Node * tail; /* 指向链表尾的指针 */
    int size;    /* 链表中的项数 */
} List; /* List的另一种定义 */

现在，还是使用List类型的第1种定义。这里要着重理解下面的声明创建了一个链表，而不一个指向节点的指针或一个结构：

List movies;

movies代表的确切数据应该是接口层次不可见的实现细节（不好理解的话可以代入上面的包含尾指针和项数的List定义）。

为了指导用户使用，可以在函数原型前面提供以下注释：

/* 操作：初始化一个链表 */
/* 前提条件：plist指向一个链表*/
/* 后置条件：该链表初始化为空 */
void InitializeList(List * plist);

这里要注意3点。第1，注释中的“前提条件”（precondition）是调用该函数前应具备的条件。例如，需要一个待初始化的链表。第2，注释中的“后置条件”（postcondition）是执行完该函数后的情况。第3，该函数的参数是一个指向链表的指针，而不是一个链表。所以应该这样调用该函数：

InitializeList(&movies);

C语言把所有类型和函数的信息集合成一个软件包的方法是：把类型定义和函数原型（包括前提条件和后置条件注释）放在一个头文件中。该文件应该提供程序员使用该类型所需的所有信息。

程序清单list.h给出了一个简单链表类型的头文件。该程序定义了一个特定的结构作为Item类型，然后根据Item定义了Node，再根据Node定义了List。然后，把表示链表操作的函数设计为接受Item类型和List类型的参数。如果函数要修改一个参数，那么该参数的类型应是指向相应类型的指针，而不是该类型。在头文件中，把组成函数名的每个单词的首字母大写，以这种方式表明这些函数是接口包的一部分。另外，该文件使用 #ifndef 指令，防止多次包含一个文件。

/* list.h -- 简单链表类型的头文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99特性 */
/* 特定程序的声明 */
#define TSIZE 45 /* 储存电影名的数组大小 */
struct film
{
    char title[TSIZE];
    int rating;
};
/* 一般类型定义 */
typedef struct film Item;
typedef struct node
{
    Item item;
    struct node * next;
} Node;
typedef Node * List;

/* 函数原型 */

/*操作： 初始化一个链表 */
/*前提条件：plist指向一个链表 */
/*后置条件：链表初始化为空 */
void InitializeList(List * plist);

/*操作： 确定链表是否为空定义 */
/*前提条件：plist指向一个已初始化的链表 */
/*后置条件：如果链表为空，该函数返回true；否则返回false */
bool ListIsEmpty(const List *plist);

/*操作： 确定链表是否已满 */
/*前提条件：plist指向一个已初始化的链表 */
/*后置条件：如果链表已满，该函数返回真；否则返回假 */
bool ListIsFull(const List *plist);

/*操作： 确定链表中的项数 */
/*前提条件：plist指向一个已初始化的链表 */
/*后置条件：该函数返回链表中的项数 */
unsigned int ListItemCount(const List *plist);

/*操作： 在链表的末尾添加项 */
/*前提条件： item是一个待添加至链表的项, plist指向一个已初始化的链表 */
/*后置条件：如果可以，该函数在链表末尾添加一个项，且返回true；否则返回false */
bool AddItem(Item item, List * plist);

/*操作： 把函数作用于链表中的每一项 */
/*前提条件：plist指向一个已初始化的链表 */
/*前提条件：pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值 */
/*后置条件：pfun指向的函数作用于链表中的每一项一次 */
void Traverse(const List *plist, void(*pfun)(Item item));

/*操作：释放已分配的内存（如果有的话） */
/*前提条件：plist指向一个已初始化的链表 */
/*后置条件：释放了为链表分配的所有内存，链表设置为空 */
void EmptyTheList(List * plist);

#endif

实现接口

C方法是把函数定义统一放在一个*.c文件中，具体函数实现可参考常用数据结构设计与实现。

使用接口

在第二步接口建立好之后便可使用接口进行开发了，实际开发中架构师定义接口（第1、2步），工程师并行实现（第3步），以此来提升开发效率。

抽象数据类型的优点

• 关注点分离： 让设计更清晰，减少思维负担。
• 灵活性/可维护性：接口和实现分离，使得更改内部实现变得非常容易，不会破坏现有代码。
• 团队协作：架构师定义接口（第1、2步），工程师并行实现（第3步）。
• 正确性：先定义契约，便于后续编写测试用例（如单元测试）。

参考文献

1. C Primer Plus （第6版）中文版. Stephen Prata.