冒號(hào)和他的學(xué)生們
——程序員提高班紀(jì)事
23．?dāng)?shù)據(jù)抽象
善張網(wǎng)者引其綱，不一一攝萬(wàn)目而后得 ——《韓非子·外儲(chǔ)說(shuō)右下》
問(wèn)號(hào)搶著說(shuō)：“我知道了：過(guò)程抽象的結(jié)果是函數(shù)，數(shù)據(jù)抽象的結(jié)果應(yīng)該是數(shù)據(jù)類(lèi)型。”
冒號(hào)首肯：“數(shù)據(jù)類(lèi)型與數(shù)據(jù)運(yùn)算是程序語(yǔ)言的基本要素，除了內(nèi)建的類(lèi)型與運(yùn)算外，程序語(yǔ)言還提供了用戶定義（user-defined）的擴(kuò)展機(jī)制，以提高編程者的效率。正如函數(shù)是一些基本運(yùn)算的復(fù)合，自定義類(lèi)型通常是一些基本類(lèi)型的復(fù)合。不過(guò)單純的復(fù)合類(lèi)型并不是真正意義上的數(shù)據(jù)抽象，我們關(guān)注的是抽象數(shù)據(jù)類(lèi)型（ADT）。”
逗號(hào)說(shuō)了句老實(shí)話：“學(xué)數(shù)據(jù)結(jié)構(gòu)時(shí)常提到抽象數(shù)據(jù)類(lèi)型，但二者究竟什么關(guān)系還真沒(méi)搞明白。”
冒號(hào)解析道：“作為數(shù)據(jù)與運(yùn)算的有機(jī)集合體，它們可看作同一事物的兩個(gè)方面。數(shù)據(jù)結(jié)構(gòu)強(qiáng)調(diào)具體實(shí)現(xiàn)，側(cè)重應(yīng)用；抽象數(shù)據(jù)類(lèi)型強(qiáng)調(diào)抽象接口，側(cè)重設(shè)計(jì)。比如棧、隊(duì)列、鏈表、二叉樹(shù)等作為數(shù)據(jù)結(jié)構(gòu)，人們關(guān)心的是如何利用它們有效地組織數(shù)據(jù)；而作為抽象數(shù)據(jù)類(lèi)型，人們更關(guān)心的是類(lèi)型的設(shè)計(jì)及其背后的數(shù)學(xué)模型。”
引號(hào)推想：“既然有抽象數(shù)據(jù)類(lèi)型，想必就有具體數(shù)據(jù)類(lèi)型吧？”
“這是當(dāng)然。”冒號(hào)肯定道，“具體數(shù)據(jù)類(lèi)型主要用于數(shù)據(jù)儲(chǔ)存，除了getter和setter之外沒(méi)有其他的運(yùn)算。例如由省、市、街道和郵編組成的通訊地址便是一個(gè)典型的具體類(lèi)型，誰(shuí)能告訴我定義這種類(lèi)型的意義？”
句號(hào)回答：“定義這種類(lèi)型可以綁定省、市、街道和郵編這四個(gè)相關(guān)的數(shù)據(jù)，便于統(tǒng)一管理，包括創(chuàng)建、復(fù)制、作為參數(shù)傳遞或作為函數(shù)返回值等等。”
“說(shuō)得不錯(cuò)！”冒號(hào)滿意地點(diǎn)點(diǎn)頭，“J2EE中常用一種設(shè)計(jì)模式：數(shù)據(jù)傳輸對(duì)象（Data Transfer Objects或DTO），又稱(chēng)值對(duì)象（Value Object或VO），這類(lèi)對(duì)象不含任何業(yè)務(wù)邏輯，僅僅作為簡(jiǎn)單的數(shù)據(jù)容器，實(shí)質(zhì)上也屬于具體數(shù)據(jù)類(lèi)型。”
“究竟這里的‘具體’具體在哪里，‘抽象’又抽象在哪里？”嘆號(hào)的眼前飄浮的迷霧也是那么具體而抽象。
冒號(hào)輕輕撥開(kāi)霧靄：“如果一個(gè)數(shù)據(jù)類(lèi)型依賴于其具體實(shí)現(xiàn)，它就是具體的，反之則是抽象的。再拿通訊地址為例，它所有的域即省、市、街道和郵編對(duì)于客戶都應(yīng)該是透明的——至于是通過(guò)getter、setter還是直接訪問(wèn)并無(wú)本質(zhì)區(qū)別，如此用戶才能有針對(duì)性地進(jìn)行數(shù)據(jù)儲(chǔ)存、傳遞和獲取。如果對(duì)該類(lèi)型進(jìn)行修改，比如增加一個(gè)代表國(guó)家的域或者減少代表郵編的域，必須知會(huì)用戶，否則毫無(wú)意義。顯然這種類(lèi)型與實(shí)現(xiàn)細(xì)節(jié)密切相關(guān)，因而是具體的。作為抽象類(lèi)型的例子，讓我們看看隊(duì)列（Queue）吧。隊(duì)列是一種非常基本的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于操作系統(tǒng)、網(wǎng)絡(luò)和現(xiàn)實(shí)生活中。請(qǐng)問(wèn)它的特征是什么？”
引號(hào)最擅長(zhǎng)這類(lèi)問(wèn)題：“隊(duì)列的特征是先進(jìn)先出（FIFO）——每次數(shù)據(jù)只能從隊(duì)尾加入，從隊(duì)首移除。”
“好的。隊(duì)列一般至少包括類(lèi)似數(shù)據(jù)庫(kù)的CRUD（增刪改查）操作：創(chuàng)建操作——建隊(duì)；刪除操作——撤隊(duì)；修改操作——入隊(duì)、出隊(duì)；查詢操作——是否為空隊(duì)、隊(duì)列長(zhǎng)度、隊(duì)首。下面我們用C來(lái)表述隊(duì)列的操作接口。”冒號(hào)投影出一段代碼——
typedef char ItemType; /* 隊(duì)列成員的數(shù)據(jù)類(lèi)型，char可換成其他類(lèi)型 */
/* QueueType待定。。。 */
typedef QueueType* Queue;
/** 初始化隊(duì)列。成功返回0，否則返回-1。*/
int queue_initialize(Queue);
/** 終結(jié)化隊(duì)列 */
void queue_finalize(Queue);
/** 加入隊(duì)列尾部。成功返回0，否則返回-1。*/
int queue_add(Queue, ItemType);
/** 移除隊(duì)列頭部。成功返回0，否則返回-1。*/
int queue_remove(Queue, ItemType*);
/** 隊(duì)列是否為空？*/
int queue_empty(Queue);
/** 隊(duì)列長(zhǎng)度 */
int queue_length(Queue);
/** 返回（但不移除）隊(duì)列頭部。成功返回0，否則返回-1。 */
int queue_head(Queue, ItemType*);
冒號(hào)解釋?zhuān)?#8220;特意用C語(yǔ)言是為了表明ADT不獨(dú)OOP專(zhuān)有。由于C不支持異常（exception），因此用非零返回值來(lái)表示錯(cuò)誤發(fā)生。我們尚未定義隊(duì)列類(lèi)型QueueType，其核心是隊(duì)列的成員集合。無(wú)論是用數(shù)組來(lái)實(shí)現(xiàn)，還是用鏈表來(lái)實(shí)現(xiàn)，用戶根本不需關(guān)心。這便是隊(duì)列的抽象所在——用戶不應(yīng)知道也不必知道它的具體實(shí)現(xiàn)，只能通過(guò)指定接口來(lái)進(jìn)行‘暗箱操作’。這樣經(jīng)過(guò)數(shù)據(jù)抽象，隊(duì)列的本質(zhì)特征由API展現(xiàn)，非本質(zhì)特征則屏蔽于客戶的視野之外。”
問(wèn)號(hào)問(wèn)道：“這種數(shù)據(jù)抽象與前面提到的參數(shù)抽象和規(guī)范抽象有何關(guān)系？”
“參數(shù)抽象使得數(shù)據(jù)接口普適化，規(guī)范抽象使得數(shù)據(jù)接口契約化。”冒號(hào)的回答簡(jiǎn)明扼要，“此外，一個(gè)完整的數(shù)據(jù)抽象除了對(duì)每個(gè)接口作規(guī)范說(shuō)明外，還需對(duì)該數(shù)據(jù)類(lèi)型作整體規(guī)范說(shuō)明，OOP中的類(lèi)注釋文檔即作此用。”
逗號(hào)要求：“能不能給出完整的實(shí)現(xiàn)代碼？光有接口沒(méi)實(shí)現(xiàn)，似乎不太過(guò)癮。”
冒號(hào)戲言：“我感覺(jué)你在把程序當(dāng)煙抽——光有煙嘴的接口，沒(méi)有香煙的實(shí)現(xiàn)，的確不太過(guò)癮。”
眾笑。
冒號(hào)借題發(fā)揮：“許多程序員都有一個(gè)通病：重實(shí)現(xiàn)，輕接口。在編寫(xiě)代碼時(shí)表現(xiàn)為：不等接口設(shè)計(jì)好就技癢難忍，揎拳捋袖地開(kāi)始大干；在閱讀代碼時(shí)表現(xiàn)為：看到API文檔便懨懨欲睡，看到代碼便兩眼放光。務(wù)必謹(jǐn)記：接口是綱，實(shí)現(xiàn)是目。綱若不舉，目無(wú)以張。也就是常說(shuō)的：‘Programming to an Interface, not an Implementation’。不過(guò)為滿足你們的要求，我還是寫(xiě)了一段基于循環(huán)數(shù)組的實(shí)現(xiàn)代碼。”
逗號(hào)正感當(dāng)靶子的滋味不好受，一見(jiàn)代碼便心旌搖蕩，寵辱皆忘了。
/* 隊(duì)列類(lèi)型定義*/
typedef struct
{
ItemType* data; /**//* 隊(duì)列成員數(shù)據(jù) */
int first; /**//* 隊(duì)首位置 */
int last; /**//* 隊(duì)尾位置 */
int count; /**//* 隊(duì)列長(zhǎng)度 */
int size; /**//* 隊(duì)列容量 */
} QueueType; /* 文件QueueImpl.c：隊(duì)列的循環(huán)數(shù)組（circular array）實(shí)現(xiàn) */
int queue_initialize(Queue q)
{
int size = 100; /**//* 初始容量 */
q->size = size;
q->data = (ItemType*)malloc(sizeof(ItemType) * size);
if (q->data == NULL) return -1; /**//* 內(nèi)存不足 */
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;
}
/**//* （內(nèi)部函數(shù)）擴(kuò)大隊(duì)列容量 */
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; /**//* 內(nèi)存不足 */
for (newIndex = 0; newIndex < q->count; ++newIndex) /**//* 復(fù)制到新數(shù)組 */
{
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) /**//* 超出容量后自動(dòng)擴(kuò)容 */
{
if (queue_resize(q) < 0) return -1; /**//* 內(nèi)存不足 */
}
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;
}
“由于函數(shù)queue_resize并非公共接口，因此前面加上static，以避免被外部調(diào)用。與Java中的涵義不同，C中static函數(shù)表示文件內(nèi)部函數(shù)。作為對(duì)比，我們?cè)倏纯搓?duì)列的鏈表實(shí)現(xiàn)。”冒號(hào)說(shuō)罷投影出另兩段代碼——
/* 隊(duì)列類(lèi)型定義*/
typedef struct NodeType
{
ItemType item; /**//* 隊(duì)列成員數(shù)據(jù) */
struct NodeType* next;
} NodeType;
typedef NodeType* Node;
typedef struct
{
Node head; /**//* 隊(duì)首 */
Node tail; /**//* 隊(duì)尾 */
int count; /**//* 隊(duì)列長(zhǎng)度 */
} QueueType;
/* 文件QueueImpl.c：隊(duì)列的鏈表（linked list）實(shí)現(xiàn) */
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; /**//* 內(nèi)存不足 */
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 <= 0) return -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 <= 0) return -1;
*item = q->head->item;
return 0;
}
嘆號(hào)發(fā)現(xiàn)：“兩種實(shí)現(xiàn)方式看起來(lái)迥然不同啊。”
“不同的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，導(dǎo)致不同的算法。正是注意到這一點(diǎn)，人們多采取‘整體設(shè)計(jì)以數(shù)據(jù)為中心，局部實(shí)現(xiàn)以算法為中心’的方針，以增強(qiáng)系統(tǒng)的可維護(hù)性。最后看看示例客戶代碼。”冒號(hào)繼續(xù)放幻燈——
/* 客戶測(cè)試代碼 */
QueueType queue;
Queue q = &queue;
char item;
int i;
queue_initialize(q);
for (i = 0; i < 26; ++i) /**//* 將26個(gè)字母加入隊(duì)列 */
{
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) /**//* 一一出隊(duì) */
{
printf("removing queue item:[%c].\n", item);
}
printf("Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
queue_finalize(q);
冒號(hào)指出：“盡管兩種實(shí)現(xiàn)方式大相徑庭，客戶代碼卻毫無(wú)二致。這種數(shù)據(jù)類(lèi)型的接口與實(shí)現(xiàn)的分離，有利于開(kāi)發(fā)時(shí)間的分離以及開(kāi)發(fā)人員的分離。開(kāi)發(fā)時(shí)間的分離指的是：開(kāi)發(fā)人員可以推遲在不同實(shí)現(xiàn)方式中作抉擇，以保證整體開(kāi)發(fā)進(jìn)程；開(kāi)發(fā)人員的分離指的是：程序的修改和維護(hù)不局限于原作者。”
問(wèn)號(hào)發(fā)現(xiàn)一個(gè)問(wèn)題：“C語(yǔ)法中沒(méi)有private關(guān)鍵詞，用戶仍然有權(quán)訪問(wèn)和修改隊(duì)列的域成員，整個(gè)代碼邏輯有可能被破壞。”
“沒(méi)錯(cuò)。但作為一個(gè)合格的程序員，寫(xiě)出的代碼不僅要合法，還要合理。”冒號(hào)擲地有聲，“合法指合乎語(yǔ)法，合理指合乎語(yǔ)義。既然用到隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，當(dāng)然要遵循其使用規(guī)范。打個(gè)比方，法律只是維護(hù)社會(huì)秩序的最低限度的規(guī)范，一個(gè)只遵守法律而不遵守通用規(guī)范的人必定與社會(huì)格格不入。從另一個(gè)角度看，假設(shè)所有程序員都是遵守規(guī)范的，那么類(lèi)似C這種非OOP語(yǔ)言，只要將數(shù)據(jù)抽象與過(guò)程抽象有機(jī)結(jié)合，同樣具有與OOP不相上下的可維護(hù)性和可重用性。”
引號(hào)有些困惑：“OOP中的類(lèi)是否就是ADT？”
冒號(hào)釋疑：“可以將類(lèi)理解為具有繼承和多態(tài)機(jī)制的ADT。但嚴(yán)格說(shuō)來(lái)，并不是所有的類(lèi)都有抽象性，比如前面提到的僅作存儲(chǔ)用的值對(duì)象。在C#中有值類(lèi)型與引用類(lèi)型之分，分別用struct和class的關(guān)鍵字來(lái)指明。可以把ADT作為選擇原則：是ADT則采用引用類(lèi)型，否則采用值類(lèi)型。C++中struct與class在機(jī)制上沒(méi)有區(qū)別，只是前者成員缺省為public而后者缺省為private。但習(xí)慣上也是前者作具體類(lèi)型，后者作抽象類(lèi)型。Java和C中沒(méi)有類(lèi)似的區(qū)分，一個(gè)只支持class，一個(gè)只支持struct。”
句號(hào)沉吟半晌，忽道：“能不能這樣總結(jié)一下抽象數(shù)據(jù)類(lèi)型？抽象——接口與實(shí)現(xiàn)相分離；數(shù)據(jù)——以數(shù)據(jù)為中心組織邏輯；類(lèi)型——單純而定義良好的概念。”
“精辟！”冒號(hào)贊賞有加，“許多人能將OOP中的封裝、繼承和多態(tài)說(shuō)得頭頭是道，用得得心應(yīng)手，便自認(rèn)為精通OOP了。殊不知抽象——尤其是數(shù)據(jù)抽象——才是OOP的核心和起源，盡管它們并非OOP的專(zhuān)利。沒(méi)有抽象作基礎(chǔ)，封裝、繼承和多態(tài)盡皆無(wú)本之木。只有貫徹ADT思想，設(shè)計(jì)出來(lái)的類(lèi)才會(huì)是‘萬(wàn)人迷’：有優(yōu)雅的外形——抽象，有豐富的內(nèi)涵——數(shù)據(jù)，有鮮明的個(gè)性——類(lèi)型。”
附：示例源代碼下載(queue.rar)