立功教授數年之心血之作《程序設計與數據結構》以及《面向AMetal框架與接口的編程（上）》，書本內容公開后，在電子行業掀起一片學習熱潮。經周立功教授授權，本公眾號特對《程序設計與數據結構》一書內容進行連載，愿共勉之。

第二章為程序設計技術，本文為2.4.1 不完全類型和2.4.2 抽象數據類型。

>>> 2.4.1 不完全類型

不完全類型是指“函數之外、類型的大小不能被確定的類型”，結構體標記的聲明就是一個不完全類型的典型示例。比如：

此時，struct _TypeA和struct _TypeB是互相引用的，雖然無論先聲明哪一邊都很麻煩，但可以先通過聲明結構體標記回避以上問題。比如：

當使用typedef聲明結構體類型時，比如：

由于TypeB類型的標記被聲明時，還不知道它的內容，因此無法確定它的大小，這樣的類型就被稱為不完全類型。因為不能確定大小，所以不能將不完全類型變成數組，也不能將其作為結構體的成員，或聲明為變量。但如果聲明為指針，則可以使用不完全類型。在后續定義struct _TypeB的內容時，TypeB就不是不完全類型了。

通常在“.h”頭文件中聲明不包含任何實現細節的結構體，然后在“.c”實現文件中定義與數據結構的特定實現配合使用的函數。數據結構的用戶可以看到聲明和函數原型，但實現會隱藏在“.c”文件中。只有使用數據結構所需要的信息會對用戶可見，如果太多的內部信息可見，用戶可能會使用這些信息從而產生依賴。一旦內部結構發生變化，則用戶代碼可能就會失效。不完全類型是因為編譯器看不見“.c”文件中的實際定義，它只能看到_demoB結構體的類型定義，而看不見結構體的實現細節。

下面將以數組為例介紹不完全類型的使用，盡管可以使用數組保存元素，由于數組的大小是固定的，因此數組并不會存儲它的大小，而且也不會檢查下標是否越界。通常用一個指向數組的指針pBuffer和記錄數組元素個數的值count代替數組。其實現如下（IA_array.c）：

為了防止用戶直接訪問結構體的成員，通常將結構體移到實現代碼中（IA_array.c）隱藏起來，然后使用不完全的類型在接口中（IA_array.h）聲明一個IntArray處理相應的數據。雖然不完全類型描述了對象，但缺少對象大小所需的信息。比如：

其告訴編譯器_IntArray是一個結構體標記，卻沒有描述結構體的成員，因此編譯器沒有足夠的信息確定結構體的大小，其意圖是不完全類型將會在程序的其它地方將信息補充完整。不完全類型的使用是受限的，因為編譯器不知道它的大小，所以不能在接口中用它聲明變量：

但可以在接口中（IA_array.h）定義一個指針類型引用不完全類型：

在這里，僅僅聲明了它的存在，而沒有做別的任何事情。對于用戶來說，看到的只是IA_array.h，而對_IntArray的構造或實現卻一無所知。

當將IntArray定義為一個指向struct _IntArray結構體類型時，即可聲明IntArray*類型的變量，將其作為函數參數進行傳遞。即：

盡管此時還沒有定義IntArray，但指針的大小始終相同，且不依賴于它指向的對象。即便在不知道結構體本身細節的前提下，編譯器同樣允許處理指向結構體的指針，這就解釋了為什么C允許這種行為。雖然這個結構體是一個不完全類型，但在實現代碼中信息變得完整，因此該結構體的成員依賴于實現方法。

雖然數組和指針有區別，但C語言不會區分它們，C對數組提供的支持只是為了便于內存管理和指針運算，最好的證明莫過于括號運算符居然有交換性。當在結構體內創建一個數組時，為了避免直接對數據進行訪問，將通過接口函數和對象交互，詳見程序清單 2.30。

程序清單 2.30 訪問數組元素和大小接口（IntArray.h）

為了說明這些函數構成了IntArray對象的接口，并防止函數名和其它對象的接口沖突，于是在每個函數名前使用了前綴IA_，且每個函數都有一個IntArray*型的對象作為參數，這個參數就是函數將要操作的對象。

IA_init()初始化使數組處于空元素的狀態，IA_cleanup()釋放在數組生存期中分配給用戶的內存。剩余的函數是控制對數組中數據的訪問，IA_setSize()設置了數組中的元素個數，且為這些元素分配存儲空間，IA_getSize()返回當前數組中的元素個數。IA_setElem()和IA_getElem()用于訪問單個數據元素，其具體實現詳見程序清單 2.31。

