CS50 problem set 5 作業回顧

第五週 cs50 介紹了幾種基本資料結構，像是 linked list, stack, queue, hash table, 跟 tries，想當然作業範圍就包括實作其中一個資料結構
經歷過前四週 C 語言的 problem set ，個人覺得 2017 cs50 課程最難的作業是 pset 5 ， 用 c 寫出一支拼字檢查程式，讀取一個字典文字檔與使用其中的單字比對文章中單字是否不在字典內，實作過程中自己卡在兩個點比較久：

1. 設計資料結構該有的元素跟對應的操作: 例如， tries 裡每一個 node 至少有一個 node 指標的陣列跟變數儲存是否為最後一個節點，在增加或刪除節點時需要考慮什麼條件
2. 程式有 memory leak: 剛開始不依賴外部資料挑戰用遞迴實作的結果雖然正確，valgrind 不帶參數跑也沒有症狀，check50 反而抓到memory，用了 valgrind \- v (-verbose) 也給出一樣的錯誤診斷，但在遞迴的過程還沒找到好的方式解決，最後參考 tech delight 上的方式用迴圈的方式重頭寫過一次

對 tries 比較陌生，就透過實作認識它，以下以作業為例介紹程式的一部分來介紹在 tries 中加入一個單字 cat 的執行過程：

主要目標是檢查拼字，但在 spec 要求考慮 ‘ 可能是單字一部分，於是設計的 tries 中的 node 結構包含：
1. 大小為 27 個 node 指標 (node*) 陣列 (a-z+’) : 記錄下一個 node 的位置
2. 一個 bool 變數 (Last_char) : 記錄是否這個 node 為結尾

Tries node 結構

A tries node

struct dic_tries
{
 struct dic_tries* next_node[27]; // node* pointer array
 bool last_char; // bool variable
};

當一個 cat 單字被加入時，有以下幾個步驟：
1. 先建立一個 tracker 去追蹤資料結構，初始化時指向ries 的入口點
2. 讀第一個字元 c ，檢查從進入點 (Dictionary Entry) 開始查指標陣列 (next_node) 中指向 c 是否為 NULL
3. 由於是第一個加入的單字，所有指標陣列的值都是 NULL，於是執行初始化一個 node 的過程，若值不為 NULL 則前進到該單字的 node
4. 將新產生的 node 的位址 (0x0001) 指派進 Dictionary Entry 裡指標陣列指向 c 的元素
5. 將 1. 中建立的 node 移到新建立的 node (0x0001)，繼續讀下一個字元，回到步驟 2. 繼續
6. 當讀到字串結尾 ‘\0’ 時，就跳出追磫資料結構的迴圈，將當下 node 的 Last_char 設為 True 表示這個 node 是某個單字的結尾，完成添加該單字的過程

Dictionary Entry 中指標陣列 C 的元素指到新增的 node 並將 node tracker 移過去

在 c 字元node 的指標陣列中，將代表 a 的元素指到新增的 node 並移動 Node tracker 過去

加入最後一個字完 t 後，將該 node 的 Last_char 設為 true，代表 cat 單字的結尾

Add a word into an tries

 
bool add_word(dic_node* entry_node, char* word)
{
    bool add_success = false ;
    dic_node* node = entry_node; // initailize a node tracker variable
    if ( node != NULL && word != NULL)
    {
        while(*word != ‘\0’) //exit loop when the string reaches the end
        {
            int index = encode_char(word);
            if ( node->next_node[index] == NULL ) // add a new node if the pointer is NULL
            {
                node->next_node[index] = add_dic_node();
            }
            node = node->next_node[index]; // move the node tracker            to the newly added or next node
            word++; // ready for the next character
        }
        node->last_char = true;
        return add_success = true;
    }
    return add_success;
}

以上三張圖描繪了在一個 tries 加入一個單字 cat 的過程跟其中 node 間的關聯； 做完後有感受到設計作業的用心，由於學員的程度不一致，cs50 團隊一開始就準備好基本架構，函數原型的宣告，讓學員直接專注在實作資料結構本身與操作方法。
在這個過程中，實際體會到開發協作方式之一就是預先定義好主架構與溝通界面，團隊成員實作與測試符合要求的程式，快速在短時間內開發其反覆迭代測試。
做 debug 時也常用到 debugger 設定 breakpoint 檢查當下變數的值或 node 的位置，對追蹤與解決邏輯錯誤幫助很大，不必再一行一行去插入 printf 印出來找。
完成這週後，有兩週的課堂不需要寫作業，一週介紹基本網路觀念，另一週介紹機器學習，再來就是 web programming，pset6, 使用 python 跟 flask 分析 twitter 內容與結果呈現。