抽象資料類型ADT（1）

1. 抽象資料類型與表示獨立性：能夠分離程式中資料結構的形式和對其使用的方式。如何設計良好的抽象資料結構，通過封裝來避免用戶端擷取資料的内部表示（表示洩露），避免潛在的bug–在client和implement之間建立“防火牆”.
2. ADT的特性：不變量、表示洩露、抽象函數AF、表示不變量RI。
3. 給出了一個類通過抽象函數和表示不變量來實作ADT意味着什麼的更正式的數學概念。
4. 抽象函數将為我們提供一種在抽象資料類型上清晰定義等式的方法。
5. 基于數學的形式對ADT的核心特征進行描述并應用于設計中。

抽象和使用者定義類型

除了程式設計語言所提供的基本資料類型和對象資料資料類型，程式員可以定義自己的資料類型。

1. 資料抽象

定義：由一組操作所刻畫的資料類型。

-number是可以進行加和乘等操作的東西

-string是可以進行連接配接或者取子字元串的東西

傳統上，程式員會提前定義自己的資料類型，比如建立一種記錄日期的類型，具有年月日的整數段。傳統的類型定義會更關注資料的具體表示

抽象類型關注于操作，強調“作用于資料上的操作”，程式員和使用者無需關心資料如何存儲。

注：抽象資料類型是由其操作定義的，與其内部實作無關。

類型T的操作和規約刻畫了T的特性。當我們談論清單類型時，我們的意思并不是連結清單、數組或者任何其他的資料結構代表一個清單，而是指的一組不透明的值，可能的對象可以有清單類型-滿足所有操作的規格get(), size()等。

2. 分類類型和操作

1. 可變和不可變資料類型：無論内置的還是使用者定義的類型，都可以分類為可變的或不可變的。

   （1） 可變類型的對象：提供了可改變其内部資料的值的操作

   （2） 不可變資料類型：其操作不可改變内部值，而是構造新的對象

   有時一個類型将以兩種形式提供，一種可變，一種不可變，比如：StringBuilder是可變版本的String（兩者不是相同的Java類型，也不可互換）

2. 對抽象類型的操作進行分類：

   （1） 構造器（從無到有）：建立該類型的新對象。

   構造器可以将對象作為參數，但是不能作為一個建構中的該類型的對象

   （2） 生産器（從有到新）：從該類型的舊對象建立新對象。比如String的conact方法就是一個生産器，它利用兩個字元串生成一個表示其串聯的新字元串。

   （3） 觀察器：擷取抽象類型的對象并傳回不同的類型。比如List的size()方法就傳回一個int型。

   （4） 變值器：改變對象屬性的方法。比如List的add()方法，通過在尾部添加元素改變清單的屬性。

   構造器：t*->T

   生産器：T+，t*->T

   觀察器：T+，t*->T

   變值器：T+，t*->void | t | T

   其中每個T本身就是抽象資料類型，t為其他類型，+标記表示該類型可能在簽名的該部分出現一次或多次，*标記表示它出現零次或多次，| 表示或。

3. 操作的簽名：

   構造器可能實作為構造函數或靜态函數，實作為靜态方法的構造器通常稱為工廠方法。

   變值器通常傳回void，如果傳回值為void，則必然意味着它改變了對象的某些内部狀态。變值器也可能傳回非空類型

3. 抽象資料類型執行個體

1. int：不可變，是以沒有變值器

   –構造器:數字文字0，1，2，…

   –生産器:算術運算符+、-、*、/

   –觀察器:比較運算符==，！= , < , >

   –變值器:無(它是不可變的)

2. String：String是Java的字元串類型，字元串是不可變的。

   –構造器:String類的構造函數

   –生産器:concat，substring，toUpperCase

   –觀察器:length，chartAt

   -變值器：無

3. List：List是Java的清單類型，是可變的。

   清單也是一個接口，這意味着其他類提供資料類型的實際實作，如ArrayList和LinkedList。

   –構造器:ArrayList和LinkedList構造函數，Collections.singletonList

   –生産器:Collections.unmodifiableList

   –觀察器:size，get

   –變值器:add , remove , addAll , Collections.sort

   

4. 設計抽象資料類型

良好ADT的設計：靠“經驗法則”，提供一組操作，設計其行為規約 spec

1. 經驗法則1：設計簡潔、一緻的操作

   –最好有一些簡單的操作，可以以強大的方式進行組合，而不是大量複雜的操作，通過簡單操作組和實作複雜的操作，操作的行為應該是内聚的

   –每個操作都應該有一個明确的目的，并且應該有一個連貫的行為，而不是一系列的特殊情況。

   –例如，我們可能不應該向清單中添加求和操作。它可能對使用整數清單的客戶有所幫助，但是字元串清單呢？還是嵌套清單？所有這些特殊情況會使sum操作變得難以了解和使用。

2. 經驗法則2：要足以支援使用者對資料所做的所有操作需要,且用操作滿足使用者需要的難度要低

   操作集應該是足夠的，因為必須有足夠的操作來完成使用者可能想要完成的計算。

   –一個好的測試是檢查該類型的對象的每個屬性都可以被提取。判斷方法：對象每個需要被通路到的屬性是否都能夠被通路到

   例如，如果沒有get操作，我們将無法找到清單的元素。沒有get()操作就無法擷取目錄的内部資料

   –基本資訊應該不難獲得。

   例如，size方法對于List來說并不是嚴格必要的，因為我們可以在遞增索引上應用get，直到失敗，但這是低效和不友善的。用周遊方式擷取List的size太複雜了，但是提供size()操作,會友善使用者使用

5. 表示獨立性

一個好的抽象資料類型應該是表示獨立的。

表示獨立性:用戶端使用ADT時無需考慮其内部如何實

現，ADT内部表示的變化不應影響外部spec和用戶端。

–抽象類型的使用獨立于其表示(用于實作它的實際資料結構或資料字段)，是以表示的變化對抽象類型本身之外的代碼沒有影響。

–例如，“List”提供的操作與清單是以連結清單還是數組表示無關。

您将根本無法更改ADT的表示，除非其操作完全由前提條件和後置條件指定，以便客戶知道依賴什麼，并且您知道您可以安全地更改什麼。通過前提條件和後置條件充分刻畫了ADT的操作，spec規定了client和implementer之間的契約,明确了client知道可以依賴哪些内容，implementer（執行者）知道可以安全更改的内容。