Chapter 3 陣列(Arrays).

Presentation on theme: "Chapter 3 陣列(Arrays)."— Presentation transcript:

1 Chapter 3 陣列(Arrays)

2 陣列 int ko[ ]=new int[5]； int ko [ ] [ ] = new int[80] [50 ] ；
陣列(Array)可分成一維陣列、二維陣列及多維陣列(三維以上的陣列)。 Java int ko[ ]=new int[5]； int ko [ ] [ ] = new int[80] [50 ] ； int ko[ ] [ ] [ ] = new int[80] [50 ] [50 ] ；

3 資料型態 資料型態名稱 佔記憶體大小(位元組) byte 1 short 2 int 4 long 8 char float double

4 一維陣列 一維陣列的宣告法： int ko[ ]=new int[5]； int [ ]ko=new int[5]；

5 一維陣列位址的配置 若陣列 ko[n]，假設每一個變數佔了 d 個位元組的空間：
變數 ko[0] ko[1] ko[2] ‧‧‧ko[n-1] 位址 m m+d m+2*d‧‧‧m+(n-1)*d d值代表資料型態所佔記憶體空間的大小，則： Loc(ko[n-1])=m+(n-1)*d．．(公式3-1) 其中 m=Loc(ko[0]) ，d 為資料型態所佔記憶體的大小，n-1 代表 ko[0] 與 ko[n-1] 間隔。 Loc 代表 Location 記憶體位置。 例題 ko3_1使用一維陣列，計算小學生成績

6 一維陣列位址的配置 P.74例題1: 假設在 Java 語言中有一陣列 A[ ] 儲存了 float 的資料，若 A[100] 的位址是 4413，則 A[200] 的位址為若干？

7 一維陣列位址的配置 解答： 已知 Loc(A[100])=4413=m+(n-1)*d=m+100*d，根據公式 3-1
Loc(ko[n-1])=m+(n-1)*d， 得知 Loc(ko[0])=m，d=4， Loc(A[100])=4413=m+100*4，得 m=4013 Loc(A[200])=m+(n-1)*d = *4 =4813

8 一維陣列位址的配置 例題 ko3_2使用一維陣列，將一組字串之大寫變小寫，小寫變大寫
P.74例題 2 例題 ko3_2使用一維陣列，將一組字串之大寫變小寫，小寫變大寫 例題 ko3_3使用一維陣列，將一組數字，依大小順序排列

9 二維陣列 二維陣列宣告方式： int ko[ ][ ]=new int[5][3]； int [ ][ ]ko=new int[5][3]；
二維陣列包含列(Row)及行(Column)： (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)

10 二維陣列 例題 ko3_4 使用二維陣列，求陣列中最大值及最小值 例題 ko3_5 使用二維陣列，列出二維陣列，並求各列數字的和
先介紹二個陣列乘積之算法

11 二維陣列位址的配置 二維陣列位置的配置可分為 以列為主陣列位置的配置 以行為主陣列位置的配置 通常都是以列為主陣列位置的配置

12 以列為主陣列位址配置 假設每一個變數佔了2個位元組的空間，y行內有δ個元素

13 以列為主陣列位址配置 若 Loc(A[0][0])=m，而且以列為主陣列位置的配置方式，則A[x][y]記憶體位置的公式如下：
Loc(A[x][y])=m+d(xδ+y)…………(公式3-2) 其中δ代表 y 行內有δ個元素，d 代表每一個變數佔了 d 個位元組的空間。

14 P.81例：有一個二維陣列A，假設A[1][1]與A[3][3]的位址分別為644與676，求A[4][4]的位址為若干？
Loc(A[1][1])=644=m+d(δ+1)……………………….(1) Loc(A[3][3])=676=m+d(3 δ+3)……………………..(2) (1)x3-(2)得 2m=1256 m=628……………………………..(3) d(δ+1)=16……………………….(4) 將(3)(4)代入 Loc(A[4][4])=m+d(4 δ+4) =m+4d(δ+1) =628+4x16 =692

15 以行為主陣列位址配置 假設每一個變數佔了2個位元組的空間，x列內有δ個元素

16 以行為主陣列位址配置 若Loc(A[0][0])=m，而且以行為主陣列位址的配置方式，則 A[x][y]記憶體位址的公式如下：
Loc(A[x][y])=m+d(yδ+x)………......(公式3-3) 其中δ代表x列內有δ個元素，d代表每一個變數佔了d個位元組的空間。

17 P.83例：有一個以行為主的二維陣列 A[x][y]，A[3][2]的位址是 1111，A[2][3]的位址為 1116。若每一個元素佔了1個位元組，求A[1][4]的位址為若 干？
已知d=1根據公式3-3 Loc(A[x][y])=m+d(yδ+x)得知： Loc(A[3][2])=1111=m+(2‧δ+3)…………………..(1) Loc(A[2][3])=1116=m+(3‧δ+2)…………………..(2) (2)-(1)得 5=δ-1，求得δ=6……………………….(3) (3)代入(1)求得 m=1096 Loc(A[1][4])=m+d(yδ+x) =1096(4‧6+1) =1121

