CS50 課程雜記

簡介

CS50是一堂哈佛大學的電腦通識課,課程公開在edx,本篇為上課隨手抄下的筆記。課程安排如下

課程安排

  1. Week 0 - Scratch
  2. Week 1 - C
  3. Week 2 - Arrays
  4. Week 3 - Algorithms
  5. Week 4 - Memory
  6. Week 5 - Data Structures
  7. Week 6 - Python
  8. Week 7 - SQL
  9. Week 8 - HTML, CSS, JavaScript
  10. Week 9 - Flask
  11. Week 10 - Emoji

筆記

不免俗的要寫一下Hello World.

#include <stdio.h>

int main(void)
{	
    printf("Hello, world! \n")
}

要執行c語言時,要先使用clang語法compile,生成一個.c的檔案

clang hello.c

而CS50這堂課可以在github的codespace上寫作業,而cs50已經將繁瑣的無趣且多步驟的compile程序簡化成一個make

make hello.c
  • 整個compile的過程可以分為preprocessing, compiling, assembling, linking。
  • preprocessing > 在c語言上#include的部份,類似於python中的import
  • compile > 將程式碼轉為電腦能讀懂的語言,在compile後,會產生assembling指令,再轉為binary,這些0和1將告訴訴cpu如何工作
  • linking > 將所有binary連結在一起,成為能執行的檔案。
  • 如果以下方的程式碼印出,將會印出各個字元的ASCII Code
#include <stdio.h>
#include <cs50.h>
 
int main(void)
{
    char c1 = "H";
    char c2 = "I";
    char c3 = "!";
 
    printf("%i %i %i \n", c1, c2, c3)
}
  • string就像array of char,各個string後方會有一個**NUL**,作為一個字串的結束,也就是兩個字串的連接會有 \0在中間。
  • string需要特殊字元定義結束點的原因是因為string沒有固定memory的使用長度。
  • 例如int是4 bytes, char是1 bytes, 而一個內容為Apple的string,其實使用了6個bytes,string的memory將因值變動而改變。
  • 如果想要寫一個command line程式,要main()後方寫入int argc, string argv[]其中的argc即為arguments count,參數的數量,argv[]即為輸入的參數
  • 在compile下方程式碼,並執行./arg_demo Peter,會印出 Hello, arg_demo
// arg_demo
 
#include <stdio.h>
 
int main(int argc, string argv[])
{
    printf("Hello, %s \n", argv[0])
}
  • 原因在於argv[]會檢視所有command line輸入的內容,包括檔案本身,因此如果要順利的印出輸入參數的名稱,要寫成
// arg_demo
 
#include <stdio.h>
 
int main(int argc, string argv[])
{
    printf("Hello, %s \n", argv[1])
}
  • 開發演算法時,注重的是code的efficiency,符號用法

  • 在不了解資料的情況下,linear search是常用的做法。
  • 如果資料排序後(sorted),可以用binary search,複雜度為O(lnN)。
  • Binary search的pseudo code如下
If no doors
    Return false
If number behind doors[middle]
    Return true
Else if number < doors[middle]
     Search doors[0] through doors[middle - 1]
Else if number > doors[middle]
     Search doors[middle + 1] through doors[n - 1]
  • 在C的世界中,能夠自建data type,以下方為例,建立一個叫作person的data type,裏頭有兩個attributes,namenumber
typedef struct
{
     string name;
     string number;
}
person
  • 上方的寫法有點類似object或是class,但C並不是物件導向的語言,建struct時並沒有辦法儲存function。但像Python中的class是可以的。
  • selection sortbubble sort的複雜度都是O(N square),merge sort複雜度是O(NlogN)
  • merge sort透過recursive完成。
  • pointer是儲存變數記憶體位值的變數,當要宣告pointer時,要加``在該變數前方,而要查找位置的變數則要加上&符號。
  • 當印出p時會得到指向的變數。
#include <stdio.h>
 
int main(void)
{
    int n = 0;
    int *p = &n;
    
    printf("%p\n", p);
    printf("%i\n", *p);
  • 在CS50的課程中,課程自建了一個string的data type,string等於char *var,也就是指向變數var的pointer,大概是怕學生第一節印不出來hello world會很崩潰XD。
  • s會指向第一個char的記憶體位址。
#include <stdio.h>
 
int main(void)
{
    char *s = "HI!";
    
    printf("%c\n", *s);
    printf("%c\n", s[0]);
    printf("%c\n", s[1]);
    printf("%c\n", s[2]);
}
  • compiler在對pointer做加法時,加 n 不等於n bits,而往後 n 個變數。
#include <stdio.h>
 
int main(void)
{
    char *s = "HI!";
    
    printf("%c\n", *s);
    printf("%c\n", *(s + 1));
    printf("%c\n", *(s + 2));
    printf("%c\n", *(s + 3));
}
  • 要copy string時沒辦法直接用=完成,因為會導致兩個變數refer到同一個address,以下方的例子來看,在更改t[0]時,也會同時改到s[0]
// Capitalizes a string
 
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    // Get a string
    string s = get_string("s: ");
 
    // Copy string's address
    string t = s;
 
    // Capitalize first letter in string
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }
 
    // Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}
  • 如果換到以下例子,用malloc()(memory allocation)配置一個新的位址給變數,再用for loop把s的值放進去,此時更改t[0]就不會影響到s[0],參照記憶體位址不同。
// Capitalizes a copy of a string
 
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void)
{
    // Get a string
    char *s = get_string("s: ");
 
    // Allocate memory for another string
    char *t = malloc(strlen(s) + 1);
 
    // Copy string into memory
    for (int i = 0, n = strlen(s); i <= n; i++)
    {
        t[i] = s[i];
    }
 
    // Capitalize copy
    t[0] = toupper(t[0]);
 
    // Print strings
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}
Tags:
# computer science
# c