4.1 一維陣列 4.2 for(:) 迴圈 4.3 動態陣列 4.4 二維陣列 4.5 非矩形陣列

Presentation on theme: "4.1 一維陣列 4.2 for(:) 迴圈 4.3 動態陣列 4.4 二維陣列 4.5 非矩形陣列"— Presentation transcript:

1 4.1 一維陣列 4.2 for(:) 迴圈 4.3 動態陣列 4.4 二維陣列 4.5 非矩形陣列
第 04 章 陣列與字串 處理到P59 4.1 一維陣列 4.2 for(:) 迴圈 4.3 動態陣列 4.4 二維陣列 4.5 非矩形陣列 4.6 排序與搜尋 4.7 String類別 4.8 StringTokenizer類別 4.9 實例 4.10 習題

2 　　當一個資料要儲存於記憶體中，需要使用一個變數來儲存，若有100筆資料，就需要使用100個變數。除了宣告變數外，程式中的敘述也變得很繁雜，維護上也很困難。若這些變數的資料型別相同，而且相關聯，我們可以利用陣列來取代變數，以減少程式在維護時的困難度。

3 4.1 一維陣列 　　陣列源自數學中的矩陣（Matrix）。它是一群具有相同資料型別的變數或物件之集合。陣列中每一個變數或物件稱為陣列元素（Array element），可簡稱為元素。陣列元素使用相同名稱（即陣列名稱），元素之間以索引值的不同來區別。 陣列中只有一組索引值時，稱為一維陣列，有兩組索引值時稱為二維陣列。下面為常用一維陣列宣告與建立。

4 一、一維陣列宣告 語法：int[ ] data; 或 int data[ ]; 說明：data為陣列名稱，int為資料型別。 二、一維陣列建立 語法：data = new int[5]; 或 data = new int[ ]{2, 4, 10, 6, 8}; 說明：  data陣列的第1個元素為data[0]，其索引值為0。第2個元素為data[1]，其索引值為1。 … 第n個元素為data[n-1]，n為陣列元素的個數。  使用 data.length，可以取得陣列的元素個數（或稱陣列的大小）。 三、一維陣列宣告與建立 語法1：int[ ] data = new int[5]; 或 int data[ ] = new int[5]; 語法2：int[ ] data = {2, 4, 10, 6, 8}; 或 int data[ ] = {2, 4, 10, 6, 8};

5

6

7

8 1. 行05：宣告並建立5個浮點數陣列。 2. 行08~11：由鍵盤輸入5個浮點數，然後存於陣列data中，如下圖： 3. 行12~15：顯示這5個陣列元素的內容，並將陣列元素的 值累加入變數sum之中。 4. 行16：顯示sum的內容。

9

10

11 1. 行03：宣告data為一維陣列。 2. 行04：建立data陣列，並給初始值，如下圖： 3. 行06：變數len由data.length取得data陣列的元素個數。 4. 行07~09：輸出5個陣列元素，每一個陣列元素以逗號「，」間隔。注意最後一個元素後面仍然有逗號。如何使最後一個陣列元素後面沒有逗號，請參閱J4_3_1.java程式碼。 5. 行11：令第一個陣列元素data[0]為最大數max_num。 6. 行12~15：由第2個陣列元素data[1]開始，一直到最後一個陣列元素data[len-1]止，分別與最大數max_num比較。結果若比max_num大，則更新最大數內容。

12 4.2 for(:) 迴圈 　　for(:) 迴圈類似第3章的for() 迴圈，而for(:) 迴圈程式比較精簡，它可應用於陣列或集合（本書沒有針對集合做介紹）。for(:) 迴圈每次會取出一個元素來進行迴圈處理。 語法：for (資料型別 變數名稱：陣列名稱) { 　　 敘述區段; 　 } 說明：  for(:) 迴圈不需「初值」、「條件式」和「增值運算式」等引數。  變數的資料型別必須與陣列的資料型別相同。  迴圈執行的次數由陣列元素或集合個數來決定。  若要中途離開迴圈，使用break; 敘述。

13

14

15

16

