Java語言程序設計-基礎篇-中文ppt-第六章

《Java語言程序設計-基礎篇-中文ppt-第六章》由會員分享，可在線閱讀，更多相關《Java語言程序設計-基礎篇-中文ppt-第六章（104頁珍藏版）》請在裝配圖網上搜索。

1、第6章 一維數(shù)組 開放問題讀取一百數(shù)字，計算它們的平均值，然后找出有多少個數(shù)大于平均值。 解決方案 Run 學習目標F描述數(shù)組在程序設計中的必要性 （第6.1節(jié)）。F聲明數(shù)組引用變量、創(chuàng)建數(shù)組 （第6.2.1-6.2.2節(jié)）。F初始化數(shù)組中的值 （第6.2.3節(jié)）。F使用下標變量訪問數(shù)組元素（第6.2.4節(jié)）。F利用一條數(shù)組初始化語法聲明、創(chuàng)建和初始化數(shù)組 （第6.2.5節(jié)）。F編寫程序實現(xiàn)常用的數(shù)組操作（顯示數(shù)組、對所有元素求和、求最大和最小元素、隨意打亂、移動元素）（第6.2.6節(jié) ）。F使用for - each循環(huán)簡化程序設計（第6.2.7）。F在LottoNumbers和DeckOfC

2、ards問題中應用數(shù)組 （第6.3-6.4節(jié)）。F將一個數(shù)組的內容復制到另一個數(shù)組 （第6.5節(jié)）。 F開發(fā)和調用帶數(shù)組參數(shù)和返回值的方法（第6.66.7節(jié)）。F定義帶變長參數(shù)列表的方法（第6.8節(jié)）。F使用線性查找算法（第6 .9.1節(jié)）或二分查找算法（第6. 9.2節(jié)）查找數(shù)組的元素。F使用選擇排序法對數(shù)組排序（第6.10.1節(jié)）。F使用插入排序算法使排序數(shù)組 （第6.10.2節(jié)）。F使用 Arrays 類中的方法（第6.11節(jié)）。 介紹數(shù)組數(shù)組是一種數(shù)據(jù)結構，它表示一組相同類型的數(shù)據(jù)。 5.6 4.5 3.3 13.2 4 34.33 34 45.45 99.993 11123 doub

3、le myList = new double10; myList reference myList0 myList1 myList2 myList3 myList4 myList5 myList6 myList7 myList8 myList9 元素值 數(shù)組引用變量 下標5處的 數(shù)組元素 聲明數(shù)組變量Fdatatype arrayRefVar;舉例： double myList;Fdatatype arrayRefVar; / 這種風格是允許的,但不推薦使用舉例： double myList; 創(chuàng)建數(shù)組arrayRefVar = new datatypearraySize;舉例：myList

4、= new double10;myList0 引用數(shù)組中的第一個元素。myList9 引用數(shù)組中的最后一個元素。 一步完成聲明和創(chuàng)建Fdatatype arrayRefVar = new datatypearraySize; double myList = new double10;Fdatatype arrayRefVar = new datatypearraySize;double myList = new double10; 數(shù)組的大小一旦數(shù)組被創(chuàng)建就不能再修改它的大小?？梢酝ㄟ^使用arrayRefVar.length來求得數(shù)組的大小。舉例：myList.length returns 1

5、0 默認值當數(shù)組被創(chuàng)建后，它的元素被賦予默認值 數(shù)值型基本數(shù)據(jù)類型的默認值是0， char 類型的默認值為u0000 ，而 boolean 類型默認值為false。 下標變量數(shù)組元素可以通過下標來訪問。數(shù)組下標是基于0的，就是說它從0開始到arrayRefVar.length-1結束。在圖6.1中的例子中, 數(shù)組myList 包含10個double值而下標是從0到9。數(shù)組中的每個元素都可以使用下面一般被稱為下標變量的語法表示：arrayRefVarindex; 使用下標變量創(chuàng)建數(shù)組后，可以采用和一般變量相同的方法使用下標變量。例如：下面的代碼是將myList0和myList1的值相加賦給myL

6、ist2。myList2 = myList0 + myList1; 數(shù)組初始化語法F一步完成數(shù)組的聲明、創(chuàng)建、初始化:double myList = 1.9, 2.9, 3.4, 3.5;這種縮略語法必須用在一條語句中。 使用縮略符號聲明、創(chuàng)建、初始化數(shù)組double myList = 1.9, 2.9, 3.4, 3.5;這里的縮略符號相當于以下面的語句：double myList = new double4;myList0 = 1.9;myList1 = 2.9;myList2 = 3.4;myList3 = 3.5; 注意 使用縮略符號時，你必須將聲明、創(chuàng)建和初始化數(shù)組都放在一條語句中。

