簡介
CS50是一堂哈佛大學的電腦通識課，課程公開在edx，本篇為上課隨手抄下的筆記。課程安排如下
課程安排
- Week 0 - Scratch
- Week 1 - C
- Week 2 - Arrays
- Week 3 - Algorithms
- Week 4 - Memory
- Week 5 - Data Structures
- Week 6 - Python
- Week 7 - SQL
- Week 8 - HTML, CSS, JavaScript
- Week 9 - Flask
- 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，name和number。
typedef struct
{
string name;
string number;
}
person
- 上方的寫法有點類似
object或是class，但C並不是物件導向的語言，建struct時並沒有辦法儲存function。但像Python中的class是可以的。 - selection sort和bubble 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);
}