17 4.3 動態陣列 　　Java允許陣列的大小可以不用事先建立，而可以在執行過程中視需要再建立。若已建立過大小的陣列，還可以重新設定陣列大小。這種方式優點比較有彈性，未使用陣列時，不會佔用主記憶體空間，缺點是記憶空間不足無法預測，萬一執行中途，發生記憶空間不足時，若無特殊處理，程式就無法正常執行，而產生當機現象。動態陣列宣告如下所示：

18

19

20 1. 行09：data陣列大小由len變數來決定，這種建立陣列 大小，視需要可置於程式任何位置，並且可以改變其 大小值。
2. 行12~15：為了使最後一個陣列元素後面不要有逗號出現，加一個判斷。

21 4.4 二維陣列 二維陣列是具有兩組索引值的陣列。第1組索引值為列（Row），第2組索引值為行（Column）。二維陣列宣告與建立語法如下：
1. 語法1：int[ ][ ] salary; salary = new int[3][4]; 或 int[ ][ ] salary = new int[3][4]; 說明：salary為陣列名稱，它為3列4行二維整數陣列。如下表：

22 語法2：salary; int[ ][ ] salary = {{21000,5000,1200,0}, {45000,120,4500,0}, {0,0,0,0}}; 說明：宣告與建立salary陣列並給初始值。如下表：

23 1. 姓名（name）為字串，與其他資料型別不同，使用一維 字串陣列。
2. 底薪、加班費、勞健保費、實發金額…皆為整數，使用 二維整數陣列。 3. 實發金額與總計是由電腦計算而得，初始值設為0。

24

25

26 1. 行04：name存放員工姓名，使用一維字串陣列。
2. 行05：salary為二維整數陣列，並指定初始值。 3. 行06：i_max為第1維陣列大小。 4. 行07：j_max為第2維陣列大小。

27 4.5 非矩形陣列 　　在上一節中所介紹二維陣列是一種矩形陣列（Rectangular），每一列都有相同的行數。遇到每一列有不同的行數時，若以最大行數來設計，就會白白浪費掉記憶空間，例如個人的經歷，每個人差異性很大，使用矩形陣列就非常浪費記憶體。Java允許建立非矩形陣列，也就是說，每一列的行數可以視需要而不同。如下圖所示：

28 建立非矩形陣列的步驟如下： 1. 宣告一個二維陣列。 2. 利用此二維陣列，建立第一維陣列大小。 3. 再利用第一維陣列元素，建立第二維陣列大小。

29

30 1. 行03：宣告data為二維浮點數陣列。 2. 行04：陣列第一維大小為2。 3. 行05~06：第0列的第二維大小為1，第1列的第二維大小為3。 4. 行07~08：設定陣列元素的內容。

31

32

33 1. 行04：宣告，建立二維非矩形陣列，並給予初始值。 因為姓名與經歷皆為字串，可使用同一陣列。
2. 行06：data.length為第1維陣列大小。 3. 行07：data[i][0]，第0行存放姓名。 4. 行08：data[i].length為第2維陣列大小。

34 4.6 排序與搜尋 　　在日常生活中，最常需要處理的東西就是找資料，更新資料。尤其當資料量很大時，為了尋找資料常花費很多時間。如果我們將資料適當分類，同類資料依特定方式排列，將來要尋找時會節省很多時間，讓別人覺得你做事很有效率。 排序（Sorting）就是將多筆資料，以某一個項目（或稱欄位）當作鍵值（key value），安排資料在適當的位置。通常鍵值由小而大（遞增）或者由大而小（遞減）來排列資料。經此種方式排序，將來要搜尋（Searching）就會很快。

35 　　學校老師的點名冊或成績登記冊是依照學生的學號（鍵值）由小而大排序，老師要點名或者登錄成績會比較快。至於入學分發是依照考試成績總分（鍵值）由高而低排序，由分數最高先決定所要就讀的學校與系所。
排序的方法有很多種，各有其優缺點，在本章只介紹最簡單且易懂的氣泡排序法（Bubble Sort），其他方法請參考資料結構（Data Structure）書籍。至於搜尋方法也有很多種，在本章將介紹線性搜尋法（Linear Search）與二分搜尋法（Binary Search）。

36 氣泡排序法 　　 氣泡排序法（Bubble Sort）簡單易懂，但比較沒有效率，當資料量少時與其他方法比較，在排序的時間花費上沒有明顯的不同，但當資料量以千萬計時，排序所花費的時間就會有很明顯差別。 氣泡排序法是採用相鄰資料的鍵值做比較，使資料的鍵值由左而右排列時，能由鍵值較小者排前面，而鍵值較大者排後面。其進行的方式是由左而右進行兩兩比較，當左邊資料的鍵值比右邊資料的鍵值大時，即進行交換工作。在第一次循環時，鍵值最大的資料會移到最右邊；第二次循環時，鍵值第二大的資料，移到最右邊算過來的第二位；依此類推…。最後，鍵值最小的資料會排在最左邊。

37 1. 題目中的資料只有1個欄位，因此資料的鍵值就是這個欄位。
2. 本例利用氣泡排序法。 3. 排序後的結果10, 12, 14, 16, 18。 4. 為了看出每一循環的處理情形，都有輸出結果，實際處理時可省略。 5. 如果資料超出兩個欄位，請參閱後面範例。

38

39

40 1. 行03：建立a陣列，並給初始值。 2. 行05~09：輸出排序前資料排列情形。 3. 行10~22：進行氣泡排序法。 4. 行17~21：輸出每一循環處理情形。

41 線性搜尋法 　　線性搜尋法（Linear Search）或稱循序搜尋法（Sequential Search），依所要搜尋資料的鍵值，由最前面資料逐筆比較，若有鍵值相同，表示已找到資料。若全部比較完畢，而沒有找到相同鍵值時，表示要搜尋資料不存在。因此當有n筆資料要搜尋時，平均要比較n/2次才能找到資料。

42 1. 先存放在陣列中的5筆資料，事先並沒有排序。
2. 資料有2個欄位，在此用兩個陣列表示。 3. 利用線性搜尋法找資料。

43

44

45 1. 行11：num = -1表示預設資料未找到。 2. 行12~17：進行線性搜尋法。 3. 行14：找到符合資料，num存資料在陣列中的索引值。 4. 行18~23：輸出是否找到資料。

46 二分搜尋法 　　前面的線性搜尋法是一種比較沒有效率的搜尋法，現在要介紹的是一種比較有效率的搜尋法，稱之為二分搜尋法（Binary Search）。此方法需先將資料依鍵值做排序，若未經排序的資料無法應用此搜尋法。 　　如果有n筆資料，線性搜尋法平均需要 n/2 次比較才能找到資料。而二分搜尋法，最多需要 log2 n + 1 的比較次數，就可以找到資料。如有1024筆料，則最多需11次的比較，便能找到所需資料。 　　二次搜尋法是將n筆資料，依鍵值由小而大排序儲存於陣列中（當然也可以由大而小排序）。然後從已排序好的n筆資料之中間（即第n/2筆）開始搜尋比較。如果比較結果相同，表示已找到；若不同，則再從比搜尋值大或小的資料中間找起（即第n/4筆或第3/4 n筆）…以此類推。

47 1. 存放在陣列中的5筆資料，先使用氣泡排序法由小而大先排序。
2. 資料有2個欄位，在此用兩個陣列表示。 3. 利用二分搜尋法找資料。 4. 在搜尋過程中，顯示搜尋的方向。

48

49

50

51

52

53 1. 行09~19：利用氣泡排序法進行排序。 2. 行26~44：進行二分搜尋法。 3. 行31~34：找到符合資料，num存資料在陣列中的索引值。 4. 行35~38：num = -1表示資料未找到。 5. 行39：往索引值較小方向尋找。 6. 行41：往索引值較大方向尋找。 7. 行45~50：輸出是否找到資料。

54 4.7 String類別 　　在字串處理在程式設計中常被使用，在此介紹一些字串常用方法，下面的str、str1、str2資料型別皆為String。 一、字串長度 　語法：int str.length() 　說明：傳回str字串的長度。 　[簡例] "Book是書本".length() → 7

55 二、比較字串 1. 語法：Boolean str1.equals(str2) 　說明：str1與str2兩個字串完全相同，傳回true，否則傳回false。 　[簡例] "Book". equals(" BOOK") → false 2. 語法：Boolean str1.equalsIgnoreCase(str2) 　說明：比較str1與str2字串，大寫與小寫英文字母視為相同。 　[簡例] "Book".equalsIgnoreCase("BOOK") → true 3. 語法：str1.compareTo(str2) 　說明：str1與str2做比較，傳回Unicode字元編碼的差值。 　　 str1<str2 傳回負值，str1=str2 傳回0，str1>str2 傳回正值。 　[簡例] “Book”.compareTo(“BOOK”) → “Book” 與 “BOOK” 的第一個字母皆為B。再比第二字母， 分別為 “o” 與 “O”，而 “o” 的Unicode字元編碼比 “O” 大32。 4. 語法：str1. compareToIgnoreCase(str2) 　說明：大小寫英文字母視為相同。 　[簡例] "Book".compareToIgnoreCase("BOOK") → 0

