CS50 week 2 - Arrays 筆記

,
👀 7 min read 👀

大家好，我是 Cindy，最近跟同事小夥伴相約一起看 CS50 的課程，CS50 (Introduction to Computer Science）是一堂美國哈佛大學知名的通識課程，完全免費，在 edx 或 youtube 或 CS50-Study-Group github 都可以非常容易地看到。

這系列的文章會是我的個人筆記，歡迎有興趣的人一定要自己去看看 CS50 的課程歐。

今天這篇是 CS50 week 2 筆記，想先看 week 0 和 week 1 筆記的各位觀眾可以點連結過去看看唷！

課程的一開始講師開始講解上週我們使用的指令 make …

make hello

1
2
3
4
5
6
7
// 此檔案為 hello.c
#include <stdio.h>

int main(void)
{
    printf ( "hello, world" );
}

上週我們使用 make 指令來做 compiling 的時候，輸入完指令後畫面會出現這些 clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wextra -Wno-sign-compare -Wno-unused-parameter -Wno-unused-variable -Wshadow hello.c -lcrypt -lcs50 -lm -o hello，實際上我們在使用的指令其實是 clang 呢！

而當我們直接使用 clang hello.c 這個指令時，我們編譯出的可執行檔案叫做 a.out(多年前人類決定的預設名稱)，而如果我們輸入的指令為 clang -o hello hello.c 時 (clang 後面的指令可以稱之為 command line arguments)，這次指令的意思是編譯 hello.c 這個檔案且 output 的檔案要叫 hello。

1
2
3
4
5
6
7
8
9
// 此檔案為 hello.c
#include <stdio.h>
#include <cs50.h>

int main(void)
{
    string name = get_string("What's your name? ");
    printf ("hello, %s\n", name);
}

當我們引用了 cs50 的 library 時，我們用同樣的 clang -o hello hello.c 指令是會出現 undefined reference to ‘get_string’ 的錯誤，因為我們沒有告訴電腦我們有使用到 cs50 的 library，這時候指令可以改成 clang -o hello hello.c -lcs50(l 表示 link)，這樣就可以正常運作了，而 make 指令其實就是在幫我們自動做這些事情。

Compiling

上週我們簡單的知道從 source code 到 machine code 會經過 compiler，但 compiling 的過程其實可以細分成四個步驟：

  1. Preprocess
    這個步驟將 header 檔案裡 function 的 prototype(原型) 寫到我們的檔案裡，例如上面的程式碼會變成這樣：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ...
    string get_string(string prompt);
    int printf(string format, ...);
    ...

    int main(void)
    {
        string name = get_string("What's your name? ");
        printf ("hello, %s\n", name);
    }

  2. Compiling
    將 source code(C) 轉變成另一種 source code 叫做 assembly code (對電腦的大腦(CPU)較友善的語言)，看起來像這樣：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    ...
    main:                         # @main
        .cfi_startproc
    # BB#0:
        pushq    %rbp
    .Ltmp0:
        .cfi_def_cfa_offset 16
    .Ltmp1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
    .Ltmp2:
        .cfi_def_cfa_register %rbp
        subq    $16, %rsp
        xorl    %eax, %eax
        movl    %eax, %edi
        movabsq    $.L.str, %rsi
        movb    $0, %al
        callq    get_string
        movabsq    $.L.str.1, %rdi
        movq    %rax, -8(%rbp)
        movq    -8(%rbp), %rsi
        movb    $0, %al
        callq    printf
        ...

  3. Assembling
    將 assembly code 轉換成最後的 machine code (0 和 1)。

  4. Linking
    將我們寫的程式碼已經轉換的 0 和 1 們，以及有用到的 library 程式碼轉換的 0 和 1 們全部合併再一起。

debugging

  • printf：將我們需要的資訊印出來看看問題在哪裡。
  • debug50：CS50 提供給我們的工具，在 CS50 IDE 中可以直接使用，在執行指令前輸入 debug50，例如 debug50 ./hello，但要先設定 breakpoint，程式才知道要停在哪裡。
  • Duck Debugging：說出來就會發現問題，跟桌上的小鴨說說話吧:)

C data types

