|
4-3 有序陣列結構
內容：
4-3-1 有序陣列結構簡介
圖 4-6 為有序陣列結構的示意圖，資料在陣列中存放有依照某一個關鍵字(或稱主鍵)的大小排列。這種排列方式的搜尋速度會比無序排列快許多。如果資料沒有依照大小排序，搜尋某一筆資料必須採用『線性搜尋法』，也就是由資料最前頭，一筆接一筆的比對，找出所要資料的位置。如果資料有一萬筆，運氣好第一筆就找到，運氣不好，找了一萬筆都沒有找到(速度為 n)。如果採用有序陣列排序的話，可以採用『二分搜尋法』，平均搜尋的速度是 log2n，n 表示資料筆數，如此速度就比有無序排序快許多。但因資料有依照主鍵大小排序，在作插入的時候，必須找到適當位置才可插入，而且必須經過適當的移位，才可以移動出一個空間，這遠比無序排列困難許多。
圖 4-6 有序陣列的儲存順序
4-3-2 範例研討：建立有序陣列
(A)程式功能：Ex4_2.java
吾人需要一個空間為 50 的有序陣列結構，來驗證陣列的處理方式，期望執行後能顯示下列結果。
|
D:\Java2_book\chap4>javac Ex4_2.java
D:\Java2_book\chap4>java Ex4_2
==
目前序陣列有
40 筆資料
==
2 4 6 8 10 12 14 16 18 20
22 24 26 28 30 32 34 36 38 40
42 44 46 48 50 52 54 56 58 60
62
64 66 68 70 72 74 76 78 80 |
(B)程式範例
圖 4-7 為其程式架構，包含 num[] 與 point 兩個類別變數，與一個 main() 主程式。
圖 4-7 Ex4_2 程式架構
|
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 |
//Ex4_2.java
/*
製作有序陣列的基本架構
*/
import java.util.*;
public class Ex4_2{
static int num[] = new int[50]; //
宣告陣列空間
static int point; //
宣告游標變數
public static void main(String args[]) {
point = -1; //
游標初值
for (int i=0; i< 40; i++){ //給予陣列初值
num[i] = (i+1) *2; //存入有序資料
point = point + 1; //游標指示目前位置
}
//
列印陣列內容
System.out.printf("\n==
目前序陣列有
%d
筆資料
==\n", point+1);
for(int i=0; i<=point; i++) {
System.out.printf("%2d ", num[i]);
if((i+1) % 10 == 0)
System.out.printf("\n"); //列印10筆,
換行
}
System.out.printf("\n"); //
列印完畢,
換行
}
} |
4-3-3範例研討：二分搜尋法
(A)程式功能：Ex4_3.java
數學老師利用一個二維陣列 score[][] 儲存某一班級學生的成績，陣列第一個元素score[k][0] 存放學生學號，由 411101 ~ 411150；第二個元素 score[k][1] 存放數學成績，由 00 ~ 100 分，如：{411101, 70}, {411102, 80}, {411103, 75}, {411104, 90}, {411105, 85}, {4111106, 65}, {411107, 83}, {411108, 78}, {411109, 67}, (411110, 72)...等等。陣列是依照學號由低到高排列。
請編寫一程式，允許輸入學生學號，則輸出該學生的成績。程式中先寫一小程式填入陣列內每一位同學的學號與成績，成績採 00 ~ 100 之間的亂數，之後印出全班成績，接著再編寫一個二分搜尋程式。期望操作介面如下：
|
D:\Java2_book\chap4>javac Ex4_3.java
D:\Java2_book\chap4>java Ex4_3
=== 411101 ~ 411150
成績列印
===
7 50 73 24 8 11 93 68 68 0
52 5 39 26 48 31 49 3 77 71
29 3 62 96 17 26 65 65 1 43
66 68 27 92 1 8 69 62 66 51
44 31 46 61 14 95 3 12 2 50
請輸入欲尋找的學生學號
=> 411120
學號
411120 成績是
71 |
(B)系統分析
『二分搜尋法』是由已排序（由大到小或由小到大排列）的陣列裡，搜尋某一筆資料，圖 4-8 為其運作程序。假設 a 陣列已由小到大排序完成（a[low] ~ a[high]），key 變數儲存欲尋找的資料，首先比對 a 陣列的中間元素（mid）的內容，如果 key = a [mid]，則資料找到；如果 key < a[mid]，則表示資料位於a[low] 與 a[mid] 之間，則 mid 取代 high；如果 key > a[mid]，則資料位於 a[mid] ~ a[high] 之間，mid 取代 low 內容。沒有找到資料的話，則將搜尋目標移到前半段或後半段繼續尋找，但還是由 a[low] ~ a[high] 搜尋（low 或 high 可能會改變）；如此依此類推，一直到找到資料或搜尋完畢為止。由此可見，此演算法每次將所有陣列資料缺切一半，再決定位於前段或後段，因此稱之為『二分搜尋法』。
此演算法較困難的地方是，如果找不到資料，如何去判斷與結束。其實，我們可以掌握一個重點，當 high 還是大於 low 的時候，表示還有資料未搜尋到；如果 high 小於或等於 low 時，表示已搜尋完所有資料，還未找到資料，則表示沒有該筆資料。
圖 4-8 二分搜尋法
(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 |
//Ex4_3.java
//
二分搜尋法
import java.util.Scanner;
import java.lang.Math;
public class Ex4_3 {
public static void main(String args[]) {
Scanner keyin = new Scanner(System.in);
int a[][], value, flag, low, high, mid;
a = new int[50][2];
int number = 411101;
for(int i=0; i<a.length; i=i+1){
a[i][0] = number + i;
a[i][1] = (int)(Math.random()*100);
}
/*
列印全班成績
*/
System.out.printf("=== 411101 ~ 411150
成績列印
===\n");
for(int i=0; i<a.length; i++) {
System.out.printf("%4d", a[i][1]);
if((i+1) % 10 == 0)
System.out.printf("\n");
}
System.out.printf("請輸入欲尋找的學生學號
=> ");
value = keyin.nextInt();
/*
二分搜尋法
*/
low = 0; high = 49;mid=0;
flag=0; //
設定是否找到旗號
while((low+1) < high) { //
陣列是否搜尋完
mid = (low + high)/2;
if (value == a[mid][0]) { //
比對陣列中間元素
flag = 1; //
找到了,
設定旗號並離開
break;
}
else if (value > a[mid][0]) //
在陣列的後半段
low = mid;
else //
在陣列的前半段
high = mid;
}
if (flag == 1)
System.out.printf("學號
%d
成績是
%d\n", a[mid][0], a[mid][1]);
else
System.out.printf("沒有
%d
學號學生\n",
value);
}
} |
(D)程式重點分析：
(1)
第 28~41
行：二分搜尋演算法。
(2)
第 29
行：『low=0; high=49;』。設定原陣列搜尋範圍。
(3)
第 30
行：『flag=0』。設定搜尋旗號為否（還未找到）。
(4)
第 31~41
行：『while((low+1) < high) { ….}』。其中 (low+1) < high 表示元素較高的指標 high 還是高於較低的 low，則陣列還未搜尋完畢。
(5)
第 32
行：『mid = (high + low)/2』。陣列元素索引 high 與 low 之間的中間元素的索引 mid。
(6)
第 33
行：『if(value == a[mid] { …}』。成立的話，表示找到該資料，則設定旗號並中斷離開。
(7)
第 37
行：『else if (value > a[mid][0]) { …}』。如未找到，但比中間值 a[mid] 大的話，則設定搜尋後半段（low = mid，但 high 未改變）。
(8)
第 39
行：『else high = mid』。都不是的話，則設定搜尋前半段（low 未改變）。
4-3-4 範例研討：有序陣列插入元素
(A)程式功能Ex4_4.java
吾人希望建立一個可供插入元素的有序陣列，其功能如下：
(1) 具有顯示陣列內容與插入元素的選項，選單如下：
|
D:\Java2_book\chap4>javac Ex4_4.java
D:\Java2_book\chap4>java Ex4_4
== 歡迎光臨 有序陣列管理系統 ==
(1) 列印有序陣列內容
(2) 插入陣列元素
(3) 離開系統
請輸入工作選項 => |
(2) 當選擇顯示陣列內容(選擇 1)，如下：
|
請輸入工作選項 =>1
== 目前序陣列有 30 筆資料 ==
2 4 6 8 10 12 14 16 18 20
22 24 26 28 30 32 34 36 38 40
42 44 46 48 50 52 54 56 58 60 |
(3) 插入元素(選擇 2)，如下： (插入元素 15後，再顯示陣列內容)
|
請輸入工作選項 =>2
請輸入欲插入元素 =>15
== 歡迎光臨 有序陣列管理系統 ==
(1) 列印有序陣列內容
(2) 插入陣列元素
(3) 離開系統
請輸入工作選項 =>1
== 目前序陣列有 31 筆資料 ==
2 4 6 8 10 12 14 15 16 18
20 22 24 26 28 30 32 34 36 38
60 |
(B)系統分析
如欲將元素插入有序陣列內，必須搜尋出他適當的位置再插入，才會保持原來有序排列。以圖 4-9 為例，有序陣列 num={2, 5, 10, 23, 34}，並以 point=4 表示目前游標在 4。如欲插入 8 的話，則必須將大於 8 的元素往後移一位，再將 8 插入。
圖 4-9 有序陣列插入元素
插入的運作程序如圖 4-10 所示。首先將游標加一(移一位的意思)，並將目前由標位置存入 k，如果 k 沒有大於0，表示是存入陣列第一筆資料。如果 k 大於 0，則比較數值是否大於欲插入的元素，如果大於的話，則往上移，否則就存入該空間。
圖 4-10 有序陣列插入元素
(C)程式範例：Ex4_4.java
程式架構如圖 4-11 所示，在 Ex4_4.class 類別內包含 5 個元件，其中兩個類別變數，與 3 個方法程式。
圖 4-11 Ex4_4 程式架構
|
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 |
//Ex4_4.java
/*
有序陣列的插入元素
*/
import java.util.*;
public class Ex4_4{
static int num[] = new int[50]; //
宣告陣列空間
static int point; //
宣告游標變數
public static void main(String args[]) {
Scanner keyin = new Scanner(System.in);
point = -1; //
游標初值
int select, k, item;
for (int i=0; i< 30; i++){ //給予陣列初值
num[i] = (i+1) *2; //存入有序資料
point = point + 1; //游標指示目前位置
}
disp_menu();
select = keyin.nextInt();
while(select != 3) {
switch(select) {
case 1:
disp_array();
break;
case 2:
if (point >=50) {
System.out.printf("陣列已滿無法插入!!\n");
}else {
System.out.printf("請輸入欲插入元素
=>");
item = keyin.nextInt();
point = point +1;
k = point;
while (true) {
if(num[k-1] > item) {
num[k] = num[k-1];
k = k - 1;
}
else {
break;
}
num[k] = item;
}
}
break;
default:
System.out.printf("輸入錯誤
!!
請重新輸入\n");
}
disp_menu();
select = keyin.nextInt();
}
}
//
列印功能表
static void disp_menu() {
System.out.printf("==
歡迎光臨
有序陣列管理系統
==\n");
System.out.printf("(1)
列印有序陣列內容\n");
System.out.printf("(2)
插入陣列元素\n");
System.out.printf("(3)
離開系統\n");
System.out.printf("\t
請輸入工作選項
=>");
}
//
列印陣列內容
static void disp_array() {
System.out.printf("\n==
目前序陣列有
%d
筆資料
==\n", point+1);
for(int i=0; i<=point; i++) {
System.out.printf("%2d ", num[i]);
if((i+1) % 10 == 0)
System.out.printf("\n"); //列印五筆,
換行
}
System.out.printf("\n"); //
列印完畢,
換行
}
} |
4-3-5 自我挑戰：有序陣列元素處理
(A)程式功能：PM4_2.java
吾人希望由 Ex4_4 中擴充可以刪除元素的功能，如下：
(1)具有顯示陣列內容、插入與刪除元素的選項，選單如下：
|
D:\Java2_book\chap4>javac PM4_2.java
D:\Java2_book\chap4>java PM4_2
== 歡迎光臨 有序陣列管理系統 ==
(1) 列印有序陣列內容
(2) 插入陣列元素
(3) 刪除陣列元素
(4) 離開系統
請輸入工作選項 => |
(2)當選擇顯示陣列(選擇 1)，如下：
|
請輸入工作選項 =>1
== 目前序陣列有 30 筆資料 ==
2 4 6 8 10 12 14 16 18 20
22 24 26 28 30 32 34 36 38 40
44 46 48 50 52 54 56 58 60 |
(3)刪除元素(選擇 3)，如下： (刪除元素 14 後，再顯示陣列內容)
|
請輸入工作選項 =>3
請輸入欲刪除元素 =>14
== 歡迎光臨 有序陣列管理系統 ==
(1) 列印有序陣列內容
(2) 插入陣列元素
(3) 刪除陣列元素
(4) 離開系統
請輸入工作選項 =>1
== 目前序陣列有 29 筆資料 ==
2 4 6 8 10 12 16 18 20 22
24 26 28 30 32 34 36 38 40 42
46 48 50 52 54 56 58 60 |
(B)系統分析
有序陣列刪除元素的運作程序幾乎與無序陣列相同，如圖 4-12 所示。首先找到欲刪除的元素，再將該元素後面的元素往前移一位 (num[i] = num[i+1])，再將游標減一(point = point -1) 即可。
圖 4-12 有序陣列刪除元素的運作
(C)程式提示
圖 4-13 為 PM4_2.java 的程式架構，包含 2 個類別變數與 4 個方法程式，其中 Binary_search() 是讓我們快速找到欲刪除元素的位置，找到後，後面的元素往前移一位即可。
圖 4-13 PM4_2 程式架構
程式片段如下：
|
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
30
31
32
33
34
35 |
import java.util.*;
public class PM4_2{
….
while(select != 4) {
switch(select) {
…..
…..
case 3:
System.out.printf("請輸入欲刪除元素
=>");
item = keyin.nextInt();
int location = Binary_serach(item);
if (location == -1){
System.out.printf("陣列內沒有
%d
元素\n",
item);
}else {
for(int i = location;i<=point;i++)
num[i] =
num[i+1];
}
point = point - 1;
break;
default:
System.out.printf("輸入錯誤
!!
請重新輸入\n");
}
…….
}
…..
//二分搜尋法
static int Binary_serach(int value){
int location=-1; //
設定找到位置
….
請參考
Ex4_3
二分搜尋法
….
return location;
}
} |
|