18 多維陣列位址的配置 以列為主陣列位址的配置
加設有一三維陣列 A[z][y][x]，A[0][0][0]的位址為m，每一個元素佔了d個位元組，則 A[a][b][c]的位址為： Loc(A[a][b][c])=m+d(ayx+bx+c)……(公式3-4)

19 P.85例：設有一三維陣列A[2][3][4]中，陣列元素A[1][1][1]在主記憶體中之位址為3000，且一個元素佔一個位元組，以列為主排列時，陣列元素A[2][1][3]之位址為何？
已知三維陣列A[2][3][4](z=2,y=3,x=4)，每一個元素佔一個位元組，d=1。根據公式 3-4 知 Loc(A[1][1][1])=m+d(ayx+bx+c)=m+1(1‧3‧4+1‧4+1)=m+17=3000，得m=2983 Loc(A[2][1][3])=m+d(ayx+bx+c) =2983+1(2‧3‧4+1‧4+3) = =3041

20 多維陣列位址的配置 以行為主陣列位址的配置
假設有一三維陣列A[z][y][x]，A[0][0][0]的位址為m，每一個元素佔了d個位元組，則A[a][b][c]的位址為： Loc(A[a][b][c])=m+d(czy+bz+a)……(公式3-5)

21 P.85例：設有一三維陣列A[2][3][4]中，陣列元素A[1][1][1]在主記憶體中之位址為3000，且一個元素佔一個位元組，以行為主排列時，陣列元素A[2][1][3]之位址為何？
已知三維陣列A[2][3][4](z=2,y=3,z=4)，每一個元素佔一個位元組，d=1。 根據公式3-5知Loc(A[1][1][1])=m+d(czy+bz+a)=m+1(1‧2‧3+1‧2+1)=m+9=3000，得 m=2991 Loc(A[2][1][3])=m+d[czy+bz+a] =2991+1(3‧2‧3+1‧2+2) = =3013

22 特殊矩陣 稀疏矩陣 所謂稀疏矩陣是指矩陣中的元素大多數為0。擁有多少個零元素才稱得上「稀疏矩陣」，並沒有明確的定義。

23 以二維陣列來儲存此稀疏陣列，地以列用來儲存稀疏矩陣的列數、行數以及非零元素數，第二列一後用來儲存稀疏矩陣的非零元素所在的位址及其值，此法稱為行列索引表示法

24 依據圖3-6，總共非零元素有8個，存放稀疏矩陣的記憶體空間=3*(8+1)=27 因此，答案應為(C)3(k+1)
P.90例：一個mxn的整數矩陣(Matrix)，其中有k個非零的值。如果用陣列儲存這個Sparse Matrix的k值。需要多少個記憶體？(A)k(B)2k+1(C)3(k+1)(D)4k 依據圖3-6，總共非零元素有8個，存放稀疏矩陣的記憶體空間=3*(8+1)=27 因此，答案應為(C)3(k+1)

25 下三角形矩陣 正方形矩陣A[x][y]其對角線以上的元素均為0。x≦y，A[x][y]=0

26 下三角形矩陣位置配置 以列為主 Loc (A[x][y])= Loc (A[0][0])+(1+x)x/2+y． ． ．(公式3-8)
例題 ko3_7 (下三角型以列為主的位址配置，二維陣列轉換成一維陣列)

27 下三角形矩陣以行為主 Loc (A[x][y])= Loc (A[0][0])+n(y-1)-y(y-1)/2+x (公式3-9)
例題 ko3_8 (下三角型以行為主的位址配置，二維陣列轉換成一維陣列)

28 上三角形矩陣 x≧y，A[x][y]=0

29 上三角形矩陣以列為主 Loc (A[x][y])= Loc (A[0][0])+n(x-1)-x(x-1)/2+y (公式3-10)
例題 ko3_9 (以上三角型矩陣以列為主的位址配置，二維陣列轉換成一維陣列)

30 上三角形矩陣以行為主 Loc (A[x][y])= Loc (A[0][0])+y(y-1)/2+x (公式3-11)
例題 ko3_10 (以上三角型以行為主的位址配置，二維陣列轉換成一維陣列)

31 多項式陣列 使用n+2長度的陣列a儲存多項式f(x)。 f(x)=7x3+4x+13 。 A[5]={3，7，0，4，13} 。

32 多項式陣列 以a[2p+1]儲存多項式f(x)。 f(x)=7x3+4x+13 。 A[7]={3，3，7，1，4，0，13} 。

33 類別 Java語言的類別與陣列類似，可將一些資料組在一起。但是資料陣列的每一元素的資料型態必須一致；類別的每一元素的資料型態不必一致。
因此，陣列記憶體的空間也較類別記憶體的空間容易掌握。 例題ko3_11使用類別宣告各種資料型態