【软件构造】第三章第三节 抽象数据型(ADT)
第三章第三節(jié) 抽象數據型(ADT)
? ? ? ?3-1節(jié)研究了“數據類型”及其特性 ;?3-2節(jié)研究了方法和操作的“規(guī)約”及其特性；在本節(jié)中，我們將數據和操作復合起來，構成ADT，學習ADT的核心特征，以及如何設計“好的”ADT。
Outline
- ADT及其四種類型
- ADT的基本概念
- ADT的四種類型
- 設計一個好的ADT
- 表示獨立性
- 不變量和表示泄露
- 抽象函數AF和表示不變量RI
- AF與RI
- 用注釋寫AF和RI
Notes
## ADT及其四種類型
【ADT的基本概念】
- 抽象數據類型（Abstract Data Type，ADT）是是指一個數學模型以及定義在該模型上的一組操作；即包括數據數據元素，數據關系以及相關的操作。
- ADT具有以下幾個能表達抽象思想的詞：
- 抽象化：用更簡單、更高級的思想省略或隱藏低級細節(jié)。
- 模塊化： 將系統劃分為組件或模塊，每個組件可以設計，實施，測試，推理和重用，與系統其余部分分開使用。
- 封裝：圍繞模塊構建墻，以便模塊負責自身的內部行為，并且系統其他部分的錯誤不會損壞其完整性。
- 信息隱藏： 從系統其余部分隱藏模塊實現的細節(jié)，以便稍后可以更改這些細節(jié)，而無需更改系統的其他部分。
- 關注點分離： 一個功能只是單個模塊的責任，而不跨越多個模塊。
- 與傳統類型定義的差別：
- 傳統的類型定義：關注數據的具體表示。
- 抽象類型：強調“作用于數據上的操作”，程序員和client無需關心數據如何具體存儲的，只需設計/使用操作即可。
-
ADT是由操作定義的，與其內部如何實現無關！
【ADT的四種類型】
- 前置定義：mutable and immutable types
- 可變類型的對象：提供了可改變其內部數據的值的操作。Date
- 不變數據類型： 其操作不改變內部值，而是構造新的對象。String
- Creators（構造器）：
- 創(chuàng)建某個類型的新對象，?個創(chuàng)建者可能會接受?個對象作為參數，但是這個對象的類型不能是它創(chuàng)建對象對應的類型?？赡軐崿F為構造函數或靜態(tài)函數。（通常稱為工廠方法）
- t* ->? T
- 栗子：Integer.valueOf( )
- Producers（生產器）：
- 通過接受同類型的對象創(chuàng)建新的對象。
- T+ , t* -> T
- 栗子：String.concat( )
- Observers（觀察器）：
- 獲取抽象類型的對象然后返回一個不同類型的對象/值。
- T+ , t* -> t
- 栗子：List.size( ) ；
- Mutators（變值器）：
- 改變對象屬性的方法 ，
- 變值器通常返回void，若為void，則必然意味著它改變了對象的某些內部狀態(tài)；當然，也可能返回非空類型?
- T+ , t* -> t || T || void
- 栗子：List.add( )
- 解釋：T是ADT本身；t是其他類型；+ 表示這個類型可能出現一次或多次；* 表示可能出現0次或多次。
- 更多栗子：
【設計一個好的ADT】
設計好的ADT，靠“經驗法則”，提供一組操作，設計其行為規(guī)約 spec
- 原則 1：設計簡潔、一致的操作。
- 最好有一些簡單的操作，它們可以以強大的方式組合，而不是很多復雜的操作。
- 每個操作應該有明確的目的，并且應該有一致的行為而不是一連串的特殊情況。
- 原則 2：要足以支持用戶對數據所做的所有操作需要，且用操作滿足用戶需要的難度要低。
- 提供get()操作以獲得list內部數據
- 提供size()操作獲取list的長度
- 原則 3：要么抽象、要么具體，不要混合 —— 要么針對抽象設計，要么針對具體應用的設計。
【測試ADT】
- 測試creators, producers, and mutators：調用observers來觀察這些 operations的結果是否滿足spec；
- 測試observers：?調用creators, producers, and mutators等方法產生或改變對象，來看結果是否正確。
?
## 表示獨立性
- 表示獨立性：client使用ADT時無需考慮其內部如何實現，ADT內部表示的變化不應影響外部spec和客戶端。
- 除非ADT的操作指明了具體的前置條件/后置條件，否則不能改變ADT的內部表示——spec規(guī)定了 client和implementer之間的契約。
【一個例子：字符串的不同表示】
讓我們先來看看一個表示獨立的例子，然后考慮為什么很有用，下面的MyString抽象類型是我們舉出的例子。下面是規(guī)格說明：
1 /** MyString represents an immutable sequence of characters. */ 2 public class MyString { 3 4 Example of a creator operation /// 5 /** @param b a boolean value 6 * @return string representation of b, either "true" or "false" */ 7 public static MyString valueOf(boolean b) { ... } 8 9 Examples of observer operations /// 10 /** @return number of characters in this string */ 11 public int length() { ... } 12 13 /** @param i character position (requires 0 <= i < string length) 14 * @return character at position i */ 15 public char charAt(int i) { ... } 16 17 Example of a producer operation /// 18 /** Get the substring between start (inclusive) and end (exclusive). 19 * @param start starting index 20 * @param end ending index. Requires 0 <= start <= end <= string length. 21 * @return string consisting of charAt(start)...charAt(end-1) */ 22 public MyString substring(int start, int end) { ... } 23 }使用者只需要/只能知道類型的公共方法和規(guī)格說明。下面是如何聲明內部表示的方法，作為類中的一個實例變量：
private char[] a;使用這種表達方法，我們對操作的實現可能是這樣的：
1 public static MyString valueOf(boolean b) { 2 MyString s = new MyString(); 3 s.a = b ? new char[] { 't', 'r', 'u', 'e' } 4 : new char[] { 'f', 'a', 'l', 's', 'e' }; 5 return s; 6 } 7 8 public int length() { 9 return a.length; 10 } 11 12 public char charAt(int i) { 13 return a[i]; 14 } 15 16 public MyString substring(int start, int end) { 17 MyString that = new MyString(); 18 that.a = new char[end - start]; 19 System.arraycopy(this.a, start, that.a, 0, end - start); 20 return that; 21 }執(zhí)行下列的代碼
MyString s = MyString.valueOf(true); MyString t = s.substring(1,3);?
我們用快照圖展示了在使用者進行 subString 操作后的數據狀態(tài)：
這種實現有一個性能上的問題，因為這個數據類型是不可變的，那么 substring 實際上沒有必要真正去復制子字符串到?個新的數組中。它可以僅僅指向原來的 MyString 字符數組，并且記錄當前的起始位置和終?位置。
? 為了優(yōu)化，我們可以將這個類的內部表示改為：
private char[] a; private int start; private int end;? 有了這個新的表示，操作現在可以這樣實現：
1 public static MyString valueOf(boolean b) { 2 MyString s = new MyString(); 3 s.a = b ? new char[] { 't', 'r', 'u', 'e' } 4 : new char[] { 'f', 'a', 'l', 's', 'e' }; 5 s.start = 0; 6 s.end = s.a.length; 7 return s; 8 } 9 10 public int length() { 11 return end - start; 12 } 13 14 public char charAt(int i) { 15 return a[start + i]; 16 } 17 18 public MyString substring(int start, int end) { 19 MyString that = new MyString(); 20 that.a = this.a; 21 that.start = this.start + start; 22 that.end = this.start + end; 23 return that; 24 }? 現在運行上面的調用代碼，可用快照圖重新進行 substring 操作后的數據狀態(tài)：
由于?MyString?的使用者僅依賴于其公共方法和規(guī)格說明，而不依賴其私有的存儲，因此我們可以在不檢查和更改所有客戶端代碼的情況下進行更改。 這就是表示獨立性的力量?！ ?/p>
?
##? 不變量（Invariants）與表示泄露
一個好的抽象數據類型的最重要的屬性是它保持不變量。一旦一個不變類型的對象被創(chuàng)建，它總是代表一個不變的值。當一個ADT能夠確保它內部的不變量恒定不變（不受使用者/外部影響），我們就說這個ADT保護/保留自己的不變量。
【一個栗子：表示泄露】
1 /** 2 * This immutable data type represents a tweet from Twitter. 3 */ 4 public class Tweet { 5 6 public String author; 7 public String text; 8 public Date timestamp; 9 10 /** 11 * Make a Tweet. 12 * @param author Twitter user who wrote the tweet 13 * @param text text of the tweet 14 * @param timestamp date/time when the tweet was sent 15 */ 16 public Tweet(String author, String text, Date timestamp) { 17 this.author = author; 18 this.text = text; 19 this.timestamp = timestamp; 20 } 21 }我們如何保證這些Tweet對象是不可變的，（即一旦創(chuàng)建了Tweet，其author，message和 date 永遠不會改變）
對不可變性的第一個威脅來自使用者可以直接訪問Tweet內部數據的事實，例如執(zhí)行如下的引用操作：
1 Tweet t = new Tweet("justinbieber", 2 "Thanks to all those beliebers out there inspiring me every day", 3 new Date()); 4 t.author = "rbmllr";? 這是一個表示泄露(Rep exposure)的簡單例子，這意味著類外的代碼可以直接修改表示。像這樣的表示暴露不僅威脅到不變量，而且威脅到表示獨立性。如果我們改變類內部數據的1表示方式，使用者也會相應的受到影響。
幸運的是，java給我們提供了處理表示暴露的方法：
1 public class Tweet { 2 private final String author; 3 private final String text; 4 private final Date timestamp; 5 6 public Tweet(String author, String text, Date timestamp) { 7 this.author = author; 8 this.text = text; 9 this.timestamp = timestamp; 10 } 11 12 /** @return Twitter user who wrote the tweet */ 13 public String getAuthor() { 14 return author; 15 } 16 17 /** @return text of the tweet */ 18 public String getText() { 19 return text; 20 } 21 22 /** @return date/time when the tweet was sent */ 23 public Date getTimestamp() { 24 return timestamp; 25 } 26 }在private和public關鍵字表明哪些字段和方法可訪問時，只在類內部還是可以從類外部訪問。所述final關鍵字還保證該變量的索引不會被更改，對于不可變的類型來說，就是確保了變量的值不可變。
但這不能解決全部的問題：表示仍然會泄露！考慮這個完全合理的客戶端代碼，它使用Tweet：
1 /** @return a tweet that retweets t, one hour later*/ 2 public static Tweet retweetLater(Tweet t) { 3 Date d = t.getTimestamp(); 4 d.setHours(d.getHours()+1); 5 return new Tweet("rbmllr", t.getText(), d); 6 }
retweetLater 希望接受一個Tweet對象然后修改Date后返回一個新的Tweet對象。
這里有什么問題？其中的 getTimestamp?調用返回一個一樣的 Date 對象，它會被t、t.timestamp 和 d?同時索引。因此，當日期對象被突變，d.gsetHours( )?被調用時，t 也會影響日期，如快照圖所示。
??
這樣，Tweet的不變性就被破壞，Tweet將自己內部對于可變對象的索引“泄露”了出來，因此整個對象都變成可變的了，使用者在使用時也容易造成隱藏的bug。
我們可以通過使用防御性拷貝來修補這種風險：制作可變對象的副本以避免泄漏對代表的引用。代碼如下：
public Date getTimestamp() {return new Date(timestamp.getTime()); }可變類型通常具有一個專門用來復制的構造函數，它允許創(chuàng)建一個復制現有實例值的新實例。在這種情況下，Date的復制構造函數就接受了一個timestamp值，然后產生一個新的對象。
復制可變對象的另一種方法是clone()，某些類型但不是全部類型支持該方法。然而clone()在Java中的工作方式存在問題，更多可參考 Effective Java , item 11
? 現在我們已經通過防御性復制解決了 timestamp 返回值的問題。但我們還沒有完成任務！還有表示泄露。考慮這個非常合理的客戶端代碼：
1 /** @return a list of 24 inspiring tweets, one per hour today */ 2 public static List<Tweet> tweetEveryHourToday () { 3 List<Tweet> list = new ArrayList<Tweet>(); 4 Date date = new Date(); 5 for (int i = 0; i < 24; i++) { 6 date.setHours(i); 7 list.add(new Tweet("rbmllr", "keep it up! you can do it", date)); 8 } 9 return list; 10 }?
此代碼旨在創(chuàng)建24個Tweet對象，為每個小時創(chuàng)建一條推文。但請注意，Tweet的構造函數保存?zhèn)魅氲囊?#xff0c;因此所有24個Tweet對象最終都以同一時間結束，如此快照圖所示。
但是，Tweet的不變性再次被打破了，因為每?個Tweet創(chuàng)建時對Date對象的索引都是?樣的。所以我們應該對創(chuàng)建者也進?防御性編程：
1 public Tweet(String author, String text, Date timestamp) { 2 this.author = author; 3 this.text = text; 4 this.timestamp = new Date(timestamp.getTime()); 5 }通常來說，要特別注意ADT操作中的參數和返回值。如果它們之中有可變類型的對象，確保你的代碼沒有直接使?索引或者直接返回索引。
你可能反對說這看起來很浪費。為什么要制作所有這些日期的副本？為什么我們不能通過像這樣仔細書寫的規(guī)范來解決這個問題？
/*** Make a Tweet.* @param author Twitter user who wrote the tweet* @param text text of the tweet* @param timestamp date/time when the tweet was sent. Caller must never * mutate this Date object again!*/ public Tweet(String author, String text, Date timestamp) {? 這種方法一般只在特不得已的時候使用——例如，當可變對象太大而無法有效地復制時。但是，由此引發(fā)的潛在bug也將很多。除非迫不得已，否則不要把希望寄托于客戶端上，ADT有責任保證自己的不變量，并避免表示泄露。
? 最好的辦法就是使用immutable的類型，徹底避免表示泄露，例如?java.time.ZonedDateTime?而不是?java.util.Date。
?
## 抽象函數AF與表示不變量RI
【AF與RI】
- 在研究抽象類型的時候，先思考一下兩個值域之間的關系：
- 表示域（rep values）里面包含的是值具體的實現實體。一般情況下ADT的表示比較簡單，有些時候需要復雜表示。?
- 抽象域（A）里面包含的則是類型設計時支持使用的值。這些值是由表示域“抽象/想象”出來的，也是使用者關注的。
- ADT實現者關注表示空間R，用戶關注抽象空間A 。
- R->A的映射特點：
- 每一個抽象值都是由表示值映射而來?，即滿射：每個抽象值被映射到一些rep值
- 一些抽象值是被多個表示值映射而來的，即未必單射：一些抽象值被映射到多個rep值
- 不是所有的表示值都能映射到抽象域中，即未必雙射：并非所有的rep值都被映射。
?
- 抽象函數（AF）：R和A之間映射關系的函數
- 表示不變量（RI）：將rep值映射到布爾值
-
- 對于表示值r，當且僅當r被AF映射到了A，RI(r)為真。?
- 表示不變性RI：某個具體的“表示”是否是“合法的”
- 也可將RI看作：所有表示值的一個子集，包含了所有合法的表示值
- 也可將RI看作：一個條件，描述了什么是“合法”的表示值
- 在下圖中，綠色表示的就是RI(r)為真的部分，AF只在這個子集上有定義。
- 表示不變量和抽象函數都應該記錄在代碼中，就在代表本身的聲明旁邊，以下圖為例?
?
public class CharSet {private String s;// Rep invariant:// s[0] <= s[1] <= ... <= s[s.length()-1]// Abstraction function:// AF(s) = {s[i] | 0 <= i < s.length()} ... }?
public class CharSet {private String s;// Rep invariant:// s.length() is even// s[0] <= s[1] <= ... <= s[s.length()-1]// Abstraction function:// AF(s) = union of {s[2i],...,s[2i+1]} for 0 <= i < s.length()/2 ... }【用注釋寫AF和RI】
- 在抽象類型（私有的）表示聲明后寫上對于抽象函數和表示不變量的注解，這是一個好的實踐要求。我們在上面的例子中也是這么做的。
- 在描述抽象函數和表示不變量的時候，注意要清晰明確：
- 對于RI（表示不變量），僅僅寬泛的說什么區(qū)域是合法的并不夠，你還應該說明是什么使得它合法/不合法。
- 對于AF（抽象函數）來說，僅僅寬泛的說抽象域表示了什么并不夠。抽象函數的作用是規(guī)定合法的表示值會如何被解釋到抽象域。作為一個函數，我們應該清晰的知道從一個輸入到一個輸入是怎么對應的。
- 本門課程還要求你將表示暴露的安全性注釋出來。這種注釋應該說明表示的每一部分，它們?yōu)槭裁床粫l(fā)生表示暴露，特別是處理的表示的參數輸入和返回部分（這也是表示暴露發(fā)生的位置）。
- 下面是一個Tweet類的例子，它將表示不變量和抽象函數以及表示暴露的安全性注釋了出來：
注意到我們并沒有對?timestamp?的表示不變量進行要求（除了之前說過的默認?timestamp!=null）。但是我們依然需要對timestamp?的表示暴露的安全性進行說明，因為整個類型的不變性依賴于所有的成員變量的不變性。
?
轉載于:https://www.cnblogs.com/hithongming/p/9132655.html
總結
以上是生活随笔為你收集整理的【软件构造】第三章第三节 抽象数据型(ADT)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： RK3288 GMAC整理
- 下一篇： 绘制路径