1.3 抽象數據類型的表示與實現

運用抽象數據類型描述數據結構，有助于在設計一個軟件系統時，不必首先考慮其中包含的數據對象，以及操作在不同處理器中的表示和實現細節，而是在構成軟件系統的每個相對獨立的模塊上定義一組數據和相應的操作，把這些數據的表示和操作細節留在模塊內部解決，在更高的層次上進行軟件的分析和設計，從而提高軟件的整體性能和利用率。

抽象數據類型的概念與面向對象方法的思想是一致的。抽象數據類型獨立于具體實現，將數據和操作封裝在一起，使得用戶程序只能通過抽象數據類型定義的某些操作來訪問其中的數據，從而實現了信息隱藏。在C++中，我們可以用類的聲明表示抽象數據類型，用類的實現來實現抽象數據類型。因此，C++中實現的類相當于數據的存儲結構及其在存儲結構上實現的對數據的操作。

抽象數據類型和類的概念實際上反映了程序或軟件設計的兩層抽象：抽象數據類型相當于在概念層（或稱為抽象層）上描述問題，而類相當于在實現層上描述問題。此外，C++中的類只是一個由用戶定義的普通類型，可用它來定義變量（稱為對象或類的實例）。因此，在C++中，最終是通過操作對象來解決實際問題的，所以我們可將該層次看做是應用層。例如，main程序就可看做是用戶的應用程序。

由此可以看出，最終表示和實現抽象數據類型，最好用面向對象的方法，比如用C++語言的類描述比較方便、有效，但本課程大都在大學低年級開設，用C語言的描述方法更符合學生的實際情況。另外，由于實際問題千變萬化，數據模型和算法也形形色色，因此抽象數據類型的設計和實現，就不可能像基本數據類型那樣規范和一勞永逸。本書所討論的數據結構及其算法主要是面向讀者的，故采用介于偽碼和C語言之間的類C語言作為描述工具。這使得數據結構與算法的描述與討論簡明清晰，不拘泥于C語言的細節，又容易轉換成C或C++程序。

本書采用的類C語言精選了C語言的一個核心子集，同時做了若干擴充修改，增強了語言的描述功能，以下對其做簡要說明。

（1）預定義常量及類型：

//函數結果狀態代碼
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函數返回值類型，其值是函數結果狀態代碼。
typedef int Status;

（2）數據結構的表示（存儲結構）用類型定義（typedef）描述；數據元素類型約定為ElemType，由用戶在使用該數據類型時自行定義。

（3）基本操作的算法都用如下格式的函數來描述：

函數類型 函數名（函數參數表）
{
   //算法說明
   語句序列
}//函數名

當函數返回值為函數結果狀態代碼時，函數定義為Status類型。為了便于描述算法，除了值調用方式外，增加了C++語言引用調用的參數傳遞方式。在形參表中，以“&”打頭的參數即為引用參數。傳遞引用給函數與傳遞指針的效果是一樣的，形參變化實參也發生變化，但引用使用起來比指針更加方便、高效。

（4）內存的動態分配與釋放。

使用new和delete動態分配和釋放內存空間：

分配空間 指針變量=new數據類型;
釋放空間 delete指針變量;

（5）賦值語句：

簡單賦值 變量名=表達式;
串聯賦值 變量名1=變量名2=...=變量名n=表達式;
成組賦值 (變量名1, ..., 變量名n)=(表達式1, ..., 表達式n);
結構賦值 結構名1=結構名2;
        結構名=(值1, 值2, ..., 值n);
條件賦值 變量名=條件表達式 ? 表達式T：表達式F;
交換賦值 變量名1 <-->變量名2;

（6）選擇語句：

條件語句1 if (表達式) 語句;
條件語句2 if (表達式) 語句;
         else 語句;
開關語句 switch (表達式)
          {
             case 值1: 語句序列1 ;break;
             case 值2: 語句序列2 ;break;
             …
             case 值n: 語句序列n;break;
             default: 語句序列n+1;
          }

（7）循環語句：

for語句        for (表達式1; 條件; 表達式2) 語句;
while語句      while (條件) 語句;
do-while語句   do {
                   語句序列;
                 } while (條件);

（8）結束語句：

函數結束語句    return 表達式;
              return;
              case或循環結束語句 break;
              異常結束語句 exit (異常代碼);

（9）輸入輸出語句使用C++流式輸入輸出的形式：

輸入語句   cin>>變量1>>…>>變量n;
輸出語句   cout<<表達式1<<…<<表達式n;

（10）基本函數：

求最大值    Max (表達式1,...,表達式n)
求最小值    Min (表達式1,...,表達式n)

下面以復數為例，給出一個完整的抽象數據類型的定義、表示和實現。

（1）定義部分：

ADT Complex {
   數據對象：D={e1,e2|e1,e2∈R,R是實數集}
   數據關系：S={<e1,e2>|e1是復數的實部，e2 是復數的虛部}
   基本操作：
     Creat(&C,x,y)
       操作結果：構造復數C，其實部和虛部分別被賦以參數x和y的值。
     GetReal(C)
       初始條件：復數C已存在。
       操作結果：返回復數C的實部值。
     GetImag(C)
       初始條件：復數C已存在。
       操作結果：返回復數C的虛部值。
     Add(C1,C2)
       初始條件：C1，C2是復數。
       操作結果：返回兩個復數C1和C2的和。
     Sub(C1,C2)
       初始條件：C1，C2是復數。
       操作結果：返回兩個復數C1和C2的差。
} ADT Complex

在后面的章節中，每定義一個新的數據結構，都先用這種定義方式給出其抽象數據類型的定義，對于數據結構的表示方法，則根據不同的存儲結構相應給出，同時用類C語言給出主要操作的實現方法。下面為了讓讀者對抽象數據類型有一個完整、正確的理解，給出復數的存儲表示和相應操作的具體實現過程。

（2）表示部分：

typedef struct                  //復數類型
{
   float Realpart;              //實部
   float Imagepart;             //虛部
}Complex;

（3）實現部分：

void Create( &Complex C, float x, float y)
{ //構造一個復數
   C.Realpart=x;
   C.Imagepart=y;
}
float GetReal(Complex C)
{ //取復數C=x+yi的實部
   return C.Realpart;
}
float GetImag(Complex C)
{ //取復數C=x+yi的虛部
   return C.Imagepart;
}
Complex Add(Complex C1, Complex C2)
{ //求兩個復數C1和C2的和sum
   Complex sum;
   sum.Realpart=C1.Realpart+C2.Realpart;
   sum.Imagepart=C1.Imagepart+C2.Imagepart;
   return sum;
}
Complex Sub(Complex C1, Complex C2)
{ //求兩個復數C1和C2的差difference
   Complex difference;
   difference.Realpart=C1.Realpart-C2.Realpart;
   difference.Imagepart=C1.Imagepart-C2.Imagepart;
   return difference;
}

這樣定義之后，就可以在主程序中通過調用Create函數構造一個復數，調用Add或Sub函數實現復數的加法或減法運算，用戶可以像使用整數類型那樣使用復數類型了。通過上述實例，讀者可以對抽象數據類型的概念有更加深刻的理解。