【筆記】CS50 - week 2 助教課總整理

把助教課的筆記整理成一篇，內容很雜又囉唆，應該只有我自己看得懂，有些跟課程內容重複到，但還是再看一次加深記憶力。

助教課程目錄：

• Array 陣列
• Function 函式
• Search 搜尋法
  • Linear Search
  • Binary Search
• Sort 排序法
  • Insertion Sort
  • Merge Sort
  • Selection Sort
• Command line 指令
• Debug 除錯

陣列 Array

影片連結：Array

把陣列比喻成郵局信箱

規則

• index 永遠都是從 0 開始
  • 假如 array_1[] 有 n 個數量
  • 第一個： array_1[0]
  • 最後一個： array_1[n-1]
• 要非常小心數量，假如 int array_1[] = {1, 2 ,3};
  • 就不該有 array[3] 的出現（ 最後一個為 array[2] ）

陣列的宣告

陣列的宣告方式： 資料類型 名稱[數量]

也可以用以下方式宣告，兩種是完全一樣的

二維陣列

當然也可以製造出二維的陣列，定義一個 2 * 3 的陣列：

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

複製陣列

這邊有一點要特別小心，在 C 語言中，我們沒辦法直接複製陣列，將 陣列一 直接賦值到 陣列二 是不被允許的，我們能做的就只有使用迴圈、將所有的內容一個一個複製過去。

例如下圖，這樣是不允許的。

正確的方式是使用迴圈複製。

傳值 or 傳參考 Pass by reference, not by value

在 C 語言中，大部分的資料型態都是 Pass by value（傳值）， 但陣列是 Pass by reference （傳參考）。

這是什麼意思呢？先從傳值來探討

當我們將變數複製給另一個變數時，int a = b;，其實並不是真的把 b 複製到 a，電腦在背後默默多了一個步驟，他將 b 先複製一個副本，再將那副本複製給 a。可以想像成 a、b 都在記憶體佔去一部分空間，彼此不相干。

那傳參考呢？

可以想像成傳送者與接收者是共用同一塊空間，會互相影響到。 仔細想想也是合理的設計，因為陣列通常比較大，如果用傳值的方式，會浪費掉許多空間。

來看看以下練習：

如果你搞清楚了 Pass by value or reference 的差別，那應該知道印出的答案是什麼？

試著自己想想解答，再繼續往下看

參考資料：

• 二維陣列
• C語言: 超好懂的指標，初學者請進～

如果算出來的答案是 10 22，恭喜你！

function 函式

課程連結：Functions

當我們架構越來越多時，不可能所有都塞在主程式裡，所以需要 function 來分化，也比較好 debug。

可以把 function 當成一個黑盒子，有些輸入 input 跟輸出 output。

為什麼說他是黑盒子呢？因為有些常用的 function 並不是自己寫的，像是常用的 printf，引用來自 <stdio.h>，我們並不了解裡頭是怎麼實現的，但知道如何使用它。

所以一個清楚的命名、及完整的文件說明是很重要的。

宣告 Declaration

內容：output type function name (argument-list);

int add_two_int(int a, int b);

定義 Definition

int add_two_int(int a, int b)
{
    int sum = a + b;
    return sum;
}

呼叫 Call

int c = sum(a, b);

練習 - 驗證是否為三角形

條件：

• 3 個數都為正數
• 任意 2 邊長要大於第 3 邊

簡短介紹 排序法 ＆ 搜尋法

影片連結：Algorithms Summary

Linear Search 線性搜尋法

影片連結：Linear Search

• 從第一個開始直到最後，逐一物件搜尋目標。
• 時間複雜度為 n
  • Best case: 1
  • Worst case: n

Binary Search 二元搜尋法

影片連結：Binary Search

二分搜尋 (Binary Search) 是取 已排序資料的中間索引的值，來確認是否為要搜尋的數，若不是，則將資料以中間索引分為兩半。此時便比較待搜尋的值與中間索引的值的大小，若比較小，則選擇較小的那一半資料，反之亦然。接著再繼續從一半的資料中取中間索引的值做比較，重複以上的步驟，直到找到為止。

