1、第七章 陣列,處理少量的資料，可以為每一筆資料設定一個變數，但如果資料量非常龐大，譬如一個班級的50位同學成績，分別設定A1、A2A50等50個變數，是一件相當麻煩的事。為了解決大批的資料處理，遂有陣列(Array)的使用。要儲存一個班級的數學成績可以宣告一個一維陣列，例如int A50代表50個人的數學成績，則A0可以用來表示1號同學的數學成績(註：陣列索引由0開始)。若要表達每班每人的國、英、數三科成績時，可以宣告一個二維陣int A503來表示。其中A00表示1號國文成績、A01表示1號英文成績、A02表示1號數學成績，依此類推。同理，如果一年級有12班，則可以宣告個三維陣列int A1
2、2503來儲存，其中A6411代表7班42號英文成績，以此類推。如果一個學校有三個年級則可宣告一個四維陣列int A312503來儲存，其中A17232表示二年級八班24號數學成績。,目錄,7_1 一維陣列7_2 二維與多維陣列7_3 實例探討,7_1 一維陣列,陣列的宣告Java使用 Array類別定義陣列型別，關於Array類別所提供的方法請看10_4節。所以，陣列的宣告與非物件導向的程式設計略有不同，其語法如下：資料型別 陣列名稱索引1 索引2=new資料型別 陣列名稱索引1 索引2or 資料型別 索引1 索引2陣列名稱=new資料型別 陣列名稱索引1 索引2以上語法說明如下：1.資料型
3、別可為3-4節Java內建的資料型別。2.陣列名稱應遵守3-2節識別字的命名規則。3.使用一個索引，即為一維陣列，以下式子為宣告並建立一個整數型別的一維陣列，註標索引從0到9，長度為10。其中陣列名稱的中刮號放在陣列名稱的前後均可,但本書以使用前者為習慣。int a=new int10; int a=new int10;,4.使用二個索引，即為二維陣列，以下式子為宣告並建立一個字元型別的二維陣列，關於二維陣列，請看72節。char b=new char32;5.陣列有一屬性length記錄陣列的長度，例如上式的a.length即為10。6.上式的int及char均為類別名稱，a及b稱為類別的實
4、現，或稱為類別變數，類別變數即為物件。例如，若有資料如下：8 1 6 3 5 7 4 9 2若以一維陣列儲存，則此陣列的初始化如下，且中刮號內務必留空白，否則會產生錯誤：int d=8,1,6,3,5,7,4,9,2;其中，d0=8、d1=1d8=2，依此類推。若以二維陣列儲存，則此陣列的初始化如下：int e=8,1,6,3,5,7,4,9,2; 其中，e00=8、e01=1、e02=6、e10=3e22=2。,陣列元素的存取,Java是用中括號代表陣列的每一個元素，例如上式執行後，陣列的第一個元素即為b0，且其值為1，第二個元素為b1，其值為2，所以若令a=b0，則a之值亦為1。以下敘述可
5、設定b 陣列索引2的值為33。b2=33;,範例7-1a,假如有資料如下1, 2, 3, 4, 5, 6, 7, 8(1)請用陣列儲存以上資料。(2)請將以上資料乘以2。(3)計算以上資料的總和。,範例7_1b,請用陣列讀入5位學生的國文成績，並可由使用者輸入座號來查詢成績。,範例7-1c,設有資料如下77, 66, 99, 44, 55請寫一個程式，以陣列儲存以上資料，並計算平均、最高分及最低分。,範例7-1d,請寫一程式將任意十進位轉為N進位。(2=N=16),7-2二維與多維陣列,含有兩個或兩個以上索引值的陣列稱為多維陣列，一般最常應用的是二維陣列，下面我們就以二維陣列為例，來介紹如何使
6、用多維陣列。,二維陣列變數宣告,以下敘述宣告一個二維的整數型別陣列變數。int arr=new int35;你可以把二維陣列想像成一個表格，所以上式arr這個陣列就像一個有3列5行可以存放15個元素的表格，當然和一維陣列一樣，不管是列或行，其索引值皆由0開始。為了讓讀者更清楚二維陣列的資料結構，我們將arr陣列的所有元素以表格表示如下：,多維陣列變數值的存取,以下敘述可以將第0列第1行這個陣列元素的值設定為1。A = Arr01;Arr01=1;arr01=1;以下敘述可以將第0列第1行這個陣列元素的值指定給變數A。a=arr01;,多維陣列變數值的初始化,假設有表格資料如下: 若以二維陣列儲
7、存，則其敘述如下：int Arr= 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 21, 22, 23, 24, 25 ;同樣的道理，中刮號內不得有值。以上敘述示範了二維陣列變數值的初始化，我們以下表顯示每個陣列元素的初始值。,範例7-2a,假設有學生成績如下：1.請以二維陣列儲存以上資料。2.計算每人平均。3.統計每人不及格科數。4.統計各科平均。,範例7-2b,假設有兩個矩陣如下: 1 2 3 1 2 04 5 6 2 1 3請以二維陣列儲存以上資料，並求其相加的結果如下： 2 4 3 6 6 9,魔術方陣,任一方陣中，若其橫向、直向與斜線總值均相等，則稱此方鎮維魔
8、術方陣。例如，以下為3階魔術方陣。製作此方陣的規則如下：1、在第一列(Row)中間行(Column)的位置設定值為1，然後按照其相鄰的東北方向位置擺進下一個數值，如下圖。,2.根據規則1推算的位置，若該位置超過了列的界限，則列的位置為最大列的相對應位置。如下圖的2，其列已超界，移至最下面一列。3.根據規則1推算的位置，若該位置超過了行的界限，則其位置為最小行的相對應位置。如下圖的3，其行已超界，所以移至最左邊。,4.根據規則1，推算位置的所在，已被其他值所佔，則以原位置為基準，將下一個數字擺於原位置的下一列的相同行之位置。如下圖的4，原位置已被1佔去，所以擺在3的下面一列。 5.當行與列都超過
9、了界，則採用規則2和規則3的綜合法則，但因該位置已被佔有，故再以規則4處理之。如下圖左的7，最後結果如下圖右。,範例7_2c,試寫一魔術矩陣程式。,矩陣相乘,矩陣的行列定義如下，下式為3行2列。矩陣要能相乘，則第一個矩陣行數要等於第二個矩陣的列數，且相乘結果的行數等於第二個矩陣的行數，列數則為第一矩陣列數。則任一子集合Cmp如下：,a00 a01 a02A23= a10 a11 a12,C22=A23 X B32,例如： 則計算過程如下：c00=a00*b00+a01*b10+a02*b20=-1*1+0*2+3*-1=-4c01=a00*b01+a01*b11+a02*b21=12c10=a
10、10*b00+a11*b10+a12*b20=6c11=a10*b01+a11*b11+a12*b21=-11以下敘述為以上說明的演算法： for (i=0;im;i+) /2 for (j=0;jp;j+) /2 cij=0; for (k=0;kn;k+) /3 cij=cij+aik*bkj; ,範例7-2d,請寫一個程式完成兩個矩陣的相乘。,7-3 實例探討,排序將一序列的值由小而大或由大而小排列，稱為排序。本節將介紹兩種簡單而實用的排序，分別稱為泡沫排序法與計數排序法。,泡沫排序法,於一數列當中，從第一筆資料逐一往後兩兩給予比較，若前者大於後者，則兩者交換（本例為由小而大排序，若由大
11、而小排序，則當前者小於後者時，兩者交換），每次的比較與交換均可得該數列的最大值於數列最右邊（末端），所以若有N筆資料進行排序，則應作N-1階次的逐一比較，且每階次的逐一比較範圍均逐漸減一個，此即為泡沫排序法(Bubble Sort)。若有8、9、7、1、2五筆資料，則其排序過程如下：,1.將資料由左而右排列如下： 8 9 7 1 2 2.共有五筆資料n=5，共須進行四個階次的逐一比較，每一階次都能將該階次的最大值移至最右邊，四個階次的逐一比較細節說明如下：(1)從第一筆到第五筆兩兩比較，若前者大於後者則兩者交換如下，得最大值9於最右邊。9已是最大值，待會兒不必參與比較，所以下一次只要從第一筆比
12、較至第四筆即可。,(2)從第一筆到第四筆兩兩比較，若前者大於後者，則兩者交換如下，得次大值8於右邊。8與9已達定位，待會兒不用參與比較。 (3)從第一筆資料到第三筆資料兩兩比較，若前者大於後者則兩者交換如下，得第三大值7 於右邊。,(4)從第一筆資料到第二筆資料兩兩比較，若前者大於後者則兩者交換如下，排序完成。 3.若有N筆資料，則須作N-1階次的比較。其次，每一階次均應逐次尋找最大值，並移至右邊，且比較次數均逐漸縮小，分別為N-1，N-2，.，1。比較次數j與 外迴圈i的關係為i+j=n，所以內迴圈的比較次數j為N-i。以上說明的演算法如下： for (i=1;iaj+1) /兩數交換 t=
13、aj; aj=aj+1; aj+1=t; ,4. 比較次數總計約為N*N2，資料交換次數約為N*N4。 5.以上每次均找到一個最大值於右邊，若將該次搜尋所得最大值與右邊位置交換，則可大大減少資料交換次數，且其比較次數不變仍為N*N2，但其資料交換次數總計約為N，請讀者自行練習。,範例7-3a,示範泡沫排序法。,計數排序法,前面的泡沫排序法是採用兩者比較並交換，達到由小而大或由大而小排列的效果，不過本節的計數排序法則是不移動資料，但直接給予名次。為了充份理解計數排序法的原理，你先假想一個N位學生的教室裡，每人均舉著自己的分數，每一學生如何知道自己是第幾名呢？有一個辦法就是每個人均數一數分數比自己
14、高的人數再加一，就是自己的名次，但其比較次數還是N*N，所以若令他們排成一排，由第一個逐一往右比較，且分數低的，令其名次加1，則第二個人就不必與第一個比較，同理，第三個也是往右比較即可，不必與第一、二個人比較，所以其總比較次數約為N*N2，此即為計數排序法，若有數列資料8、2、9、7、1則其演算過程如下：,1.先假設每人均為第一名。 2.共有五筆資料，分別以前四筆資料為基準往右比較：(1)以第一筆資料8為基準往右（第二、三、四、五筆）比較，分數低的名次加一，則其名次如下，第一筆資料8確定為第二名，下次不用再參與比較。(2)以第二筆資料2為基準往右（第三、四、五筆）比較，分數低的名次加一，則其名
15、次如下，第二筆資料2確定為第四名，下次不用再參與比較。,以第三筆資料9為基準往右（第四、五筆）比較，分數低的名次加一，則其名次如下，第三筆資料9確定為第一名，下次不用參與比較。以第四筆資料7為基準往右（第五筆）比較，分數低的名次加一，則其名次如下，全部名次確定，排序完成。,3.若有N筆資料，則須作N-1階次的比較，每階次的比較次數均逐漸縮小，分別為N-1，N-2，.，1，故其總比較次數約為N*N2。for (i=1;iaj) /分數小的人，名次加一 bj+; /a 是分數，b 是名次 else bi+;,示範計數排序法。,範例 73B,搜尋,本節將介紹兩種常見的搜尋方式，其一是線性搜尋法，其二
16、是二分搜尋法。,線性搜尋法,於序列中，從頭到尾逐一比對搜尋的方式，稱為線性搜尋法。例如，若有12個員工電話號碼如下：,首先，必須先以陣列儲存以上資料如下：String a= 0,0, aa,1111168, hh,2222168, cc,3333168, gg,4444168, ff,5555168, ii,6666168, ee,7777168, bb,8888168, jj,9999168, dd,1688168, kk,2688168, ll,3688168;,接著，輸入姓名如下：String name;name=buf.readLine();其次，採用逐一訪視的方式,逐一比對字串是否相
17、符，若相符則輸出其電話號碼，其敘述如下：for (i=1;i=12 ;i+) /字串的比較，但大小寫視為相同,相同時傳回 0 if (pareToIgnoreCase( ai0)=0) System.out.println(“其電話號碼為: ” +ai1); found=true; break; ,範例7-3c,設有員工電話如下，請以陣列儲存，並能輸入姓名而查得電話號碼。,二分搜尋法,前面的線性搜尋法，是採用逐一訪視的方式搜尋所要的資料，但當資料量龐大時，就顯得毫無效率。舉例而言，資料數量若有1000筆，則採用線性搜尋法平均搜尋次數為500次，但若採用本節所討論的二分搜尋法，則至多不會超過10次(210=1024)。使用二分搜尋法前應先將資料排序。在一個已排序的序列中，首先與序列的中間值比較，若待搜尋資料比中間值大，則待搜尋資料必在此中間值的後面，反之則在前面，所以二分搜尋法每次可將搜尋範圍減半，如此對於資料量龐大時，可提高搜尋效率。例如，上例中，必須先將資料排序，則二分搜尋的演算法如下：,l=1; /下界 u=12;/上界 while (l0) l=m+1; /調整下界 else u=m-1; /調整上界 if (found=false) System.out.println(查無此人);,範例7-3d,同上範例，但使用二分搜尋法。,
