Arrays — index / traverse / search / sort

陣列

程式語言一 · 導覽投影片

→ / space 前進　← 回　Esc 總覽　F 全螢幕
導覽：建框架。完整內容在 PDF，可跑範例在 index。

01為什麼要陣列 · 學習地圖

要存 100 個成績不可能宣告 100 個變數。陣列把一排同型態資料用一個名字管理、用索引（從 0 起）存取。

宣告/初始化記憶體連續遍歷越界(UB)傳函式=傳址值當索引搜尋/排序

本投影片只建地圖；每站完整程式在 PDF 與 index。

02宣告與初始化

int a[5];                       // 未初始化＝垃圾值
int a[5] = {10,20,30,40,50};    // 宣告 + 初始化
int a[5] = {0};                 // 全部補 0
int a[]  = {10,20,30};          // 編譯器算長度＝3

大小在宣告時就固定、必須是常數，不能中途改。

03記憶體：連續的格子

04遍歷與越界

int s = 0;
for (int i = 0; i < n; i++) s += a[i];   // 遍歷標準式：i < n

越界：a[n] 不存在（最後是 a[n-1]）。C 不檢查邊界、是未定義行為，可能改到別的變數或 crash。本地用 -fsanitize=address 可當場抓到。

05陣列傳函式：傳的是位址

變數：傳值
函式改的是複本，呼叫端不變。
void f(int x){x=99;} → a 不變

陣列：傳址
陣列名退化成位址，函式改得到原陣列。
void f(int a[]){a[0]=99;} → 真的變

代價：函式內 sizeof(a) 是位址大小、不是長度 → 要另外傳 n。

06用值當索引 · 搜尋與排序

int cnt[10] = {0};
for (int i = 0; i < n; i++) cnt[data[i]]++;  // 值當索引，O(n) 統計頻率

演算法	複雜度	前提
線性搜尋	O(n)	無
二分搜尋	O(log n)	須先排序
氣泡 / 選擇排序	O(n²)	—

07常見錯誤分類

症狀	成因
結果不穩 / crash	越界：`arr[n]`、遍歷用 `i <= n`
讀到怪數字	未初始化（垃圾值）；需要時 `={0}`
大輸入爆掉	陣列開太小
函式內長度錯	忘了另傳 n（sizeof 失效）
二分搜尋找錯	資料沒先排序

接著動手

讀 PDF → index 跑遍歷／傳函式／頻率／氣泡排序 → 本地練習 5 題（反轉／極值／排序／頻率／二分，開 ASan）→ Quizlet + 測驗卷 ≥ 90%。