註：本課程筆記參考CS50官方課程和官方notes。
本週的課程是數據結構（data structure）。
當解決複雜的問題，需要面對大量的數據的時候，就需要先想想怎麼組織這些數據。比如很多app用戶量上億，這麼大的數量，怎麼存儲用戶名和密碼，然後讓用戶花最少的時間登陸自己的帳號，這就涉及按什麼邏輯處理這些數據，可以讓用戶啊很快的log in。這個處理背後的邏輯就是數據結構。
課程筆記：
課程總共花費約9個小時（課程看三遍，某些short看三遍）。
1.Array
優點：back to back，無論在在stack或heap上數據存儲都是連續的。
缺點：如果存在stack上存儲大小是固定的，無法增加。
如果想要增加，必須使用malloc分配動態存儲空間存在heap上面。也可直接使用realloc，既分配存儲空間，同時直接複製原本陣列的數據。
list[0] = 1;
list[1] = 2;
list[2] = 3;
int *tmp = realloc(list, 4 * sizeof(int));
free(list);
list = tmp;
// Add number to list
list[3] = 4;
複雜度：
- search：O(log n)
- insert：O(n)
2.linked list
linked list是一串link在一起的node組成的數據結構。每個node包含兩部分：變量本身和下一個node的地址。
重點在這個linked list不能斷鏈，這個教授在課程中具體有一步步code說明，還特別請同學上台很形象的展示了。新的node要插入的話，必須先讓n->next先指向，而不是讓已有的linked list來指向新的node，因為會產生斷鏈問題而導致失去後面鏈接的node。
如何在linked list裡插入數值。除了課程講的，google出來的這個視頻List in C/C++ - Inserting a node at beginning也很有幫助。
typedef struct node
{
int number;
struct node *next;
}
node;
//第一步 創立空的list
node *list = NULL;
//第二步 創立暫時的變量n的地址
node *n = malloc(sizeof(node));
//第三步 臨時變量賦值
if（n ！= NULL)
{
n->number = 1;
n->next = NULL;
}
//第四步 臨時變量變成list
list = n;
複雜度：
- search：O(n)。
- insert：如果需要排序的話O(n)，如果不需要排序直接插入，O(1)。
3.hash table
hash table本質上就是很多linked list組成的array。像是撲克牌，可以52張混在一起變成一個linked list，也可以把四種不同的花色分成四個桶子，每一個桶子13張牌組成一個linked list，這四個linked list組成的array就是hash table。
當不介意數據是否是排序好的時候，可以用hash table。
本週的作業實作了hash table，增加理解。
複雜度：
- search：理論上是O(n)，但是實際上，可以大幅增加效率，比如把人名按26個字母分為26個linked list，這樣搜索的效率就是26倍。
作業心得(Speller)：
總共花費8個小時。
這週的作業難度又加大了，要求寫一個查文件裡錯誤詞彙的程式，如果沒有walkthrough簡直就是不可能完成的任務。CS50的作業設置的很難，學生很容易直接放棄；但是作業又提供有詳細講解的walkthrough，這真是一大陷阱，讓人覺得努力一下還是可以解題的。walkthrough又是點到為止，只是給個線索，還是要自己加深學習才能運用，就這樣在walkthrough的帶領下一步步試試看，不行改改再試試，就這樣一步步在不停的錯了再改中實踐正課的學習。最後一開始看似不可能完成的任務就這樣一步一步的完成了，好像玩一個很難的遊戲闖關成功一樣，收穫滿滿的成就感，接下來再闖下一關。如果CS50的作業沒有這麼精心的設計，我估計早就放棄了。
花了好幾天看了幾遍課程和短片，看了很多遍walkthrough並跟著寫出了程式，結果可以compile但是不能運行。
1.Segmentation fault (core dumped)
運行help50：
$ help50 valgrind ./speller texts/cat.txt
提示如下錯誤：
問題應該出在對hash table和linked list理解，再複習下shorts，google了insert in linked list。改正了如下錯誤：
1)hash table邏輯問題
如果用首兩個字母的話，會漏掉只有一個字母的詞，比如a和i，也會漏掉i‘m等。
2）hash table的數字問題
hash table的數字要大於等於0，小於等於N-1，不能超過這個範圍。
3）fopen沒有fclose
解決了這三個問題，發現程式可以運行，且沒有了memory leak的問題。
2.Could not unload dictionaries/large.
google了後發現問題出在unload function不小心return了false。
改正了這個錯誤再次運行。
3.case-insensitive的問題，根源應該出在check function。
我把check function的for loop改為while loop，問題依然存在。最後翻看了txt的文件，發現裡面大小寫都有，而我的hash function 沒有把大小寫區別對待。再次修改hash function，最後成功解題。
不過我的總運行時間是0.22s，遠遠超過CS50老師們的運行時間0.09s，顯示我的hash table還有很多提升空間。
下面是幾個重要的function：
//hash function
unsigned int hash(const char *word)
{
int sum = 0;
for(int i = 0; i<strlen(word);i++)
{
sum = sum+ tolower(word[i]);
}
return sum%500;
}
//load function
FILE *file = NULL;
bool load(const char *dictionary)
{
// open dictionary file:
file=fopen(dictionary,"r");
if (!dictionary)
{
return 1;
}
// read one at a time:
char word2[LENGTH + 1];
while(fscanf(file,"%s",word2)!=EOF)
{
node *n=malloc(sizeof(node));
if(n == NULL)
{
return 1;
}
strcpy(n->word,word2);
int x = hash(word2);
counter++;
n->next = table[x];
table[x] = n;
}
fclose(file);
return true;
}
//unload function
bool unload(void)
{
// TODO
for(int i = 0; i < N; i++)
{
node *cursor = table[i];
while(cursor!=NULL)
{
node *tmp=cursor;
cursor=cursor->next;
free(tmp);
}
}
return true;
}
學習心得：
本週課程對我很難，很難的東西，一次學一點，分開多次學，讓我們的大腦慢慢把這些知識組塊（chunk）。所以我花了很久學這節課，也看了很多遍。最後大腦吸收的越來越多，一開始很難的東西好像變得沒有那麼難了。
推薦學習coursera課程：學習如何學習。