[資料結構] 使用 C 語言:資料結構要學些什麼

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    資料結構是在電腦程式中有效率地儲存和使用資料的方法。一般來說,資料結構的教材會包括以下四個部分:

    • ADT (abstract data type)
    • 虛擬碼 (pseudocode)
    • 程式效率 (即演算法分析)
    • 實作 (implementation)

    前三個是抽象的思維,最後一個才是實際的程式碼 (code)。初心者往往會急著想要看程式碼,筆者可以體會這個心情,因為一開始學習程式設計時,重點在程式的語法,要解決的問題都很簡單,程式碼長度也都很短,我們就會略過前面的抽象思維,直接進入實作的部分。不過,最好還是慢慢跳脫這個習慣,在還沒寫程式時就要能夠估計程式的效率,以免花了時間和心力卻做出效能不彰的程式。

    ADT 是用抽象、數學式的語言來描述某種資料型別,即使像是整數 (integer) 這種基本資料型別也可以用 ADT 描述,而我們這裡用 ADT 來描述資料結構。ADT 可視為虛擬碼的公開約定 (contract) 而虛擬碼可視為 ADT 的內部實作。ADT 是為了讓我們了解某個資料結構有什麼功能可用,也就是該資料結構的特性 (feature),但是 ADT 往往會用比較精實的語句來描述,初心者只看 ADT 大概也不太懂該資料結構實際的功能。一般教材為了讓學習者易於理解,會用文字敘述搭配一些圖形來說明。

    虛擬碼是用半結構式的文字來描述某個資料結構 (或演算法) 的實作方式。比起程式碼,虛擬碼更加簡潔,更容易看到某個資料結構或演算法的思維;此外,虛擬碼不需要考慮某個程式語言實作上的限制,寫起來更加精實。不過,讀寫虛擬碼也要一段時間才能習慣,初學者對於實作不夠熟練,將虛擬碼轉成程式碼的過程也會碰到阻礙,這要靠多多實作來逐步克服。由於虛擬碼沒有固定的格式,通常是按照學校老師或指定教材的風格即可,也可以試著自己撰寫虛擬碼 (看這裡)。

    一開始學資料結構 (和演算法) 時,會把重心放在實作 (implementation) 上,但更重要的是估計程式的效率。計算程式實際執行的時間是其中一個方法;然而,每次都要寫出程式後才能估計過於耗時;此外,同樣的程式在不同機器上時間有所不同,執行時間不能直接拿來比較。演算法分析是一種比較程式效率的抽象數學模型,可以讓我們在撰寫程式前就可以預估程式效率好壞 (參考這裡)。

    初心者一開始都會很在意程式碼的部分,本系列文章的確也會提供範例程式。但讀者不應過度依賴範例程式碼,閱讀範例程式碼無法取代自己實作的過程。最好能夠在閱讀虛擬碼後就自行實作看看,甚至完全不依賴本文所提供的程式碼。

    本系列文章會在每個主題提供這四個項目的參考範例,但不宜用本系列文章直接取代教科書,讀者還是應該要讀過正規的教科書,再把本文做為一個交互參考的輔助資料。

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk
    標籤: DATA STRUCTURES