課程說明

上課教材

這門課既不使用傳統的課本, 也不使用我寫的講義, 而是使用網路上合法授權的上課教材。 使用網路上的合法教材有一些優缺點:

  1. 可以光明正大合法影印, 同學們不會因為為了省錢而觸犯法律; 老師也不會被迫在鼓勵非法拷貝與強迫推銷之間做一選擇。
  2. 學習技術的同時, 也可以學到分享知識與感恩。
  3. 一般網路教材比較欠缺習題/作業, 排版也較不美觀。
  4. 一般網路教材的份量比較少。 這可以算是缺點也可以算是優點。

目前網路上的自由文件選擇有限, 不像自由軟體那麼豐富成熟, 所以我還是會列一些參考書。 建議同學 -- 特別是計劃考研究所的同學 -- 各人買不同的參考書, 再彼此交換作習題。 書買來之後不要怕借人, 最怕的就是束諸高閣根本沒有用, 那就很可惜了。

程式語言

資料結構離不開程式設計, 所以我們必須選擇一種語言來作為表達資料結構的工具。 就一般應用而言, 個人認為 scripting 類的語言才最值得所有人學習; 至於 物件導向 類的語言, 則比較適合撰寫大型程式, 或用於資料結構這類介面乾淨清楚的應用場合。 如果我可以選擇, 會選用既是物件導向, 又是 scripting 的 ruby 或 python 來上這門課。 但是本系有推動 java 的共識, 所以我們就採用它吧。 就學習困難度而言, 它當然遠比 scripting 語言複雜囉嗦, 但至少比 C++ 更高階, 更簡單一些, 所以也還好啦。 而且資料結構的觀念才是課程的重點, java 語言並不是, 所以對 java 只需要熟悉到可以深入閱讀理解, 並可以做小幅度的修改即可, 不需要有從零開始撰寫完整大程式的能力。

閱讀要領

  1. 我的講義綱要: 提供 順序與進度
  2. Williams 的 Data Structures: 主要圍繞在 Java 程式實作 -- 注意 java 的語法及觀念。
  3. Morris 的 Data Structures and Algorithms: 的圖示與觀念解釋很棒
  4. Holte 的 Data Structure Lecture Notes: 的圖示與觀念解釋蠻也很棒
  5. Drakos 的 Data Structures and Algorithms: 對名詞的定義很精確, 比較數學/理論
  6. 其他一些零星的參考資料及我的補充教材

這麼多份講義, 有 java 又有 c, c++, 該怎麼讀? 不要擔心, 程式碼部分, 只需要仔細研讀 Williams 及我寫的範例; 其他人的講義主要看名詞解釋及圖示即可, 不必理會程式。

整體來講, 課程前半段的觀念非常簡單, 沒什麼好考, 所以我們會用較多時間複習/考 java 語法; 後半段的資料結構與演算法較稍微複雜, 所以花在程式設計的時間會比較少。

參考資料

(上 google 找 "data structures lecture notes", 注意複數!)

線上講義:

  1. Peter M. Williams. Data Structures: 使用 Java 語言, 實作重於理論, 用資料結構非常適切地展現出 java 物件導向觀念的實際用途
  2. Robert C. Holte. Data Structure Course: 摘要式, 很多圖解, 使用 C 語言
  3. John Morris. Data Structures and Algorithms: 資料結構與演算法兩課程的合併
  4. Nikos Drakos et. al. Data Structures and Algorithms: 資料結構與演算法兩課程的合併, 對每一 ADT 有嚴謹的數學定義, 使用 C 語言
  5. Skiena. Data Structures and Programming: 摘要式, 使用 modula-3 語言
  6. de Vel and Dyreson. CP2001 Data Structures [Lecture Notes]: 摘要式, 很多圖解, 使用 C 語言
  7. Demaine. Advanced Data Structures: 如標題, 進階 的資料結構。 很多題目我也還沒學過。

其他參考資料:

  1. Dictionary of Algorithms and Data Structures
  2. Algorithms Directory - Lecture Notes, Courses ...