7、將它們分開會引起語法錯誤。例如：下面的語句就是錯誤的:double myList;myList = 1.9, 2.9, 3.4, 3.5; 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 聲明數(shù)組變量value，創(chuàng)建一個數(shù)組并將它的引用賦值給values動 畫 跟蹤數(shù)組程序public class Test public

8、 static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i 變?yōu)?1動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + val

9、ues4; i （=1）小于5動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這一行被執(zhí)行后，values1是1 After the first iteration 0 1 2 3 4 0 1 0 0 0 動 畫 跟蹤數(shù)組程序public class Test public static void main(St

10、ring args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i+后，i 變?yōu)?2動 畫 After the first iteration 0 1 2 3 4 0 1 0 0 0 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valu

11、esi-1; values0 = values1 + values4; i（= 2）小于5動 畫 After the first iteration 0 1 2 3 4 0 1 0 0 0 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這一行被執(zhí)行之后，values2 為3（2 + 1） After the secon

12、d iteration 0 1 2 3 4 0 1 3 0 0 動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這之后，i就 變?yōu)?3. After the second iteration 0 1 2 3 4 0 1 3 0 0 動 畫 跟蹤數(shù)組程序public class Test public static

13、 void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i（=3）依舊小于5 After the second iteration 0 1 2 3 4 0 1 3 0 0 動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) val

14、uesi = i + valuesi-1; values0 = values1 + values4; 這一行之后，values3變成 6（3 + 3） After the third iteration 0 1 2 3 4 0 1 3 6 0 動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這之后，i變成4 Af

15、ter the third iteration 0 1 2 3 4 0 1 3 6 0 動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i（=4） 仍舊小于5 After the third iteration 0 1 2 3 4 0 1 3 6 0 動 畫 跟蹤數(shù)組程序public class Test pub

16、lic static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這之后，values4變成 10（4 + 6） After the fourth iteration 0 1 2 3 4 0 1 3 6 10 動 畫 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for

