冒号和他的学生们（连载23）——数据抽象

 

冒号和他的学生们

——程序员提高班纪事

 

23．数据抽象

善张网者引其纲，不一一摄万目而后得            ——《韩非子·外储说右下》

  

问号抢着说：“我知道了：过程抽象的结果是函数，数据抽象的结果应该是数据类型。”

冒号首肯：“数据类型与数据运算是程序语言的基本要素，除了内建的类型与运算外，程序语言还提供了用户定义（user-defined）的扩展机制，以提高编程者的效率。正如函数是一些基本运算的复合，自定义类型通常是一些基本类型的复合。不过单纯的复合类型并不是真正意义上的数据抽象，我们关注的是抽象数据类型（ADT）。”

逗号说了句老实话：“学数据结构时常提到抽象数据类型，但二者究竟什么关系还真没搞明白。”

冒号解析道：“作为数据与运算的有机集合体，它们可看作同一事物的两个方面。数据结构强调具体实现，侧重应用；抽象数据类型强调抽象接口，侧重设计。比如栈、队列、链表、二叉树等作为数据结构，人们关心的是如何利用它们有效地组织数据；而作为抽象数据类型，人们更关心的是类型的设计及其背后的数学模型。”

引号推想：“既然有抽象数据类型，想必就有具体数据类型吧？”

“这是当然。”冒号肯定道，“具体数据类型主要用于数据储存，除了getter和setter之外没有其他的运算。例如由省、市、街道和邮编组成的通讯地址便是一个典型的具体类型，谁能告诉我定义这种类型的意义？”

句号回答：“定义这种类型可以绑定省、市、街道和邮编这四个相关的数据，便于统一管理，包括创建、复制、作为参数传递或作为函数返回值等等。”

“说得不错！”冒号满意地点点头，“J2EE中常用一种设计模式：数据传输对象（Data Transfer Objects或DTO），又称值对象（Value Object或VO），这类对象不含任何业务逻辑，仅仅作为简单的数据容器，实质上也属于具体数据类型。”

“究竟这里的‘具体’具体在哪里，‘抽象’又抽象在哪里？”叹号的眼前飘浮的迷雾也是那么具体而抽象。

冒号轻轻拨开雾霭：“如果一个数据类型依赖于其具体实现，它就是具体的，反之则是抽象的。再拿通讯地址为例，它所有的域即省、市、街道和邮编对于客户都应该是透明的——至于是通过getter、setter还是直接访问并无本质区别，如此用户才能有针对性地进行数据储存、传递和获取。如果对该类型进行修改，比如增加一个代表国家的域或者减少代表邮编的域，必须知会用户，否则毫无意义。显然这种类型与实现细节密切相关，因而是具体的。作为抽象类型的例子，让我们看看队列（Queue）吧。队列是一种非常基本的数据结构，广泛应用于操作系统、网络和现实生活中。请问它的特征是什么？”

引号最擅长这类问题：“队列的特征是先进先出（FIFO）——每次数据只能从队尾加入，从队首移除。”

“好的。队列一般至少包括类似数据库的CRUD（增删改查）操作：创建操作——建队；删除操作——撤队；修改操作——入队、出队；查询操作——是否为空队、队列长度、队首。下面我们用C来表述队列的操作接口。”冒号投影出一段代码——

typedef char ItemType;         /* 队列成员的数据类型，char可换成其他类型  */

/* QueueType待定。。。 */

typedef QueueType* Queue;

/** 初始化队列。成功返回0，否则返回-1。*/
int queue_initialize(Queue);

/** 终结化队列 */
void queue_finalize(Queue);

/** 加入队列尾部。成功返回0，否则返回-1。*/
int queue_add(Queue, ItemType);

/** 移除队列头部。成功返回0，否则返回-1。*/
int queue_remove(Queue, ItemType*);

/** 队列是否为空？*/
int queue_empty(Queue);

/** 队列长度 */
int queue_length(Queue);

/** 返回（但不移除）队列头部。成功返回0，否则返回-1。 */
int queue_head(Queue, ItemType*);

冒号解释：“特意用C语言是为了表明ADT不独OOP专有。由于C不支持异常（exception），因此用非零返回值来表示错误发生。我们尚未定义队列类型QueueType，其核心是队列的成员集合。无论是用数组来实现，还是用链表来实现，用户根本不需关心。这便是队列的抽象所在——用户不应知道也不必知道它的具体实现，只能通过指定接口来进行‘暗箱操作’。这样经过数据抽象，队列的本质特征由API展现，非本质特征则屏蔽于客户的视野之外。”

问号问道：“这种数据抽象与前面提到的参数抽象和规范抽象有何关系？”

