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

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

C 语言程序设计:栈抽象数据类型 中描述了栈抽象数据类型,并介绍了几种实现方法。遗憾的是,这里的抽象数据类型存在一些问题,使其达不到工业级强度。下面一起来看看这些问题,并探讨一下可能的解决方案。

一、命名惯例

目前的栈抽象数据类型函数都采用简短、便于记忆的名字:createdestroymake_emptyis_emptyis_fullpushpop。如果在一个程序中有多个抽象数据类型,两个模块中就很可能有同名函数,这样就会导致命名冲突。(例如,每个抽象数据类型都需要自己的 create 函数。)所以,我们可能需要在函数名中加入抽象数据类型本身的名字,比如使用 stack_create 代替 create

二、错误处理

栈抽象数据类型通过显示出错消息或终止程序的方式来处理错误。这是一个不错的处理方式。程序员可以通过在每次调用 pop 之前调用 is_empty,以及在每次调用 push 之前调用 is_full,来避免从空栈中弹出数据项或者向满栈里压入数据项。因此从理论上来讲,对 poppush 的调用没有理由会出错。(但在链表实现中,调用 is_full 并没有效果,后续调用 push 仍然可能出错。)不过,我们可能希望为程序提供一种从这些错误中恢复的途径,而不是简单地终止程序。

一个可选的方案是让 pushpop 函数返回一个 bool 值说明函数调用是否成功。目前 push 的返回类型为 void,所以很容易改为在操作成功时返回 true,当栈已满时返回 false。但修改 pop 函数就困难一些了,因为目前 pop 函数返回的是弹出的值。如果让 pop 返回一个指向弹出的值的指针而不是返回该值本身,那就可以让 pop 返回 NULL 来表示此时栈为空。

最后关于错误处理的一点评论:C 标准库包含带参数的 assert 宏,可以在指定的条件不满足时终止程序。可以用该宏的调用取代目前栈抽象数据类型中使用的 if 语句和 terminate 函数的调用。

三、通用抽象数据类型

C 语言程序设计:栈抽象数据类型 中,我们通过简化对存储在栈中的数据项类型的修改来改进栈抽象数据类型——我们需要做的工作只是改变 Item 类型的定义。这样做仍然有些麻烦,如果栈能够适应任意类型的值而不需要改变 stack.h 文件会更好些。同时我们注意到,现在的抽象数据类型栈还存在一个严重的问题:程序不能创建两个数据类型不同的栈。创建多个栈很容易,但这些栈中的数据项必须具有相同的类型。为了允许多个栈具有不同的数据项类型,需要复制栈抽象数据类型的头文件和源文件,并改变一组文件,使 Stack 类型及相关的函数具有不同的名字。

我们希望有一个“通用”的栈类型,可以用来创建整数栈、字符串栈或者需要的其他类型的栈。在 C 中有很多不同的途径可以做到这一点,但没有一个是完全令人满意的。最常见的一种方法是使用 void * 作为数据项类型,这样就可以压入和弹出任何类型的指针了。如果使用这种方法,stackADT.h 文件和我们最初的版本相似,但 pushpop 函数的原型需要修改为如下形式:

void push(Stack s, void *p);
void *pop(Stack s);

pop 返回一个指向从栈中弹出的数据项的指针,如果栈为空,则返回空指针。

使用 void * 作为数据项类型有两个缺点。第一,这种方法不适用于无法用指针形式表示的数据。数据项可以是字符串(用指向字符串第一个字符的指针表示)或动态分配的结构,但不能是 intdouble 之类的基本类型。第二,不能进行错误检测。存放 void * 数据项的栈允许各种类型的指针共存,因此无法检测出由压入错误的指针类型所导致的错误。

四、新语言中的抽象数据类型

上面讨论的问题在新的基于 C 的语言(如 C++、Java 和 C#)中处理得更好。通过在中定义函数名可以避免命名冲突的问题。栈抽象数据类型可以用一个 Stack 类来表示,栈函数都属于这个类,而且仅当作用于 Stack 对象时才能被编译器识别。这些语言都提供了一种叫作异常处理(exception handling)的特性,允许 pushpop 等函数在检测出错误时“抛出”异常。客户代码可以通过“捕获”异常来处理错误。C++、Java 和 C# 还专门提供了定义通用抽象数据类型的特性。例如,在 C++ 中可以定义一个栈模板而不用指定数据项的类型。

请参阅

(完)

comments powered by Disqus