1.2.4　數據類型及數據抽象

在數據結構中往往涉及數據類型（Data Type）的概念，雖然數據類型與數據結構存在對應關系，如數據結構中的數組與數據類型中的數組，數據結構中的串與數據類型中的串都有同一性，但二者的意義卻不相同。簡單地講，數據結構定義了一組按某種關系結合在一起的數據元素，重點是研究數據元素之間的關系；而數據類型則是在軟件開發工具中體現數據結構對應性的具體方式。數據類型最早出現在高級算法語言中，用以刻畫數據操作對象的特性。每一種高級算法語言都定義有自己的數據類型，在用高級算法語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的確定的數據類型。數據類型明顯或隱含地規定了在程序執行期間變量或表達式所有可能取值的范圍。因此，數據類型是一個值的集合和定義在這個值的集合上的一組操作的總稱。例如，在C++語言中，整型（int）的值集范圍是[-32768，32767]，主要運算有+、-、*、/、％等。從硬件角度看，它們的實現涉及“字”“字節”“位”“位的運算”等。但從用戶角度看，并不需要了解整數在計算機內是如何表達的，運算細節是如何實現的。用戶只需了解整數的加減法或取模運算的抽象特性，而不必了解“位運算”細節，就可運用高級算法語言進行程序設計。可以說，數據類型是數據結構在算法語言中的實現。

數據類型可分為簡單類型和結構類型兩種。簡單類型中的每個數據都是無法再分割的整體，數據值內部無結構可言，如一個整數、實數、字符、指針、枚舉量等都是無法再分割的整體，所以它們所屬的類型均為簡單類型。結構類型由簡單類型按照一定的規則構造而成，其數據結構是相應元素的集合（它實際上是該結構類型中的一個值）和元素之間所含關系的集合，并且結構類型中可以包含結構類型。所以，結構類型中的數據可以分解為若干簡單數據或結構數據，每個結構數據仍可再分。例如，在C++語言中的數組是一種結構類型，它由固定個數的同種數據類型順序排列而成。

數據類型也可被定義為一種數據結構和能夠對該數據結構進行的操作的集合。對于簡單類型，其數據結構就是相應取值范圍內的所有數據，每一個數據值是不可分的獨立整體，因而數據值內部無結構可言。對于結構類型，其數據結構是相應元素的集合和元素之間所含關系的集合。

總之，數據結構是指計算機處理的數據元素的組織形式和相互關系，而數據類型是某種程序設計語言中已實現的數據結構。在程序設計語言提供的數據類型的支持下，可以根據從問題中抽象出來的各種數據模型，逐步構造出描述這些數據模型的各種新的數據結構。

在軟件工程中，有數據抽象和信息屏蔽的概念。所謂數據抽象，就是提取反映問題本質的數據結構。與數據結構密切相關的是定義在數據結構之上的一組操作，操作的種類和數目不同，即使邏輯結構相同，這個數據結構能起的作用也不同。一個數據結構加上定義在這個數據結構上的一組操作，即構成一個抽象數據類型的定義。抽象數據類型概念的實質和高級算法語言中的數據類型概念相同。

各種高級算法語言中所擁有的所有數據類型，都可認為是抽象數據類型。盡管它們在不同處理器上實現的方法可以不同，但由于它們的數據特性相同，故從用戶的角度看來都是相同的。

抽象數據類型（Abstract Data Type，ADT）是指基于一類邏輯關系的數據類型及定義在這個類型之上的一組操作。抽象數據類型的定義取決于客觀存在的一組邏輯特性，而與其在計算機內如何表示及實現無關。也就是說，只在程序模塊內部給出抽象數據類型的表示和實現細節，而在模塊外部使用的只是抽象的數據和抽象的操作，因此，不論其內部結構如何變化，只要它的數學特性不變，都不影響其外部使用。為了提高軟件的復用率，在現代程序設計方法學中指出，一個軟件系統的框架應建立在數據之上，而不是建立在傳統軟件設計方法所強調的操作之上。在某種意義上，抽象數據類型和數據類型實質上是同一個概念。整數類型、浮點類型和字符類型都是典型的抽象數據類型實例。“抽象”的意義在于數學特性的抽象。但抽象數據類型的含義更廣，不僅包含各種不同的計算機處理器中已定義并已實現的數據類型，還包括設計軟件系統時用戶自己定義的復雜數據類型。所定義的數據類型的抽象層次越高，含有該抽象數據類型的軟件復用程度就越高。因為抽象數據類型是以面向對象的思想為指導，直接面向數據結構的邏輯應用，故抽象層次越高，屏蔽的具體實現細節就越深，暴露的邏輯層面就越有通用性，也就意味著越易于復用。

例如，一個線性表的抽象數據類型可描述如下：

ADT Linear_list

其中：

數據元素：所有ai屬于同一數據對象，i=1，2，…，n。

邏輯結構：所有數據元素ai（i=1，2，…，n-1）存在次序關系<ai，ai+1>，a1無前驅，an無后繼。

操作：

設L為Linear_list類型的線性表，則：

Initial（L）為線性表初始化操作；

Length（L）為求線性表表長操作；

Get（L，i）為取線性表的第i個元素；

Insert（L，i，b）在線性表L的第i個位置插入元素b；

Delete（L，i）刪除線性表的第i個元素。

以上定義的Linear_list很明顯是抽象的，數據元素所屬的數據對象沒有局限于一個具體的數據類型，所具有的操作也是抽象的數學特性，并沒有具體到何種計算機語言指令與程序編碼。而數據結構就可討論對ADT的具體實現，如可以用面向對象的C++語言來實現上述的Linear_list。

對于抽象數據類型的具體實現要依賴于所選擇的高級語言的功能。從程序設計方法的發展過程來看，有幾種不同的實現方法：一種是傳統的面向過程的程序設計，即根據數據的邏輯結構選定合適的存儲結構，根據所要求的操作設計出相應的子程序或子函數；另一種是模塊化的設計方法，如Pascal語言提供了單元結構，用這類結構實現抽象數據類型比起第一種方法有所進步；第三種是面向對象的程序設計（Object Oriented Programming，OOP），在面向對象的程序設計語言中，存儲結構的說明和操作函數的說明被封裝在一個整體結構中，這個整體結構稱為類（Class），屬于某個類的具體變量稱為對象（Object）。OOP非常適合于抽象數據類型的實現。

從某種意義上說，抽象數據類型相當于軟件設計過程中的數據結構規劃圖。該圖是系統設計者對于所設計的軟件系統的想象及精確描述，開發人員必須按規劃圖開發才能設計出符合要求的軟件系統。抽象數據類型的說明基本上是功能性的，對具體的實現并未做多的約束。在具體實現時，完成任務的算法、數據類型、數據結構、程序的邏輯組織，甚至采用哪種程序設計語言都是可自由選擇的。

抽象數據類型的主要目的之一是對用戶隱蔽所有的表示方法、算法的詳細細節、實現操作的具體代碼及其他所有不必要的細節，這些細節都被局限于具體實現的模塊內部，從而實現了信息的隱蔽。

抽象數據類型的明顯優點就是簡單性。盡管數據類型被抽象化了，但抽象化的過程往往具有簡化的作用。因為數據抽象的目的是將數據的本質特征、它們的結構及操作同它們的具體表示及實現細節區分開，從而得到了簡化。