Java 程式設計(二)  ：第 四章 陣列資料結構      下一頁

 

第四章  陣列資料結構

內容：

  • 4-1 資料結構簡介

  • 4-2 無序陣列結構

    • 4-2-1 無序陣列結構簡介

    • 4-2-2 範例研討：建立無序陣列

    • 4-2-3 自我挑戰：無序陣列元素處理

4-1 資料結構

既然電腦是處理資料的能手，勢必也有儲存大量資料的能力，到底資料怎麼儲存才好？這牽涉到的問題很廣。從最基本的觀點來看，電腦除了能儲存大量資料外，還必須具有處理這些資料的能力，譬如，從中搜尋所要的資料，或可以容易的插入、刪除或更新資料內容。如果資料不多時，隨便儲存都不會產生大礙，然而當資料超過千萬筆時，如何可快速處理這些資料，這可就非常困難。然而為了讓資料可以被快處理，這就牽涉儲存方式，一般稱之為『資料結構』。

資料結構有許多種方法，譬如：陣列、鏈路、樹狀、B-Tree、B+-Tree 等等方法。B-Tree 以上的資料結構處理方法並不容易，但他們的搜尋速度最快，較適合巨量儲存環境；陣列結構的處理方法最簡單，但搜尋速度最慢，較適合小資料量的儲存。相對應的利用 B-Tree 資料結構所建立的資料庫系統，遠比利用陣列建立的貴很多。本書僅利用陣列要介紹資料結構的程式編寫技巧，至於較複雜的儲存方式，留給專門課程介紹。

4-2 無序陣列結構

4-2-1 無序陣列結構簡介

陣列資料結構的基本構想是利用二維陣列，陣列中每一行為一筆資料。基本上每一筆資料都有一個關鍵欄位，此關鍵欄位在所有其他資料中不可重複，又稱為『主鍵』。如果資料儲存於陣列中沒有依照主鍵的大小排列，則稱為『無序陣列結構』，反之，有依照主鍵的大小排列，則稱為『有序陣列結構』。圖 4-1 為兩者的比較，同樣都是儲存文具庫存資料，並以序號為主鍵，無序陣列沒有照次序儲存；有序陣列則有依照序號大小排列。為了簡化程式設計，以下的範例僅利用主鍵來說明。

  

圖 4-1 無序陣列結構

圖 4-1-1 有序陣列結構

4-2-2 範例研討：建立無序陣列

(A)系統功能：Ex4_1.java

吾人希望建立一個無序陣列，儲存空間為 50 筆，並具有插入與列印資料的功能，期望操作介面如下：

(1)具有 3 個選單如下：

D:\Java2_book\chap4>java Ex4_1

== 歡迎光臨 無序陣列管理系統 ==

(1) 列印無序陣列內容

(2) 插入陣列元素

(3) 離開系統

84    74  38  27  80

(2)選擇列印資料(選擇 1) 如下：

         請輸入工作選項 =>1

 

== 列印無序陣列內容

32  58  40  56  76

16  10   9  62  94

94  53   1  27  71

25  77  63  85  34

69    59  77  76  98

(3)插入元素後其結果 (選擇 2 與 1) 如下：

         請輸入工作選項 =>2

請輸入欲插入元素 =>45

== 歡迎光臨 無序陣列管理系統 ==

(1) 列印無序陣列內容

(2) 插入陣列元素

(3) 離開系統

         請輸入工作選項 =>1

== 列印無序陣列內容

32  58  40  56  76

16  10   9  62  94

94  53   1  27  71

25  77  63  85  34

69  59  77  76  98

84    74  38  27  80

45

(B)系統分析：

圖 4-2 是我們需建立一個空間為 50 的陣列，空間為：num[0] ~ num[49]，其中利用一個 point 指標來顯示目前資料到甚麼地方，當陣列空間還未儲存資料則 point = -1，插入一筆資料後 point = point + 1，為 0 ，依此類推。如果刪除資料則 point = point -1，如果 point=-1 則表示陣列空閒；point=49 則表示陣列已滿不可再存入。

圖 4-2 無序陣列的插入元素(插入 5)

(C)程式範例

