第2章 資料結構與演算法的關係 Java程式複習

Presentation on theme: "第2章 資料結構與演算法的關係 Java程式複習"— Presentation transcript:

1 第2章 資料結構與演算法的關係 Java程式複習

2 課程內容 資料結構基本介紹 資料結構與演算法 效能分析的重要 複習-Java程式設計 判斷 迴圈 陣列

3 資料結構的基本概念 資料結構 (data structures) 就是在探討收納與使用資料的問題。

4 資料結構的形成 陣列(Array)就是資料結構的其中一種。

5 演算法 (Algorithm) 資料結構是表示問題的方式， 演算法則是解決問題的辦法。
但是一個問題的解決途徑可能有多種，往往同一 個問題可以用不同的資料結構來表示，同時也會 發展出不同的演算法來，不過在效能上會有差異。

6 資料結構與演算法的關聯 data structures + algorithms = programs
任何人都可以創造新的資料結構和演算法，前提 是這些資料結構和演算法要有實際的用途，換句 話說，理論要跟應用結合在一起。 例：撰寫九九乘法表程式， 使用二維陣列、一維陣列或 無陣列的程式寫法會就不同。

7 資料結構、演算法與程式語言 資料結構跟演算法都還是以人類的方式來思考的， 因此必須再用某種程式語言來完成資料宣告、並 將演算法的程序寫成程式，才能交由電腦來執行。 要用哪一種程式語言並沒有特別規定，因為當我 們探討資料結構或演算法時，是把它們當成一種 觀念來敘述，任何一種程式語言都應該有能力把 觀念具體化。

8 效能分析與效率計量 電腦解決一個問題的時候要花多少時間或是多少 儲存的空間，都可以當成效能 (performance) 的 指標
花的時間越少(時間複雜度)、使用的儲存空間越 小(空間複雜度)，代表效能越好。 就效能來說，資料結構與演算法是分不開的，因 為問題的描述以及問題解決的方法，都是透過資 料結構與演算法來定義的。

9 複習-Java程式設計 判斷 迴圈 陣列

10 判斷-選擇性結構 根據條件的成立與否，再決定要執行哪些敘述

11 if-else 敘述 (1/2) if-else敘述的格式與流程圖如下： if-else 敘述的格式 if(判斷條件) { 敘述主體1; }
敘述主體2; if -else敘述的流程圖

12 巢狀 if 敘述 if 敘述中又包含其它 if 敘述時，稱為巢狀 if 敘述 （nested if） 若判斷條件1成立，則執行這個部份
{ if(判斷條件2) 敘述主體; } ... 其它敘述; 若判斷條件2成立，則執行這個部份

13 邏輯運算子 (1/2) 邏輯運算子與真值表： 邏輯運算子的使用範例：
邏輯運算子的成員 AND與OR真值表 邏輯運算子的使用範例： （1）a>0 && b>0 // 兩個運算元皆為真，運算結果才為真 （2）a>0 || b>0 // 兩個運算元只要一個為真，運算結果就為真

14 練習 修改JPA201程式，讓使用者輸入成績，按照以下標 準顯示結果 100 49 60 成績輸入錯誤 需要補考

15 迴圈的種類 while 迴圈 do while 迴圈 for 迴圈

16 while 迴圈 (1/2) while迴圈敘述格式 設定迴圈初值; while(判斷條件) { 迴圈主體; 設定增減量; }
這兒不可以加分號 這兒不可以加分號

17 while 迴圈 (2/2) 利用while迴圈計算1+2+...+10：
在程式設計的慣例上，會在確定迴圈次數時選擇for迴圈，而在不確定迴圈次數時選擇while迴圈，這樣的做法能讓語意更清楚的表達

18 do while 迴圈 (1/2) do while是用於迴圈執行的次數未知時 do while至少會執行1次迴圈主體
設定迴圈初值; do { 迴圈主體; 設定增減量; } while(判斷條件); 要加分號

19 do while 迴圈 (2/2)

20 for迴圈 (1/2) for迴圈的格式及執行流程： for迴圈敘述格式 for(設定迴圈初值; 判斷條件; 設定增減量) { 迴圈主體;
} 這兒不可以加分號 這兒不可以加分號

21 for迴圈 (2/2) 下面的程式利用for迴圈計算 ：

22 for迴圈裡的區域變數 迴圈裡宣告的變數是區域變數（local variable），跳 出迴圈，這個變數便不能再使用

23 練習 修改JPA202檔案，使其印出的count之值為27。

24 陣列 陣列的宣告與使用 一維、二維、三維陣列

25 一維陣列的基本結構與特性 [一維陣列的基本結構]
一維陣列就是只用一個編號來標示個別元素空間 的陣列結構。就像冰箱裡單排的蛋架，每個空間 只需要一個編號就可以區別，而一個位置剛好可 以裝一顆蛋。

26 一維陣列 一維陣列（1-dimensional array）可以存放多個相同 資料型態的資料。 使用陣列必須經過兩個步驟：
(1) 宣告陣列 (2) 配置記憶體給該陣列 一維陣列的宣告與配置記憶體格式： 一維陣列的宣告與配置記憶體 資料型態 陣列名稱[]; // 宣告一維陣列 陣列名稱 = new資料型態[個數]; // 配置記憶體給陣列

27 一維陣列的宣告及使用 (1/3) 下面的範例是一維陣列的宣告及記憶體配置： 執行完第1行後，編譯器會配置一塊記憶體給它：

28 一維陣列的宣告及使用 (2/3) 第2行是記憶體配置的動作： 陣列是屬於非基本資料型態，因此score儲存的是陣列實體的參考位址

29 一維陣列的宣告及使用 (3/3) 宣告一維陣列的另一種寫法： 一維陣列的宣告範例： 資料型態 陣列名稱[]=new資料型態[個數];
宣告陣列的同時便配置記憶體 資料型態 陣列名稱[]=new資料型態[個數]; 一維陣列的宣告範例： int score[]=new int[4]; 宣告一個整數陣列score，同時配置一塊可存放4個整數的連續記憶體空間 將陣列score化為圖形表示

30 陣列元素的表示方法 要存取陣列裡的元素，可以利用索引值（index） 陣列索引值的編號是由0開始
下圖為score陣列中元素的表示法及排列方式：

31 二維陣列的基本結構與特性 [二維陣列的基本結構]
方形的結構同樣叫做陣列，由於在空間上具有直 行 (column) 與橫列 (row) 兩個維度，所以也稱為 二維陣列。它的排列呈方塊狀，每一行的元素個 數均相等，而每一列的元素個數也都相同。

32 二維陣列的基本結構與特性 [二維陣列的基本特性]
同樣可以用一個共同的陣列名稱加上索引來代表 任何一個元素、也可以對所有元素進行隨機的存 取；唯一的差別就是陣列的排列方向多了一個， 而索引的寫法也從單一數字變成了一組數對。

33 二維陣列的宣告 二維陣列的宣告與配置記憶空間的格式： 如下面的範例： 以較為簡潔的方式來宣告陣列： 下面是二維陣列的宣告範例：
二維陣列的宣告格式 資料型態 陣列名稱[][]; 陣列名稱=new 資料型態[列的個數][行的個數]; 二維陣列的宣告格式 資料型態 陣列名稱[][]=new 資料型態[列的個數][行的個數];

34 三維陣列 三維陣列的宣告範例： 2×4×3的三維陣列可看成是由2個4×3的二維陣列所組成
也就是兩組4個橫列，3個直行的積木併在一起，組成一個立方體