17、(int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i+后，i 變成5動 畫 After the fourth iteration 0 1 2 3 4 0 1 3 6 10 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; i

18、 ( =5） 5 為假。退出循環(huán)動 畫 After the fourth iteration 0 1 2 3 4 0 1 3 6 10 跟蹤數(shù)組程序public class Test public static void main(String args) int values = new int5; for (int i = 1; i 5; i+) valuesi = i + valuesi-1; values0 = values1 + values4; 這行之后，values0 為11 (1 + 10） 0 1 2 3 4 11 1 3 6 10 動 畫 處理數(shù)組下面是一些示例：F（使用輸

19、入值初始化數(shù)組）F（使用隨機數(shù)初始化數(shù)組）F（打印數(shù)組）F（對所有元素求和）F（找出最大元素）F（找出最大元素的最小下標值） F（隨意打亂） 1.（移動元素） 使用輸入值初始化數(shù)組java.util.Scanner input = new java.util.Scanner(System.in);System.out.print(Enter + myList.length + values: );for (int i = 0; i myList.length; i+) myListi = input.nextDouble(); 使用隨機數(shù)初始化數(shù)組for (int i = 0; i myLis

20、t.length; i+) myListi = Math.random() * 100; 打印數(shù)組for (int i = 0; i myList.length; i+) System.out.print(myListi + ); 對所有元素求和double total = 0;for (int i = 0; i myList.length; i+) total += myListi; 找出最大的元素double max = myList0;for (int i = 1; i max) max = myListi; 隨意打亂 for (int i = 0; i myList.length; i

21、+) / Generate an index j randomly int index = (int)(Math.random() * myList.length); / Swap myListi with myListj double temp = myListi; myListi = myListindex; myListindex = temp; myList 0 1 . . . index A random index i swap 移動元素 double temp = myList0; / Retain the first element / Shift elements left

22、for (int i = 1; i myList.length; i+) myListi - 1 = myListi; / Move the first element to fill in the last position myListmyList.length - 1 = temp; myList 增強型for循環(huán)（for - each循環(huán)）JDK 1.5引入了一個新的for循環(huán)，它可以讓你不使用下標變量就可以順序地遍歷整個數(shù)組。 例如：下面的代碼顯示數(shù)組myList中的所有元素： for (double value: myList) System.out.println(value);

23、 一般來講，這個語法是 for (elementType value: arrayRefVar) / Process the value 當需要以其它順序遍歷該數(shù)組或改變數(shù)組中的元素時，你還是必須使用下標變量。 問題：樂透號碼假設你要玩選10樂透游戲，每張籌碼有10個范圍從1到99的獨特的數(shù)字。假設你買了一堆籌碼，希望它們涵蓋1到99的所有數(shù)字。編寫一個程序，從一個文件中讀取籌碼上的數(shù)字，并檢查是否涵蓋所有的數(shù)字。 假設這個文件的最后一個數(shù)字是0。 問題：一副牌編寫一個程序，它隨機地從一副52張牌中選擇4張。所有的牌可以使用一個名為deck的數(shù)組表示，這個數(shù)組用從0到51的初始值來填充，如下所

24、示：int deck = new int52;/ Initialize cardsfor (int i = 0; i deck.length; i+) decki = i; 問題：一副牌（續(xù)） 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51 13 Spades (?) 13 Hearts (?) 13 Diamonds (?) 13 Clubs (?) 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51 deck 0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51

25、Random shuffle 6 48 11 24 . . . . . . . . . . . . . . . . deck 0 1 2 3 4 5 . . . 25 26 . . . 38 39 . . . 51 Card number 6 is 7 of Spades Card number 48 is 10 of Clubs Card number 11 is Queen of Spades Card number 24 is Queen of Hearts 問題:一副牌這個問題為今后構建一個更有趣和更具現(xiàn)實意義的應用程序打一個基礎：參見練習題25.9。 復制數(shù)組在程序中，你經常需要復制

26、一個數(shù)組或數(shù)組的一部分。在這種情況下，你可能會嘗試使用賦值語句（=），如下所示： list2 = list1; list1 的內容 list1 list2 的內容 list2 賦值語句 list2 = list1;之前 list1 的內容 list1 list2 的內容 list2 賦值語句 list2 = list1;之后 Garbage 復制數(shù)組使用循環(huán)：int sourceArray = 2, 3, 1, 5, 10;int targetArray = new intsourceArray.length;for (int i = 0; i sourceArrays.length; i+)

27、 targetArrayi = sourceArrayi; arraycopy工具arraycopy(sourceArray, src_pos, targetArray, tar_pos, length);例如：System.arraycopy(sourceArray, 0, targetArray, 0, sourceArray.length); 傳遞數(shù)組給方法public static void printArray(int array) for (int i = 0; i array.length; i+) System.out.print(arrayi + ); Invoke the

28、methodint list = 3, 1, 2, 6, 4, 2;printArray(list);Invoke the method printArray(new int3, 1, 2, 6, 4, 2);匿名數(shù)組 匿名數(shù)組語句printArray(new int3, 1, 2, 6, 4, 2); 使用下面的語法創(chuàng)建一個數(shù)組：new dataTypeliteral0, literal1, ., literalk;這里沒有數(shù)組的顯式引用變量。這樣的數(shù)組被稱為匿名數(shù)組。 值傳遞Java使用值傳遞的方法傳遞實參給方法。傳遞基本數(shù)據(jù)類型變量的值與傳遞數(shù)組值會有很大不同。F 對于基本數(shù)據(jù)類型參數(shù)，

29、傳遞的是實參的值。在方法中改變局部參數(shù)的值并不影響方法之外變量的值。F 對于數(shù)組類型參數(shù)，參數(shù)值是數(shù)組的引用，傳遞給方法的是這個引用。方法體中數(shù)組發(fā)生的改變，將會影響到作為參數(shù)傳給方法的原始數(shù)組。 public class Test public static void main(String args) int x = 1; / x represents an int value int y = new int10; / y represents an array of int values m(x, y); / Invoke m with arguments x and y System.

30、out.println(x is + x); System.out.println(y0 is + y0); public static void m(int number, int numbers) number = 1001; / Assign a new value to number numbers0 = 5555; / Assign a new value to numbers0 簡單的例子 調用棧 當調用m(x,y)時，x和y的值被傳遞給 number 和 numbers。因為y包含的是數(shù)組的引用值，所以，numbers現(xiàn)在包含的是指向同一數(shù)組的相同引用值。 Space requi

31、red for the main method int y: int x: 1 棧 Space required for method m int numbers: int number: 1 reference 0 0 0 The arrays are stored in a heap. 堆 reference Array of ten int values is 調用棧當調用m(x,y)時，x和y的值被傳遞給 number 和 numbers。因為y包含的是數(shù)組的引用值，所以，numbers現(xiàn)在包含的是指向同一數(shù)組的相同引用值。 Space required for the main me

32、thod int y: int x: 1 Stack Space required for method m int numbers: int number: 1001 reference 5555 0 0 The arrays are stored in a heap. Heap reference Array of ten int values is stored here 堆 Space required for the main method int y: int x: 1 reference The arrays are stored in a heap. Heap 5555 0 0

33、 JVM將數(shù)組存儲在一個被稱作堆的內存區(qū)域，堆是用來動態(tài)分配內存的，在堆中的內存塊可以按任意順序分配和釋放。 傳遞數(shù)組參數(shù)F目標：演示傳遞基本數(shù)據(jù)類型變量和傳遞數(shù)組變量的不同之處。 舉例（續(xù)） Invoke swap(int n1, int n2). The primitive type values in a0 and a1 are passed to the swap method. Space required for the main method int a Stack Space required for the swap method n2: 2 n1: 1 reference

34、a1: 2 a0: 1 The arrays are stored in a heap. Invoke swapFirstTwoInArray(int array). The reference value in a is passed to the swapFirstTwoInArray method. Heap Space required for the main method int a Stack Space required for the swapFirstTwoInArray method int array reference reference 從方法中返回數(shù)組public

35、 static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 跟蹤reverse方法public static int reverse(int list) int result = new intli

36、st.length; for (int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = 1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0聲明result 并創(chuàng)建數(shù)組 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for

37、(int i = 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0 i = 0 而 j = 5 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i =

38、 0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 0 i (= 0) 小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = re

39、sult.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1 i = 0 而 j = 5 將list0賦值給result5 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i =

40、0, j = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1這之后，i 變?yōu)? 而 j 變?yōu)?4 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j

41、 = result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 0 1 i（=1）小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.len

42、gth - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1 i = 1 而 j = 4 將list1賦值給給 result4 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j =

43、 result.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1這之后，i 變成2 而 j 變?yōu)?3 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = res

44、ult.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 0 2 1 i (=2) 依舊小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.lengt

45、h - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1 i = 2 而 j = 3 將listi賦值給 resultj 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = re

46、sult.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1這之后，i 變成 3 而 j 變成 2 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = resul

47、t.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 0 3 2 1 i（=3）依舊小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length -

48、1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1 i = 3 而 j = 2 將listi賦值給 resultj 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result

49、.length - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1這之后，i 變成 4 而 j 變成 1 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.le

50、ngth - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 0 4 3 2 1 i（=4）依舊小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i

51、 list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1 i = 4 而 j = 1 將listi賦值給 resultj 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.len

52、gth - 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1這之后，i變成5 而 j 變成 0 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length -

53、 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 60 5 4 3 2 1 i (=5) 依舊小于6 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i lis

54、t.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1 i = 5 而 j = 0 將listi賦值給resultj 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length -

55、 1; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1這之后， i 變成 6 而j 變成 -1 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1

56、; i list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1 i（=6） 6 為假，所以退出循環(huán) 動 畫 跟蹤reverse方法（續(xù)）public static int reverse(int list) int result = new intlist.length; for (int i = 0, j = result.length - 1; i

57、list.length; i+, j-) resultj = listi; return result; int list1 = new int1, 2, 3, 4, 5, 6;int list2 = reverse(list1);listresult 1 2 3 4 5 66 5 4 3 2 1返回 resultlist2 動 畫 問題：統(tǒng)計每個字母出現(xiàn)的次數(shù)F隨機生成100個小寫字母，將它們賦值給一個字符數(shù)組。F統(tǒng)計數(shù)組中的每個字母的出現(xiàn)計數(shù)。 (a) Executing createArray in Line 6 Space required for the main method ch

58、ar chars: ref Heap Array of 100 characters Space required for the createArray method char chars: ref (b) After exiting createArray in Line 6 Space required for the main method char chars: ref Heap Array of 100 characters Stack Stack 數(shù)組的搜索 public class LinearSearch /* The method for finding a key in

59、the list */ public static int linearSearch(int list, int key) for (int i = 0; i list.length; i+) if (key = listi) return i; return -1; list key 將key 和 listi for i = 0, 1, 進行比較 0 1 2 搜索就是在數(shù)組中尋找特定元素的過程；例如：判斷某一特定分數(shù)是否包含在成績列表中。搜索是計算機程序設計中一種經常要完成的任務。有許多關于搜索的算法和數(shù)據(jù)結構。在本節(jié)中，討論兩種常用的方法：線性查找法和二分查找法。 線性查找法線性查找法就是

60、將要查找的關鍵元素key順序地與數(shù)組list中的每一個元素進行比較。這個方法一直繼續(xù)直到在列表中找到與關鍵字匹配的元素，還有一種情況就是忙乎了半天，在list中也沒找到匹配的元素。如果匹配成功，線性查找法返回與數(shù)組中與關鍵字匹配的元素的下標。 如果匹配不成功，則返回 -1。 線性查找法的動畫6 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 86 4 1 9 7 3 2 83333 33 動 畫Key List 從想法到解決方案/* The method for finding a key in t

61、he list */public static int linearSearch(int list, int key) for (int i = 0; i list.length; i+) if (key = listi) return i; return -1;int list = 1, 4, 4, 2, 5, -3, 6, 2; int i = linearSearch(list, 4); / returns 1int j = linearSearch(list, -4); / returns -1int k = linearSearch(list, -3); / returns 5跟蹤這

62、個方法 二分查找法使用二分查找法的前提是數(shù)組中的元素必須已經被排好序。為不時一般性，假設數(shù)組以升序排序。例如： 2 4 7 10 11 45 50 59 60 66 69 70 79二分查找法首先將關鍵字key與數(shù)組中間的元素進行比較。 二分查找法（續(xù)）F如果關鍵字key小于中間元素，你只需要在數(shù)組的前半部分的元素中繼續(xù)查找關鍵字。F如果關鍵字key等于中間元素，這個查找結束。F如果關鍵字key大于中間元素，你只需要在數(shù)組的后半部分的元素中繼續(xù)查找關鍵字?？紤]下面三種情況： 二分查找法1 2 3 4 6 7 8 91 2 3 4 6 7 8 91 2 3 4 6 7 8 9888Key Lis

63、t動 畫 二分查找法（續(xù)） 0 1 2 3 4 5 6 7 8 9 10 11 12 2 4 7 10 11 45 50 59 60 66 69 70 79 key 是 11 key 7 key = 11 high low mid high low list 3 4 5 mid high low list 2 4 7 10 11 45 10 11 45 Binary Search, cont. 0 1 2 3 4 5 6 7 8 9 10 11 12 2 4 7 10 11 45 50 59 60 66 69 70 79 key 是 54 key 50 list mid 0 1 2 3 4 5

64、 6 7 8 9 10 11 12 key 66 key = low) int mid = (low + high) / 2; if (key listmid) high = mid - 1; else if (key = listmid) return mid; else low = mid + 1; return -1 - low; 方法Arrays.binarySearch由于二分查找法經常在程序設計中用到，所以Java在類java.util.Arrays提供了方法binarySearch的幾個重載方法，它們可以在由 int、double、char、short、long,和 float