1 byte(位元組) = 8 bits(位元)

  • bool(布林)：1 byte
  • char：1 byte
  • double：8 bytes
  • float：4 bytes
  • int：4 bytes
  • long：8 bytes
  • string：? bytes (依據長度有所不同)

通常占多少空間依據電腦而有所不同。

memory

RAM(Random Access Memory)：資料短暫儲存的記憶體(要插電才能運作)，因為還沒有存到永久記憶體中而可能遺失，但速度快。
硬碟：資料永久儲存的地方。

當我們在執行程式的時候，變數會暫存在記憶體中，而佔用的空間可以參考上一段 C data types。

arrays

由左至右有序的排列，例如：int scores[3];表示 3 個 integer 的 array，在電腦中慣例是從 0 開始數，所以 3 個數字會是 scores[0]、scores[1]、scores[2]。

在 function 中可以傳入 array 作為參數，範例如下：

1
2
3
4
5
float average(int length, int array[])
{
    ...
    return sum / (float) length;
}

型別轉換

我們都知道了字母或符號在 ASCII 都會有對應的數字，所以我們可以直接將 char 或符號轉換成 int，例如：

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void)
{
    char c = '#';

    // print 35
    printf("%i\n", c);
}

strings

我們將 char 放在 array 裡實現了 string (雙引號)，所以我們可以 s[0] 取出 string 中的第一個字母，而電腦需要知道在記憶體中這個 string 是在哪裡結束(不會跟記憶體中的其他東西混在一起)，string 會在最後多占一個 byte 存 00000000，或用 \0 表示 byte 中全是 0，又稱為 NUL，告訴電腦這裡是結束的位置，所以我們每次使用 string 都會多佔用一個 byte(00000000)。

  • 注意：我們在 C 語言可以訪問記憶體中的任何位置。例如我只有存了叫做 HI! 的 string，string s = "HI!"; 卻可以透過 s[3] 得到 0，s[400] 得到記憶體中的某個東西。

我們可以透過 s[i] != '\0' 來判斷是不是最後一個字母，或著我們可以直接用 string.h 提供給我們的方法 strlen(s) 來知道 string 的長度。

英文大小寫轉換

再次觀察 ASCII 表，我們可以知道 s[i] >= 'a' && s[i] <= 'z' 表示是小寫英文字母，而大寫英文和小寫英文都差了 32，所以可以利用這個特性做到大小寫轉換，而 ctype.h 提供給我們 islower function。

Command-Line Arguments

1
2
3
4
int main (int argc, string argv[])
{
  ...
}
  • argc 表示 argument count，使用者輸入的所有字的數量(包含程式指令)。
  • argv 表示 argument vector，使用者輸入的所有字(包含程式指令)，以陣列中的 string 來表示。由於 string 本身也是 array，所以我們可以透過 array in array 的關係得到在 argv 中的每一個單字。

為什麼 main 回傳的是 integer？

執行指令後會回傳代碼，0 表示正常，1 或其他數字表示錯誤，當我們執行完程式後可利用 echo $? 來確認上一步驟執行的程式最後回傳的值是什麼，以利於發生錯誤時的檢測。

Cryptography

當我們在傳紙條的時候不會希望紙條的內容被其他人看懂，這時候我們可能會用類似暗號的方式，而暗號通常會有一個對照表找出暗號要表達的意思，這樣的話只要知道對照表的人就可以知道紙條的內容了，而這時候我們就會想要作加密這件事情，例如我們可能本來想要傳遞的訊息是 I LOVE YOU 而我們可以利用 ASCII 找到對應的數字 73 76 79 86 89 79 85，接著將每個值都 +1，內容會變成 74 77 80 87 90 80 86，接著再利用 ASCII 將數字轉換成英文，所以我們最終的結果會變成 J MPWF ZPV，其中 key 是 1，plaintext 是 I LOVE YOU，經過 cipher 加密後 ciphertext 為 J MPWF ZPV，如此的話只有知道如何加密且擁有 key 的人才會知道要怎麼解密。

過程示意如下：

key ->
plaintext -> cipher -> ciphertext

總結

這堂課針對前幾堂課的內容做更深入點的說明，讓我們認識 array，也讓我們了解 string 的運作是利用將單字放在 array 裡而達成的，並且了解了字母或符號是如何可以做型別轉換…等等，是內容豐富的一堂課，如果想知道更多的話可以參考官網唷！