程序清單 2.31 訪問數組元素和大小接口的實現（IntArray.c）

其中，IA_setSize()用于改變數組大小，首先釋放原有的元素，然后保存新的元素，且為新元素分配存儲空間。當然，也可以優化進一步代碼，比如，只有數組大小增加時才重新分配空間。IA_getSize()訪問給定下標所指的元素，讓IntArray檢查下標是否在界內。

由此可見，IntArray的實現是由兩部分組成的，即保存對象信息的數據和構成對象接口的函數，其使用范例程序詳見程序清單 2.32。

程序清單 2.32 使用IntArray.h范例程序

>>> 2.4.2 抽象數據類型

1. 棧的實現

假設需要一個字符棧，且棧的大小是固定的，即可使用數組保存棧中的元素，然后指定一個計數器表明棧中元素的數量。其數據結構定義如下：

由于調用者并不能直接訪問底層，因此在向棧中壓入元素之前，必須先創建一個棧。其函數原型為：

由于剛開始時棧為空，暫時還沒有元素存儲到數組elements[0]中，因此只要將數組的下標置為0，即可創建一個空棧。即：

其調用形式如下：

當向棧中壓入一個新的元素時，將元素存儲在數組接下來的空間中，并計數遞增。其函數原型為：

也就是說，當top的值加1時，則將新的元素值value入棧。即：

當彈出元素時，計數遞減并返回棧頂元素。其函數原型如下：

也就是說，當top的值減1時，則刪除棧頂結點，返回該結點的值。比如：

除了這些基本的操作之外，經常還需要知道棧所包含的元素數量，以及棧是空還是滿，這些函數的原型為：

顯然，只要返回棧頂值就知道棧中存儲了多少個元素，而當stack->top為0時，說明棧為空；當stack->top大于等于MAXSIZE時，說明棧已滿。

實際上，當定義了一個結構體指針變量stack后，（stack->top）就成為了一個變量，即可通過stack->top與stack->elements[stack->top++]分別實現對stack的各成員的訪問。顯然程序暴露了“數組和下標”這一內部結構，且無法阻止用戶使用stack指針變量直接訪問結構體的成員。比如：

由于對直接訪問top和elements，因此用戶有可能破壞棧中的數據。如果其內部實現發生變化，也必須對程序進行相應的修改。如果程序規模很大，則修改的工作量也很大，因此很多時候明明知道通過重構能夠改善程序，也會因工作量太大而不愿意改變具體的實現。

由此可見，上述棧的實現方法不僅暴露了棧的數據結構，而且僅有1個棧。如果需要多個棧時，怎么辦？一種方法是編寫多個名字不同功能相同的函數，這樣就會出現多段處理完全相同的代碼。為了解決這個問題，抽象的方法是將棧中的數據結構隱藏到實現代碼中。

2. 建立抽象

雖然標準C提供了類似int、char、float、double這樣不可分割的原子數據類型，但如果需要表示任意大的整數，顯然原子數據類型無能為力。此時，創建一種新的整數類型勢在必行，而這種新的數據類型便是一種抽象數據類型ADT（Abstract Data Type）。

設計一個基于Stack的抽象數據類型，我們應該從哪里開始呢？一個不錯的方法是用一句話來描述。這種描述應該盡可能地抽象，盡量不要涉及數據的內部結構，要簡單到誰都能夠理解它，因此可以描述“棧（Stack）是一個可以在同一個位置上插入（push）和刪除（pop）數據（value）的存儲器，該位置是存儲器的末端，即棧頂（top）”。該定義既未說明棧中存儲什么數據，也未指定是用數組、結構體還是其它數據形式存儲數據，而且也沒有規定用什么方式實現操作，這些細節都留給實現去完成。

關于棧的詳細描述如下：

• 類型名：Stack

• 類型屬性：可以存儲有序的數據（value）

• 類型操作：創建棧（newStack）和銷毀棧（freeStack），從棧頂添加數據（push）和從棧頂刪除數據（pop），確定棧是否為空（stackIsEmpty），確定棧是否已滿（stackIsFull），返回棧中元素的個數（getStackDepth），讀取棧中任何位置的元素（getStackElement）。

