第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.

Presentation on theme: "第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java."— Presentation transcript:

1 第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java

2 資料結構簡介 資料與資訊 演算法 演算法的條件

3 資料與資訊 所謂資料(Data)，指的就是一種未經處理的原始文字(Word)、數字(Number)、符號(Symbol)或圖形(Graph)等，它所表達出來的只是一種沒有評估價值的基本元素或項目。 當資料經過處理(Process)，例如以特定的方式有系統的整理、歸納甚至進行分析後，就成為「資訊」(Information)。

4 演算法 日常生活中有許多工作都可以利用演算法來描述，例如員工的工作報告、寵物的飼養過程、學生的功課表等。
資料結構與演算法是程式設計中最基本的內涵。 程式是否能清楚而正確的把問題解決，取決於演算法。 所以可以這麼認為：「資料結構加上演算法等於可執行的程式。」 日常生活中有許多工作都可以利用演算法來描述，例如員工的工作報告、寵物的飼養過程、學生的功課表等。

5 演算法的條件 當認識了演算法的定義後，我們還要說明演算法所必須符合的五個條件：

6 演算法的五項條件 演 算 法 特 性 內 容 與 說 明 輸入(Input) 0個或多個輸入資料，這些輸入必須有清楚的描述或定義。
輸出(Output) 至少會有一個輸出結果，不可以沒有輸出結果。 明確性(Definiteness) 每一個指令或步驟必須是簡潔明確而不含糊的。 有限性 (Finiteness) 在有限步驟後一定會結束，不會產生無窮迴路。 有效性(Effectiveness) 步驟清楚且可行，能讓使用者用紙筆計算而求出答案。

7 常用的演算法 一般文字敘述：中文、英文、數字等。文字敘述法的特色在使用文字或語言敘述來說明演算步驟。例如以下就是一個學生小華早上上學並買早餐的簡單文字演算法：

8 虛擬語言(Pseudo-Language)：接近高階程式語言的寫法，也是一種不能直接放進電腦中執行的語言。一般都需要一種特定的前置處理器(preprocessor)，或者用手寫轉換成真正的電腦語言，經常使用的有SPARKS、PASCAL-LIKE等語言。以下是用SPARKS寫成的鏈結串列反轉的演算法： Procedure Invert(x) 　　Px;QNil; 　　WHILE P≠NIL do 　　　　　rq;qp; 　pLINK(p); 　LINK(q)r; 　　　END 　　xq; END

9 表格或圖形：如陣列、樹狀圖、矩陣圖等。

10 流程圖：流程圖( Flow Diagram) 算是一種通用的表示法，也有的圖型符號。例如請您輸入一個數值，並判別是奇數或偶數。

11 程序語言：目前演算法也能夠直接以可讀性高的高階語言來表示，例如Visual Basic語言、C語言、C++語言、Java語言。

12 演算法和程序 演算法和程序是有所區別，因為程式不一定要滿足有限性的要求，如作業系統或機器上的運作程式。
除非當機，否則永遠在等待迴路(waiting loop)，這也違反了演算法五大原則之一的「有限性」。 只要是演算法都能夠利用程式流程圖表現，但因為程式流程圖可包含無窮迴路，所以無法利用演算法來表達。

13 認識程式設計 資料結構與演算法必須透過程式(Program)的轉換，才能真正由電腦系統來執行。
所謂程式，是由合乎程式語言語法規則的指令所組成，而程式設計的目的就是透過程式的撰寫與執行來達到使用者的需求。

14 程式語言的好壞 可讀性(Readability)高：閱讀與理解都相當容易。
平均成本低：成本考量不侷限於編碼的成本，還包括了執行、編譯、維護、學習、除錯與日後更新等成本。 可靠度高：所撰寫出來的程式碼穩定性高，不容易產生邊際錯誤(Side Effect)。 可撰寫性高：對於針對需求所撰寫的程式相對容易。

15 程式設計步驟 需求認識(requirements)：了解程式所要解決的問題是什麼，有那些輸入及輸出等。
設計規劃(design and plan)：根據需求，選擇適合的資料結構，並以任何的表示方式寫一個演算法以解決問題。 分析討論(analysis and discussion)：思考其他可能適合的演算法及資料結構，最後再選出最適當的標的。 編寫程式(coding)：把分析的結論，寫成初步的程式碼。 測試檢驗(verification)：最後必需確認程式的輸出是否符合需求，這個步驟得細步的執行程式並進行許多的相關測試。

