###### tags: `homework` `sysprog2017` 2017q3 Homework2(prefix-search) === contributed by <`Jetudie`> >您是不是沒有填寫課程表單? >[name=課程助教][color=red] >>當初錯填帳號名稱，已找老師修改 >>若有需要，可再重填一份表單給您 >>[name=Jetudie][color=royalblue] --- 題目： [C04: prefix-search](https://hackmd.io/s/Bki0g_P3Z) ### Reviewed by `jackyhobingo` * 實驗上發現會有 search 'A' 時會發生 segfault，解決了嗎？若沒有解決可以參考我的[解決方法](https://hackmd.io/s/B1V8tv33W) * 查看原始資料會發現輸入是 "city, country" or "city, city, country"，會有逗號的都是城市，也許可以修改輸入時 split 的方法，將逗號處理掉 ## 編譯及測試 + 取得程式碼、編譯並執行 ``` $ git clonehttps//github.com/sysprog21/prefix-search $ cd prefix-search $ make $ ./test_cpy ``` + 出現如下 ``` ternary_tree, loaded 259112 words in 0.128302 sec Commands: a add word to the tree f find word in tree s search words matching prefix d delete word from the tree q quit, freeing all data choice: ``` ### 測試 find the word in tree + 輸入 `f` 按下 Enter, 輸入 `Taiwan`, 再按 Enter ``` find word on tree: Taiwan found Taiwan in 0.000002 sec. ``` + 輸入 `f` 按下 Enter, 輸入 `Tai`, 再按 Enter ``` find word on tree: Tai Tai not found. ``` ### 測試 search the words matching prefix + 接著又出現選擇畫面，輸入 `s` 按下 Enter, 再搜尋 `Tain` ``` find words matching prefix (at least 1 char): Tain Tain - seacjed prefix in 0.000013 sec suggest[0] : Tain, suggest[1] : Tainan, suggest[2] : Taino, suggest[3] : Tainter suggest[4] : Taintrux, ``` 發現==有些資料後面有逗號 (comma)，有些則無== 接著看到 [jackyhobingo 的分析](https://hackmd.io/s/B1V8tv33W)之後，也試試以單一字母開頭搜尋 + 搜尋 `T` , 得到的結果為 1024 筆，末項是 `Tasqillo` 。發現其中==出現重複的資料==，差別只在後面有無 comma, 列出其中幾項示意 ``` ... suggest[57] : Tío suggest[58] : Tío, ... suggest[112] : Týn suggest[113] : Týn, ... suggest[274] : Tabor suggest[275] : Tabor, ... suggest[944] : Tarnów suggest[945] : Tarnów, ... suggest[1023] : Tasquillo, ``` 看末項，顯然 `Ta` 都沒列完，接著搜尋 `Tas` , 發現 `Tasquillo` 後面的確還有資料。又以`B`搜尋，得到同樣的結果，目前結論為此程式==最多一次列出 1024 筆資料== + 搜尋 `A` , 發現得到以下結果 ``` find words matching prefix (at least 1 char): A Segmentation fault (core dumped) ``` --- ## 探討在 find words matching prefix, 輸入 A 發生 Segmentation fault 的原因 + 用 gdb 找錯誤在哪發生 ``` $ gdb ./test_cpy ... (gdb) run ... choice: s find words matching prefix (at least 1 char): A Program received signal SIGSEGV, Segmentation fault. 0x0000555555555eea in tst_suggest (p=0x555556b1cb90, c=65 'A', nchr=1, a=0x7fffffffbdd0, n=0x7fffffffbd90, max=1024) at tst.c:330 330 a[(*n)++] = (char *) p->eqkid; ``` 發現在 tst.c:330 發生 Segmentation fault ```clike=317 void tst_suggest(const tst_node *p, const char c, const size_t nchr, char **a, int *n, const int max) { if (!p || *n == max) return; tst_suggest(p->lokid, c, nchr, a, n, max); if (p->key) tst_suggest(p->eqkid, c, nchr, a, n, max); else if (*(((char *) p->eqkid) + nchr - 1) == c) a[(*n)++] = (char *) p->eqkid; tst_suggest(p->hikid, c, nchr, a, n, max); } ```