6.2 Array

陣列 Array

  • Def: array 用來表示 orderlist 的一種資料結構, 又可稱為 dense list 或 sequential list
  • 概念: 將 data 的第 i 格元素存到第 i 格子之中
  • 圖:
  • 特色: (選擇居多)
    1. 佔用連續的 mem. space
    2. array 中放置相同型態的元素, 沒有彈性
    3. 需事先宣告 array 大小, 沒有彈性
    4. 同時支援 random access (O(1)) 及 sequential access (O(n))

陣列儲存位址計算

  • 一維陣列
    1. 宣告方式1: A[1.....n]
    2. 宣告方式2: A[l.....u]
    3. Ex: array: A(-3...9), l0 = 100, d = 4, 問 A[5] 之 location
    • Sol: l0 + (i - l) * d = 100 + ( 5-(-3)) * 4 = 132
  • 二維陣列
    1. 宣告方式1: A[1...m, 1...n] -> m列, n行
    • 計算 A[i, j] 之 location
      1. Row Major:
      • 公式: l0+[(i-l1)*(u2-l2+1)+(j-l2)]*d
      1. Column Major:
      • 公式: l0+[(j-l2)*(u1-l1+1)+(i-l1)]*d
    1. 宣告方式2: A[l1...u1, l2...u2] -> u1-l1+1列, u2-l2+1行
    2. Ex:
  • 常見題型
    1. 給定所有值, 求算 A[i, j] 之 location
    • Ex: array: A[-3....8, -5....14], l0=100, d=2, 問 A[3, 8] 之 location; 以 Row Major and Column Major
      Sol:
      1. Row Major
        = l0+[(i-l1)*(u2-l2+1)+(j-l2)]*d
        = 100+[(3-(-3))*(14-(-5)+1)+(8-(-5))]*2
        = 366
      2. Column Major
        = l0+[(j-l2)*(u1-l1+1)+(i-l1)]*d
        = 100+[(8-(-5))*(8-(-3)+1)+(3-(-3))]*2
        = 424
    1. 給予2個已知量: A[i1, j1], A[i2, j2], 求 A[i, j] 之 location
    • Note: 無法取得 l0, d, 而已知 A[i1, j1] < A[i2, j2], 則
      1. Row Major:
        A[i2, j2] = A[i1, j1] + [(i2-i1)*n+(j2-j1)]*1
      2. Column Major:
        A[i2, j2] = A[i1, j1] + [(j2-j1)*m+(i2-i1)]*1
    • Row Major 中可以推得 “行”, "列"不得而知
    • Column Major 中可以推得 “列”, "行"不得而知
    • Ex: A[4, 2] 之 address = 1978, A[2, 3] 之 address = 1986, 問 A[3, 8] 之 address = ?
      Sol: 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      // Step1: check Row Major or Column Major
      A[4, 2] = 1978
      A[2, 3] = 1986  // Column Major

      // Step2: 
      // 求 行 => 當為 Row Major, 可求得行數 
      // 求 列 => 當為 Column Major, 可求得列數 
      A[2, 3] = A[4, 2] + [(3-2) * m + (2-4)]*1
      1986 = 1978+m-2
      m = 10

      // Step3: 求 A[i, j]
      A[3, 8] = A[4, 2] + [(8-2)*10+(3-4)]*1
              = 1978+59
              = 2037
    1. 同題型2, 但無法判別 Row Major or Column Major
    • Ex: A[3, 3] 之 address = 121, A[6, 4] 之 address = 159, 問 A[4, 9] 之 address = ?
      Sol: 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      // Step1: check Row Major or Column Major
      A[3, 3] = 121
      A[6, 4] = 159  // Row Major or Column Major 皆有可能

      // Step2: 
      // 1. Row Major
      A[6, 4] = A[2, 2] + [(6-3) * n + (4-3)]*1
      159 = 121+3n+1
      n = 37/3 = 12.33333 //不符合

      // 2. Column Major
      A[6, 4] = A[2, 2] + [(4-3) * m + (6-3)]*1
      159 = 121+m+3
      m = 35 

      // Step3: 求 A[i, j], 以 Column Major
      A[4, 9] = A[3, 3] + [(9-3)*35+(4-3)]*1
              = 121+211
              = 332
  • 三維陣列
    • 宣告方式: A(1...u1, 1...u2, 1...u3)
    • 計算:
      1. Row Major A[i, j, k] 之 location
      • 公式: l0+[(i-1)*u2*u3+(j-1)*u3+(k-1)]*d
      1. Column Major A[i, j, k] 之 location
      • 公式: l0+[(k-1)*u2*u1+(j-1)*u1+(i-1)]*d

多項式的資料結構

  • 方法:
    1. 依指數由高 -> 低, 依序儲存其係數
    • Ex: 當多項式的最高係數為 n 時, 需準備 n+2 格
      -> 缺點: 若非0項極少時不適用, f(x) = 2^1000 +9 => k=2 => 準備 A[1...5]
    1. 只存放非零項次的係數與指數
    • 作法: 若非0項有 “k” 個 -> 準備 2k+1 個格子
    1. 利用 linked list 表示

特殊矩陣

稀疏矩陣

  • 指矩陣的非零項元素很少
  • Ex: 矩陣 A4x3
  • 3-turple
    • 說明: 準備一二維陣列 A(0...k, 1...3), 其中 k 代表非零項的數量
    • 以上例而言, k = 3, 故準備 A[0...3, 1...3]

上三角, 下三角矩陣

  • 說明:
    • 上三角: 即對角線以下的元素皆0, aij = 0, if i > j
    • 下三角: 即對角線以上的元素皆0, aij = 0, if i < j
  • 特色: 一 n * n 的上或下三角矩陣其元素共有:
1
2
3
4
5
6
7
1+2+...+n = n(n+1) / 2
=> 若採用 "二維陣列", 則
=> 浪費 space n^2-n(n+1)/2

Solution:
利用一維陣列 B[1....n(n+1)/2]
來將上 下三角之資料一一對應
  • 上三角
    • Row Major
    • Column Major
  • 下三角
    • Row Major
    • Column Major

對稱矩陣

  • 定義: 一矩陣 An*n: 若 Aij = Aji謂之, 有效率地存放方式, 只存上 or 下三角即可
  • 上三角: aij : k = j(j-1)/2 +i
  • 下三角: k = i()i-1/2 + i
  • 合併為單一公式: max(i, j) * (max(i, j)-1)/2 + min(i, j)
  • Ex: