Array

• 為表示有序串列之一種方式
• 其佔用連續性的記憶體空間
• 各元素型態皆需相同 (一致)
• 支援 Sequential Sequential 及 Random Access Random Access
• 插入、刪除元素較為麻煩
  • ∵ 需挪移其它元素
  • ∴ 不易動態增刪空間大小
  • Time = O(n)

N維陣列

N維陣列儲存在主記憶體中的方式有兩種:

• Row-major
• Column-major

一般化宣告

宣告: A[1: , 1: , 1: , …, 1: ], 起始位址為: , 元素大小: d

議題(2維為例)

• 給予所有宣告，求A[i, j]之location
• 給予兩個已知位置，求A[i, j]之location
  • 須自行判斷出Row或Column-major
• 給予兩個已知位置，但判斷出Row或Column-major皆有可能，求A[i, j]之location
• 給予三個已知位置量，求A[i, j]之location

多項式

1. 按照指數由高到低，依序儲存係數
2. 儲存非零項次的係數與指數

稀疏矩陣 (Sparse Matrix)

1. 利用 m x n 的二維陣列
2. 利用3-tuple來儲存非零元素 補充： Column-major 也可以

下三角矩陣 (Lower Triangular Matrix)

上三角矩陣 (Upper Triangular Matrix)

對稱矩陣 (Symmetric Matrix)

參考資料

國立聯合大學陳士杰資料結構