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

 

冒号和他的学生们

——程序员提高班纪事

 

23.数据抽象

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

  

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

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

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

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

引号推想:“既然有抽象数据类型,想必就有具体数据类型吧?”

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

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

“说得不错!”冒号满意地点点头,“J2EE中常用一种设计模式:数据传输对象Data Transfer ObjectsDTO),又称值对象Value ObjectVO),这类对象不含任何业务逻辑,仅仅作为简单的数据容器,实质上也属于具体数据类型。”

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

冒号轻轻拨开雾霭:“如果一个数据类型依赖于其具体实现,它就是具体的,反之则是抽象的。再拿通讯地址为例,它所有的域即省、市、街道和邮编对于客户都应该是透明的——至于是通过gettersetter还是直接访问并无本质区别,如此用户才能有针对性地进行数据储存、传递和获取。如果对该类型进行修改,比如增加一个代表国家的域或者减少代表邮编的域,必须知会用户,否则毫无意义。显然这种类型与实现细节密切相关,因而是具体的。作为抽象类型的例子,让我们看看队列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) < 0return -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 <= 0return -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 <= 0return -1;

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

 

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

/* 队列类型定义*/

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
    
{
        q
->head = q->tail = node;
    }

    
++q->count;
    
return 0;
}


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

    
*item = oldHead->item;
    q
->head = oldHead->next;
    free(oldHead);
    
if (--q->count == 0)
    
{
        q
->tail = NULL;
    }

    
return 0;
}


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

    
*item = q->head->item;
    
return 0;
}

   

叹号发现:“两种实现方式看起来迥然不同啊。”

“不同的内部数据结构,导致不同的算法。正是注意到这一点,人们多采取‘整体设计以数据为中心,局部实现以算法为中心’的方针,以增强系统的可维护性。最后看看示例客户代码。”冒号继续放幻灯——
    /* 客户测试代码 */

QueueType queue;
Queue q 
= &queue;
char item;
int i;

queue_initialize(q);
for (i = 0; i < 26++i) /* 将26个字母加入队列 */
{
    queue_add(q, 
'a' + i);
}


printf(
"Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
printf(
"Queue length = %d\n", queue_length(q));

while (queue_remove(q, &item) == 0/* 一一出队 */
{
    printf(
"removing queue item:[%c].\n", item);
}


printf(
"Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
queue_finalize(q);

 

冒号指出:“尽管两种实现方式大相径庭,客户代码却毫无二致。这种数据类型的接口与实现的分离,有利于开发时间的分离以及开发人员的分离。开发时间的分离指的是:开发人员可以推迟在不同实现方式中作抉择,以保证整体开发进程;开发人员的分离指的是:程序的修改和维护不局限于原作者。”

问号发现一个问题:“C语法中没有private关键词,用户仍然有权访问和修改队列的域成员,整个代码逻辑有可能被破坏。”

“没错。但作为一个合格的程序员,写出的代码不仅要合法,还要合理。”冒号掷地有声,“合法指合乎语法,合理指合乎语义。既然用到队列这个数据结构,当然要遵循其使用规范。打个比方,法律只是维护社会秩序的最低限度的规范,一个只遵守法律而不遵守通用规范的人必定与社会格格不入。从另一个角度看,假设所有程序员都是遵守规范的,那么类似C这种非OOP语言,只要将数据抽象与过程抽象有机结合,同样具有与OOP不相上下的可维护性和可重用性。”

引号有些困惑:“OOP中的类是否就是ADT?”

冒号释疑:“可以将类理解为具有继承和多态机制的ADT。但严格说来,并不是所有的类都有抽象性,比如前面提到的仅作存储用的值对象。在C#中有值类型引用类型之分,分别用structclass的关键字来指明。可以把ADT作为选择原则:是ADT则采用引用类型,否则采用值类型。C++structclass在机制上没有区别,只是前者成员缺省为public而后者缺省为private。但习惯上也是前者作具体类型,后者作抽象类型。JavaC中没有类似的区分,一个只支持class,一个只支持struct。”

句号沉吟半晌,忽道:“能不能这样总结一下抽象数据类型?抽象——接口与实现相分离;数据——以数据为中心组织逻辑;类型——单纯而定义良好的概念。”

“精辟!”冒号赞赏有加,“许多人能将OOP中的封装、继承和多态说得头头是道,用得得心应手,便自认为精通OOP了。殊不知抽象——尤其是数据抽象——才是OOP的核心和起源,尽管它们并非OOP的专利。没有抽象作基础,封装、继承和多态尽皆无本之木。只有贯彻ADT思想,设计出来的类才会是‘万人迷’:有优雅的外形——抽象,有丰富的内涵——数据,有鲜明的个性——类型。”

附:示例源代码下载(queue.rar)

posted on 2008-07-16 12:32 郑晖 阅读(2235) 评论(6)  编辑  收藏 所属分类: 冒号和他的学生们

评论

# re: 冒号和他的学生们(连载23)——数据抽象 2008-07-16 14:28 着重号

. 期待更加精彩的文章  回复  更多评论   

# re: 冒号和他的学生们(连载23)——数据抽象 2008-07-16 16:40 wangxiaojs@gmail.com

好!  回复  更多评论   

# re: 冒号和他的学生们(连载23)——数据抽象 2008-07-16 22:00 无羽苍鹰

精彩,,学习了。。支持下  回复  更多评论   

# re: 冒号和他的学生们(连载23)——数据抽象 2008-07-18 16:36 隔叶黄莺

"有优雅的外形——抽象,有丰富的内涵——数据,有鲜明的个性——类型"

精辟!  回复  更多评论   

# re: 冒号和他的学生们(连载23)——数据抽象 2008-07-19 08:02 支持支持

好!多谢博主的专业与专心!!!  回复  更多评论   

# re: 冒号和他的学生们(连载23)——数据抽象 2009-01-19 13:52 duxu

真不是盖的  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

导航

统计

公告

博客搬家:http://blog.zhenghui.org
《冒号课堂》一书于2009年10月上市,详情请见
冒号课堂

留言簿(17)

随笔分类(61)

随笔档案(61)

文章分类(1)

文章档案(1)

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