Yakim shu Hi, 這是我擴充腦內海馬體的地方。
分類文章 全文列表

【筆記】CS50 - week 2 編譯、陣列、加密、排序法 ( 2019年更新 )

Week 2 主要課程素材 :

助教課程：

編譯 Compiling

上一節提過的將人類可閱讀的程式碼，轉換成電腦認得的機械碼，這過程稱為編譯，編譯還可以再細分為以下 4 個步驟：

  1. preprocessing
    • 在之前的案例中，在主程式開始前，先引用了包裝好的 liberary
    • #include <cs50.h> 代表著先定義好了 string get_string(string prompt)
    • #include <stdio.h> 代表著先定義好了 int printf(const char *format, ...)
  2. compiling
    • 編譯成 底層語言又稱組合語言 assembling language（ CPU 能讀懂的 ）

組合語言-w500

  1. assembling
    • 編譯成 機械碼（即 1 & 0 ）
  2. linking
    • 把 a, b, c 三個檔案合併起來
    • a. main.c 編譯後的 2 進位碼
    • b. cs50.h 編譯後的 2 進位碼
    • c. stdio.h 編譯後的 2 進位碼

linking-w500

CS50 課程提供的幫助指令

RAM 記憶體

硬碟的容量大，是存放資料的地方，而記憶體只在有電源的時候運作，且容量比硬碟小很多，不過也快速許多，在你打開某個文件或運行某軟體的瞬間，CPU 會往硬碟查找資料並暫時存放在 RAM 開始運作。

我們可以將 RAM 視為很多方格(Byte)組成的空間：

記憶體空間-w400

陣列 Array

當我們要儲存的變數開始越來越多，且有時連需要多少變數都不知道的時候，陣列 Array 就派上用場了。

字串 String

其實 字串 String 就是 字元 char 組成的陣列。

更好的寫法

假如我要印出字串中每個字元，在迴圈內，因為此例中字串的長度是不會變的，沒有必要每次都去詢問字串的長度為何，所以可以考慮先存在一個變數裡。

存長度在變數-w400

（不過 n 只在迴圈裡運作，如果其他地方也會使用到 n，就可以把 n = strlen(s); 提到外面。）

更進一步了解字串

假設有一個 32 byte 的記憶體位置，放入一個 Zamyla 的字串。

Zamyla-w450

假如再加入另一個的字串 Andi，那電腦要如何得知這它們之間的斷點呢?

所以在結束一個字串後，會自動加上 \0 的字元，當做此字串的結束。

Zamyla&Andi-w450

那知道了字串後面都會帶有 \0 能做到什麼勒~

還記得剛剛計算字串長度的 strlen 函式嗎?

我們可以把剛剛的練習改寫得更簡單!!

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = get_string();
    int n = 0;
    while (s[n] != '\0')
    {
        n++;
    }
}

看以上程式，我甚至不用調用 strlen 來取出字串長度，只要判斷它還沒讀到 \0，就知道字串結束與否。

加密

這節開始談到如何加密一段文字。

最簡單的加密方法就是給一段原始資料，透過神秘的key(金鑰)，組成一段難以閱讀的新資料。

加密-w500

反過來說，你拿到一段加密後的資料，只要有正確的金鑰，就可以還原成原始資料。

還記的 week 0 提到的 ASCII 嗎?

ASCII-w500

參照上圖，可以看到
065 - 090 → 是大寫的 A ~ Z
097 - 122 → 是小寫的 a ~ z

假設你要傳個愛的小紙條給隔壁桌帥哥又不想被礙事的老師發現內容：

好玩的部分來了，利用 ASCII 碼，自己的幸福自己追

示愛第一步：寫下深思熟慮過後的愛的訊息

加密 - step1-w350

示愛第二步：把訊息轉成 ASCII 碼，會得到以下數字

加密 - step2-w350

示愛第三步：想辦法加密，深怕愛到一個笨蛋，就簡單的就每個數字都 + 1

加密 - step3-w350

示愛第四步：再把我們加密過後的訊息轉回字元

加密 - step4-w350

登愣!!! 簡單加密就完成了

等待帥哥足夠聰明、成功解碼接收到我的愛。

同場加映：字元也可以 Loop

還可以更神奇的用字元來做 for loop，兩邊結果是一樣的。

#include <stdio.h>

int main(void)
{
    for (char c = 'A'; c <= 'Z'; c++)
    {
        printf("%c is %i\n", c, c);
    }
}
// 結果：
// A is 65
// B is 66
// C is 67
// ....

小練習：小寫轉大寫

寫一個小程式，讓使用者輸入的單字轉為大寫

#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>

int main(void)
{
    string s = get_string();
    if (s != NULL)
    {
        for (int i = 0, n = strlen(s); i < n; i++)
        {
            if (s[i] >= 'a' || s[i] <= 'z')
            {
                // 3種寫法都一樣
                // 1. printf("%c", s[i] - 32);
                // 2. printf("%c", s[i] - ('a' - 'A'));
                // 3.
                printf("%c", toupper(s[i]));
            }
            else
            {
                printf("%c", s[i]);
            }
        }
    }
}

或者，不需要用if else判斷，直接全部轉大寫即可

#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>

int main(void)
{
    string s = get_string();
    if (s != NULL)
    {
        for (int i = 0, n = strlen(s); i < n; i++)
        {
            printf("%c", toupper(s[i]));
        }
    }
}

引數

main 可以接收到引數的資訊

例如： 檔名為 argv0.c ，我輸入指令執行 ./argv0 Yakim：

  1. int argc 為引數的數量，argc 為 2。
  2. string argv[] 為引數的內容，argv[] 為 ["./argv0", "Yakim"]
    • argv[0] 為 ./argv0
    • argv[1] 為 Yakim

以下程式碼會依行列出 引數中的每個字元

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(int argc, string argv[])
{
    // 列表引數中的字串
    for(int i = 0; i < argc; i++)
    {
        // 列表各字串的字元
        for(int j = 0, n = strlen(argv[i]); j < n; j++)
        {
            printf("%c\n", argv[i][j]);
        }
    }
}

錯誤代碼

main 主程式沒有出錯，預設會回傳 0，也可以寫上任何錯誤代碼來辨別是哪種錯誤訊息，就像是常看到網頁出錯會出現的 404 一樣。

維基百科： HTTP 404或Not Found錯誤訊息是HTTP的其中一種「標準回應訊息」（HTTP狀態碼），此訊息代表客戶端在瀏覽網頁時，伺服器無法正常提供訊息，或是伺服器無法回應且不知原因。

echo $? 是什麼？可以參考 鳥哥的 Linux 私房菜

錯誤代碼-w600

排序法 Sorting

排序法

排序(sorting)，將一組資料一使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。

排序後之資料，優點為容易閱讀、統計分析、與快速搜尋所要之資料。

泡沫排序 Bubble Sort

方法：比較相鄰兩值，進行交換

Bubble Sort

假如有 8 個數字，由以下步驟進行排序：

優點：最右邊已經確定，每次比較都可以少一個

選擇排序 Selection Sort

方法：找出最小的值，丟到左邊交換

Selection Sort

假如有 8 個數字，由以下步驟進行排序：

優點：最左邊已經確定，每次比較都可以少一個人 缺點：每次都要搜尋一遍最小數，即使一開始順序就是對的

合併排序 Merge Sort

方法：持續二等分，直到最小單位再開始比較，再進行合併

Merge Sort-w500

假如有 8 個數字，由以下步驟進行排序：

優點：移動的次數比泡沫跟選擇更有效率，每個數字只移動了 3 次，8 * 3 共 24 次 缺點：需要用到額外記憶體

結論

整體來說，泡沫排序跟選擇排序的效率是差不多的，都是 (n-1)+(n-2)+….+1。我們可以說這算法的效率計算方式如下圖，時間複雜度為 n²。

n平方-w300

而合併排序的效率是更好了，時間複雜度為 n * log(n)

時間複雜度-w350

至於什麼是時間複雜度，我也是看了很久才有點頭緒，頭上充滿問號的同學可以參考這篇 初學者學演算法｜談什麼是演算法和時間複雜度，強力推薦！！寫得非常清楚到讓人感動的地步。

由以下這張 gif 可以看出三種排序法明顯的差別，以時間複雜度來說，Merge 優於 Bubble 優於 Selection。

Apr-07-2019 15-56-53

參考資料：

Written on April 27th, 2017 by Yakim shu
Feel free to share!

You may also enjoy: