本文介紹瞭如何設計和定義一個新的數據類型，具體包括建立抽象、建立接口和實現接口三個部分。總結這三步法：從思考“做什麼”（抽象）到規定“怎麼做才對”（接口），最後才是“怎麼做到”（實現），這是編寫健壯、清晰、可維護代碼的基石。

引言

設計一種數據類型包括設計如何儲存該數據類型（屬性）和設計一系列管理該數據的函數（操作）。

計算機科學領域已開發了一種定義新類型的好方法，用3個步驟完成從抽象到具體的過程。

1. 提供類型屬性和相關操作的抽象描述。這些描述既不能依賴特定的實現，也不能依賴特定的編程語言。這種正式的抽象描述被稱為抽象數據類型（ADT）。
2. 開發一個實現 ADT 的編程接口。也就是説，指明如何儲存數據和執行所需操作的函數。例如在C中，可以提供結構定義和操控該結構的函數原型。這些作用於用户定義類型的函數相當於作用於C基本類型的內置運算符。需要使用該新類型的程序員可以使用這個接口進行編程。
3. 編寫代碼實現接口。這一步至關重要，但是使用該新類型的程序員無需瞭解具體的實現細節。

抽象數據類型以面向問題而不是面向語言的方式，把解決問題的方法和數據表示結合起來。設計一個ADT後，可以在不同的環境中複用。理解ADT可以為將來學習面向對象程序設計（OOP）以及C++語言做好準備。

建立抽象

以鏈表為例，非正式但抽象的鏈表定義是：鏈表是一個能儲存一系列項且可以對其進行所需操作的數據對象。該定義既未説明鏈表中可以儲存什麼項，也未指定是用數組、結構還是其他數據形式來儲存項，而且並未規定用什麼方法來實現操作（如，查找鏈表中元素的個數）。這些細節都留給實現完成。

為了讓示例儘量簡單，一種簡化的鏈表類型總結如下：

類型名： 簡單鏈表

類型屬性： 可以儲存一系列項

類型操作： 初始化鏈表為空

確定鏈表為空

確定鏈表已滿

確定鏈表中的項數

在鏈表末尾添加項

遍歷鏈表，處理鏈表中的項

清空鏈表

下一步是為開發簡單鏈表ADT開發一個C接口。

建立接口

這個簡單鏈表的接口有兩個部分。第1部分是描述如何表示數據，第2部分是描述實現ADT操作的函數。接口設計應儘量與ADT的描述保持一致。因此，應該用某種通用的Item類型而不是一些特殊類型，如 int 或 struct film 。可以用C的 typedef 功能來定義所需的Item類型：

#define TSIZE 45 /* 儲存電影名的數組大小 */
struct film
{
    char title[TSIZE];
    int rating;
};
typedef struct film Item;

然後，就可以在定義的其餘部分使用 Item 類型。如果以後需要其他數據形式的鏈表，可以重新定義Item類型，不必更改其餘的接口定義。定義了 Item 之後，現在必須確定如何儲存這種類型的項。實際上這一步屬於實現步驟，但是現在決定好可以讓示例更簡單些。這裏採用鏈節節點結構：

typedef struct node
{
    Item item;
    struct node * next;
} Node;
typedef Node * List;

在鏈表的實現中，每一個鏈節叫作節點（node）。每個節點包含形成鏈表內容的信息和指向下一個節點的指針。為了強調這個術語，我們把node作為節點結構的標記名，並使用typedef把Node作為struct node結構的類型名。最後，為了管理鏈表，還需要一個指向鏈表開始處的指針，我們使用typedef把List作為該類型的指針名。因此，下面的聲明：

List movies;

創建了該鏈表所需類型的指針movies。
這是否是定義List類型的唯一方法？不是。例如，還可以添加一個變量記錄項數，添加第2個指針儲存鏈表的末尾：

typedef struct list
{
    Node * head; /* 指向鏈表頭的指針 */
    Node * tail; /* 指向鏈表尾的指針 */
    int size;    /* 鏈表中的項數 */
} List; /* List的另一種定義 */

現在，還是使用List類型的第1種定義。這裏要着重理解下面的聲明創建了一個鏈表，而不一個指向節點的指針或一個結構：

List movies;

movies代表的確切數據應該是接口層次不可見的實現細節（不好理解的話可以代入上面的包含尾指針和項數的List定義）。

