陣列(Array) 簡介 - NotFalse 技術客-

陣列(Array)，又稱數組，為一資料結構(Data Structure)， 是用來儲存一群『相同資料型態 [註1] 的元素(element)』之串列。

跳至主內容區陣列(Array)，又稱數組，為一資料結構(DataStructure)，是用來儲存一群『相同資料型態[註1]的元素(element)』之串列。

通常佔用連續的(consecutive)記憶體位置(memorylocation)。

 每個元素，會有一類似編號的東西，與之循序對映(sequentialmapping)，稱為索引(index)。

 PhotobyRomanDrits [註1]:相同資料型態，又稱為同質的homogeneous[͵homəˋdʒinɪəs]。

  目錄隨機存取(RandomAccess)存取原理插入&刪除(Insertion&Deletion)一維陣列(One-dimensionalArray)位址計算二維陣列(Two-dimensionalArray)位址計算Row-majorJava沒有多維陣列！總結More隨機存取(RandomAccess)不同於循序存取(sequentialaccess)的鏈結串列(LinkedList)：『(單向)鏈結串列』其元素通常散落於不連續記憶體位置，且A元素只認識B元素，B元素只認識C元素…，要找到Z元素便只能一一尋訪(A->B->C…>Z)，時間複雜度:O(n)。

 而陣列(Array)是置於連續的記憶體位置，藉由其索引們(indices)的計算，可得出任一元素的所在位址(address)，以達成隨機存取(RandomAccess)，使其存取元素的時間複雜度為O(1)！！(當然，也支援循序存取) 例:一個儲存『顏色』的陣列，將其命名為a:  其儲存於『連續的記憶體位置』中(假設每個Color大小為4bytes)：   藉由計算『索引(Index)』來存取元素，而不需一個一個地尋訪。

想取得『Red』，只要透過索引值『1』即可:  存取原理已知a[0]位址為0x7FAA0，則a[1]為0x7FAA0+4=0x7FAA4(假設每個Color大小為4bytes)，透過該位址，即可取得該元素。

 由此可知，計算陣列的記憶體位址(address)尤其重要，將於後幾節提及。

我們常說的RAM(隨機存取記憶體RandomAccessMemory)即是類似的概念。

  許多人認為索引很不直覺，為何第一個元素的索引，為『0』，而不是『1』? 索引(Index)，可想成是陣列的偏移量/差量(offset)，『第一個元素』自然沒有偏移囉!這也是為何，索引通常皆為無號整數(非負整數)。

  插入&刪除(Insertion&Deletion)然而，相較於其他資結(e.g.,鏈結串列)，陣列若想插入、刪除一個元素，較不方便。

因為需挪移其他元素，插入/刪除時間複雜度為O(n)。

 例如，欲插入(Insert)一元素『綠色』至a[1]。

 得把『紅色』、『黃色』往後移動，還得考慮是否已超過陣列大小，否則，可能會導致陣列索引值超出範圍例外(ArrayIndexOutOfBoundsException)。

 反之，若想刪除某元素，得把其他元素往前挪動:  一維陣列(One-dimensionalArray)陣列，可以是一維、二維…多維(維度Dimension)陣列，維度，是指定某點(物)所需的最小座標數，也就是我們常說的『點』、『線』、『面』啦~分別對應零維、一維、二維。

 上述範例中，如『顏色』陣列般的線性資料，即是一維陣列囉！  位址計算前面提及了，計算陣列記憶體位址的重要性，一維陣列的計算公式如下:一陣列A(L:μ)，有n個元素，其初始索引為L[註2]，陣列的基底位址為L0，每個元素大小為d，則A[i]之位址=L0+(i–L)*d，其中，n=μ–L+1。

   例:有一int陣列A，有200個元素，其初始索引為10，基底位址為9007，每個元素大小為4bytes，求A[130]之位址? Ans:A[130]之位址=9007+(130–10)*4=9487#  [註2]:考題不一定會給初始索引，且有些預設為『0』，有些為『1』，需多加注意!  二維陣列(Two-dimensionalArray)二維陣列，即是藉由行與列[註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)，稱為byteaddressing。

 當二維陣列放入記憶體，便需要計算其位址，以供存取陣列元素啦😆。

  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]將拋出陣列索引值超出範圍例外(ArrayIndexOutOfBoundsException)。

  這在C語言中(以下的宣告方式)，並不被允許，其嚴格的規範子陣列的長度(當然，也能自行實踐陣列in陣列)。

 ex:C宣告二維陣列:inta[2][4]={ {3,3,0}, {9,5,2,7} }; 由於子陣列的長度會固定，透過索引a[0][3]將會取得預設值0，而非拋出例外。

  許多人認為:『連續的記憶體』只是陣列最常見的作法，(因此，本文最上方介紹『連續』時，用了通常二字)並不能說『陣列的陣列』就不是多維陣列。

 其實，平常溝通聽得懂就ok啦！若要嚴格討論實作方式，才加以區別😃。

  總結陣列可說是最簡單、也最重要的資料結構，它可用來表示方程式、矩陣…，也時常做為其他資結的構成基礎(e.g.,堆疊、佇列、完整二元樹)。

 礙於篇幅，本篇不進一步探討，未來再補充陣列的使用與實作😀。

 最後，附上bigocheatsheet的複雜度分析表！  分享此文：分享到Twitter(在新視窗中開啟)按一下以分享至Facebook(在新視窗中開啟)按一下以分享到Google+(在新視窗中開啟)分享到Pocket(在新視窗中開啟)More作者:鄭中勝喜愛音樂，但不知為何總在打程式? 期許能重新審視、整理自身所學，幫助有需要的人。

文章導覽列⟵進制簡介(二進制、八進制、十進制、十六進制)電腦常見單位:bit、bps、byte、octet、word、KB、KiB…⟶在《陣列(Array)簡介》中有2則留言講解地太清楚了！！請受我一拜！回覆自動引用通知:Array–BenHuang’sNotes發表迴響取消回覆搜尋關鍵字:適用電子郵件訂閱網站輸入你的電子郵件地址訂閱網站的新文章，使用電子郵件接收新通知。

電子郵件位址分類分類選取分類HTTP  (26)TCP/IP  (11)WEB開發  (5)未分類  (2)計算機組織/概論  (6)設計模式/原則  (7)資結/演算法  (6)PopularRecent標籤AJAXArrayAsync/AwaitChecksumCORSGoFIoC/DIjQueryLiskov替代原則MemorydumpMSSmtuPub/SubrwndSACKSocketSOLIDstacksyncvs.asyncVueword一的補數介面導向程式設計位元依賴倒置原則函式呼叫同源政策單一職責原則回調函式多型多載存取範圍工廠方法模式延遲確認快速重送滑動視窗箭頭函式覆寫觀察者模式記憶體設計原則設計模式進制遞迴開閉原則