記錄以下自己重溫數據結構的筆記，附帶自己實現的C代碼，
其中部分Python代碼是網上教程里的，順手粘貼過來，做一對比/
（Python確實簡潔，但是C更好理解不是嗎哈哈哈）

數組的定義

數組：線性表數據結構，利用一段連續的內存空間，存儲相同類型的數據
數組中的每個元素有唯一的下標索引
兩個角度理解數組：線性表結構，連續的內存空間，本質：采用順序存儲結構的線性表

隨機訪問數據元素

數組最顯著的特點：支持隨機訪問，就是通過下標直接定位并訪問任意一個元素
本質：第一個元素地址為首地址，每個元素都有唯一的下標和對應的內存地址，訪問數組元素時，利用下標通過尋址公式快速計算出目標元素的內存地址，實現高效訪問
尋址公式：下標 i 的元素地址 = 首地址 + i × 單個元素占用的字節數

多維數組

一般由m行n列的數據元素組成，本質上可理解為數組的數組，每個元素本身也是一個數組。
第一維表示行，第二維表示列。內存中，二維數組通常采用行優先或列優先的存儲方式。
二維數組常被視為矩陣，可用于處理如矩陣轉置、矩陣加法、矩陣乘法等問題。

數組在不同編程語言中的實現

不同編程語言中的數據實現存在一定差異。
C/C++中的數組最貼合其定義：他們使用一塊連續的內存空間來存儲相同類型的數據元素。
無論是基本數據類型，還是結構體、對象，在數組中都以連續方式排列。

int arr[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};

Java中的數組類似于C，但在多維數組的情況下，其允許創建不規則數組，即每個嵌套數組的長度可以不同。

int[][] arr = new int[3][];
arr[0] = new int[]{1, 2, 3};
arr[1] = new int[]{4, 5};
arr[2] = new int[]{6, 7, 8, 9};

Python使用“列表”這種容器類型，類似于Java中的ArrayList，通常將其作為數組使用，與傳統數組不同的是，Python不僅可以存儲不同類型的數據元素，長度也可以動態變化，并且支持豐富的內置方法。

arr = ['python', 'java', ['asp', 'php'], 'c']

數組的幾種基本操作

基本上，數組的操作主要涉及“增刪改查”四類，掌握這個就可以說掌握了數組的具體應用

訪問元素

假設我們要訪問數組中第 i 個元素：

1. 首先檢查下標 i 是否在合法范圍內，即 0 ≤ i ≤ len（nums）-1，超出該范圍屬于非法訪問
2. 如果下標合法，則可直接通過下標獲取對應元素的值
3. 如果下標不合法，則拋出異常或返回特殊值
4. 訪問數組元素不依賴于數組元素個數，因此其時間復雜度為O(1)
5. C語言不會在訪問時檢查數組下標是否越界，因此編程者必須自己確保索引在有效范圍內

int arr[10] = {1, 2, 3, 4, 56, 7, 89, 999};int main() {printf("the first number is %d\n", arr[3]);arr[3] = 8;printf("the second number is %d\n", arr[3]);return 0;
}

// 從數組 nums 中讀取下標為 i 的數據元素值
def get_element(nums: list[int], index: int):"""獲取數組中指定下標的元素值"""if 0 <= index < len(nums):return nums[index]else:raise IndexError(f"數組下標 {index} 超出范圍 [0, {len(nums)-1}]")//示例用法
arr = [0, 5, 2, 3, 7, 1, 6]
print(get_element(arr, 3))  # 輸出: 3

查找元素

查找數組中元素值為 val 的位置

1. 遍歷數組，將目標值與每個元素進行比較
2. 找到匹配元素時返回其下標
3. 遍歷完未找到時返回特殊值
4. 當數組無序時，查找元素只能通過將 val 與數組中的每個元素依次比較，這種方式稱為線性查找。由于需要遍歷整個數組，線性查找的時間復雜度為O(n)

