Data Abstraction: The Walls Chapter 3 Data Abstraction: The Walls

3.1 Abstract Data Types (抽象資料型態) 模組化 讓我們可以經由一個大程式的元件間的互動來管理複雜的大程式 可以隔離錯誤 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types 模組化(Continued) 模組化的程式 消去重複的程式碼 易寫 易讀 易改 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types(抽象資料型態) 程序的抽象化 (Procedural Abstraction) 將模組的目的及使用方式與模組的實作分離 模組的規格(specification)應該 詳述此模組的行為表現(由外面觀察到) 指出隱藏在此模組內部的細節 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types 資訊隱藏 (Information hiding) 隱藏部份此模組內部之實做細節 讓這些細節無法由模組外部得知 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types Q 是應用程式，Q 不用知道工作 T 是怎樣完成的，但 Q 必須知道這個工作的內容以及如何啟動 T 這個工作 (就是呼叫 T ) Figure 3.1 隔離的工作: 工作 T 的實作不會影響應用程式 Q 的工作 © 2005 Pearson Addison-Wesley. All rights reserved

函式的規格, 或說是合約, 主導他們之間如何互動 Abstract Data Types 模組的隔離並非全面性的(牆上有留細縫作為模組與外部之介面) 函式的規格, 或說是合約, 主導他們之間如何互動 Figure 3.2 牆上的細縫 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types 對資料的慣有標準操作 新增資料至資料集 自資料集移除資料 詢問資料集之資料的相關問題 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types 資料抽象化(Data abstraction) 要求你思考你可以為一個資料集做什麼，先不用考慮如何實做該操作 允許你可以獨立開發各個資料結構，不會被解決方案其他部分綁住 是程序抽象化很自然的擴充 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types (ADT) 一個資料集 一群定義在這個資料集上的操作 一個 ADT 的規格指出 這個 ADT 的操作會做什麼，不是如何實做那些操作 一個 ADT 的實做 包含選擇一個適當的資料結構 © 2005 Pearson Addison-Wesley. All rights reserved

範例 如果要設計可以儲存一群員工姓名及薪資的資料結構 const int MAX_NUMBER = 500; string names[MAX_NUMBER]; double salaries[MAX_NUMBER]; 在此第 i 個員工的姓名為 names[i]，薪資為 salaries[i]，names 及 salaries 這兩個陣列就形成一個資料結構，C++ 並沒有資料型態 (data type) 可以直接表示這樣的資料結構 當程式需要執行一些程式語言並不直接支援的資料相關操作，我們就要先設計一個抽象資料型態 (ADT)，定義其相關操作的內容(what)，接著才去實做這些相關操作 © 2005 Pearson Addison-Wesley. All rights reserved

Abstract Data Types 範例：製冰機、販賣機 Figure 3.4 一個 ADT 的操作形成的牆 隔離了資料結構的實做與使用該資料結構的程式 範例：製冰機、販賣機 © 2005 Pearson Addison-Wesley. All rights reserved

製冰機 © 2005 Pearson Addison-Wesley. All rights reserved

3.2 The ADT List (抽象資料型態：清單) 除了第一及最後這兩個項目, 其他每個項目都有一個唯一的前一項 (predecessor) 及唯一的後一項(successor) 序列頭(Head, 又稱序列最前線) 並沒有前一項 序列尾巴(Tail,又稱序列最後)並沒有後一項 在清單上的項目們, 加上可以針對清單及其項目進行的操作，形成一個 ADT © 2005 Pearson Addison-Wesley. All rights reserved

超市購物清單序列 © 2005 Pearson Addison-Wesley. All rights reserved

The ADT List 項目是透過他們在清單的位置被引用(referenced) ADT 操作的規格 不規定清單如何儲存、內部如何實做這些操作 ADT 操作應可以直接讓應用程式呼叫，應用程式不需知道這些操作是如何實做出來的 © 2005 Pearson Addison-Wesley. All rights reserved

The ADT List ADT 清單的操作範例 新增一個空白清單 詢問一個清單是否為空白 詢問一個清單裡的項目個數 在清單的某個位置加入一個項目 將清單的某個位置的項目移除 清空整份清單 擷取 (get)清單的某個位置的項目 © 2005 Pearson Addison-Wesley. All rights reserved

UML Diagram for ADT List © 2005 Pearson Addison-Wesley. All rights reserved

應用程式 假設有一 aList，以下每一動作執行完後，請問 aList 的內容會變成什麼樣子?? aList.createList( ); aList.insert(1, milk, success); aList.insert(2, eggs, success); aList.insert(3, butter, success); aList.insert(4, apples, success); aList.insert(5, bread, success); aList.insert(6, chicken, success); aList.insert(4, nuts, success); aList.remove(5, success); 我們不用知道 List 是怎麼實做的就可以知道 aList 在這些動作後的結果，這就是 ADT 的優點 success 是一個 boolean 參數, 用來表示此操作是成功還是失敗 © 2005 Pearson Addison-Wesley. All rights reserved

應用程式 列印清單上所有項目 displayList(in aList:List) 的程式 for (position = 1 through aList.getlength( ) ) { aList.retrieve(position, dataItem, success) cout << dataItem << endl; } © 2005 Pearson Addison-Wesley. All rights reserved

ADT 操作的牆壁 © 2005 Pearson Addison-Wesley. All rights reserved

應用程式 aList.remove(i, success); 以一個新項目取代某位置原有項目 replace(in aList: List, in i:integer, in newItem:ListItemType, out success:boolean) 的程式 aList.remove(i, success); if (success) aList.insert(i, newItem, success); © 2005 Pearson Addison-Wesley. All rights reserved

The ADT List 另一個 ADT 排過序清單 (sorted list) 會將清單的項目自動維持在排過序的狀況 加入及移除項目時只要直接給該項目的值，不用提供其位置 © 2005 Pearson Addison-Wesley. All rights reserved

The ADT sorted list 相關操作 createSortedList() destroySortedList( ) sortedIsEmpty( ): boolean {query} sortedGetLength( ): integer {query} sortedInsert(in newItem:ListItemType, out success:boolean) sortedRemove(in anItem:ListItemType, out success: boolean) sortedRetrieve(in index:integer, out dataItem: ListItemType, out success: boolean) {query} locatePosition(in anItem: ListItemType, out isPresent: boolean): integer {query} © 2005 Pearson Addison-Wesley. All rights reserved

Designing an ADT ADT 的設計應該隨著解決問題的過程自然演進 設計ADT 時該問的事 這個問題需要哪些資料? 這個問題需要哪些操作? 放假日範例 會議簿範例 © 2005 Pearson Addison-Wesley. All rights reserved

範例 列出每年所有放假日演算法如下 listHolidays(in year: integer) date = date of the first day of year while ( date is before the first day of year+1) { if (date is a holiday) cout << date << “is a holiday” << endl; date = next day of date } // end of while 要有哪些資料？有哪些操作? © 2005 Pearson Addison-Wesley. All rights reserved

