C 语言程序设计:抽象数据类型

目录汇总:C 语言零基础入门教程

作为抽象对象的模块(像 C 语言程序设计:信息隐藏 中的栈模块)有一个严重的缺点:无法拥有该对象的多个实例(本例中指多个栈)。为了达到这个目的,需要创建一个新的类型

一旦定义了 Stack 类型,就可以有任意个栈了。下面的程序片段显示了如何在同一个程序中有两个栈:

1
2
3
4
5
6
7
8
Stack s1, s2;

make_empty(&s1);
make_empty(&s2);
push(&s1, 1);
push(&s2, 2);
if (!is_empty(&sl))
  printf("%d\n", pop(&s1));    /* prints "1" */

我们并不知道 s1s2 究竟是什么(是结构,还是指针),但这并不重要。对于栈模块的客户,s1s2抽象,它只响应特定的操作(make_emptyis_emptyis_fullpush 以及 pop)。

接下来将 stack.h 改成提供 Stack 类型的方式,其中 Stack 是结构。这需要给每个函数增加一个 Stack 类型(或 Stack *)的形式参数。stack.h 现在如下(stack.h 中改动的地方用粗体显示,未改动的部分不显示):

#define STACK_SIZE 100

typedef struct {
  int contents[STACK_SIZE];
  int top;
} Stack;

void make_empty(Stack *s);
bool is_empty(const Stack *s);
bool is_full(const Stack *s);
void push(Stack *s, int i);
int pop(Stack *s);

函数 make_emptypushpop 参数的栈变量应为指针,因为这些函数会改变栈的内容。is_emptyis_full 函数的参数并不需要是指针,但这里我们仍然使用了指针。给这两个函数传递 Stack 指针比传递 Stack 值更有效,因为传递值会导致整个数据结构被复制。

一、封装

遗憾的是,上面的 Stack 不是抽象数据类型,因为 stack.h 暴露了 Stack 类型的具体实现方式,因此无法阻止客户将 Stack 变量作为结构直接使用:

1
2
3
4
Stack s1;

s1.top =0;
s1.contents[top++] = 1;

由于提供了对 topcontents 成员的访问,模块的客户可以破坏栈。更糟糕的是,由于无法评估客户的修改所产生的效果,我们不能改变栈的存储方式。

我们真正需要的是一种阻止客户知道 Stack 类型的具体实现的方式。C 语言对于封装类型的支持很有限。新的基于 C 的语言(包括 C++、Java 和 C#)对于封装的支持更好一些。

二、不完整类型

C 语言提供的唯一封装工具为不完整类型(incomplete type,在 C 语言弹性数组成员C 语言指针的高级应用:问与答 简单提过)。C 标准对不完整类型的描述:“描述了对象但缺少定义对象大小所需的信息。”例如,声明

1
struct t;    /* incomplete declaration of t */

告诉编译器 t 是一个结构标记,但并没有描述结构的成员。因此,编译器并没有足够的信息来确定该结构的大小。这样做的意图是,不完整类型会在程序的其他地方将信息补充完整。

不完整类型的使用是受限的。因为编译器不知道不完整类型的大小,所以不能用它来声明变量:

1
struct t s;  /*** WRONG ***/

但是完全可以定义一个指针类型引用不完整类型:

1
typedef struct t *T;

这个类型定义表明,类型 T 的变量是指向标记为 t 的结构的指针。现在可以声明类型 T 的变量,将其作为函数的参数进行传递,并可以执行其他合法的指针运算(指针的大小并不依赖于它指向的对象,这就解释了为什么 C 语言允许这种行为)。但我们不能对这些变量使用 -> 运算符,因为编译器对 t 结构的成员一无所知。

请参阅

(完)

comments powered by Disqus