int arrfind(int nums[], int size, int val) {for (int i = 0; i < size; i++) {if(nums[i] == val){return i;}}return -1;
}int arr[] = {1, 2, 3, 4, 56, 7, 89, 999};int main() {// 查找數組元素int arr_size = sizeof(arr);// sizeof(arr[0]);// 在arr數組中尋找元素3int i1 = arrfind(arr,arr_size,3);printf("num 5 index is: %d\n",i1);// 在arr數組中尋找元素15int i2 = arrfind(arr,arr_size,15);printf("num 15 index is: %d\n",i2);return 0;
}

def find_element(nums: list[int], val: int):"""查找數組中元素值為 val 的位置"""for i in range(len(nums)):if nums[i] == val:return ireturn -1示例用法
arr = [0, 5, 2, 3, 7, 1, 6]
print(find_element(arr, 5))  # 輸出: 1
print(find_element(arr, 9))  # 輸出: -1 (未找到)

插入元素

在數組的第 i 個位置插入值 val

1. 檢查 i 是否在數組范圍之內
2. 拓展數組長度，為新元素騰出空間
3. 將 i 及其之后的元素整體向后移動一位
4. 在 i 位置插入 val

bool insert_element(int arr[], int *currentSize, int maxSize, int index, int val) {// 檢查索引是否有效：必須在 0 到 currentSize 之間（含）// 注意：可以在末尾插入，即 index == *currentSizeif (index < 0 || index > *currentSize) {printf("錯誤：插入索引 %d 越界！有效范圍是 [0, %d]\n", index, *currentSize);return false;}// 檢查數組是否已滿if (*currentSize >= maxSize) {printf("錯誤：數組已滿，無法插入新元素！\n");return false;}// 【關鍵步驟】 從最后一個元素開始，逐個向后移動，為新元素騰出空間for (int i = *currentSize - 1; i >= index; i--) {arr[i + 1] = arr[i];}// 在指定位置插入新值arr[index] = val;// 更新數組的實際大小(*currentSize)++;return true;
}

改變元素

將數組中的第 i 個元素改為 val

1. 檢查 i 是否在數組長度之內
2. 將第 i 個元素值賦值為 val

// 改變數組指定的元素值
bool change_array(int arr[], int size, int index, int val)
{if (index < 0 || index >= size) {printf("錯誤：賦值索引 %d 越界！有效范圍是 [0, %d]\n", index, size);return false;}arr[index] = val;return true;
}

刪除元素

刪除數組中指定 i 位置的元素

1. 檢查下標 i 是否在合法的范圍內
2. 將 i + 1 位置及其之后的元素整體向前移動一位
3. 刪除最后一個元素（或更新數組長度）
4. 刪除元素需要移動后續元素，移動次數與數組長度有關，因此時間復雜度為O(n)

/*** 刪除數組中指定索引位置的元素* @param arr: 目標數組* @param currentSize: 指向當前數組元素個數的指針（函數會修改它）* @param index: 要刪除的元素索引* @return: 成功返回 true，失敗（索引越界）返回 false*/
bool delete_element(int arr[], int *currentSize, int index) {// 檢查索引是否有效：必須在 [0, currentSize - 1] 范圍內if (index < 0 || index >= *currentSize) {printf("錯誤：刪除索引 %d 越界！有效范圍是 [0, %d)\n", index, *currentSize);return false;}// 從 index + 1 開始，將每個元素向前移動一位for (int i = index; i < *currentSize - 1; i++) {arr[i] = arr[i + 1];}// 邏輯上減少數組大小(*currentSize)--;return true;
}

總結

數組采用連續的內存空間來存儲相同類型的數據，其優勢在于支持隨機訪問，可以通過下標高效定位和訪問任意元素
數組的訪問和修改操作時間復雜度為時間復雜度為O(1)，而插入和刪除操作需要移動元素，時間復雜度為O(n)
這部分內容需要掌握的是邏輯（其實概括一下都是先校驗索引范圍，再操作數據，最后打印出來展示，三步走），具體的實現比較簡單，實際應用中更應關注函數、指針等細節方面