陣列 (Array),又稱數組,為一資料結構 (Data Structure),
是用來儲存一群『相同資料型態 [註1] 的元素 (element)』之串列。
通常 佔用 連續的 (consecutive) 記憶體位置 (memory location)。
每個元素,會有一類似編號的東西,
與之循序對映 (sequential mapping),稱為 索引 (index)。
[註1]: 相同資料型態,又稱為 同質的 homogeneous [͵homəˋdʒinɪəs]。
目錄
隨機存取 (Random Access)
不同於 循序存取 (sequential access) 的 鏈結串列 (Linked List):
『 (單向) 鏈結串列 』其元素通常散落於不連續記憶體位置,
且 A 元素 只認識 B 元素,B 元素 只認識 C 元素…,
要找到 Z 元素便只能一一尋訪 (A->B->C…>Z),
時間複雜度: O(n) 。
而 陣列 (Array) 是置於 連續的 記憶體位置,
藉由其 索引們 (indices) 的計算,可得出任一元素的所在位址 (address),
以達成 隨機存取 (Random Access),使其 存取元素的時間複雜度為 O(1)!!
(當然,也支援 循序存取)
例:
一個儲存『顏色』的陣列,將其命名為 a:
其儲存於『連續的記憶體位置』中 (假設每個 Color 大小為 4 bytes):
藉由計算『索引 (Index)』來存取元素,而不需一個一個地尋訪。
想取得 『Red』,只要透過索引值 『1』即可:
存取原理
已知 a[0] 位址為 0x7FAA0,
則 a[1] 為 0x7FAA0 + 4 = 0x7FAA4 (假設每個 Color 大小為 4 bytes),
透過該位址,即可取得該元素。
由此可知,
計算陣列的記憶體位址 (address) 尤其重要,將於後幾節提及。
我們常說的 RAM (隨機存取記憶體 Random Access Memory) 即是類似的概念。
許多人認為 索引 很不直覺,
為何第 一 個元素的 索引 ,
為 『0』,而不是 『1』?
索引 (Index),可想成是陣列的 偏移量/差量 (offset),
『第一個元素』自然沒有偏移囉!
這也是為何,索引 通常皆為無號整數 (非負整數)。
插入 & 刪除 (Insertion & Deletion)
然而,相較於其他資結 (e.g., 鏈結串列),
陣列 若想插入、刪除一個元素,較不方便。
因為需挪移其他元素,插入/刪除 時間複雜度為 O(n)。
例如,欲插入 (Insert) 一元素 『綠色』至 a[1]。
得把『紅色』、『黃色』往後移動,還得考慮是否已超過陣列大小,
否則,可能會導致 陣列索引值超出範圍例外 (Array Index Out Of Bounds Exception)。
反之,若想刪除某元素,得把其他元素往前挪動:
一維陣列 (One-dimensional Array)
陣列,可以是一維、二維…多維 (維度 Dimension) 陣列,
維度,是指定某點 (物) 所需的最小座標數,
也就是我們常說的『點』、『線』、『面』啦~
分別對應 零維、一維、二維。
上述範例中,如『顏色』陣列般的線性資料,即是 一維陣列 囉!
位址計算
前面提及了,計算陣列記憶體位址的重要性,
一維陣列的計算公式如下:
一陣列 A( L : μ ) ,有 n 個元素,
其初始索引為 L [註2],
陣列的基底位址為 L0,每個元素大小為 d,
則 A[i] 之位址 = L0 + ( i – L ) * d,
其中,n = μ – L + 1 。
例:
有一 int 陣列 A,有 200 個元素,
其初始索引為 10 ,
基底位址為 9007,每個元素大小為 4 bytes,
求 A[130] 之位址?
Ans:
A[130] 之位址 = 9007 + (130 – 10) * 4 = 9487 #
[註2]:
考題不一定會給 初始索引,
且有些預設為 『0』,有些為『1』,需多加注意!
二維陣列 (Two-dimensional Array)
二維陣列 ,即是藉由行與列 [註3] 的方式,
將資料循序存取到連續記憶體中。
由於多了一個維度,
其需用兩個索引值,來對映一個元素,
這也使得相較於 一維,二維陣列 能夠處理更多『面向』的問題。
ex:
某一維陣列 a,存有班上三位同學的成績:
若有 3 個班級呢?
二維陣列就派上用場啦!
欲存取 乙班、1 號 同學的成績,即可透過 a["乙班"] [1] 的方式!
[註3]:
因翻譯問題、書寫習慣…,
台灣的 『行』與『列』 容易產生混淆,
『直行橫列』還是『橫行直列』各說各話。
為避免誤會:
Row ,以下稱為 『列』,方向為 『一』;
Column , 以下稱為『行』,方向為『 | 』,
索引的用法,如同矩陣 (matrix) 的概念,
第 i 列 、第 j 行的元素,表示為 a[i] [j]。
例:
一個儲存『動物』的二維陣列,將其命名為 a:
想存取 小雞雞,可以使用 a[1] [1],
想存取 小豬豬,可以使用 a[2] [0]。
位址計算
計算二維 (多維) 陣列位址,普遍的兩種方式:
- 以列為主 (Row-major)
- 以行為主 (Column-major)
其實,皆只是將二維陣列 轉換為 一維陣列的方式,
C、C++、C#… 等程式語言主要 (沒有一定) 採用 Row-major 的對應方式 ,
Fortran、OpenGL… 等,多採用 Column-major。
Row-major
以 Row-major 為例,顧名思義,
透過一列一列的方式,將二維陣列循序存入記憶體中,
Column-major 反之,不再累述。
一陣列 A( L1 : μ1 , L2 : μ2 ) ,有 m 列、n行,
陣列的基底位址為 L0,每個元素大小為 d,
則 A[i] [j]之位址 = L0 + ( i – L1 ) * (n * d) + ( j – L2 ) * d ,
其中,m = μ₁ – L₁ + 1 ,n = μ₂ – L₂ + 1 。
( i – L1 ) 用來算出所有的列數 ( A[i] [j] 此列 不算),
( n * d ) = n 行 * d (bytes) ,也就是此二維陣列 中,一列的 bytes 大小,
( j – L2 ) 算出 A[i] [j] 此元素 以左的行數。
但是,為何要轉為一維陣列呢?
如上述圖示:
我們可將 記憶體 視為一個很大的 一維 位元組 (bytes) 陣列!
每一位元組,皆有其 位址 (address),稱為 byte addressing。
當二維陣列放入記憶體,
便需要計算其位址,以供存取陣列元素啦 😆。
Java 沒有多維陣列!
至於 Java 提供的二維陣列,是使用 Row-major 還是 Column-major 呢?
兩者皆非
∵ Java 並沒有二維 (多維) 陣列!
你可能會認為:「蛤 下方不就是標準的 Java 二維陣列嗎 😑 ?」
Java 宣告二維陣列:
int[][] a = {
{3, 3, 0},
{9, 5, 2, 7}
};
對不起 我標題殺人 😂,一般來說,這的確稱二維陣列。
然而,嚴格來看,Java 只有一維陣列 無誤!
事實上不只 Java,許多語言的 二維 (多維) 陣列,
並非『連續』的記憶體位置,而是『陣列中的陣列』之概念。
也就是:
由多個 一維陣列 所組成
例:
下圖範例中,一 Java 二維陣列,命名為 a,
a[0] 存有指向 一維陣列 {3, 3, 0} 的參照 (reference),
a[1] 存有指向 一維陣列 {9, 5, 2, 7} 的參照。
有趣的是,Java 這樣的宣告方式,允許子陣列的長度不相等:
一維陣列 {3, 3, 0} 長度為 3 ;
一維陣列 {9, 5, 2, 7} 長度為 4。
透過索引:
a[0][0] 可取得 3, a[0][1] 可取得 3, a[0][2] 可取得 0,
a[0][3] 將拋出 陣列索引值超出範圍例外 (Array Index Out Of Bounds Exception)。
這在 C 語言中 (以下的宣告方式),並不被允許,
其嚴格的規範 子陣列的長度 (當然,也能自行實踐 陣列in陣列)。
ex:
C 宣告二維陣列:
int a[2][4] = {
{3, 3, 0},
{9, 5, 2, 7}
};
由於子陣列的長度會固定,
透過索引 a[0][3] 將會取得 預設值 0,而非拋出例外。
許多人認為:『連續的記憶體』只是 陣列 最常見的作法,
(因此,本文最上方介紹『連續』時,用了 通常 二字)
並不能說 『陣列的陣列』就不是多維陣列。
其實,平常溝通聽得懂就 ok 啦!
若要嚴格討論實作方式,才加以區別 😃。
總結
陣列 可說是最簡單、也最重要的資料結構,
它可用來表示方程式、矩陣…,
也時常做為其他資結的構成基礎 (e.g., 堆疊、佇列、完整二元樹)。
礙於篇幅,本篇不進一步探討,
未來再補充 陣列的使用與實作 😀。
最後,附上 bigocheatsheet 的複雜度分析表!
在《陣列 (Array) 簡介》中有 2 則留言
講解地太清楚了!!
請受我一拜!