链结的实现.PPT

Chapter 09 抽象資料型態與演算法 學習目標 定義抽象資料型態並討論它在演算法發展上的角色 區分資料型態與資料結構 區分陣列為基礎的實現與鏈結的實現 區分陣列與串列 區分未排序的串列與已排序的串列 區分選擇排序與泡沫排序 以手寫方式應用選擇排序、泡沫排序到串列的項目上 區分堆疊與佇列的操作之不同 了解複雜資料結構，如樹狀結構、圖形等 具體說明你對本章裏所提的演算法之了解程度，並以手寫方式模擬這些演算法 9.1 抽象資料型態 資料形態 (data type)：是一些值與能被用於該類型的值上的基本運算的集合 如：Integer 的值範圍 -215 至 215 -1，其運算子有 + - * / mod 等等 抽象資料型態（abstract data type，簡寫為 ADT）：被指定的特性（資料與操作）與任何特定的實現方式無關的資料型態 例如：代表帳戶的抽象資料型態就需提供 存款、提款、轉帳、查詢帳戶餘額等操作 抽象化設計的目標就是要降低複雜度，如果在邏輯層面定義出某 抽象資料型態 一些有用的結構及操作方式，就不用管它如何被實現，可以直接應用這些結構及操作方式 抽象資料型態(續) 在計算機領域裏，我們從三個方面來看待資料 應用層面（Application level） 看待資料是在一特定問題之中 邏輯層面（ Logical level）或抽象層面 (Abstract level ) 資料值（值域）的一種抽象觀點與操作這些值的運算子之集合 物件導向的類別 (class) 可以用 CRC (Class-Responsibility-Collaboration)卡及其 ADT 行為的演算法來表示 實現層面（Implementation level） 具有資料項目的結構與在程式語言中運算的程式碼之特定表達方式，關注的是 資料結構 抽象資料型態(續) 資料結構（data structure）：在抽象資料型態中組成資料欄位的實現方法 這些 ADT 也叫做 容器（container），用來儲存資料項目與顯示其指定行為 9.2 實現 本節討論實現串列(List，也可稱為 清單) 的 2 種不同類型實現方式 以陣列為基礎 鏈結 串列在邏輯層應有的操作 放入項目 (Put item): 轉變者 移除項目 (Remove item): 轉變者 取得下一項目(Get next item)： 重複者 (iterator) 還有項目? (More item?): 觀察者 (observer) 陣列為基礎的實現 回想 陣列被視為是同質項目集合的名稱 在集合中的位置稱之為索引（index） 陣列可用來儲存在容器內的項目 如果在容器內的項目沒有次序關係，我們稱此容器是未經排序的（unsorted） 如果有一種次序關係存在，我們稱此容器是排序過的（sorted） 陣列為基礎的實現(續) 陣列為基礎的實現(續) 陣列為基礎的實現(續) Put item: 給定一個索引值，移動之後所有項目到陣列中的下一個槽，儲存項目到索引槽 如：put_item(3, 100) Remove item:給定一個索引值，移動之後所有項目到陣列的上一個槽 如：remove_item(3) Get next item: 增加索引值 (+1)，並讀取那個索引位置的項目 “More items?” : 檢查索引值是否還小於 length -1，為一布林值，如果”是” 則傳回值 TRUE，如果 “否” 則傳回值 FALSE 鏈結的實現 鏈結的實現（linked implementation）：基於節點（node）的概念 節點是由兩部分的資料組成：一個是使用者希望存在串列中的資料項目(info)，一個是指向串列中下一個節點的指標(next pointer) 鏈結的實現(續) 鏈結的實現(續) 鏈結的實現(續) 鏈結的實現(續) Get next item: 將 current 設定成 next(current)，即將 current 改設為 原 current 所指向節點的下一個節點 “More items?”: 檢查 current 指向的節點的 next 是否為 null ，如果”是” 則傳回值 FALSE，如果 “否” 則傳回值 TRUE 9.3 串列(又稱 清單) 串列的三種特性： 項目都是同性質的、項目都是線性的、串列具有可變動的長度 串列必須要能做的動作 建立它自己 插入一個項目 刪除一個項目 印出它自己 知道它所儲存的項目數量 串列(續) 通用資料型態（generic data type）（或類別）：一種指定好動作，但是要被操作的物件型態或類別則還未指定的資料型態 (或類別) 串列是一種通用資料型態 串列(續) 串列(續) Insert(Item)第一