16 資料型態簡介 基本資料型態(atomic data type) 結構型資料型態(structure data type)
抽象資料型態(Abstract Data Type, ADT)

17 基本資料型態(atomic data type)
或稱為實質資料型態(physical data type)，也就是一個基本的資料實體，例如一般程式語言中的整數、實數、字元等等。 像C語言的基本資料型態為整數(int)、字元(char)、單精度浮點數(float)與倍精度浮點數(double)。

18 結構型資料型態 (structure data type)
或稱為虛擬資料型態(virtual data type)，比實質資料型態更高一層，是指一個資料實體包含其他的資料型態。 例如字串(string)、集合(set)、陣列(array)。

19 抽象資料型態 (Abstract Data Type, ADT)
比結構型資料型態更高一層，ADT是指定義一些結構型資料型態所具備的數學運算關係，使用者毋需考慮到ADT的製作細節，只要知道如何使用即可。 通常出現於物件導向程式語言(OOP) 中，例如堆疊(stack)或佇列(queue)就是一種很典型的ADT模式。

20 結構化程式設計 主要是以「由下而上法」與「由上而下法」為主。
「由下而上法」是指程式設計師將整個程式需求最容易的部份先編寫，再逐步擴大來完成整個程式。 「由上而下法」將整個程式需求從上而下、由大到小逐步分解成較小的單元，或稱為「模組」 (module)。 核心精神，就是「由上而下設計」 與「模組化設計」。 例如在Pascal語言中，這些模組稱為「程序」 (Procedure)，C語言中稱為「函式」 (Function)。

21 結構化程式設計控制流程 流程結構名稱 概念示意圖 [循序結構] 逐步的撰寫敘述。 [選擇結構] 依某些條件做邏輯判斷。 [重複結構]
依某些條件決定是否重複執行某些敘述。

22 物件導向程式設計 「物件導向程式設計」 (Object-Oriented Programming, OOP) 是近年來相當流行的一種新興程式設計理念。 它主要讓我們在設計程式時，能以一種更生活化、可讀性更高的設計觀念來進行，並且所開發出來的程式也較容易擴充、修改及維護。 常見的物件導向語言包括C++、Java等語言。

23 抽象化動作說明表 名稱 特 色 與 說 明 屬性 屬性(attribute)是指物件的靜態外觀描述，例如一輛車子的顏色、
　　　　　　　　　特　色　與　說　明 屬性 屬性(attribute)是指物件的靜態外觀描述，例如一輛車子的顏色、 大小等。就如同於JAVA程式中的類別成員資料(member data)。 方法 方法(method)是指物件中的動態回應方式，例如車子可以開動、停 止。就是一種行為模式，是用來代表一個物件的功能，也就是JAVA 中的類別成員方法(member method)。 事件 事件(event)是指物件可以針對外部事件做出各種反應，譬如車子沒油 時，引擎就會停止，當然物件也可以主動地發出事件訊息。例如 JAVA程式中的視窗元件就可以對事件做出反應與處理。

24 物件導向程式設計 封裝(Encapsulation) 繼承(Inheritance) 多形(Polymorphism)

25 封裝(Encapsulation) 是利用「類別」來實作「抽象化資料型態」(ADT)。
「抽象化」，就是將代表事物特徵的資料隱藏起來，並定義一些方法來做為操作這些資料的介面，也符合了資訊隱藏的意義，就稱為「抽象化資料型態」。 可將其資料成員定義為私有的(private)，而將用來運算或操作資料的函式成員則定義為公有的(public)或受保護的(protected)來實現資訊隱藏的功能，這就是「封裝」(encapsulation)的作用。

26 繼承(Inheritance) 在繼承關係中，被繼承者稱為「基礎類別」或「父類別」，而繼承者則稱「衍生類別」或「子類別」。
而繼承允許我們去定義一個新的類別來繼承既存的類別，進而使用或修改繼承而來的方法，並可在子類別中加入新的資料成員與函式成員。

27 多形(Polymorphism) 「多形」也是物件導向設計的重要特性，也稱為「同名異式」。 功能可讓軟體在發展和維謢時，達到充份的延伸性。
最直接的定義就是讓具有繼承關係的不同類別物件，可以呼叫相同名稱的成員函式，並產生不同的反應結果。

