冒號和他的學生們
——程序員提高班紀事
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
{
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;
}
嘆號發現：“兩種實現方式看起來迥然不同啊。”
“不同的內部數據結構，導致不同的算法。正是注意到這一點，人們多采取‘整體設計以數據為中心，局部實現以算法為中心’的方針，以增強系統的可維護性。最后看看示例客戶代碼。”冒號繼續放幻燈——
/* 客戶測試代碼 */
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#中有值類型與引用類型之分，分別用struct和class的關鍵字來指明。可以把ADT作為選擇原則：是ADT則采用引用類型，否則采用值類型。C++中struct與class在機制上沒有區別，只是前者成員缺省為public而后者缺省為private。但習慣上也是前者作具體類型，后者作抽象類型。Java和C中沒有類似的區分，一個只支持class，一個只支持struct。”
句號沉吟半晌，忽道：“能不能這樣總結一下抽象數據類型？抽象——接口與實現相分離；數據——以數據為中心組織邏輯；類型——單純而定義良好的概念。”
“精辟！”冒號贊賞有加，“許多人能將OOP中的封裝、繼承和多態說得頭頭是道，用得得心應手，便自認為精通OOP了。殊不知抽象——尤其是數據抽象——才是OOP的核心和起源，盡管它們并非OOP的專利。沒有抽象作基礎，封裝、繼承和多態盡皆無本之木。只有貫徹ADT思想，設計出來的類才會是‘萬人迷’：有優雅的外形——抽象，有豐富的內涵——數據，有鮮明的個性——類型。”
附：示例源代碼下載(queue.rar)