陣列(Array)
二維陣列
- 由1起始,A[1:m, 1:n] of data,也可寫作A[m, n]
- m列(Row), n行(Column), m×n個空間
記憶體中的儲存方式:
以列為主(Row-Major)
- 若第一個元素為A[0, 0],位址公式為:
- A[i,j] = I0 + (i × n + j)×d
- 若陣列A[5, 4]第一個元素為A[0, 0], I0=1000,d=1,求A[3, 2]=?
- A[i, j] = 1000 + (3 × 5 + 2) × 1 = 1017
- 若第一個元素為A[1, 1],位址公式為 :
- A[i,j] = I0 + [(i-1) × n + (j-1)] × d
- 若陣列A[6, 5]第一個元素為A[1, 1], I0=1000,d=1,求A[4, 3]=?
- A[i,j] = 1000 + [(4 - 1) × 5 + (3 - 1)] × 1 = 1017
以行為主(Column-Major)
- 若第一個元素為A[0, 0],位址公式為:
- A[i,j] = I0 + (i + j × m )× d
- 若陣列A[5, 4]第一個元素為A[0, 0], I0=1000,d=1,求A[3, 2]=?
- A[i,j] = 1000 + (3 + 2 × 6) × 1 = 1015
- 第一個元素為A[1, 1],位址公式為:
- A[i,j] = I0 + [(i-1) + (j-1) × m] × d
- 若陣列A[6, 5]第一個元素為A[1, 1], I0=1000,d=1,求A[4, 3]=?
- A[i,j] = 1000 + [(4-1) + (3-1) × 6] × 1 = 1015
非0或1起始之二維陣列
- 由m1及m2起始:A[m1:n1, m2:n2] of data
- 共n1-m1+1列,n2-m2+1行
- 位址計算公式與第一個元素為A[1, 1]的公式雷同
- 將1替換成m1及m2
- 列數m改為 (n1 - m1 + 1)
- 行數n改為 (n2 - m2 + 1)
- Row-Major:
- A[i,j] = I0 + [(i-m1) × (n2 - m2 + 1) + (j - m2)] × d
- Column-Major:
- A[i,j] = I0 + [(i - m1) + (j-m2) × (n1 - m1 + 1)] × d
二維陣列相關問題
- 給2個元素的位置及位址,判斷是Row-Major或Column-Major的方法
- Row-Major時,列數較大的元素 位址必較大
- Row-Major時,列數較小的元素 位址必較小
- Column-Major時,行數大的元素 位址必較大
- Column-Major時,行數小的元素 位址必較小
- 若給定的元素 ,其中一元素的列數、行數、位址皆大於或小於另一元素 無法判斷為Row-Major或Column-Major
- 令A[3, 5] = 14, A[5, 3] = 22
- 比較位址及列數:14 < 22, 3 < 5 Row-Major
- 令A[3, 5] = 14, A[5, 3] = 10
- 比較位址及行數:14 > 10, 5 > 3 Column-Major
- 令A[3, 5] = 14, A[5, 7] = 33
- 比較位址、列數、行數:14 < 30, 3 < 5, 5 < 7 無法判斷
- A[-3:7, -4:8],元素大小為2, I0 = 10,採Row-Major,求A[3, 4]的位址
- 有7-(-3)+1 = 11列, 8-(-4)+1 = 13行
- A[3, 4] = 10 + [ (3-(-3) × ( 8 - (-4) +1 ) + (4 - (-4) ) ] × 2 = 182
- A[3, 2]的位址是1110,A[5, 4]的位址為1116,元素大小為1,第一個元素為A[1, 1],求A[1,4]和A[5,4]的位址
- 判斷是Row-Major或Column-Major:
- 3<5, 2<4, 1110<1115 Column Major
- 利用公式 A[i,j] = I0 + [(j-1)×m + (i-1)]×d,求I0和列數
- A[3, 2] = I0 + [(2-1) × m + (3-1) ] × 1 = I0 + m + 2 = 1110
- A[5, 4] = I0 + [(4-1) × m + (5-1) ] × 1 = I0 + 3m + 4 = 1116
- 由(2) - (1) 可得 4 = 2m m = 2
- 將m = 2代入(1)可得I0 = 1106
- I0 = 1106, m = 2
- 代入公式A[i,j] = I0 + [(j - 1) × m + (i-1)] × d,求A[1,4] A[5,4]
- A[1 ,4] = 1106 + [ (4-1) × 3 + (1-1) ] × 1 = 1115
- A[5, 4] = 1106 + [(4-1) × 3 + (5-1) ] × 1 = 1119
- 陣列A[-1:m, 2:n],A[5,3]的位址是1026,A[3, 5]的位址為1050,元素大小為2,求A[2,7]的位址
- 判斷是Row-Major或Column-Major:
- 5>3, 3<5, 1026<1050 Column Major
- 用A[m1:n1, m2:n2]的公式A[i,j] = I0 + [(i - m1) + (j - m2) × (n1 - m1 + 1)] × d,求I0和列數
- A[3, 5] = I0 + [(3-(-1)) + (5 - 2)×(m - (-1) + 1) ] × 2 = I0+[4 + 3 ×(m+2)]× 2
- 1050 = I0 + 6m + 20 1030 = I0 + 6m --- (1)
- A[5, 3] = I0 + [(5-(-1)) + (3 - 2)×(m - (-1) + 1) ] × 2 = I0 + [6 + 1 × (m+2)] × 2
- 1026 = I0 + 2m + 16 1010 = I0 + 2m --- (2)
- 由(1)-(2)可知20 = 4m m = 5
- 將m=5代入(1) 1050 = I0 + 6×5 + 20 I0 = 1000
- 將I0=1000,m=5代入公式A[i,j] = I0 + [(i - m1) + (j - m2) × (n1 - m1 + 1)] × d,求A[2,7]
- A[2, 7] = 1000 + [(2-(-1)) + (7 - 2)×(5-(-1) + 1) ]×2 = 1000 + [3+5×7 ]×2 = 1076
- A[1, 1]的位址是2,A[2, 3]的位址為18,A[3, 2]的位址為28,求A[4, 5]的位址
- 判斷是Row-Major或Column-Major:
- 2 < 3, 3 > 2, 18 < 28 Row-Major
- 因為A[1, 1] = 2 , ∴ I0=2
- 代入公式A[i,j] = I0 + [(i-1)×n + (j-1)]×d,求出n和d
- a[2, 3] = 2 + [(2-1)×n + (3-1)]×d = 2 + nd + 2d = 18 nd + 2d = 16 --- (1)
- a[3, 2] = 2 + [(3-1)×n + (2-1)]×d = 2 + 2nd + d = 28 2nd + d = 26 --- (2)
- (1)×2 - (2) = 3d =6 d=2, n=6
- 將A[4, 5] 代入公式A[i,j] = I0 + [(i-1)×n + (j-1)]×d
- a[2, 3] = 2 + [(4-1)×6 + (5-1)]×2 = 46