28 演算法效能分析 對一個程式(或演算法)效能的評估，經常是從時間與空間兩種因素來做考量。
時間方面是指程式的執行時間，稱為「時間複雜度」(Time Complexity)。 空間方面則是此程式在電腦記憶體所佔的空間大小，稱為「空間複雜度」(Space Complexity)。

29 時間複雜度 例如程式設計師可以就某個演算法的執行步驟計數來衡量執行時間的標準，但是同樣是兩行指令：
由於涉及到變數儲存型態與運算式的複雜度，所以真正絕對精確的執行時間一定不相同。 這時可以利用一種「概量」的觀念來做為衡量執行時間，我們就稱為「時間複雜度」(Time Complexity)。 a=a+1與a=a+0.3/0.7*10005

30 時間複雜度詳細定義 在一個完全理想狀態下的計算機中，我們定義一個T(n)來表示程式執行所要花費的時間，其中n代表資料輸入量。
當然程式的執行時間或最大執行時間(Worse Case Executing Time)作為時間複雜度的衡量標準，一般以Big-oh表示。 由於分析演算法的時間複雜度必須考慮它的成長比率(Rate of Growth)往往是一種函數，而時間複雜度本身也是一種「漸近表示」(Asymptotic Notation)。

31 Big-oh O(f(n))可視為某演算法在電腦中所需執行時間不會超過某一常數倍的f(n)，也就是說當某演算法的執行時間T(n)的時間複雜度(Time Complexity)為O(f(n))(讀成Big-oh of f(n)或Order is f(n))。 意謂存在兩個常數c與n0，則若n≧n0，則T(n)≦cf(n)，f(n)又稱之為執行時間的成長率(rate of growth)。

32 範例 1.3.1 假如執行時間T(n)=3n3+2n2+5n，求時間複雜度為何？ 範例 1.3.2 請證明 　 =O(n2)

33 範例1.3.3 考慮下列x←x+1的執行次數。 (1) (3) : x←x+1 : for i←1 to n do :
(2) for i←1 to n do : 　x←x+1 : end (3) for i←1 to n do :　 　　　for j←1 to m do 　　　　:　 　　　x←x+1 　　　　: 　　　end : end

34 範例1.3.4 範例1.4.5 求下列演算法中x←x+1的執行次數及時間複雜度。 請決定以下片斷程式的執行時間：
for i←1 to n do 　　j←i 　　for k←j+1 to n do x←x+1 　　end end k=100000 while k<>5 do 　　k=k DIV 10 end

35 常見Big-oh Big-oh 特 色 與 說 明 O(1) 稱為常數時間(constant time)，表示演算法的執行時間是一個常數倍。
　　　　　　　　特　色　與　說　明 O(1) 稱為常數時間(constant time)，表示演算法的執行時間是一個常數倍。 O(n) 稱為線性時間(linear time)，執行的時間會隨資料集合的大小而線性成長。 O(log2n) 稱為次線性時間(sub-linear time)，成長速度比線性時間還慢，而比常數時間還快。 O(n2) 稱為平方時間(quadratic time)，演算法的執行時間會成二次方的成長。 O(n3) 稱為立方時間(cubic time)，演算法的執行時間會成三次方 的成長。 O(2n) 稱為指數時間(exponential time)，演算法的執行時間會成 二的n次方成長。 O(nlog2n) 稱為線性乘對數時間，介於線性及二次方成長的中間之行為 模式。

36

37 對於n≥16時，時間複雜度的優劣比較關係如下：
範例1.3.6 決定下列的時間複雜度(f(n)表執行次數) O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(2n) a.f(n)=n2logn+logn 　　 b.f(n)=8loglogn c.f(n)=logn d.f(n)=4loglogn e.f(n)=n/ /n f.f(n)=n!

38 Ω(omega) Ω是一種時間複雜度的漸近表示法，以下是Ω的定義： 範例1.3.7
對f(n)= Ω(g(n))(讀作”big-omega of g(n)”)，意思是存在常數c和n0，對所有的n值而言，n>= n0時，f(n)≧cg(n)均成立。 例如f(n)=5n+6，存在c=5 n0=1，對所有n≧1時，5n+6≧5n，因此f(n)= Ω(n)而言，n就是成長的最大函數。 範例1.3.7 f(n)=6n2+3n+2，請利用Ω來表示f(n)的時間複雜度。