65、構成數(shù)組中搜索關鍵字。例如：下面的代碼在包含數(shù)字的數(shù)組和包含字符的數(shù)組中查找關鍵字。int list = 2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79;System.out.println(Index is + java.util.Arrays.binarySearch(list, 11); char chars = a, c, g, x, y, z;System.out.println(Index is + java.util.Arrays.binarySearch(chars, t); 為使binarySearch正常運轉，必須使數(shù)組按升序

66、排列。 返回 4返回 4 （返回點是3，所以返回 -3-1) 數(shù)組的排序像查找一樣，排序在計算機程序設計中也是一個常用任務。已經開發(fā)出許多不同的排序算法。 本節(jié)將介紹兩種簡單的、直觀的排序算法：選擇排序法和插入排序法。 選擇排序就是找到數(shù)列中的最小數(shù)并將它放在最前面。 然后找到剩余數(shù)中最小的并將它放到最前面第二位，直到數(shù)列中只包含一個數(shù)字。 圖6.17顯示如何使用選擇排序法對隊列 2、9、5、4、8、1、6 進行排序。選擇排序法 2 9 5 4 8 1 6 swap Select 1 (the smallest) and swap it with 2 (the first) in the list 1 9 5 4 8 2 6 swap The number 1 is now in the correct position and thus no longer needs to be considered. 1 2 5 4 8 9 6 swap 1 2 4 5 8 9 6 Select 2 (the smallest) and swap it with 9 (the first) in