我們前面學了複雜度、Big O、遞迴，接下來就要開始接觸比較實際的資料結構了 !

第一個要認識的就是陣列(Array)

什麼是陣列?

陣列結構是 一排連續的可數記憶體，用來存取相同類型的元素，每個元素都有一個索引(index)來存取。

陣列在程式裡非常常見，假設今天有很多 同種類型 的資料需要儲存，與其宣告一堆變數，不如直接使用陣列

一維陣列

假設今天有個大小為 n 的陣列叫做 array[n]，index的值從 0 開始，總共有 n 個元素，那 index的範圍是 0 ~ n-1

陣列宣告

int arr[5]; //資料型態 陣列名稱[大小]

初始化陣列

int arr[5]={1,2,3,4,5};
int array[5]={0}; //全部都是0

存取

int value = arr[2]; // 根據上面的arr宣告，value==3

搜尋(search)
在不知道索引的情況下，只能一個一個找，O(n)

int search(int arr[],int n,int target){
    for(int i=0;i<n;i++){
        if(arr[i]==target) return i; //找到回傳索引
    }
    
    return -1; //找不到
}

插入陣列(insert)
在陣列中插入，因為陣列是連續記憶體，插入位置後面的元素要 全都往後搬一格，O(n)

//insert(陣列，大小，插入的位置(索引)，要插入的值)

void insert(int arr[], int& n, int pos, int value) {
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];   // 從尾端開始,依序往後搬
    }
    arr[pos] = value;
    n++;  // 陣列長度+1
}

例如

int arr[10] = {10, 20, 30, 40}; 
int n = 4;

insert(arr, n, 2, 25); //在arr[2]插入25

刪除(delete)
跟插入相反,刪除某個位置的元素後,後面的元素要往前搬一格補上空缺,O(n)

void remove(int arr[],int& n,int pos){
    for(int i=pos;i < n-1; i++){
        arr[i]=arr[i+1]; //後面元素往前搬
    }

    n-- //陣列長度-1
}

二維陣列

二維陣列和一維陣列的概念其實一樣，我就直接用圖和程式碼來解說好了

int arr[3][4]; //arr[row][column]

宣告並初始化：

int arr[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

存取

cout << arr[1][2];

6 //output

走訪二維陣列

通常會使用兩層迴圈：

int arr[2][3]={1,2,3,4,5,6}
for(int i=0;i<2;i++){
    for(int j=0;j<3;j++){
        cout<<arr[i][j]<<" ";
    }
    cout<<'\n';
}

三維陣列

三維陣列可以想像成很多個二維陣列疊在一起
如下圖 :

宣告

int arr[3][3][4];

存取

arr[1][2][3];

-> 第一層 第二列(row) 第三行(column)
不過在一般程式設計中，比較常用的是一維和二維陣列，三維以上較少見。

陣列的常見應用

字串(String)

字串本質上就是字元(char)陣列,只是最後通常會多存一個結尾符號 \0
標示字串結束:

char str[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

字元一樣是連續存放,一樣可以用位址公式直接存取第 i 個字元,邏輯跟一般陣列完全相同。

陣列的記憶體位置怎麼算?

一維陣列

假設有一個陣列 arr,起始位址是 α(代表 arr[0] 存放的位址),
每個元素佔用 d bytes(例如 int 通常是 4 bytes),
那麼第 i個元素 arr[i] 的位址公式是:

Loc(arr[i])=α+i×d

來實際算算看:
假設 int arr[5],起始位址 α=1000,int 佔 d = 4bytes,那麼:

二維陣列

電腦的記憶體本質上是線性排列的,所以二維陣列 arr[m][n] (m 列 n 行)實際上還是要攤平成一維空間存放,方式有兩種:

1. Row-Major(以列為主,大部分語言採用,例如 C/C++)

   先把第 0 列存完,再存第 1 列……依此類推。要找 arr[i][j] 的位址:

   Loc(arr[i][j])=α+(i×n+j)×d

2. Column-Major(以欄為主,例如 Fortran)

   反過來,先把第 0 行存完,再存第 1 行:

   Loc(arr[i][j])=α+(j×m+i)×d

實際算一次

假設 int arr[3][4](3 列 4 行),起始位址 α=2000,int 佔 4 bytes,採用 Row-Major,要找 arr[2][1] 的位址:

Loc(arr[2][1])=2000+(2×4+1)×4=2000+9×4=2036

常見操作時間複雜度

題目練習

1. 已知陣列 arr[20],起始位址 α=2000,每個元素佔 8 bytes,求 arr[15] 的位址。

2. 已知 arr[6][8],起始位址 α=0 ,採用 Row-Major,已知 arr[2][5] 的位址是 168,請問每個元素佔多少 bytes?

明天我們會帶到 leetcode的簡單題目!
原本想放這篇結果發現寫太多這樣每篇不能平均分配字數
然後畫圖的時間比寫的時間還多
btw 最近看了吉伊卡哇電影版，推薦大家去看~

參考資料和書籍

1. 圖解資料結構×演算法:運用C++ 胡昭明
2. https://noob.tw/data-structure-array/
3. https://notfalse.net/15/array-intro
4. https://medium.com/@simiao-it/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-1-%E9%99%A3%E5%88%97-array-dd98d0cbc415
5. https://learn.microsoft.com/zh-tw/dotnet/csharp/language-reference/builtin-types/arrays
6. https://learn.microsoft.com/zh-tw/dotnet/visual-basic/programming-guide/language-features/arrays/array-dimensions