【程式學習】哈佛CS50x學習筆記_Week5：資料結構

Get it?

 

*本文是CS50x的中文學習筆記，是原課程的筆記補充，建議先上完課，看完原課程筆記，再閱讀本文。

之前應該有稍微提過此概念，學習程式的技巧無他，惟手熟爾，各位一定都懂。可是，有時難免會遇到較難理解的概念，也許都看懂了，但是實際練習，卻什麼都寫不出來，想練習也沒辦法，該怎麼辦呢？

我個人的解決辦法就是直接看解答，然後再蓋住解答，自己寫一次。這樣就會了嗎？當然不是，未來你還需要針對類似的問題，多解個幾次。我認為學習程式，就是要讓你的大腦重複練習思考過程，就像是騎腳踏車一樣， 一定得反覆地練習幾次。所以如果卡住了，假設卡了好一陣子，直接看答案吧，別再浪費時間苦撐了。

程式人必學的三門課，演算法與資料結構、計算機結構、作業系統，如果有餘力，再加一門電腦網路應用更好。在這三門課中，我覺得又以演算法與資料結構最為重要，本週談的就是資料結構，看課綱顯示，也是C語言的最後一堂（終於...）。

資料結構

透過自訂資料型別，電腦專家從陣列開始，創造了四種常用的資料結構，再從這四種結構變化出其他模式。

陣列 array

陣列是一般學習者第一個學習到的資料結構，在之前已經練習過很多次了。它的特性是查找資料方便，能夠讓我們隨機進入(random access)結構裡。例如有一串陣列為 int a[4] = {0, 1, 2, 3};，我們可以直接搜尋 a[i]，就可以找到對應的值。相對於其他資料結構，陣列在記憶體區域是一連串的區塊，也比較不佔用空間。

陣列的缺點是，我們很難中途插入或刪除資料，得移動其他資料。以上述例子為例，要刪除 a[2]的值，得將 a[3]的值覆蓋 a[2]，把 a[4] 的值覆蓋 a[3]。陣列的尺寸也必須固定，在寫程式的當下就要確認要使用多少記憶體區域。

連結串列 linked list

連結串列跟陣列是完全不同的概念，陣列需要一連串相鄰的記憶體區塊，但是串列不用。我在知名的程式教學網站上找了這張圖：

我們以此資料結構，設了一共4個節點。

cs50x_week5_1.c

從上述的程式碼應該能看得出來，串列要插入資料非常方便，指標指過去就好了，刪除也是，指標換過去就可以。缺點也很明顯，由於不是一連串的記憶體空間，除非一個一個檢查，我們不會知道串列裡每一個的值為何。排序時也不是很方便，除非在一開始建資料時，就針對大小排序了。

雜湊表 hash table

雜湊表專門用在資料無須排序時，它是陣列與連結串列的結合。我們這裡用本週作業裡的函式來解釋。我們做一個開頭26個字母的雜湊表，所以我們會把apple放到a箱子，banna放到b箱子。

cs50x_week5_2.c

雜湊表結合了陣列與連結串列的優缺點，如果我們記憶體空間足夠，我們可以把陣列設得大一點，未來要查找資料就很迅速。要刪除的話，就利用指標的特性去重新設定指標。不過雜湊表的排序不是很方便。所佔的空間會稍微大一點，但是小於字典樹。

字典樹 Tries

字典樹是雜湊表的再變形，等於是有一堆陣列彼此串起來。字典樹在建立時，就已經排序了，由於字典樹每一個節點都有陣列，查找資料非常快。不過它所佔用的空間最大。這裡可看下列圖示，會更加清楚（來源）。

作業

上次就注意到了，不過到了Week 5課程才確定。是的，作業的難度跳了一個等級。以前的課程，只要懂得迴圈、if-else條件式，就能完成作業了。但是到了week 4以後，必須學會管理記憶體，讀取外部資料、寫入檔案、自訂資料結構，另外還用了許多以前沒介紹過的標頭檔。要閱讀的程式檔案，也從單一變成兩個以上的檔案，如本週作業有dictionary.c、dictionary.h、speller.c。

在speller.c，你可能會看到一些完全沒看過的語法，如下面這個。如果有興趣可以研究看看。但是我個人是覺得先囫圇吞棗地，大概看一次。然後，再使用不同的學習材料，學習同樣的主題，這樣會比你在一題上卡很久很久要來得好。

Ternary Operator

char* dictionary = ((argc == 3) ? argv[1] : DICTIONARY); 　　/* 上面這串跟下面的一樣，是一種簡化寫法 　　if (argc == 3) 　　{ 　　　　char* dictionary = argv[1]; 　　}else 　　{ 　　　　char* dictionary = DICTIONARY; 　　} */

如果把作業的介紹全部看完，你會發現其實你不懂speller.c也沒關係，因為重點是dictionary.c。speller.c主要是檢查我們寫的函式，花了多少時間去比對單字。底下是本次的範例，提供給各位參考。

cs50x_week5_3.c

記得要用 valgrind ./speller texts/cat.txt檢查有無沒有釋放的記憶體區域。

Happy coding!