“参数抽象使得数据接口普适化，规范抽象使得数据接口契约化。”冒号的回答简明扼要，“此外，一个完整的数据抽象除了对每个接口作规范说明外，还需对该数据类型作整体规范说明，OOP中的类注释文档即作此用。”

逗号要求：“能不能给出完整的实现代码？光有接口没实现，似乎不太过瘾。”

冒号戏言：“我感觉你在把程序当烟抽——光有烟嘴的接口，没有香烟的实现，的确不太过瘾。”

众笑。

冒号借题发挥：“许多程序员都有一个通病：重实现，轻接口。在编写代码时表现为：不等接口设计好就技痒难忍，揎拳捋袖地开始大干；在阅读代码时表现为：看到API文档便恹恹欲睡，看到代码便两眼放光。务必谨记：接口是纲，实现是目。纲若不举，目无以张。也就是常说的：‘Programming to an Interface, not an Implementation’。不过为满足你们的要求，我还是写了一段基于循环数组的实现代码。”

逗号正感当靶子的滋味不好受，一见代码便心旌摇荡，宠辱皆忘了。

/* 队列类型定义*/

typedef struct
{
    ItemType* data;         /* 队列成员数据  */
    int first;                      /* 队首位置 */
    int last;                       /* 队尾位置 */
    int count;                    /* 队列长度 */
    int size;                       /* 队列容量 */ 
} QueueType;

 /* 文件QueueImpl.c：队列的循环数组（circular array）实现 */

int queue_initialize(Queue q)
{
    int size = 100;             /* 初始容量 */
    q->size = size;
    q->data = (ItemType*)malloc(sizeof(ItemType) * size);
    if (q->data == NULL) return -1; /* 内存不足 */

    q->first = 0;
    q->last = -1;
    q->count = 0;
    return 0;
}

void queue_finalize(Queue q)
{
    free(q->data);
    q->data = NULL;
    q->first = 0;
    q->count = 0;
}

int queue_empty(Queue q)
{
    return q->count <= 0;
}

int queue_length(Queue q)
{
    return q->count;
}

/* （内部函数）扩大队列容量 */
static int queue_resize(Queue q)
{
    int oldSize = q->size;
    int newSize = oldSize * 2;
    int newIndex;
    int oldIndex = q->first;
    ItemType* data = (ItemType*)malloc(sizeof(ItemType) * newSize);

    if (data == NULL) return -1; /* 内存不足 */

    for (newIndex = 0; newIndex < q->count; ++newIndex) /* 复制到新数组  */
    {
        data[newIndex] = q->data[oldIndex];
        oldIndex = (oldIndex + 1) % oldSize;
    }

    free(q->data);
    q->data = data;
    q->first = 0;
    q->last = oldSize - 1;
    q->size = newSize;
    return 0;
}

int queue_add(Queue q, ItemType item)
{
    if (q->count >= q->size) /* 超出容量后自动扩容 */
    {
        if (queue_resize(q) < 0) return -1;   /* 内存不足 */
    }

    q->last = (q->last + 1) % q->size;
    q->data[q->last] = item;    
    ++q->count;
    return 0;
}

int queue_remove(Queue q, ItemType* item)
{
    if (q->count <= 0) return -1;

    *item = q->data[q->first];
    q->first = (q->first + 1) % q->size;
    --q->count;
    return 0;
}

int queue_head(Queue q, ItemType* item)
{
    if (q->count <= 0) return -1;

    *item = q->data[q->first];
    return 0;
}

 

“由于函数queue_resize并非公共接口，因此前面加上static，以避免被外部调用。与Java中的涵义不同，C中static函数表示文件内部函数。作为对比，我们再看看队列的链表实现。”冒号说罢投影出另两段代码——

/* 队列类型定义*/

typedef struct NodeType
{
    ItemType item;                  /* 队列成员数据 */
    struct NodeType* next;
} NodeType;

typedef NodeType* Node;

typedef struct
{
    Node head;                      /* 队首 */
    Node tail;                       /* 队尾 */
    int count;                       /* 队列长度 */
} QueueType;

/* 文件QueueImpl.c：队列的链表（linked list）实现 */

int queue_initialize(Queue q)
{
    q->head = NULL;
    q->tail = NULL;
    q->count = 0;
    return 0;
}

void queue_finalize(Queue q)
{
    ItemType item;
    while (queue_remove(q, &item) >= 0)
        ;
}

int queue_empty(Queue q)
{
    return q->count <= 0;
}

int queue_length(Queue q)
{
    return q->count;
}

int queue_add(Queue q, ItemType item)
{
    Node node = (Node)malloc(sizeof(NodeType));
    if (node == NULL) return -1; /* 内存不足 */

    node->item = item;
    node->next = NULL;
    if (q->tail)
    {
        q->tail->next = node;
        q->tail = node;
    }
    else