01 / 導讀
導讀
引用
Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.
章節概要
全書共15章，736頁，書末附參考文獻和索引。據 Wiley 介紹，習題按目的分類：鞏固題檢查理解，創造題要求編寫新的類別，專案題要求寫出完整的程式。與許多資料結構教材不同，本書用前兩章講 Java 語言和物件導向設計，之後才出現資料結構；第一個資料結構（陣列）要到第103頁才出現。
第1–2章：Java入門；物件導向設計
第1章複習語言基礎：類別與物件，字串、包裝類別、陣列和列舉型別，表示式，控制流，簡單的輸入輸出，以及套件。最後一節把軟體開發當作一個過程來講，包括設計、虛擬碼、編碼、文件與風格、測試與除錯。第2章講物件導向設計的目標、原則和模式，然後依次是繼承，介面與抽象類別，例外，型別轉換與泛型，巢狀類別。
第3章：基本資料結構
先講陣列，例子有儲存遊戲記錄、陣列排序、用字元陣列做簡單加密和二維陣列。接著依次是單向鏈結串列、迴圈鏈結串列和雙向鏈結串列，每種都給出實作，本章最後討論等價性判斷和資料結構的複製。
第4章：演算法分析
本章從實驗研究及其侷限講起，引入「本書使用的七個函數」，再展開用大O記號進行的漸近分析，最後講簡單的論證方法，包括歸納法和迴圈不變式。
第5章：遞迴
由階乘、繪製英制刻度尺、二分查詢和檔案系統等例子入手，進入遞迴演算法的分析，線性遞迴、二元遞迴和多重遞迴，遞迴演算法的設計，Java 中遞迴失控的危險，以及尾遞迴的消除。Wiley 指出，本章是第6版新增的，把以前分散在幾章中的內容集中到了一起。
第6–7章：堆疊、佇列和雙端佇列；列表與迭代器抽象資料型別
第6章把這三種結構分別作為抽象資料型別介紹，再用陣列實作，必要時也用鏈結串列實作；應用包括反轉陣列，以及比對括號和 HTML 標籤。第7章講列表抽象資料型別、帶有動態陣列平攤分析的陣列列表、位置列表、迭代器和 Java Collections Framework，最後以一個用「移至佇列前端」啟發式維護存取頻率的案例收尾。
第8–9章：樹；優先佇列
第8章定義一般樹和二元樹，給出鏈式和陣列兩種表示，並用較長的一節講遍歷（先序、後序、廣度優先、中序、尤拉巡遊）。第9章定義優先佇列抽象資料型別，先用無序列表和有序列表實作，再用堆實作，並把選擇排序、插入排序和堆排序作為藉助優先佇列的排序來講，最後是可調整優先佇列。
第10–11章：映射、雜湊表和跳躍串列；搜尋樹
第10章講映射抽象資料型別、雜湊表（雜湊函式、衝突處理、裝載因子與重新雜湊）、有序映射、跳躍串列，以及集合、多重集合和多重映射。第11章從二元搜尋樹和一個用於平衡的 Java 框架講起，然後依次是 AVL 樹、伸展樹、(2,4)樹和紅黑樹。
第12–13章：排序與選擇；文字處理
第12章講歸併排序和快速排序、比較排序的下界、桶排序與基數排序、各種排序演算法的比較，以及用剪枝搜尋做選擇。第13章轉向字串：模式比對（暴力法、Boyer-Moore、Knuth-Morris-Pratt）、字典樹、用貪婪法做文字壓縮，以及動態規劃。
第14–15章：圖演算法；記憶體管理與B樹
第14章給出圖的抽象資料型別、四種圖的表示、深度優先和廣度優先搜尋、傳遞閉包、拓撲排序、最短路徑和最小生成樹。第15章探討語言之下的一層：Java 虛擬機器中的堆疊與堆、垃圾回收、儲存層次與快取、B樹以及外部記憶體排序。
核心概念
第1–5章：語言、設計、分析與遞迴
- 物件導向設計的原則與模式：第2章引入的一套術語，後面用來解釋各種結構為何這樣構造。
- 泛型與介面：用 Java 表達每個抽象資料型別所依靠的機制。
- 大O記號與漸近分析：此後每一種結構都用它來衡量執行時間。
- 遞迴：有自己分析方法和失敗方式的技術，用專門一章來講。
第6–11章：線性結構、樹與映射
- 抽象資料型別：只規定操作的規格說明，書中每個都配有一個 Java 介面。
- 平攤分析：用於動態陣列，也用於帶星號小節中的伸展樹。
- 位置列表與迭代器：在不暴露內部表示的前提下指明序列中位置的方法。
- 堆、雜湊表與平衡搜尋樹：分別是優先佇列、映射和有序映射的核心結構。
第12–15章：演算法與系統
- 分治排序與排序下界：歸併排序與快速排序的對比，以及比較排序的侷限。
- 字典樹與動態規劃：文字處理一章的工具。
- 圖的遍歷、最短路徑與生成樹：圖一章的核心。
- 儲存層次與B樹：資料結構與機器實際執行之間的聯絡。
評析
優點
- 先介面，後實作。 據 Wiley 介紹，每個抽象資料型別都有對應的 Java 介面，具體結構則是實作這些介面的類別，集中在 net.datastructures 套件中，設計上與 Java Collections Framework 互補。第7章把書中的位置列表直接與 Collections Framework 作比較，有助於讀者從教學程式碼過渡到函式庫程式碼。
- 有意安排的順序。 演算法分析（第4章）和遞迴（第5章）排在依賴它們的堆疊、樹和排序之前；最難的結構——平衡樹（第11章）——在映射和優先佇列確立了寫法之後才出現。
- 按目的分類的習題。 分為鞏固題、創造題和專案題，課程可以把簡短的檢查題用作作業，把完整的程式用作大作業。
- 一本書的覆蓋面較廣。 文字處理、圖演算法和外部記憶體都與經典結構並列，本書可以作為通向專門的演算法課程的橋梁。
侷限
- 讀者需要先付出 Java 的「門票」。 前一百頁左右講語言和物件導向設計。對需要的讀者這是幫助，但已經會寫 Java 的讀者會略過這部分；希望與語言無關的讀者則會發現程式碼與泛型、迭代器、巢狀類別等 Java 慣用法綁得很緊。
- 較新的 Java 特性不在其中。 Wiley 的改動說明提到了 Java 7 引入的型別推斷，而目錄中沒有任何內容指向更晚的語言特性，因此用較新的 Java 風格寫出的程式碼，與書中印刷的示例會有所不同。
- 演算法部分比較簡略。 文字處理一章約四十頁，圖一章約七十五頁，所以本書是在介紹這些主題，而不是充分展開。
- 有些小節分析較重。 目錄中有幾個小節帶星號（例如自底向上建構堆、跳躍串列的機率分析、伸展樹的平攤分析）。初學者可以預期把它們留到第二遍再讀。
在課程中的定位
本書是第二門課的教材：它假定讀者已學過一門程式設計課程，並在一種語言中建構資料結構。在本課程列出的書中，Wengrow 的 A Common-Sense Guide to Data Structures and Algorithms 和 Bhargava 的 Grokking Algorithms 是更平易或以圖解見長的入門書，可用於第一遍閱讀或作為配套；兩者都不是圍繞 Java 類別庫組織的。Pat Morin 的 Open Data Structures 涵蓋類似內容，為每種結構給出精確的介面、實作和執行時間證明，並提供 Java、C++ 和虛擬碼三種線上免費版本，很適合作為第二參考，補充 Goodrich 等人講得較輕的證明。
Brass 的 Advanced Data Structures 是研究生水平的教材，把資料結構當作演算法設計來講，程式碼用 C 寫成；Okasaki 的 Purely Functional Data Structures 討論函式式語言中的不可變結構。二者都適合作為讀完本書之後的下一步，而不是本書的替代品。
如何使用本書
本書適合已學完第一門程式設計課程、想用 Java 實作經典資料結構的大學部二年級學生。目錄中沒有單獨的數學章節，第4章自己會引入成長函數、大O記號和歸納證明。已經會 Java 的讀者可以從第2章或第3章開始。
一個學期的實用安排：
- 核心： 按順序讀第3章到第9章，並在讀到用到其分析的結構之前先讀第4章；第5章應在樹一章之前讀完。
- 後半部分： 第10章和第11章（映射與搜尋樹）以及第12章（排序）；平衡樹可按課程需要挑選（例如 AVL 樹和紅黑樹）。
- 選讀： 第13章到第15章，作為通向演算法課程的橋梁或自學材料；初讀時跳過帶星號的小節。
不要只看程式碼，要自己動手寫：根據介面實作堆疊、佇列和位置列表，再把每一個與 Java Collections Framework 中對應的類別作比較。每一小節之後做鞏固題，創造題和專案題留到各章結束時再做。