圖 4-3 為 Ex4_1.java 的程式架構，包含有 3 個『方法程式』(method) 與 2個類別變數，其中 main 為主程式、disp_menu 是顯示功能選項程式、disp_array 為列印陣列內容程式。類別變數 num[] 是無序陣列的儲存空間；point 是指示目前陣列存放位置的游標，兩者類別變數允許所有方法程式存取。

其中『類別變數』(class variable)又稱為『整體變數』，它允許類別內所有『方法程式』存取。亦是，num[] 與 point 兩變數允許 main()、disp_menu() 與 disp_array() 等方法共同存取使用。如果這兩個變數在 main() 方法內宣告的話，則僅被 main() 存取，其他兩個方法就無法使用到他們。

圖 4-3 Ex4_1 程式架構

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

//Ex4-1.java

/* 製作一個空間為 50 的無序陣列，並具有插入元素與

* 列印陣列內容的功能 */

 

import java.util.*;

public class Ex4_1{

  static int num[] = new int[50];      // 宣告無序陣列空間

  static int point;                   // 宣告游標變數

  public static void main(String args[]) {

      Scanner keyin = new Scanner(System.in);

      Random random = new Random();

      int value;       // 輸入元素

      int select;      // 功能選擇

      point = -1;      // 游標初值

      for(int i=0; i<30; i++){      //給予陣列初值

          value = random.nextInt(100);

          point = point +1;

          num[point] = value;

      }

      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("請輸入欲插入元素 =>");

                       value = keyin.nextInt();

                       point = point +1;

                       num[point] = value;

                   }

                   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== 列印無序陣列內容\n");   

      for(int i=0; i<=point; i++) {

           System.out.printf("%2d  ", num[i]);

            if((i+1) % 5 == 0)

               System.out.printf("\n");    //列印五筆, 換行

      }

      System.out.printf("\n");           // 列印完畢, 換行

   }

}

(D)編譯與執行如下：

(E)重點說明

(1) 第7~8 行：宣告產生類別變數 num[] 與 point。

(2) 第16~20行：給予 num[] 某些初值。

4-2-3自我挑戰：無序陣列中元素處理

(A)系統功能：PM4_1.java

吾人希望在 Ex4_1 的無序陣列中，可選擇刪除某一個元素的功能，期望操作介面如下：

望操作介面如下：

(1)具有 4 個選單如下：

== 歡迎光臨 無序陣列管理系統 ==

(1) 列印無序陣列內容

(2) 插入陣列元素

(3) 刪除陣列元素

(4) 離開系統

         請輸入工作選項 =>1

(2)選擇列印資料(選擇 1) 如下：

         請輸入工作選項 =>1

 

== 列印無序陣列內容

83  65  26  31  44  79  62  19  11  26

22  22   1  63  51  48  44  68  49  87

84    23   4  41  93  65  97  64  54  54

(3)刪除元素後其結果 (選擇 3 與 1) 如下：

         請輸入工作選項 =>3

請輸入欲刪除元素 =>44

== 歡迎光臨 無序陣列管理系統 ==

(1) 列印無序陣列內容

(2) 插入陣列元素

(3) 刪除陣列元素

(4) 離開系統

         請輸入工作選項 =>1

 

== 列印無序陣列內容

83  65  26  31  79  62  19  11  26  22

22   1  63  51  48  44  68  49  87  86

23    4  41  93  65  97  64  54  54

(B)系統分析

圖 4-4 是由無序陣列中刪除某一元素的示意圖。它有以下步驟：

(1) 搜尋欲刪除的元素是否在陣列中，如沒有則結束。

(2) 如找到了，記錄其儲存位置(譬如 num[k])，則由 num[k+1] 以後到游標(num[point]) 的資料都往前移一位，將 num[k] 內容覆蓋。

圖 4-4 無序陣列刪除元素(刪除 2)的運作

(C)程式提示

圖 4-5 為程式架構圖，由 Ex4_1.java 中增加了 Linear_search()，它的功能是搜尋所欲刪除元素的位置，如果找到的話，則回傳 location 位置，否則回傳 location=-1。

圖 4-5 PM4_1 程式架構

(D)編譯與執行如下：

翻轉工作室：粘添壽

 

Java 程式設計(二) 含物件導向

 

 

翻轉電子書系列：