56 三、取得子字串 1. 語法：String str.substring(int n1) 　說明：由str字串的n1索引位置開始，取到字串的結束，索引 由0開始。 　[簡例] "good boy".substring(3) → "d boy" 2. 語法：String str.substring(int n1, int n2) 　說明：由str字串的n1索引位置開始取到n2-1索引位置的字串。 　[簡例] "good boy".substring(2, 6) → "od b"

57 四、搜尋字串 　語法：int str1.indexOf(String str2) 　說明：傳回str2字串在str1字串內第一次出現的索引值位置，若 搜尋不到，則沒有傳回-1。 　[簡例] "pen and pencil".indexOf("and") → 4 五、取代字串 　語法：str.replace(String str1, String str2) 　說明：將str字串內的str1子字串全部由str2子字串取代。 　[簡例] "big bird and small bird".replace("bird", "dog") → "big dog and small dog"

58 六、大小寫英文字母 　語法1：String str.toLowerCase() 　說明：將str字串內所有英文字母轉為小寫字母。 　[簡例] "Book".toLowerCase() → "book" 　語法2：String str.toUpperCase() 　說明：將str字串內所有英文字母轉為大寫字母。 　[簡例] "Book".toUpperCase() → "BOOK"

59 七、字串轉為數值 　語法：int Integer.parseInt(String str) long Long.parseLong(String str) float Float.parseFloat(String str) double Double.parseDouble(String str) 　說明：將str字串內的文數字分別轉換成整數、長整數、單精確 浮點數、倍精確浮點數。 　[簡例] Double.parseDouble("25") → 25.0 八、其它資料型別轉為字串資料 　語法：String String.valueOf(其它型別資料或變數) 　說明：括弧內的參數可為任何型別的資料或變數，而傳回值為 字串資料。 　[簡例] String.valueOf(2600)　→　傳回字串 ”2600”

60

61

62 1. 行11~18：統計a, e, i, o, u出現次數。 2. 行12：由句子中取出一個字元。 3. 行14：將英文字母轉為小寫。

63 4.8 StringTokenizer類別 　 Java可以將一個長字串分解成多個子字串（token），但要在子字串之間用特定「分解符號」（delimiter）。一般常用分解符號有空格字元「 」與逗號「,」。StringTokenizer類別提供此方面方法，StringTokenizer類別在java.util套件中，因此程式碼須先載入此套件。下面的str資料型別為String。 　　 　　import java.util.*;

64 有關StringTokenizer類別的宣告與提供常用方法如下：
1. StringTokenizer(String str) 建構子 以空格字元為分解符號，將str字串分解為子字串後，傳入StringTokenizer物件中。(有關類別與建構子的說明，請參閱第六章) 2. StringTokenizer(String str, String delim) 建構子 以delim字串為分解符號，將str字串分解為子字串後，傳入StringTokenizer物件中。delim字串可以為任何字元。 3. boolean str.hasMoreTokens() 判斷str字串後面是否還有token（子字串），若有傳回true，否則傳回false。 4. String str.nextToken() 傳回str字串的token子字串，並指向下一個 token。 5. int str.countTokens() 計算str字串還剩餘多少個token子字串尚未傳回。

65

66

67 1. 行05：將str1字串以逗號為分解字元，分解為三個子字串，然後傳回給StringTokenizer類別物件str2。
2. 行09：str2尚未傳回子字串，因此目前剩餘3個子字串（token）。 3. 行10~12：先後傳回品名、單價與數量等資料。

68 4.9 實例

69

70

71

72 1. 行05：prob陣列為題目。 2. 行06：right陣列為正確答案。 3. 行09~21：進行測驗，並判斷答案是否正確，若錯 誤給正確答案。 4. 行22~29：依答對題數給不同評語。