[資料結構(Data Structure, DS)] 陣列(Array)

陣列介紹

• 一群相同型態資料的有序集合
• 特性：
  • 元素的型態需一致
  • 一種有序串列
  • 佔用連續的記憶體空間
  • 用索引值及共同的名稱(陣列名稱)存取資料
  • 支援循序(Sequential)及隨機(Random)存取
  • 插入、刪除元素較複雜
    • 需挪移其它元素，不易動態增刪空間
    • 假設有n個元素，對第一個位置插入需挪移n個元素，對第二個位置插入需挪移n-1個元素
    • 平均挪移次數=(n +(n-1) + ... + 1) / n = n(n-1)/2 × 1/n = (n+1)/2 = Ο(n)

陣列的抽象資料型態 (ADT of Array)

• Data：
  • 成對<index, value>的集合
  • 每個索引(index)都有對應的值(value)
  • index是一維或多維的有限有序集合
  • 
    一維：{ 0, 1, ...., n - 1}
    二維：{(0, 0), (0, 1), (0, 2), (1, 0), (1,1), (1,2), (2, 0), (2, 1), (2, 2)}
• Operation：
  • ∀A ∈ Array, i ∈ index, x ∈ item, j ∈ Integer, size ∈ Integer
  • Create(j, list)：
    • return一個j維陣列
    • list是j個位元的集合
    • list的第i個元素，代表第i維的大小
    • 陣列元素的value都尚未定義
  • Item Retrive(A, i)：取值

    if ( i ∈ index)
        return 陣列A中，索引值為i的關聯項目
    else
        return 錯誤
    

  • Array Store(A, i, x)：指派值

    if( i is in index)
        return 插入<i, x>後的A陣列
    else
        return 錯誤