第一章抽象數據類型——信息隱藏 · ANSI C 面向對象編程

# 第一章抽象數據類型——信息隱藏 > 來源：http://blog.csdn.net/besidemyself/article/details/6376408 > 譯者：[besidemyself](http://my.csdn.net/besidemyself) ## 1.1 數據類型數據類型是每種編程語言不可或缺的一部分。ANSI-C（標準化C）擁有一些基本數據類型：`int` ，`double`和`char`。有限的數據類型幾乎不能滿足程序員的要求，所以編程語言會提供一種機制來使得程序員使用這些基本的預定義數據類型構造新的數據類型。一個簡單的應用就是構造集合，如數組，結構體和聯合體。而指針集，依照C.A.R Hare的話：“從這一步起，我們也許永遠不會復蘇”允許我們描述和操作本質上無限復雜的數據。什么才是真正的數據類型呢？我們可以發表不同的觀點。數據類型是一系列值的集合——`char`(字符型)數據類型擁有256個不同的值，`int`（整型）數據類型擁有更多不同值，他們之間的間隔相等，表現形式多少有點像數學中的自然數或整數，而`double`(浮點數據類型)類型擁有更多的可能的值，類似數學中的帶小數部分的數。有選擇性地，我們能夠定義一種數據類型作為一個值的集合加上一系列操作來做一些事情。典型地，定義的這些值計算機能夠表示，這樣的操作過程能夠翻譯成機器指令。在這方面，`int` 型在標準C語言中做的并不是很好。這些數據的集合的值的范圍可能隨著不同機器而不同，操作方式就像算術中的右移操作，表現形式可能不盡相同。太復雜的例子往往不能得到有效的說明。我們可以典型地把一個線性列表中的元素定義成一個結構體如下： ```c typedef struct node { struct node *Next; …information… }node ; ``` 并且，對于這個列表的操作，我們指定列表的頭，如下： ```c node * head (node * elt , const node * tail); ``` 然而，這樣的應用是非常冗余的，好的編程規則指示我們隱藏數據項的表示，僅僅聲明操作方法。 ## 1.2 抽象數據類型如果我們不把對這個數據類型的表示呈現給用戶，則我們稱這個數據類型為抽象數據類型。從理論的角度，要求我們通過包含可能性操作的數學表達式中指定數據類型的屬性。例如，我們從隊列中刪除一個我們先前增加的元素，并且可以從隊列中以相同的次序檢索我們增加的元素。抽象數據類型為程序員提供了很強的便利性。因為表達式不是定義的一部分。我們可以自由的選擇更簡單，更有效的方式去實現。如果我們能夠正確的分離出必要的信息，那么對數據類型的使用和實現將完全的獨立開來。抽象數據類型滿足了“信息隱藏”和“分而治之”的良好編程規則。例如數據項表達式——---- 只給需要知道的人提供，給抽象數據類型的實現者，而不是用戶。通過使用抽象數據類型，我們可以清晰的分離出實現者和使用者的不同任務。并且可很好的把一個大的系統分解成各個小的模塊。 ## 1.3 舉例--——集合由此，我們怎樣的實現一個抽象數據類型呢？我們以對一個集合中的元素操作為例，使用操作方法，`add`（增加），`find`（查找），和`drop`（刪除）。這些方法均用于集合和集合中的元素。`add` 方法向集合中添加一個元素，并返回要添加的元素，`find`方法從集合中查找指定的元素，可被用于實現來判斷一個指定的元素是否在集合中，`drop`方法從集合中刪除一個元素。使用這種方式，即可看到`set`(集合)是一個抽象的數據類型。現在聲明一下我們想要做的，以一個頭文件`Set.h` 開始： ```c #ifndef __USR_SET_H__ #define __USR_SET_H__ extern const void * Object; void* add(void* set,const void* element); void* find(const void* set,const void *element); void* drop(void *set,const void * element); int contains(const void* set,const void* element); #endif ``` 前兩句的作用可使編譯器對這段聲明加以保護處理。無論頭文件`Set.h` 被包含多少次，C編譯器只對這個聲明編譯一次。這樣的聲明頭文件的方法是很標準的，GNU C 預處理器能夠識別，而且當保護符號（如上的`__USR_SET_H__`）被定義，則保證不會再進入保護區聲明的代碼。 `Set.h` 很完整，但它真的很有用嗎？我們幾乎不可能發覺和想象出它的不足：`Set`（集合）理所當然代表一個實例，我們可以使用這個實例來做很多事情。`Add()` 方法傳遞一個元素，并把它添加到集合，并且返回所添加的元素或集合中已經存在的元素；`find()` 在指定的集合中查找元素，并且返回找到的元素，若沒有找到，則返回`NULL`（空）；`drop()` 定位一個元素，把這個元素從集合中刪除，并且返回刪除的元素；`contains()` 的本質就是把`find()` 方法所查找的結果轉換為“真”值。通用指針類型 `void*` 的應用貫穿全文。一方面它使得我們想發現集合到底是什么東西成為不可能。但是另一方面它允許我們向如`add()` 和其他方法中傳遞任意類型的數據。并不是每件事都會擁有像集合和集合中的元素一樣的表現形式——在信息隱藏的樂趣中我們犧牲了類型的安全性。然而，我們可以在第八章看到這樣的應用會非常之安全。 ## 1.4 內存管理也許我們已經瞥見了某些東西：怎樣的獲得一個集合呢？`Set`（集合）是一個指針，并不是被`typedef` 關鍵字定義的類型；因此我們不能把`Set`定義成一個局部或全局的類型。相反的我們只是使用指針來引用集合和集合中的元素，并且建立一個文件`new.h`，并聲明如下： ```c void * new (const void * type, ...); void delete (void * item); ``` 就像`Set.h` 文件一樣的做法，文件被預處理器符號`NEW_H`保護起來。以后只列出感興趣的部分，所有的源代碼和所有實例的代碼均能在光碟中找到。 `new()` 接收一個像`Set`的描述符,傳遞更多可能的參數用于初始化操作，返回一個指向新數據項的攜帶描述符信息的指針。`delete()` 接受一個由`new()` 所原先產生的指針，并回收關聯的資源。 `new()` 和 `delete()` 可看成類似于標準Ｃ函數`calloc()` 和`free()` 。如果的確是，描述符得能夠指示出至少需要申請多大的內存空間。 ## 1.5 （`Object`）對象如果我們想搜集在集合感興趣的東西，我們需要另外一個抽象數據類型`Object` ,在頭文件`Object.h` 中有如下描述： ```c extern const void * Object; /* new(Object); */ int differ (const void * a, const void * b); ``` `differ()` 是用來做對象比較的：即若兩個對象不相等則返回真，否則返回假。這樣的描述為C語言函數`strcmp()` 留有余地：因為在某些比較中我們也許選擇返回一個整數或負數的值來指示排列的次序（正序或倒敘）。現實生活的對象需要更多的功能去做有用的事情。此刻，我們約束我們自己只對集合中的成員（必須品）操作而已。如果我們建立一個更大的類庫，我們將看到所謂的集合 — 實際，包括其他所有東西 — 均是一個對象。從這個觀點出發，很多的對象包含的功能其實都是無條件存在的。 ## 1.6 應用包含頭文件，和庫信息，抽象數據類型，我們能夠寫一個`main.c` 的應用程序如下所示： ```c #include <stdio.h> #include "New.h" #include "Object.h" #include "Set.h" int main() { void* s=new(Set); void* a=add(s,new(Object)); void* b=add(s,new(Object)); void* c=new(Object); if(contains(s,a)&&contains(s,b)){ puts("ok"); } if(contains(s,c)){ puts("contains?"); } if(differ(a,add(s,a))){ puts("differ?"); } if(contains(s,drop(s,a))){ puts("drop?"); } delete(drop(s,a)); delete(drop(s,a)); return 0; } ``` 我們創建了一個結合并給集合中添加了兩個新建的對象。如果不出意外，我們可以發現對象會在集合中，并且我們不會再發現其他的新對象。程序的運行會簡單得打印出ok 。對 `differ()` 的調用會證明出這樣的語義：數學上的集合只包含集合 `a` 的一份拷貝；對一個元素的重復添加必須返回已經加入的對象，因此上述程序的 `differ()` 為假。相似的，一旦我們從一個結合刪除一個元素，它將不會再存在于這個集合中。從一個集合中刪除一個不存在的元素將返回一個空的指針傳遞給 `delete()` 。現在，我們已經指示出 `free()` 的語義且必須是合情合理可接受的。 ## 1.7 一種實現機制——`Set`（集合） `main.c` 會編譯成功，但在連接和執行之前，我們必須實現其中的抽象數據類型和內存管理。如果一個對象不存儲信息，且每個對象最多屬于一個結合，我們可以把每個對象和集合當成，小的，獨立的，正整數的值。可在 `heap[]` 中通過數組下標來索引到。如果一個對象（這里的對象為數組元素的地址）是一個集合的成員，則數組元素的值代表這個集合。對象指向包含它的集合。首先的解決方案是非常簡單的，即我們把其他模塊與`Set.c` 相結合。集合對象集有相似的呈現方式。因此，對于 `new()` 無需關注類型描述。它僅僅從數據 `heap[]` 中返回非零元素。 ```c void * new (const void * type, ...) { int *p ; /*&heap[1...]*/ for(p=heap+1;p<heap+MANY;++p){ if(!*p){/*若heap 中的某個元素為0，則返回這個指針，并把值設為MANY*/ break; } } assert(p<heap+MANY); *p=MANY; return p; } ``` 我們是用`0`來標記 `heap[]` 中有效的元素；因此不能返回`heap[0]` 的引用——如果它是一個集合，而集合的元素可以是索引值為`0`的對象。在一個對象被添加到集合當中之前，我們讓它包含無效的索引`MANY`，以便于`new()` 不會再次返回它，請不能誤解 `MANY` 是集合的一個成員。 `new()` 能夠使用完內存。這是很多“致命性錯誤”的其中一個。我們可以簡單的使用標準化Ｃ語言宏的宏 `assert()` 來標記這些錯誤。一個更理想的實現方式是至少會打印合理的錯誤信息或使用用戶可重寫的錯誤處理機制的通用功能。這也是我們的目的中，編碼技術完整性的一部分。在第13章，我們會介紹一種通用異常處理的技術。 `delete()` 必須得嚴加防范空指針的傳入。通過設置其元素的值為`0` 來進行 `heap[]` 中元素的回收。 ```c void delete (void * _item) { int* item=_item; if(item){ assert(item>heap && item,heap+MANY); *item=0; } } ``` 我們需要統一的處理通用指針；因此，給每個通用指針的變量的前面加上下劃線前綴，然后僅僅使用它初始化指定類型的局部變量。一個集合被它的對象所表示。集合中的每個元素指向它的集合。如果元素包含 `MANY` ，則它可以被添加到一個集合中。否則它已經屬于一個集合的元素了。因為我們不允許一個對象屬于多個集合。 ```c void* add(void* -_set,const void* _element); { int * set=_set; const int *element=_element; assert(set>heap && set<heap+MANY); assert(*set==MANY); assert(element>heap&& element<heap+MANY); if(*element==MANY){ *(int*)element=set-heap; } else{ assert(*element==set-heap); } return (void*) element; } ``` `assert()` 在這里稍微顯得遜色：我們只關注在 `heap[]` 內的指針和集合不屬于其他部分的集合，等等，數組元素的值應該為 `MANY`。其他的功能都是很簡單的。`find()` 只查找元素的值為集合索引的元素。若找到，返回元素，否則返回`NULL`。 ```c void* find(const void* _set,const void * _element) { const int* set=_set; const int* *element=_element; assert(set>heap && set<heap+MANY); assert(*set==MANY); assert(element>heap && element<heap+MANY); assert(*element); return *element==set-heap?(void*)element:0; } ``` `contains()` 把 `find()` 的結果轉換為真值： ```c int contains(const void* _set,const void* _element) { return find(_set,_element)!=0; } ``` `drop()` 依賴于`find()` 的結果，若在集合中查找到，則把此元素的值標記為`MANY`，并返回此元素： ```c void* drop(void * _set,const void * _element) { int* element=find(_set,_element); if(element){ *element=MANY; } return element; } ``` 如果我們深入挖掘，一定會堅持被刪除的元素要不包含于其他集合中。在這種情況下，毫無疑問會在 `drop()` 中復制更多 `find()` 的代碼。我們的實現是很非傳統的。在實現一個集合時似乎不需要 `differ()` 。我們仍然提供它，因為我們的程序要使用這個函數。 ```c int differ (const void * a, const void * b) { return a!=b; } ``` 當數組中對象的索引不同時，這個對象必然是不同的，也就是索引值就能區分它們的不同，但一個簡單的指針比較已經足夠了。我們已經做完了——對于這個問題的解決我們還沒有使用描述符 `Set` 和 `Object` ，但是不得不定義它以使我們的編譯器能通過。 ```c const void * Set; const void * Object; ``` 我們在 main() 函數中使用上述指針來創建集合和對象。 ## 1.8 另一種實現——包不需要改變`Set.h` 中的接口，我們來改變接口的實現方式。這次使用動態內存分配，使用結構體來表示集合和對象： ```c struct Set{ unsigned count; }; struct Object{ unsigned count; struct Set* in; }; ``` `count` 用于跟蹤集合中的元素的計數個數。對于一個元素來說，`count` 記錄這個元素被集合添加的次數。如果我們想遞減`count` 值，可調用 `drop()` 方法。一旦一個元素的`count` 值為`0`，我們就可以刪除它，我們擁有一個包，即，一個集合，集合中的元素擁有一個對`count` 的引用。因為我們使用動態內存分配機制去表示集合集和對象集，所以需要初始化`Set` 和 `Object` 描述符，以便于`new()` 能夠知道需要分配多少內存： ```c static const size_t _Set=sizeof(struct Set); static const size_t _Object=sizeof(struct Object); const void * Set=&_Set; const void * Object=&_Object; ``` `new()` 方法現在更加簡單： ```c void * new (const void * type,...) { const size_t size= *(const size_t*)type; void* p=calloc(1,size); assert(p); return p; } ``` `delete()` 可直接把參數傳遞給 `free()`——標準化C語言中一個空的指針可以傳進 `free()` 。如下：（如意調用） ```c void delete (void * _item) { free(_item); } ``` `add()` 方法多多少少對它的指針自變量比較信任。它會增加元素的引用計數和集合的引用計數。 ```c void* add(void* _set,const void* _element) { struct Set *set=_set; struct Object* element=(void*)_element; assert(set); assert(element); if(!element->in){ element->in=set; } else{ assert(element->in==set); } ++element->count; ++set->count; return element; } ``` `find()` 方法仍然會檢查，一個元素是否指向一個適當的集合： ```c void* find(const void* _set,const void * _element) { const struct Object* element=_element; assert(element); return element->in==_set?(void*)element:0; } ``` `contains()` 方法基于`find()` 方法來實現，仍然保持不變。若 `drop()` 在集合中找到它要操作的元素，它將遞減元素的引用計數和元素在集合中的計數。如果引用計數減為0，這個元素即被從集合中刪除： ```c void* drop(void * _set,const void * _element) { struct Set* set=_set; struct Object* element=find(set,_element); if(element){ if(--element->count==0){ element->in=0; } --set->count; } return element; } ``` 現在我們可以提供一個新的方法，用來獲取集合中的元素個數： ```c unsigned count(const void* _set) { const struct Set* set=_set; assert(set); return set->count; } ``` 當然啦，直接讓程序通過讀 `對象 .count` 顯得比較簡單，但是我會堅持不去披露集這樣的實現。與應用程序重寫臨界值的危險性相比上述功能的調用的開銷是可忽視的。包的表現與集合是不同的。一個元素可被添加多次；當一個元素的刪除次數等于其被添加的次數時，這個元素被從集合中刪除，`contains()` 方法仍然能夠找著它。測試程序的運行結果如下： ``` ok drop? ``` ## 1.9 總結對于抽象數據類型，我們完全隱藏了其實現的細節，例如應用程序代碼中數據項的描述。程序代碼只訪問頭文件，在頭文件中描述符指針表示數據類型，對數據類型的操作作為一種方法被聲明，此方法接收和返回通用指針。描述符指針被傳進通用方法 `new()` 中去獲得一個指向數據項的指針，這個指針被傳進通用方法 `delete()` 中去回收關聯的資源。通常情況，每個抽象數據類型被在單獨的源文件中實現。理想情況下，它不對其他數據類型描述。這個描述符指針正常情況下至少指向一個固定大小的值來指示需要的數據項空間大小。 ## 1.10 練習略。