陣列(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] = I₀ + (i × n + j)×d
    • 若陣列A[5, 4]第一個元素為A[0, 0], I₀=1000，d=1，求A[3, 2]=?
      • A[i, j] = 1000 + (3 × 5 + 2) × 1 = 1017
  • 若第一個元素為A[1, 1]，位址公式為 ：
    • A[i,j] = I₀ + [(i-1) × n + (j-1)] × d
    • 若陣列A[6, 5]第一個元素為A[1, 1], I₀=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] = I₀ + (i + j × m )× d
    • 若陣列A[5, 4]第一個元素為A[0, 0], I₀=1000，d=1，求A[3, 2]=?
      • A[i,j] = 1000 + (3 + 2 × 6) × 1 = 1015
  • 第一個元素為A[1, 1]，位址公式為：
    • A[i,j] = I₀ + [(i-1) + (j-1) × m] × d
    • 若陣列A[6, 5]第一個元素為A[1, 1], I₀=1000，d=1，求A[4, 3]=?
      • A[i,j] = 1000 + [(4-1) + (3-1) × 6] × 1 = 1015

非0或1起始之二維陣列

• 由m1及m2起始：A[m₁:n₁, m₂:n₂] of data
  • 共n₁-m₁+1列，n₂-m₂+1行
  • 位址計算公式與第一個元素為A[1, 1]的公式雷同
    • 將1替換成m₁及m₂
    • 列數m改為 (n₁ - m₁ + 1)
    • 行數n改為 (n₂ - m₂ + 1)
• Row-Major：
  • A[i,j] = I₀ + [(i-m₁) × (n₂ - m₂ + 1) + (j - m₂)] × d
  
• Column-Major：
  • A[i,j] = I₀ + [(i - m₁) + (j-m₂) × (n₁ - m₁ + 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, I₀ = 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] = I₀ + [(j-1)×m + (i-1)]×d，求I₀和列數
    • A[3, 2] = I₀ + [(2-1) × m + (3-1) ] × 1 = I₀ + m + 2 = 1110
      • 1108 = I₀ + m ----- (1)
    • A[5, 4] = I₀ + [(4-1) × m + (5-1) ] × 1 = I₀ + 3m + 4 = 1116
      • 1112 = I₀ + 3m ---- (2)
    • 由(2) - (1) 可得 4 = 2m m = 2
    • 將m = 2代入(1)可得I₀ = 1106
    • I₀ = 1106, m = 2
  • 代入公式A[i,j] = I₀ + [(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] = I₀ + [(i - m₁) + (j - m₂) × (n₁ - m₁ + 1)] × d，求I₀和列數
    • A[3, 5] = I₀ + [(3-(-1)) + (5 - 2)×(m - (-1) + 1) ] × 2 = I₀+[4 + 3 ×(m+2)]× 2
      • 1050 = I₀ + 6m + 20 1030 = I₀ + 6m --- (1)
    • A[5, 3] = I₀ + [(5-(-1)) + (3 - 2)×(m - (-1) + 1) ] × 2 = I₀ + [6 + 1 × (m+2)] × 2
      • 1026 = I₀ + 2m + 16 1010 = I₀ + 2m --- (2)
    • 由(1)-(2)可知20 = 4m m = 5
    • 將m=5代入(1) 1050 = I₀ + 6×5 + 20 I₀ = 1000
  • 將I₀=1000，m=5代入公式A[i,j] = I₀ + [(i - m₁) + (j - m₂) × (n₁ - m₁ + 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 , ∴ I₀=2
  • 代入公式A[i,j] = I₀ + [(i-1)×n + (j-1)]×d，求出n和d
    • ａ[2, 3] = 2 + [(2-1)×n + (3-1)]×d = 2 + nd + 2d = 18 nd + 2d = 16 --- (1)
    • ａ[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] = I₀ + [(i-1)×n + (j-1)]×d
    • ａ[2, 3] = 2 + [(4-1)×6 + (5-1)]×2 = 46