為了指導用户使用，可以在函數原型前面提供以下注釋：

/* 操作：初始化一個鏈表 */
/* 前提條件：plist指向一個鏈表*/
/* 後置條件：該鏈表初始化為空 */
void InitializeList(List * plist);

這裏要注意3點。第1，註釋中的“前提條件”（precondition）是調用該函數前應具備的條件。例如，需要一個待初始化的鏈表。第2，註釋中的“後置條件”（postcondition）是執行完該函數後的情況。第3，該函數的參數是一個指向鏈表的指針，而不是一個鏈表。所以應該這樣調用該函數：

InitializeList(&movies);

C語言把所有類型和函數的信息集合成一個軟件包的方法是：把類型定義和函數原型（包括前提條件和後置條件註釋）放在一個頭文件中。該文件應該提供程序員使用該類型所需的所有信息。

程序清單list.h給出了一個簡單鏈表類型的頭文件。該程序定義了一個特定的結構作為Item類型，然後根據Item定義了Node，再根據Node定義了List。然後，把表示鏈表操作的函數設計為接受Item類型和List類型的參數。如果函數要修改一個參數，那麼該參數的類型應是指向相應類型的指針，而不是該類型。在頭文件中，把組成函數名的每個單詞的首字母大寫，以這種方式表明這些函數是接口包的一部分。另外，該文件使用 #ifndef 指令，防止多次包含一個文件。

/* list.h -- 簡單鏈表類型的頭文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99特性 */
/* 特定程序的聲明 */
#define TSIZE 45 /* 儲存電影名的數組大小 */
struct film
{
    char title[TSIZE];
    int rating;
};
/* 一般類型定義 */
typedef struct film Item;
typedef struct node
{
    Item item;
    struct node * next;
} Node;
typedef Node * List;

/* 函數原型 */

/*操作： 初始化一個鏈表 */
/*前提條件：plist指向一個鏈表 */
/*後置條件：鏈表初始化為空 */
void InitializeList(List * plist);

/*操作： 確定鏈表是否為空定義 */
/*前提條件：plist指向一個已初始化的鏈表 */
/*後置條件：如果鏈表為空，該函數返回true；否則返回false */
bool ListIsEmpty(const List *plist);

/*操作： 確定鏈表是否已滿 */
/*前提條件：plist指向一個已初始化的鏈表 */
/*後置條件：如果鏈表已滿，該函數返回真；否則返回假 */
bool ListIsFull(const List *plist);

/*操作： 確定鏈表中的項數 */
/*前提條件：plist指向一個已初始化的鏈表 */
/*後置條件：該函數返回鏈表中的項數 */
unsigned int ListItemCount(const List *plist);

/*操作： 在鏈表的末尾添加項 */
/*前提條件： item是一個待添加至鏈表的項, plist指向一個已初始化的鏈表 */
/*後置條件：如果可以，該函數在鏈表末尾添加一個項，且返回true；否則返回false */
bool AddItem(Item item, List * plist);

/*操作： 把函數作用於鏈表中的每一項 */
/*前提條件：plist指向一個已初始化的鏈表 */
/*前提條件：pfun指向一個函數，該函數接受一個Item類型的參數，且無返回值 */
/*後置條件：pfun指向的函數作用於鏈表中的每一項一次 */
void Traverse(const List *plist, void(*pfun)(Item item));

/*操作：釋放已分配的內存（如果有的話） */
/*前提條件：plist指向一個已初始化的鏈表 */
/*後置條件：釋放了為鏈表分配的所有內存，鏈表設置為空 */
void EmptyTheList(List * plist);

#endif

實現接口

C方法是把函數定義統一放在一個*.c文件中，具體函數實現可參考常用數據結構設計與實現。

使用接口

在第二步接口建立好之後便可使用接口進行開發了，實際開發中架構師定義接口（第1、2步），工程師並行實現（第3步），以此來提升開發效率。

抽象數據類型的優點

• 關注點分離： 讓設計更清晰，減少思維負擔。
• 靈活性/可維護性：接口和實現分離，使得更改內部實現變得非常容易，不會破壞現有代碼。
• 團隊協作：架構師定義接口（第1、2步），工程師並行實現（第3步）。
• 正確性：先定義契約，便於後續編寫測試用例（如單元測試）。

參考文獻

1. C Primer Plus （第6版）中文版. Stephen Prata.