範例 date = firstDay(year) while ( isBefore(date, firstDay(year+1) ) { if (date.isHoliday()) cout << date << “is a holiday” << endl; date = date.nextDay() } // end of while © 2005 Pearson Addison-Wesley. All rights reserved

範例 會議簿： 假設你希望可以紀錄上班日自上午 8 點至 下午 5 點各整點及 30 分的各項會議主題 要有哪些資料？有哪些操作？ 設定會議日期、時間、主題 取消某日期、時間的會議 查詢某個日期時間是否有會議要開？ 如果有會議，主題為何？ 細節請參考課本 p. 128 © 2005 Pearson Addison-Wesley. All rights reserved

範例 會議簿的操作 請運用以上操作,練習寫一個修改已知會議的日期、時間的程式？ createAppointmentBook( ) isAppointment( in appDate:aDate, in appTime:Time): boolean {query} makeAppointment(in appDate:Date, inappTime:Time, in purpose:string): boolean cancelAppoint(in appDate:aDate, in appTime:Time): boolean checkAppointment(in appDate:aDate, in appTime:Time, out purpose:string): boolean {query} 請運用以上操作,練習寫一個修改已知會議的日期、時間的程式？ © 2005 Pearson Addison-Wesley. All rights reserved

ADTs that suggests other ADTs 假設你要設計一個食譜資料庫 資料項目是食譜 對此資料庫的操作包括： insertRecipe(in aRecipe: Recipe, out: success: boolean) deleteRecipe(in aRecipe: Recipe, out: success: boolean) retrieveRecipe(in name: string, out: a Recipe: recipe, out success: boolean) {query} © 2005 Pearson Addison-Wesley. All rights reserved

ADTs that suggests other ADTs 現在要將食譜擴充可服務人數：假設原食譜可服務 n 個人現在要服務 m 個人 這個問題建議我們為食譜物件再增加一個 ADT：份量(measurement) Operations getMeasure(): Measurement {query} setMeasure(in m: Measurement) scaleMeasure(out newMeasure:Measurement, in scaleFactor: float) convertMeasure(in oldUnits: MeasureUnit, out newMeasure: Measurement, in newUnits: MeasureUnit) {query} © 2005 Pearson Addison-Wesley. All rights reserved

ADTs that suggests other ADTs 假設份量(Measurement)又要細到可以做分數的運算 這個問題建議我們為份量物件再增加一個 ADT：分數 (fraction) Operations 加、減、乘、除 © 2005 Pearson Addison-Wesley. All rights reserved

Designing an ADT 對於複雜的資料型態, 其操作之行為表現應該以數學公理 (Axiom) 來下規格 Ex. : (aList.createList()).size() = 0 透過這些數學定理，證明比較嚴謹，但需要有紮實數學基礎才做得到 Axioms 部分跳過 (p. 131 – 133上半) © 2005 Pearson Addison-Wesley. All rights reserved

3.3 Implementing ADTs 一個 ADT的實做是由選擇一個適當的資料結構來表示一個 ADT 內的資料開始 資料結構的選擇取決於 此 ADT 的操作細節 這些操作的使用情境 再來要依據 ADT 的操作，寫存取這個資料結構的函式 通常要經過接連的多層次抽象化的過程來將 ADT 操作實做出來，也就是要用由上而下 (top-down) 的方式來設計各個 操作 的演算法 © 2005 Pearson Addison-Wesley. All rights reserved

Implementing ADTs 實做細節應該都要隱藏在 ADT 操作牆的後面 應用程式僅能藉由ADT 操作來存取實做的資料結構 傳統非物件導向的方式無法禁止應用程式違反這項原則，例如：如果以陣列 items 來儲存 ADT List 的各個項目時，無法防止應用程式以下列方式讀取資料： firstItem = items[0]; 當以其他方式來實做 ADT List 時，這些程式都要跟著修改，造成不便 © 2005 Pearson Addison-Wesley. All rights reserved

Implementing ADTs Figure 3.8 ADT operations provide access to a data structure © 2005 Pearson Addison-Wesley. All rights reserved

Implementing ADTs Figure 3.9 違反 ADT 操作牆的資料存取 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Classes 封裝 (Encapsulation) 將一個 ADT 的資料及操作組合成一個物件 一個物件就是一個類別的實例 一個類別需定義及實作其實例所需之資料成員及成員函式 所有類別內的資料成員 (也就是成員變數)都預設為私有的 (private) 一個 ADT 的操作就成為觀察該物件的行為表現之介面 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Classes 當你只是要將不同型別的資料放在一起，你可以使用 struct , 如果有操作就需要用 class 類別的定義(宣告)放在一個標頭檔 Classname.h 類別的成員函式的實做放在一個實做檔 Classname.cpp © 2005 Pearson Addison-Wesley. All rights reserved

C++ Classes Figure 3.10 一個物件的資料及操作都要經過封裝 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Classes (Example) Sphere (球體) 相關檔案 標頭檔: Sphere.h 實作檔: Sphere.cpp 應用程式: SphereDemo.cpp 如何在 project 中放入 3 個檔的作法請參考 http://mail.im.tku.edu.tw/~cjou/ds2005/project.doc © 2005 Pearson Addison-Wesley. All rights reserved

Class Constructors and Destructors 產生及初始化一個類別的實例內的資料成員 與類別名稱相同 沒有傳回資料型態，連 void 也不用 © 2005 Pearson Addison-Wesley. All rights reserved

Class Constructors and Destructors 一個類別可以有數個建構子 預設建構子沒有任何參數 初始段 (就是如 : theRadius(1.0) 這一段)可以設定資料成員的初始值 如果一個類別沒有任何建構子, 編譯器會主動產生該類別的預設建構子 但如果有其他需要參數的建構子，卻沒有預設建構子，那麼 compiler 就不會自動產生預設建構子，也就不能做如下宣告： Sphere defaultSphere; © 2005 Pearson Addison-Wesley. All rights reserved

Class Constructors and Destructors 建構子 (及任何成員函式) 的實做都要放在類別有效範圍運算元 (::) 之後 Sphere::Sphere(double initialRadius) : theRadius(initialRadius) © 2005 Pearson Addison-Wesley. All rights reserved

Class Constructors and Destructors 當某物件的生命週期結束時(如結束函式時，該函式的區域物件的生命週期就結束了)，摧毀此物件的實體，讓他佔用的記憶體空間回收到電腦系統 每一類別都僅有一個解構子 大多數類別，可以不用特別寫解構子 如果成員變數裡包含有動態陣列，就不能省略，否則程式執行一段時間後會當掉 當類別沒有解構子時，編譯器會主動產生一個預設的解構子 © 2005 Pearson Addison-Wesley. All rights reserved

Inheritance (繼承) in C++ (跳過) A derived class or subclass inherits any of the publicly defined functions or data members of a base class or superclass 這部份 3 年級再上 (課本 p. 143 – p.144先跳過) © 2005 Pearson Addison-Wesley. All rights reserved

Inheritance in C++ (跳過) An instance of a derived class can invoke public methods of the base class: #include “Sphere.h” enum Color {RED, BLUE, GREEN, YELLOW} class ColoredSphere: public Sphere { public: … Color getColor() const; © 2005 Pearson Addison-Wesley. All rights reserved

C++ Namespaces (命名空間) 這個機制將相關宣告及定義框在一起，成為一個通用的宣告區 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Namespaces 一個命名空間的內容可以讓命名空間裡面及外面的程式碼存取 在命名空間外面要存取其內容，要使用有效範圍運算元 (::) 或是, 加上 using 宣告就可以直接使用內容的名稱 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Namespaces 產生一個命名空間 使用一個命名空間 namespace smallNamespace { int count = 0; void abc(); } //end smallNamespace 使用一個命名空間 using namespace smallNamespace; count +=1; abc(); © 2005 Pearson Addison-Wesley. All rights reserved

C++ Namespaces C++ Standard Library 所宣告的項目都在std 命名空間宣告 有些函式所需的 C++ include 檔案也都在 std 命名空間 要使用 C++ 輸入輸出函式庫裡的函式, 要包括以下程式碼 include <iostream> using namespace std; © 2005 Pearson Addison-Wesley. All rights reserved

An Array-Based ADT List (以陣列實做的清單) 清單的項目儲存在陣列 items 陣列及清單都是使用位置來區別其項目(元素)，但是陣列的索引由 0 開始，清單的位置由 1 開始 相關檔案：ListA.h, ListA.cpp, ListDemo.cpp © 2005 Pearson Addison-Wesley. All rights reserved

An Array-Based ADT List 清單第 kth 個項目儲存在 items[k-1] Figure 3.11 An array-based implementation of the ADT list © 2005 Pearson Addison-Wesley. All rights reserved

An Array-Based ADT List 在位置 3 插入新內容必須將原來在位置 3 集之後的所有項目往右移一個位置 © 2005 Pearson Addison-Wesley. All rights reserved

An Array-Based ADT List 刪除時會造成一個空隙 © 2005 Pearson Addison-Wesley. All rights reserved

An Array-Based ADT List 在刪除位置 之後的所有項目往左移一個位置 © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions (以下全部跳過) A mechanism for handling an error during execution A function indicates that an error has occurred by throwing an exception The code that deals with the exception is said to catch or handle it © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions Throwing exceptions A throw statement is used to throw an exception throw ExceptionClass (stringArgument); © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions try block A statement that might throw an exception is placed within a try block Syntax try { statement(s); } // end try © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions catch block Used to catch an exception and deal with the error condition Syntax catch (exceptionClass identifier) { statement(s); } // end catch © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions A programmer-define ListException class #include <exception> #include <string> using namespace std; class ListException: public exception { public: ListException (const string & message = “”) : exception(message.c_str()) {} }; // end ListException © 2005 Pearson Addison-Wesley. All rights reserved

C++ Exceptions List with Exception handling 相關檔案： ListAexcep.h, insert.cpp, (還不完整), ListException.h, ListIndexOutOfRangeException.h, ListDemo.cpp (但要修一下 include 的檔案) © 2005 Pearson Addison-Wesley. All rights reserved

Summary Data abstraction controls the interaction between a program and its data structures Abstract data type (ADT): a set of data-management operations together with the data values upon which they operate Mathematical study of ADTs uses axioms to specify the behavior of ADT operations An ADT should be fully defined before any implementation decisions © 2005 Pearson Addison-Wesley. All rights reserved

Summary Hide an ADT’s implementation by defining the ADT as a C++ class An object encapsulates both data and operations A class contains at least one constructor and a destructor The compiler generates default constructor and destructor if none are provided © 2005 Pearson Addison-Wesley. All rights reserved

Summary Members of a class are private by default Data members are typically private Public functions can be provided to access them Define and implement a class within header and implementation files Namespace: a mechanism to group classes, functions, variables, types, and constants Use exception handling to throw, catch, and handle errors during program execution © 2005 Pearson Addison-Wesley. All rights reserved