資結/演算法

陣列 (Array) 簡介

陣列 (Array),又稱數組,為一資料結構 (Data Structure),
是用來儲存一群『相同資料型態 [註1] 的元素 (element)』之串列。
通常 佔用 連續的 (consecutive) 記憶體位置 (memory location)。
 
每個元素,會有一類似編號的東西,
與之循序對映 (sequential mapping),稱為 索引 (index)
 

Photo by Roman Drits
 
[註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]。
 

 
 

位址計算

計算二維 (多維) 陣列位址,普遍的兩種方式:

  1. 以列為主 (Row-major)
  2. 以行為主 (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 的複雜度分析表!
Common Data Structure
 
 

作者: 鄭中勝

喜愛音樂,但不知為何總在打程式 ?
期許能重新審視、整理自身所學,幫助有需要的人。

發表迴響