| |
7-4 陣列線性搜尋
內容：
7-4-1 線性搜尋演算法
從陣列內尋找某一筆資料，最簡單的方法是線性搜尋法；演算法是由陣列的起頭開始比較尋找（比較內容），如搜尋到則立即停止，否則繼續往下一個元素尋找，一直到陣列結束為止，如圖 7-5 所示。線性演算法所處理的陣列不需要特殊處理（如由大到小排列），最佳狀況是第一筆資料就找到；最差狀態是最後一筆資料才搜尋到。
圖 7-9 線性搜尋法的運作
7-4-2 範例研討：實現線性搜尋法
吾人利用 num[] 陣列儲存 10 個整數，輸入一個整數來查詢是否在 num 內，再顯示其執行結果，如下：
|
num[] = 20 13 45 24 42 34 22 89 19 70
請輸入一個數值 =>17
17
不在 num
陣列內
num[] = 20 13 45 24 42 34 22 89 19 70
請輸入一個數值 =>24
24
找到了 |
（B）程式範例：
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16 |
import
java.util.Scanner;
public
class Ex7_6 {
public static void main(String args[]) {
Scanner keyin = new Scanner(System.in);
int value, flag=0, i;
int[] num = {20, 13, 45, 24, 42, 34, 22, 89, 19, 70};
System.out.printf("num[] = ");
for (int k=0; k<10; k++)
System.out.printf("%d ", num[k]);
System.out.printf("\n");
System.out.printf("請輸入一個數值
=>");
value = keyin.nextInt();
i=0;
while (i < 10) {
if (value == num[i]){
flag = 1;
break;
}
i++;
}
if(flag == 1)
System.out.printf("num[%d] = %d
找到了\n",
i, value);
else
System.out.printf("%d
不在
num
陣列內",
value);
}
} |
7-4-3 範例研討：大樂透電腦選號
（A）程式功能：Ex7_7.java
請製作大樂透的電腦選號系統，系統能自動選出 6 個由 01 ~ 49 號碼，但這六個號碼都不可以重複。期望操作介面如下：
（B）製作技巧研討：
編寫一個產生 6 個隨機亂數的程式並不困難，但如果要這 6 個亂數不重複的話，不加點小技巧是不行的。首先準備一個 6 個元素的陣列（int[] num = new int[6];），每次隨機選出號碼後，立即比較陣列內是否有重複號碼（之前所取的），如果沒有則加入該陣列內。第 1 次選出號碼（i=0），陣列還是空的（j=0），則幾乎不用比對；如已選出 3 個號碼，下一個選出號碼就必須比對之前 3 個號碼是否有重複，依此類推。最後再印出以選出的 6 個號碼。
(C)程式範例：
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 |
//Ex7_7.java
import java.lang.Math;
public class Ex7_7 {
public static void main(String args[]) {
int value, flag; //
隨機選取號碼
int[] num = new int[6]; //
儲存選取號碼
int i=0;
while (i < 6) {
flag=0;
value = 1 + (int)(Math.random()*46);
for (int j=0; j<i; j++) { //
檢視已選出的號碼
if (value == num[j]) { //
是否重複
flag = 1; //
重複則放棄重來
break;
}
}
if (flag == 0) {
num[i] = value; //
沒重複則填入陣列
i = i+1;
}
}
System.out.printf("幸運號碼是:
");
for (i=0; i<6; i++)
System.out.printf("%d ", num[i]);
System.out.printf("\n");
}
} |
（D）程式重點分析
-
第 9~16
行：『while{i<6} {…}』。選出 6 個不重複號碼。
-
第 11~17
行：『for(int j=0; j<i; j++) { if(value == num[j]) …}』。線性搜尋敘述句。
-
第 13~14
行：『if(value == num[j]) continue;』。如發現號碼重複，則放棄重來。
7-4-4 自我挑戰：最高與最低成績者
（A）程式功能：PM7_6.java
數學老師利用一個二維陣列儲存某一班級學生的成績，score[][] = {{411101, 70}, {411102, 80}, {411103, 75}, {411104, 90}, {411105, 85}, {4111106, 65}, {411107, 83}, {411108, 78}}。請編寫一程式列印出該班成績最高與最低分數與姓名，期望操作介面如下：
|
D:\Java2_book\chap3>javac PM7_6.java
D:\Java2_book\chap3>java PM7_6
最高者 411104
成績= 90
最低者 411106
成績= 65
|
（B）製作技巧提示：
二維陣列（score[][]）的每行（score[i], i =0, 1, 2 .., 7）紀錄一筆學生資料，第 0 列（score[i][0]）儲存學號、第 1 列（score[i][1]）儲存數學成績。吾人可利用兩只一維陣列（max[] 與 min[]）儲存最高成績與最低成績，其中第 0 列（如max[0]）儲存學號、第 1 列（如max[1]）存放成績。圖 7-6 為搜尋運作程序，起先將最高成績的陣列設定為 0（max = {0, 0}）；最低成績設定成超過成績界線（min = {0, 999}），再依序比較每位學生成績，如果高於 max，則該紀錄複製到 max 陣列內；如果低於 min，則複製到 min 上。如此由第 0 筆到最後一筆搜尋之後，max 與 min 陣列分別得到最高與最低成績的紀錄。虛擬碼提示如下：
圖 7-11 最高與最低成績搜尋
|
01
02
03
04
05
06
07
08
09
10 |
宣告成績儲存陣列並給初值（int
score[][]= {{411101, 70}, …}）；
宣告最高成績陣列（int
max[] = {0, 0}）；
宣告最低成績陣列（int
min[] = {0, 9999}）；
搜尋最高與最低成績者：
for(int i=0; i<score.length; i++) {
if(score[i][1] > max[1])
max = score[i];
if(score[i][1] < min[1])
min = score[i];
} |
7-4-5 自我挑戰：成績查詢系統
（A）程式功能：PM7_7.java
數學老師利用一個二維陣列儲存某一班級學生的成績，score[][] = {{411101, 70}, {411102, 80}, {411103, 75}, {411104, 90}, {411105, 85}, {4111106, 65}, {411107, 83}, {411108, 78}}。請編寫程式可允許輸入學生學號，並輸出該學生的數學成績，期望操作介面如下：
|
D:\Java2_book\chap3>java PM3_2
==
成績查詢系統 ==
請輸入學生學號 =>4111120
沒有學號 = 4111120
的資料
D:\Java2_book\chap3>java PM3_2
==
成績查詢系統 ==
請輸入學生學號 =>411103
學號 = 411103,
成績= 75 |
（B）製作技巧提示：
利用輸入學號作為查詢關鍵，由陣列的起頭到結尾依序比較第 0 個欄位（score[i][0], i=0, 1, 2, …, score.length-1），如果相同則印出第 1 個欄位的內容（score[i][1]，成績欄位）；虛擬碼提示如下：
|
01
02
03
04
05
06
07
08
09
10
11
12
13 |
宣告輸入物件（Scanner）；
宣告成績儲存陣列並給初值（int
score[][]= {{411101, 70}, …}）；
宣告旗號並給予初值（int
flag=0）；
讀入查詢學號（num）；
搜尋查詢成績：
for(int i=0; i<score.length; i++) {
if(score[i][0] == num){
輸出顯示學號與成績；
flag = 1;
}
}
if(flag ==0)
輸出顯示沒有資料； |
|
翻轉工作室：粘添壽
Java 程式設計(一) 含程式邏輯
翻轉電子書系列：
|