記得進行 Binary Search 之前，目標資料一定是已經排序好的。

當起始點大於終點時，一直被分化的陣列數量直到變成 0，代表目標物不在資料裡。

參考資料：

• [演算法] 二分搜尋 (Binary Search)

Insertion Sort 插入排序法

影片連結：Insertion Sort

可以很直覺的想像成玩撲克牌時，整理牌的方法。

• 先把最左邊的（藍色部分）當作 sorted，然後往右查找，小就插入左邊，換言之、大就插入右邊，直到所有都都排序完成。
• 時間複雜度為 n²
  • Best case: n
  • Worst case: n²

Merge Sort 合併排序法

影片連結：Merge Sort

• 持續二等分，直到最小單位再開始比較，再進行合併
  • 跟之後會教到遞迴 recursion 有關
• 時間複雜度為 n log n
  • Best case: n log n
  • Worst case: n log n

參考資料：

• Comparison Sort: Merge Sort(合併排序法)

Selection Sort 選擇排序法

影片連結：Selection Sort

• 找出最小的值，丟到左邊交換
• 時間複雜度為 n²
  • Best case: n²
  • Worst case: n²

Command Line 指令

課程連結：Command Line

不管是使用 PC（cmd 命令提示字元） 或 Mac （ Terminal 終端機），如果我們要對電腦下命令，除了一般常用的圖形化介面 GUI，也可以用輸入指令對電腦說明要做什麼動作。

例如說要進入桌面上的資料夾，我們習慣的操作是 對著該資料夾，使用滑鼠 double click。

但也可以開啟 Terminal，輸入 cd 該資料夾名稱，登愣！也可以辦到相同效果，是不是很酷呢？

以下是比較常用的指令：

• ls 查看此位置的所有檔案
• cd 跳到指定的檔案夾
  • cd folder_1（只能往下查找目標資料夾）
  • cd .. 跳到上一層資料夾
  • cd 後面不輸入資料夾名稱，可以直接跳到根目錄
• pwd 查看當前的檔案夾位置
• mkdir 新增資料夾
  • mkdir newfolder
• cp 複製檔案
  • 接收兩個參數 exist_file new_file
  • cp file_1 file_2
  • 如果想複製整個檔案夾與裡面的檔案
    • cp -r dir_1 dir_2
• rm 刪除檔案
  • 無法回復，所以要非常小心，通常會回問你「是否確定要刪除檔案？」
    • rm file
  • 如果不想再輸入一次 yes or y，也可以強制刪除
    • rm -f file
• rm -r 刪除整個檔案夾，跟 cp 很像
  • rm -r dir
  • 同樣的，也可以強制刪除，但要非常謹慎使用
    • rm -rf dir
• mv 重新命名
  • 接收兩個參數 old_name new_name
  • mv old_name new_name

還有更多常用的 指令，有興趣可以自己去搜尋。

餐考資料：

• 命令提示字元 00：教學目錄
  • 強力推薦，寫得超級清楚！有耐心看完一系列的人絕對可以功力大增。

Debug 除錯

課程連結：Debugging

help50

在發生邏輯上的衝突、導致編譯發生錯誤時使用。

在下任何指令前，前面加上 help50 能夠幫助你找出錯誤的位置，或提供一些頭緒除錯。

eprintf(“”)

比起 printf，eprintf 會提供是哪一行的資訊，更方便除錯。

debug50

在編譯沒問題但結果不如預期，試圖找出設計上錯誤時使用。

注意，debug50 並無法直接幫你找出錯誤，畢竟電腦不知道你想要到結果是什麼，但可以幫助你更暸解程式運行的步驟，監控變數的變化，找出在哪一個環節出錯。

除錯介面

• 設 breakpoint 中斷點
  • 設定方法：在行數左邊按一下（再按一次可以取消）
  • 暫停在某一行
• 繼續執行程式
  • stop over
    • 往下一行執行
  • step into
    • 往 function 內執行
  • step out
    • 跳出 function
• 觀察面板
  • Call Stack
    • 觀察在哪一個 function 裡
    • function name file
  • Local Variable
    • 觀察變數的變化
    • variable name value type