也就是說，在向棧中添加元素之前，必須先創建一個棧。當不再使用內存時，必須銷毀棧。對棧的基本操作有push（進棧）和pop（出棧），前者相當于插入，后者相當于刪除最后插入的元素。對空棧進行的pop，認為是棧ADT的錯誤。另一方面，當運行push時空間用盡是一個實現錯誤，但不是ADT錯誤。

3. 建立接口

（1）隔離變化

為了防止用戶直接訪問top和elements而破壞棧中的數據，根據以往的經驗，可以使用使用依賴倒置原則。將保存在結構體中棧的實現所需要的數據結構隱藏在“.c”文件中，將處理數據的接口包含在“.h”文件中，用戶將無法看到棧的數據結構在底層是如何實現的。

雖然可以將一個數組看作是具有固定小的，但是內置數組并不會存儲它的大小，而且也不會檢查下標是否越界。通常將一個指向數組的指針data和記錄數組元素個數的值numData存儲棧的最大容量，以及記錄棧頂元素的位置top進行打包，將棧的數據結構隱藏在“.c”文件中。即：

對于用戶來說，現在只能通過“.h”文件中的接口操作棧。盡管此時還沒有定義stackCDT，由于指針的大小始終相同，且不依賴于它指向的對象。即便在不知道結構體本身細節的前提下，編譯器同樣允許處理指向結構體的指針，因此可以定義一個指針類型引用不完全類型，將stackADT定義為一個指向stackCDT *結構體類型。比如：

雖然這個結構是一個不完全類型，但在實現棧的文件中信息變得完整，因此該結構的成員依賴于棧的實現方法。stackADT結構體類型的變量定義如下：

由于一個stack1指向一個存儲單元，即一個存儲單元代表一個棧，因此你想要多少個棧就有多少個棧。比如：

顯而易見，stackADT是代表stack1、stack2、stack3等所有具體棧的總稱的抽象數據類型，stack1、stack2和stack3分別指向不同的棧。因此只要將stack1、stack2和stack3作為實參傳遞給相應的函數，即可訪問與之相應的棧。而抽象的方法是在棧的實現代碼和使用棧的代碼之間添加一個函數層。比如：

通常將稱為函數上下文的stackADT類型的stack作為函數的第一個參數，這個參數就是函數將要操作的對象。它代表指向當前對象（棧）的指針，用于請求對象對自身執行某些操作。而結構體的成員變量就是通過stack指針找到自己所屬的對象的，其引用方式如下：

由此可見，用戶僅通過接口函數與棧交互，而不是直接訪問它的數據。

（2）操作方法

• 創建棧

由于用戶完全不知道底層是如何表示的，因此必須提供一個用于創建一個新stackADT的函數，且將它返回給用戶。用于創建一個新的抽象類型的值的函數名稱以new開始，以強調動態分配。其函數原型如下：

前置條件：stackADT被定義為一個指向結構體的指針，該結構體包含top和numData。一旦知道最大容量，則該棧即可被動態確定。創建一個具有給定最大值MAXSIZE的棧，其分別是為stackCDT結構體分配空間和長度為MAXSIZE的數組分配空間。同時將top初始化為0，并將numData置為最大值MAXSIZE。

后置條件：返回棧。

其調用形式如下：

• 銷毀棧

當接口定義了一個分配新的抽象類型的值的函數時，通常還要為接口提供一個用于釋放用戶不再使用的棧的動態內存的函數。其函數原型如下：

前置條件：stack指向之前創建的棧；

后置條件：釋放動態分配的所有內存，即先釋放棧的數組，然后釋放棧的結構。

其調用形式如下：

• 從棧頂添加據（進棧）

當用戶向棧頂添加一個數據時，就是將該值存儲在內部的數據結構中。即通過在容器的頂端插入元素實現push，其函數原型如下：

前置條件：stack指向之前創建的棧，value是待壓入棧頂的數據；

后置條件：如果棧不滿，將value放在棧頂，該函數返回true，否則棧不變，該函數返回false。

其調用形式如下：

• 從棧頂刪除數據（出棧）

當用戶彈出棧元素時，就是將存儲的值返回給用戶。即通過刪除容器頂端的元素實現pop，其函數原型如下：

前置條件：stack指向之前創建的棧，pValue為指向存儲返回值變量的指針；

后置條件：如果棧不空，將棧頂的值拷貝到*pValue，刪除棧頂的值，該函數返回true，如果刪除前棧為空，棧不變，該函數返回false。

其調用形式如下：

• 判斷棧是否為空

判斷棧是否為空的函數原型如下：

前置條件：stack指向之前創建的棧；

