冒号和他的学生们―程序员提高班纪事23数据抽象管理资料.pdf

欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！冒号和他的学生们程序员提高班纪事 23：数据抽象-管理资料 系列文章汇总：冒号和他的学生们程序员提高班纪事 数据抽象 善张网者引其纲，不一一摄万目而后得韩非子外储说右下 问号抢着说：“我知道了：过程抽象的结果是函数，数据抽象的结果应该是数据类型，冒号和他的学生们程序员提高班纪事 23：数据抽象。”冒号首肯：“数据类型与数据运算是程序语言的基本要素，除了内建的类型与运算外，程序语言还提供了用户定义（user-defined）的扩展机制，以提高编程者的效率。正如函数是一些基本运算的复合，自定义类型通常是一些基本类型的复合。不过单纯的复合类型并不是真正意义上的数据抽象，我们关注的是抽象数据类型（ADT）。”逗号说了句老实话：“学数据结构时常提到抽象数据类型，但二者究竟什么关系还真没搞明白。”冒号解析道：“作为数据与运算的有机集合体，它们可看作同一事物的两个方面。数据结构强调具体实现，侧重应用；抽象数据类型强调抽象接口，侧重设计。比如栈、队列、链表、二叉树等作为数据结构，人们关心的是如何利用它们有效地组织数据；而作为抽象数据类型，人们更关心的是类型的设计及其背后的数学模型。”引号推想：“既然有抽象数据类型，想必就有具体数据类型吧？”“这是当然。”冒号肯定道，“具体数据类型主要用于数据储存，除了getter 和 setter 之外没有其他的运算。例如由省、市、街道和邮编组成的通讯地址便是一个典型的具体类型，谁能告诉我定义这种类型的意义？”句号回答：“定义这种类型可以绑定省、市、街道和邮编这四个相关的数据，便于统一管理，包括创建、复制、作为参数传递或作为函数返回值等等。”欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！“说得不错！”冒号满意地点点头，“J2EE 中常用一种设计模式：数据传输对象（Data Transfer Objects 或 DTO），又称值对象（Value Object 或VO），这类对象不含任何业务逻辑，仅仅作为简单的数据容器，实质上也属于具体数据类型。”“究竟这里的具体具体在哪里，抽象又抽象在哪里？”叹号的眼前飘浮的迷雾也是那么具体而抽象。冒号轻轻拨开雾霭：“如果一个数据类型依赖于其具体实现，它就是具体的，反之则是抽象的。再拿通讯地址为例，它所有的域即省、市、街道和邮编对于客户都应该是透明的至于是通过 getter、setter 还是直接访问并无本质区别，如此用户才能有针对性地进行数据储存、传递和获取。如果对该类型进行修改，比如增加一个代表国家的域或者减少代表邮编的域，必须知会用户，否则毫无意义。显然这种类型与实现细节密切相关，因而是具体的。作为抽象类型的例子，让我们看看队列（Queue）吧。队列是一种非常基本的数据结构，广泛应用于操作系统、网络和现实生活中。请问它的特征是什么？”引号最擅长这类问题：“队列的特征是先进先出（FIFO）每次数据只能从队尾加入，从队首移除。”“好的。队列一般至少包括类似数据库的 CRUD（增删改查）操作：创建操作建队；删除操作撤队；修改操作入队、出队；查询操作是否为空队、队列长度、队首。下面我们用 C 来表述队列的操作接口。”冒号投影出一段代码 typedefcharItemType;/*队列成员的数据类型，char 可换成其他类型*/*QueueType 待定。*/typedef QueueType*Queue;/初始化队列。成功返回 0，否则返回-1。*/intqueue_initialize(Queue);/终结化队列*/voidqueue_finalize(Queue);/加入队列尾部。成功返回 0，否则返回-1。*/intqueue_add(Queue,ItemType);欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！/移除队列头部。成功返回 0，否则返回-1。*/intqueue_remove(Queue,ItemType*);/队列是否为空？*/intqueue_empty(Queue);/队列长度*/intqueue_length(Queue);/返回（但不移除）队列头部。成功返回 0，否则返回-1。*/intqueue_head(Queue,ItemType*);冒号解释：“特意用 C 语言是为了表明 ADT 不独 OOP 专有。由于 C 不支持异常（exception），因此用非零返回值来表示错误发生。我们尚未定义队列类型 QueueType，其核心是队列的成员集合。无论是用数组来实现，还是用链表来实现，用户根本不需关心。这便是队列的抽象所在用户不应知道也不必知道它的具体实现，只能通过指定接口来进行暗箱操作。这样经过数据抽象，队列的本质特征由 API 展现，非本质特征则屏蔽于客户的视野之外。”问号问道：“这种数据抽象与前面提到的参数抽象和规范抽象有何关系？”“参数抽象使得数据接口普适化，规范抽象使得数据接口契约化。”冒号的回答简明扼要，“此外，一个完整的数据抽象除了对每个接口作规范说明外，还需对该数据类型作整体规范说明，OOP 中的类注释文档即作此用。”逗号要求：“能不能给出完整的实现代码？光有接口没实现，似乎不太过瘾。”冒号戏言：“我感觉你在把程序当烟抽光有烟嘴的接口，没有香烟的实现，的确不太过瘾。”众笑。冒号借题发挥：“许多程序员都有一个通病：重实现，轻接口。在编写代码时表现为：不等接口设计好就技痒难忍，揎拳捋袖地开始大干；在阅读代码时表现为：看到 API 文档便恹恹欲睡，看到代码便两眼放光。务必谨记：接口是纲，实现是目。纲若不举，目无以张。也就是常说的：Programming to an Interface,not an Implementation。不过为满足你们的要求，我还是写了一段基于循环数组的实现代码。”欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！逗号正感当靶子的滋味不好受，一见代码便心旌摇荡，宠辱皆忘了。/*队列类型定义*/*文件QueueImpl.c：队列的循环数组（circular array）实现*/typedefstruct ItemType*data;/*队列成员数据*/intfirst;/*队首位置*/intlast;/*队尾位置*/intcount;/*队列长度*/intsize;/*队列容量*/QueueType;intqueue_initialize(Queue q)intsize=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;return0;欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！voidqueue_finalize(Queue q)free(q-data);q-data=NULL;q-first=0;q-count=0;intqueue_empty(Queue q)returnq-countcount;/*（内部函数）扩大队列容量*/staticintqueue_resize(Queue q)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！intoldSize=q-size;intnewSize=oldSize*2;intnewIndex;intoldIndex=q-first;ItemType*data=(ItemType*)malloc(sizeof(ItemType)*newSize);if(data=NULL)return-1;/*内存不足*/for(newIndex=0;newIndex count;+newIndex)/*复制到新数组*/datanewIndex=q-dataoldIndex;oldIndex=(oldIndex+1)%oldSize;free(q-data);q-data=data;q-first=0;q-last=oldSize-1;q-size=newSize;return0;intqueue_add(Queue q,ItemType item)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！if(q-count=q-size)/*超出容量后自动扩容*/if(queue_resize(q)last=(q-last+1)%q-size;q-dataq-last=item;+q-count;return0;intqueue_remove(Queue q,ItemType*item)if(q-countdataq-first;q-first=(q-first+1)%q-size;-q-count;return0;intqueue_head(Queue q,ItemType*item)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！if(q-countdataq-first;return0;“由于函数 queue_resize 并非公共接口，因此前面加上 static，以避免被外部调用，管理资料 冒号和他的学生们程序员提高班纪事23：数据抽象。与 Java 中的涵义不同，C 中 static 函数表示文件内部函数。作为对比，我们再看看队列的链表实现。”冒号说罢投影出另两段代码 /*队列类型定义*/typedefstructNodeType ItemType item;/*队列成员数据*/structNodeType*next;NodeType;typedef NodeType*Node;typedefstruct 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！Node head;/*队首*/Node tail;/*队尾*/intcount;/*队列长度*/QueueType;/*文件QueueImpl.c：队列的链表（linked list）实现*/intqueue_initialize(Queue q)q-head=NULL;q-tail=NULL;q-count=0;return0;voidqueue_finalize(Queue q)ItemType item;while(queue_remove(q,&item)=0);intqueue_empty(Queue q)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！returnq-countcount;intqueue_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;return0;intqueue_remove(Queue q,ItemType*item)Node oldHead=q-head;if(q-countitem;q-head=oldHead-next;free(oldHead);if(-q-count=0)q-tail=NULL;return0;intqueue_head(Queue q,ItemType*item)if(q-counthead-item;return0;叹号发现：“两种实现方式看起来迥然不同啊。”“不同的内部数据结构，导致不同的算法。正是注意到这一点，人们多采取整体设计以数据为中心，局部实现以算法为中心的方针，以增强系统的可维护性。最后看看示例客户代码。”冒号继续放幻灯 /*客户测试代码*/QueueType queue;Queue q=&queue;charitem;inti;queue_initialize(q);for(i=0;i26;+i)/*将 26 个字母加入队列*/queue_add(q,a+i);printf(Queue is%s,queue_empty(q)?empty:nonempty);printf(Queue length=%d,queue_length(q);欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！while(queue_remove(q,&item)=0)/*一一出队*/printf(removing queue item:%c.,item);printf(Queue is%s,queue_empty(q)?empty:nonempty);queue_finalize(q);冒号指出：“尽管两种实现方式大相径庭，客户代码却毫无二致。这种数据类型的接口与实现的分离，有利于开发时间的分离以及开发人员的分离。开发时间的分离指的是：开发人员可以推迟在不同实现方式中作抉择，以保证整体开发进程；开发人员的分离指的是：程序的修改和维护不局限于原作者。”问号发现一个问题：“C 语法中没有 private 关键词，用户仍然有权访问和修改队列的域成员，整个代码逻辑有可能被破坏。”“没错。但作为一个合格的程序员，写出的代码不仅要合法，还要合理。”冒号掷地有声，“合法指合乎语法，合理指合乎语义。既然用到队列这个数据结构，当然要遵循其使用规范。打个比方，法律只是维护社会秩序的最低限度的规范，一个只遵守法律而不遵守通用规范的人必定与社会格格不入。从另一个角度看，假设所有程序员都是遵守规范的，那么类似C 这种非 OOP 语言，只要将数据抽象与过程抽象有机结合，同样具有与 OOP 不相上下的可维护性和可重用性。”引号有些困惑：“OOP 中的类是否就是 ADT？”冒号释疑：“可以将类理解为具有继承和多态机制的ADT。但严格说来，并不是所有的类都有抽象性，比如前面提到的仅作存储用的值对象。在C#中有值类型与引用类型之分，分别用 struct 和 class 的关键字来指明。可以把 ADT作为选择原则：是 ADT 则采用引用类型，否则采用值类型。C+中 struct 与 class在机制上没有区别，只是前者成员缺省为 public 而后者缺省为 private。但习惯上也是前者作具体类型，后者作抽象类型。Java 和 C 中没有类似的区分，一个只支持 class，一个只支持 struct。”句号沉吟半晌，忽道：“能不能这样总结一下抽象数据类型？抽象接口与实现相分离；数据以数据为中心组织逻辑；类型单纯而定义良好的概念。”欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！“精辟！”冒号赞赏有加，“许多人能将 OOP 中的封装、继承和多态说得头头是道，用得得心应手，便自认为精通 OOP 了。殊不知抽象尤其是数据抽象才是 OOP 的核心和起源，尽管它们并非 OOP 的专利。没有抽象作基础，封装、继承和多态尽皆无本之木。只有贯彻 ADT 思想，设计出来的类才会是万人迷：有优雅的外形抽象，有丰富的内涵数据，有鲜明的个性类型。”附：示例源代码下载(queue.rar)（酷勤网备用下载地址：queue.rar 2.9k）来自：/xyz98/archive/2008/07/16/215180.html