39 θ(theta) 是一種比Big-O與Ω更精確時間複雜度的漸近表示法。定義如下：
f(n)= θ(g(n))(讀作”big-theta of g(n)”)，意是存在常數c1、c2、n0，對所有的n≧n0時，c1g(n)≦f(n)≦c2g(n)均成立。換句話說，當f(n)=θ(g(n))時，就表示g(n)可代表f(n)的上限與下限。 例如以f(n)=n2+2n為例，當n≧0時，n2+2n≦3n2，可得f(n)=O(n2)。同理，n≧0時，n2+2n≧n2，可得f(n)=Ω(n2)。所以f(n)=n2+2n=θ(n2)

40 物件導向程式設計與Java JAVA是一種純物件導向程式設計(Object-Oriented Programming, OOP)語言。
程式中所有相關的程式運算或執行動作，都是利用由類別所產生的物件來控制。

41 類別與物件 通常物件並不會無憑空產生，它必須有一個可以依據的原型(Prototype)，而這個原型就是一般在物件導向程式設計中所稱的「類別」(Class)。 在JAVA中，物件的實作宣告方式如下： new：依照類別建構子所代表的參考型別，配置記憶體空間，以建立該類別的實體物件。 建構子(constructor)：用來建立該類別的物件，並在建立的同時設定初始值。 類別名稱 物件(變數)名稱 = new 建構子();

42 範例程式：ch01_01.java

43 物件導向特性 名稱 特 色 與 說 明 封裝 使用類別來製作抽象化的資料型態(abstract data type,
　　　　　　　　特　色　與　說　明 封裝 使用類別來製作抽象化的資料型態(abstract data type, ADT)，也就是利用類別將資料和用來處理資料的方法 包裝起來。 繼承 繼承是使所謂的衍生類別能完全地使用基礎類別的成員 資料與成員方法。 多形 多形或稱為「同名異式」（Polymorphism），就是讓具 有繼承關係的不同類別物件，可以呼叫相同名稱的成員 方法，並產生不同的反應結果。

44 資料封裝 關鍵字名稱 特 色 與 說 明 private 以private（私有的）所宣告的資料或方法，僅能被同一類別中的成員所使用。
　　　　　　特　色　與　說　明　　 private 以private（私有的）所宣告的資料或方法，僅能被同一類別中的成員所使用。 　protected 以protected所宣告的資料或方法，只可以在同一個類別，或是衍生類別或同一套件中，作有限度地存取動作。 　public 以public所宣告的各種資料或方法，可以被所有外部程式、類別或物件使用。

45 程式宣告片段 private int usePassword //宣告整數型態變數userPassword 為私有的資料成員
protected getPassword() //宣告類別方法getPassword為受 保護的成員方法 public class checkPassword //宣告類別checkPassword為公開 的類別

46 類別繼承 繼承就類似遺傳的觀念，當物件導向技術以這種生活實例去定義其功能時，則稱為繼承(inheritance)。
這種繼承模式在JAVA平台下的宣告語法如下： 存取修飾子 class 衍生類別名稱 extends 基礎類別名稱

47 存取修飾子 它代表的意義為：相同「套件」(package)中的所有類別都能存取此類別。 存取修飾子的關鍵字如下表： 關鍵字 特 色 說 明
特　色　說　明 public (公開的) 代表所有類別皆可存取此類別。 abstract（抽象的） 代表此類別不能被實體化(建立物件)。 final（最終的） 代表此類別無法再被重新定義(繼承)。

48 範例程式：ch01_02.java

49 物件多形 是利用類別繼承架構的基礎，先建立一個內容為「null」的基本類別物件，讓使用者可以將它轉變成為各種衍生類別物件，進而加以控制所有衍生類別的「同名異式」方法。

50 範例程式：ch01_03.java

51 抽象類別 宣告語法如下： abstract class 類別名稱 { … abstract 傳回值的資料型態 成員方法(引數列); }

52 範例程式：ch01_04.java

53 介面 宣告語法表列如下： interface 介面名稱 { … 傳回值的資料型態 成員方法(); }

54 範例程式：ch01_05.java