后置條件：如果棧為空則返回true，否則返回false。

其調用形式如下：

• 判斷棧是否已滿

判斷棧是否已滿的函數原型如下：

前置條件：stack指向之前創建的棧；

后置條件：如果棧已滿則返回true，否則返回false。

其調用形式如下：

• 確定棧中元素的個數

確定棧中元素的個數的函數原型如下：

前置條件：stack指向之前創建的棧；

后置條件：返回棧中元素的個數。

其調用形式如下：

• 讀取棧中任何位置的元素

讀取棧棧任意位置元素的函數原型如下：

前置條件：stack指向之前創建的棧，index為索引值，表示返回棧中某個位置的元素， pValue為指向存儲返回值變量的指針；

后置條件：如果index大于top，該函數返回false，反之將index位置的值拷貝到*pValue，該函數返回true。

其調用形式如下：

由于數組的下標是從0開始的，當index為0時，則getStackElemnt(stack, 0, &temp)返回棧頂的元素，getStackElemnt(stack, 1, &temp)返回接下來的那個元素，依此類推。

封裝時，頭文件中只放最小的接口函數聲明，且內部函數都要加上static關鍵字。抽象棧的接口詳見程序清單 2.33，接口揭示了棧的數據類型和用戶在操作棧時需要的各種功能，這些功能實現了抽象棧類型的基本操作。

程序清單 2.33 抽象棧接口（stack.h）

這些函數共同創建了接口，每個函數都以stackADT作為它的第一個參數。當聲明了函數接口后，即可實現相應的接口。

4. 實現接口

由于數組的長度在編譯時就已經確定了，無法在運行時動態地調整。但有些應用在編譯時并不知道應該分配多大的內存空間才能滿足要求，因此可以根據需要使用動態內存“在運行時”為它分配內存空間。和任何接口一樣，實現Stack.h接口需要編寫一個模塊Stack.c，它提供了抽象類型的輸出函數和表示細節的代碼，詳見程序清單 2.34。

程序清單 2.34 抽象棧的實現（Stack.c）

表面上看起來getStackDepth()函數只有一行代碼，也許有人會說，為何不直接使用“stack->top;”代替該函數呢？如果用戶在程序中使用top，那么程序將依賴于stackADT表示的具體結構，而使用該函數的好處是為用戶和實現之間提供了隔離層。由于維護代碼是軟件工程生命周期中的一個重要步驟，因此要盡量做好隨時修改的準備。

當然，上述程序還是不能創建兩種數據類型不同的棧，最常見的方法是使用void *作為數據類型，這樣就可以壓入和彈出任意類型的指針了。這里不再詳細描述，將留給讀者自己實現。但使用void *作為數據類型的最大缺點是不能進行錯誤檢測，存放void *數據的棧允許各種類型的指針共存，因此無法檢測由壓入錯誤的指針類型而導致的錯誤。

5. 使用接口

實際上使用棧的人并不關心棧是如何實現的，即使要改變棧的內部實現方式，也不用對使用棧的程序做任何修改。將整數推入棧，然后再打印輸出的范例程序詳見程序清單 2.35。

程序清單 2.35 使用棧接口的范例程序

綜上所述，Stack棧的接口分為兩部分，其一是描述如何表示數據，其二是描述實現ADT操作的函數，因此必須先提供存儲數據的方法。設計一個結構體，在“.h”接口中定義棧的抽象數據類型stackADT，在“.c”實現中定義棧的具體類型stackCDT。其次必須提供管理該數據的函數（方法），通過函數原型隱藏它們的底層實現。只要保留它們的接口不變，對于任何抽象都可以改變它的實現。實際上，當引入一個抽象數據類型stackADT時，就是在使用依賴倒置原則，將保存在結構體中棧的實現所需要的數據和處理數據的接口徹底分離，因為stackADT沒有暴露它的細節，用戶依賴于satcADT抽象，而不是細節。

顯然，抽象數據類型可利用已經存在的原子數據類型構造新的結構，用已經實現的操作組合新的操作。對于ADT，用戶程序除了通過接口中提到的那些操作之外，并不訪問任何數據值。數據的表示和實現操作的函數都在接口的實現里面，與用戶完全分離。抽象的接口隱臧不相關的細節，用戶不能通過接口看到方法的實現，將注意力集中在本質特征上，將程序員從關心程序如何實現的細節上得到解放。對于任何抽象來說，只要保持接口不變，我們可以根據需要改變其實現方式。