1、1 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures陣列陣列(Arrays)Chapter 32 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures陣列陣列p陣列陣列(Array)可分成一維陣列、二維陣列及可分成一維陣列、二維陣列及多維陣列多維陣列(三維以上的陣列三維以上的陣列)。pJavaint ko=new int5；int ko =new int80 50 ；int ko =new int80 50 50 ；3 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data S
2、tructuresData Structures資料型態資料型態資料型態名稱資料型態名稱佔記憶體大小佔記憶體大小(位元組位元組)byte1short2int4long8char2float4double84 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一維陣列一維陣列p一維陣列的宣告法：一維陣列的宣告法：int ko=new int5；int ko=new int5；int ko=1，2，3，4，5；int ko=1，2，3，4，5；5 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Str
3、uctures一維陣列位址的配置一維陣列位址的配置p若陣列若陣列 kon，假設每一個變數佔了，假設每一個變數佔了 d 個個位元組的空間：位元組的空間：變數變數 ko0 ko1 ko2 kon-1位址位址 m m+d m+2*d m+(n-1)*dd值代表資料型態所佔記憶體空間的大小，則：值代表資料型態所佔記憶體空間的大小，則：Loc(kon-1)=m+(n-1)*d(公式公式3-1)其中其中 m=Loc(ko0)，d 為資料型態所佔記憶體的大小，為資料型態所佔記憶體的大小，n-1 代表代表 ko0 與與 kon-1 間隔。間隔。Loc 代表代表 Location 記憶記憶體位置。體位置。例題例
4、題 ko3_1使用一維陣列，計算小學生成績使用一維陣列，計算小學生成績6 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一維陣列位址的配置一維陣列位址的配置pP.74例題例題1:假設在假設在 Java 語言中有一陣列語言中有一陣列 A 儲存了儲存了 float 的資料，若的資料，若 A100 的位址是的位址是 4413，則則 A200 的位址為若干？的位址為若干？7 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一維陣列位址的配置一維陣列位址的配置p解答：解答：已知已知
5、Loc(A100)=4413=m+(n-1)*d=m+100*d，根據，根據公式公式 3-1Loc(kon-1)=m+(n-1)*d，得知得知 Loc(ko0)=m，d=4，Loc(A100)=4413=m+100*4，得，得 m=4013Loc(A200)=m+(n-1)*d =4013+200*4 =48138 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures一維陣列位址的配置一維陣列位址的配置pP.74例題例題 2p例題例題 ko3_2使用一維陣列，將一組字使用一維陣列，將一組字串之大寫變小寫，小寫變大寫串之大寫變小寫，小寫變大
6、寫p例題例題 ko3_3使用一維陣列，將一組數使用一維陣列，將一組數字，依大小順序排列字，依大小順序排列9 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures二維陣列二維陣列p二維陣列宣告方式：二維陣列宣告方式：int ko =new int53；int ko=new int53；int ko =1，2，3，4；int ko=1，2，3，4；二維陣列包含列二維陣列包含列(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 樹德科技
7、大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures二維陣列二維陣列p例題例題 ko3_4 使用二維陣列，求陣列中最大使用二維陣列，求陣列中最大值及最小值值及最小值p例題例題 ko3_5 使用二維陣列，列出二維陣列，使用二維陣列，列出二維陣列，並求各列數字的和並求各列數字的和p例題例題 ko3_6 使用二維陣列，計算二個陣列使用二維陣列，計算二個陣列之乘積之乘積 先介紹二個陣列乘積之算法先介紹二個陣列乘積之算法11 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures二維陣列位址的配置二維陣
8、列位址的配置 p二維陣列位置的配置可分為二維陣列位置的配置可分為 以列為主陣列位置的配置以列為主陣列位置的配置 以行為主陣列位置的配置以行為主陣列位置的配置通常都是以列為主陣列位置的配置通常都是以列為主陣列位置的配置12 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures以列為主陣列位址配置以列為主陣列位址配置p假設每一個變數佔了假設每一個變數佔了2個位元組的空間，個位元組的空間，y行內有行內有個元素個元素13 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures以列為主陣列位址配
9、置以列為主陣列位址配置p若若 Loc(A00)=m，而且以列為主陣列位，而且以列為主陣列位置的配置方式，則置的配置方式，則Axy記憶體位置的公記憶體位置的公式如下：式如下：Loc(Axy)=m+d(x+y)(公式公式3-2)其中其中代表代表 y 行內有行內有個元素，個元素，d 代表每一代表每一個變數佔了個變數佔了 d 個位元組的空間。個位元組的空間。14 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresP.81例：例：有一個二維陣列有一個二維陣列A，假設，假設A11與與A33的位址分別為的位址分別為644與與676，求，求A44的位址
10、為若干？的位址為若干？pLoc(A11)=644=m+d(+1).(1)Loc(A33)=676=m+d(3+3).(2)(1)x3-(2)得得2m=1256m=628.(3)d(+1)=16.(4)將將(3)(4)代入代入Loc(A44)=m+d(4+4)=m+4d(+1)=628+4x16=69215 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures以行為主陣列位址配置以行為主陣列位址配置p假設每一個變數佔了假設每一個變數佔了2個位元組的空間，個位元組的空間，x列內有列內有個元素個元素16 樹德科技大學樹德科技大學 資訊管理系資訊
11、管理系 Data StructuresData Structures以行為主陣列位址配置以行為主陣列位址配置p若若Loc(A00)=m，而且以行為主陣列位，而且以行為主陣列位址的配置方式，則址的配置方式，則 Axy記憶體位址的記憶體位址的公式如下：公式如下：Loc(Axy)=m+d(y+x).(公式公式3-3)其中其中代表代表x列內有列內有個元素，個元素，d代表每一代表每一個變數佔了個變數佔了d個位元組的空間。個位元組的空間。17 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresP.83例：例：有一個以行為主的二維陣列有一個以行為主的
12、二維陣列 Axy，A32的位址是的位址是 1111，A23的位址為的位址為 1116。若每。若每一個元素佔了一個元素佔了1個位元組，求個位元組，求A14的位址為若的位址為若干？干？p已知已知d=1根據公式根據公式3-3 Loc(Axy)=m+d(y+x)得知：得知：Loc(A32)=1111=m+(2 +3).(1)Loc(A23)=1116=m+(3 +2).(2)(2)-(1)得得 5=-1，求得，求得=6.(3)(3)代入代入(1)求得求得 m=1096Loc(A14)=m+d(y+x)=1096(4 6+1)=112118 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data St
13、ructuresData Structures多維陣列位址的配置多維陣列位址的配置 p以列為主陣列位址的配置以列為主陣列位址的配置加設有一三維陣列加設有一三維陣列 Azyx，A000的的位址為位址為m，每一個元素佔了，每一個元素佔了d個位元組，個位元組，則則 Aabc的位址為：的位址為：Loc(Aabc)=m+d(ayx+bx+c)(公式公式3-4)19 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresP.85例：例：設有一三維陣列設有一三維陣列A234中，陣列元素中，陣列元素A111在主記憶體中之位址為在主記憶體中之位址為3000，
14、且一個元，且一個元素佔一個位元組，以列為主排列時，陣列元素素佔一個位元組，以列為主排列時，陣列元素A213之位址為何？之位址為何？p已知三維陣列已知三維陣列A234(z=2,y=3,x=4)，每一個元，每一個元素佔一個位元組，素佔一個位元組，d=1。根據公式。根據公式 3-4 知知 Loc(A111)=m+d(ayx+bx+c)=m+1(1 3 4+1 4+1)=m+17=3000，得，得m=2983Loc(A213)=m+d(ayx+bx+c)=2983+1(2 3 4+1 4+3)=2983+24+4+3 =304120 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data Struc
15、turesData Structures多維陣列位址的配置多維陣列位址的配置p以行為主陣列位址的配置以行為主陣列位址的配置假設有一三維陣列假設有一三維陣列Azyx，A000的的位址為位址為m，每一個元素佔了，每一個元素佔了d個位元組，個位元組，則則Aabc的位址為：的位址為：Loc(Aabc)=m+d(czy+bz+a)(公式公式3-5)21 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresP.85例：例：設有一三維陣列設有一三維陣列A234中，陣列元素中，陣列元素A111在主記憶體中之位址為在主記憶體中之位址為3000，且一個元，且
16、一個元素佔一個位元組，以行為主排列時，陣列元素素佔一個位元組，以行為主排列時，陣列元素A213之位址為何？之位址為何？p已知三維陣列已知三維陣列A234(z=2,y=3,z=4)，每一個元素佔一個，每一個元素佔一個位元組，位元組，d=1。根據公式根據公式3-5知知Loc(A111)=m+d(czy+bz+a)=m+1(1 2 3+1 2+1)=m+9=3000，得，得m=2991Loc(A213)=m+dczy+bz+a =2991+1(3 2 3+1 2+2)=2991+18+2+2 =301322 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData St
17、ructures特殊矩陣特殊矩陣p稀疏矩陣稀疏矩陣 所謂稀疏矩陣是指矩陣中的元素大多數為所謂稀疏矩陣是指矩陣中的元素大多數為0。擁有多。擁有多少個零元素才稱得上稀疏矩陣，並沒有明確的少個零元素才稱得上稀疏矩陣，並沒有明確的定義。定義。23 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structuresp以二維陣列來儲存此稀疏陣列，地以列用來儲以二維陣列來儲存此稀疏陣列，地以列用來儲存稀疏矩陣的列數、行數以及非零元素數，第存稀疏矩陣的列數、行數以及非零元素數，第二列一後用來儲存稀疏矩陣的非零元素所在的二列一後用來儲存稀疏矩陣的非零元素所在的位址及其值
18、，此法稱為行列索引表示法位址及其值，此法稱為行列索引表示法24 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData StructuresP.90例：例：一個一個mxn的整數矩陣的整數矩陣(Matrix)，其中有，其中有k個個非零的值。如果用陣列儲存這個非零的值。如果用陣列儲存這個Sparse Matrix的的k值。需要多少個記憶體？值。需要多少個記憶體？(A)k(B)2k+1(C)3(k+1)(D)4kp依據圖依據圖3-6，總共非零元素有，總共非零元素有8個，存放稀個，存放稀疏矩陣的記憶體空間疏矩陣的記憶體空間=3*(8+1)=27因此，答案應為因此，答案應
19、為(C)3(k+1)25 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures下三角形矩陣下三角形矩陣p正方形矩陣正方形矩陣Axy其對角線以上的元素均其對角線以上的元素均為為0。xy，Axy=0 26 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures下三角形矩陣位置配置下三角形矩陣位置配置p以列為主以列為主 1AX00 1 1110-AXA22A21A20A11A10A00AxyYXAXAXAXXAXAp Loc(Axy)=Loc(A00)+(1+x)x/2+y (公式公式3-8
20、)例題例題 ko3_7(下三角型以列為主的位址配置，二維陣列轉下三角型以列為主的位址配置，二維陣列轉換成一維陣列換成一維陣列)27 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures下三角形矩陣以行為主下三角形矩陣以行為主 pLoc(Axy)=Loc(A00)+n(y-1)-y(y-1)/2+x(公式公式3-9)例題例題 ko3_8(下三角型以行為主的位址配置，二維陣列下三角型以行為主的位址配置，二維陣列轉換成一維陣列轉換成一維陣列)28 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Struc
21、tures上三角形矩陣上三角形矩陣 pxy，Axy=0 29 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures上三角形矩陣以列為主上三角形矩陣以列為主pLoc(Axy)=Loc(A00)+n(x-1)-x(x-1)/2+y(公式公式3-10)例題例題 ko3_9(以上三角型矩陣以列為主的位址配以上三角型矩陣以列為主的位址配置，二維陣列轉換成一維陣列置，二維陣列轉換成一維陣列)30 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures上三角形矩陣以行為主上三角形矩陣以行為主 pLo
22、c(Axy)=Loc(A00)+y(y-1)/2+x(公式公式3-11)例題例題 ko3_10(以上三角型以行為主的位址配置，以上三角型以行為主的位址配置，二維陣列轉換成一維陣列二維陣列轉換成一維陣列)31 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures多項式陣列多項式陣列 p使用使用n+2長度的陣列長度的陣列a儲存多項式儲存多項式f(x)。pf(x)=7x3+4x+13。pA5=3，7，0，4，13。32 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures多項式陣列多項式陣
23、列 p以以a2p+1儲存多項式儲存多項式f(x)。pf(x)=7x3+4x+13。pA7=3，3，7，1，4，0，13。33 樹德科技大學樹德科技大學 資訊管理系資訊管理系 Data StructuresData Structures類別類別pJava語言的類別與陣列類似，可將一些語言的類別與陣列類似，可將一些資料組在一起。但是資料陣列的每一元資料組在一起。但是資料陣列的每一元素的資料型態必須一致；類別的每一元素的資料型態必須一致；類別的每一元素的資料型態不必一致。素的資料型態不必一致。p因此，陣列記憶體的空間也較類別記憶因此，陣列記憶體的空間也較類別記憶體的空間容易掌握。體的空間容易掌握。p例題例題ko3_11使用類別宣告各種資料型態使用類別宣告各種資料型態
