前言
資料結構是在電腦程式中有效率地儲存和使用資料的方法。一般來說,資料結構的教材會包括以下四個部分:
- ADT (abstract data type)
- 虛擬碼 (pseudocode)
- 程式效率 (即演算法分析)
- 實作 (implementation)
前三個是抽象的思維,最後一個才是實際的程式碼 (code)。
初心者往往會急著想要看程式碼,筆者可以體會這個心情,因為一開始學習程式設計時,重點在程式的語法,要解決的問題都很簡單,程式碼長度也都很短,我們就會略過前面的抽象思維,直接進入實作的部分。
不過,最好還是慢慢跳脫這個習慣,在還沒寫程式時就要能夠估計程式的效率,以免花了時間和心力卻做出效能不彰的程式。
抽象資料型態 (Abstract Data Type)
ADT 是用抽象、數學式的語言來描述某種資料型別,即使像是整數 (integer) 這種基本資料型別也可以用 ADT 描述,而我們這裡用 ADT 來描述資料結構。
ADT 可視為虛擬碼的公開界面,而虛擬碼可視為 ADT 的內部實作。ADT 是為了讓我們了解某個資料結構有什麼功能可用,也就是用來描述該資料結構的特性 (feature)。
但是 ADT 往往會用比較精實的語句來描述,初心者只看 ADT 大概也不太懂該資料結構實際的功能。一般教材為了讓學習者易於理解,會用文字敘述搭配一些圖形來輔助說明。
虛擬碼 (Pseudocode)
虛擬碼是用半結構式的文字來描述某個資料結構 (或演算法) 的實作方式。比起程式碼,虛擬碼更加簡潔,更容易看到某個資料結構或演算法的思維;此外,虛擬碼不需要考慮某個程式語言實作上的限制,寫起來更加精實。
不過,讀寫虛擬碼也要一段時間才能習慣,初學者對於實作不夠熟練,將虛擬碼轉成程式碼的過程也會碰到阻礙,這要靠多多實作來逐步克服。
由於虛擬碼沒有固定的格式,通常是按照學校老師或指定教材的風格即可。也可以試著自己撰寫虛擬碼 (看這篇文章)。
程式的效率
一開始學資料結構 (和演算法) 時,會把重心放在實作 (implementation) 上,但更重要的是估計程式的效率。
計算程式實際執行的時間是其中一個方法;然而,每次都要寫出程式後才能估計過於耗時;此外,同樣的程式在不同機器上時間有所不同,執行時間不能直接拿來比較。
比較好的方式,是在寫程式前估計出程式的執行效率,省下實作的時間。演算法分析是一種比較程式效率的抽象數學模型,可以讓我們在尚未撰寫程式時就預估出程式效率好壞 (參考這裡)。
程式實作 (Implementation)
初心者一開始都會很在意程式碼的部分,本系列文章的確也會提供每種抽象資料型態的 C 範例程式碼。
但讀者不應過度依賴這些範例程式碼,閱讀範例程式碼無法取代自己實作的過程。最好能夠在閱讀虛擬碼後就自行實作看看,然後才和文章中的實作相互比較,甚至完全不依賴文章所提供的程式碼。
本系列文章的方向
本系列文章會在每個主題提供這四個項目的參考範例,但不宜用本系列文章直接取代教科書,讀者還是應該要讀過正規的教科書,再把本文做為一個交互參考的輔助資料。