CS50 wk5 課程筆記和作業心得

註:本課程筆記參考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課程:學習如何學習。

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *