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