資料結構課程大綱

課程說明

Data Encapsulation

問題: 大程式如何分工?

例一: 一個超級簡單的 排序演算法: 把資料逐筆丟進一個袋子裡, 再逐筆取出袋中目前最小元素, 結束! 只要袋子每次吐出來的都是最小元素就可以了; 至於究竟袋子究竟是一個機器人, 一個外星人 (MIB 星際戰警裡面的郵務員), 還是一隻天才黑猩猩, 並不重要。

例二: 分數 [Holte]

例三: 家庭影音設備。 [Hung]

分層負責 [Holte]

藉一個排序實例認識 Java 環境

何謂資料結構?

要描述一個 abstract data type 有兩種方式。 behavioural definition: 你能提供那些服務? structural definition: 你如何運用資源提供這些服務? [Holte]

如果設計得當, 它的 specification 或 declaration 大致對應到 behavioural definition, 不論用什麼方式實作都一樣; 它的 implementation 則會根據不同的 structural definition 而有不同的程式碼。 [Morris]

例如 PriorityQueue [Williams] 就是一個 abstract data type 的 specification; 而 BinaryHeap [Williams] 和 "經過實驗二修改過的" FSUArray [Hung] 則是兩種不同的 implementations。

Java 的陣列

二維陣列: 習慣畫法/稱呼: 直行橫列 -- 直的是一 行 column; 橫的是一 列 row。 現代多數的程式語言, 儲存方式採 row major, (想像一篇英文文件寫字的順序: 由上而下, 由左而右); 古代的某些語言, 例如 Fortran, 則採 column major (請複習計算機概論)。

上述儲存方式, 不論按照那種順序, 都將資料存在一整片長方形的空間當中。 另外一種較省空間, 但程式處理稍微麻煩的二維陣列儲存方式叫做 ragged array。 ragged array -- 參差不齊的陣列

深層 vs 淺層 [Williams]:

  1. deep copy (深層拷貝): 複製。
  2. shallow copy (淺層拷貝): 取外號/別名。
  3. 深層比較: 是否長得一模一樣?
  4. 淺層比較: 是否根本就是同一個傢伙?
  5. 在 java 裡面, "=" 是淺層拷貝; "==" 是 淺層比較。

Stack 堆疊

Stack: 先進後出 FILO [Morris], [Drakos], [Williams],

使用 stack 的範例:

  1. 火車調度問題: [Evans]; 參考解答: TrainDemo.java 與 TrainCar.java
  2. (題外話: expression trees [Hung], [Swartz]) postfix notation 求值: [Hung], [c2.com]
  3. 系統如何執行 遞迴 recursive 程式? 或者說, 如果系統不支援遞迴, 如何自力救濟? 將 activation record 存入 system stack。 [Hung], [Morris]

Queue 佇列

Queues: 先進先出 FIFO [Williams], [Drakos],

用陣列實作 circular queue: 就像一條倒退走的蛇 circular queue 就像一條倒退走的蛇

Double-Ended Queue

兩頭皆可新增刪除的 double ended queue (deque) [NIST], [Drysdale], [Strandh],

Linked List

linked list, 首尾相連的 circularly linked list, 正反雙向通行的 doubly linked list: [Morris], [Drakos], [Holte] (Lectures 4,5,6),

用 linked list 實作 stack 與 queue: [Williams],

實作 list 時一樣可能需要考慮深層/淺層拷貝的問題: [Holte] 的 "Semantics Of Assignments" 部分。

Java 的 Cloneable: 對 DList 做 addTail()

Linked list 的應用: 多項式 [Bellacqua and Johnson]

Stack/Queue/Deque 與 Array/List 的關係 小結: Stack, Queue, Deque 都是抽象的資料結構; Array 與 Linked List 則是具體的資料結構。 前三者皆可用 Array 實作, 亦可用 Linked List 實作。 Q: 實作時, 各需要注意何事?

在此之前, 大部分時間可能花在複習 java; 在此之後, 大部分時間可能花在觀念與演算法。

Binary Search 二分搜尋法

藉 Binary Search 二分搜尋法 認識 java 的 Comparable 介面, 及 time complexity 時間複雜度: [Morris], [Williams]

深入了解 asymptotic notations: [Hung], [Morris], [Drakos],

Binary Search Tree 二元搜尋樹

tree 樹: [Hung], [Drakos],

binary tree 二元樹: [Morris], [Drakos]

binary search tree 二元搜尋樹: [Drakos] [Williams],

tree traversal: [Drakos] [Holte], [Morris],

從 BST 裡面刪除一個元素: [Williams], [Holte],

Balanced BST 平衡樹

BST 的困境: [Holte]

Rotation: [Holte]

Red-Black Tree: [Hung], [Morris],

結論: 為什麼要學平衡樹?

查詢 新增 刪除
unsorted array O(n) O(1) O(n)
sorted array O(lg n) O(n) O(n)
search trees O(h) O(h) O(h)

對一般的 BST 而言, h 可以大到 O(n) (如果是 skewed tree); 對平衡樹而言, h 則只有 O(lg n)。

用 Heap 實作 Priority Queue

用 heap 堆積 實作 priority queue: [Hung], [Morris], [Drakos] (6.1), [Holte]

用 Hash 實作 Map/Table/Dictionary

Map/Table/Dictionary: 方便用 key 找 value 的資料結構: [Drakos], [Holte],

先前講的平衡樹, 這章講的 hash, 之後要講的 skip list, 都可以拿來實作 map。 當然用簡單的 unsorted array, sorted array, 或 linked list 也都可以, 但是效率當然就比較差。 (進行增刪查改等動作的 time complexity 較高)

Hash: 用數學運算取代大部分的搜尋工作: [Donaldson] 26, 27, 29, 兩類處理 collision 的方式: chaining [Holte] 與 open addressing [Holte]; (如何處理 detete? [Holte] 的說明比較清楚。)

其他講義: [Morris], [Drakos] (3.3 到 3.5),

Skip List

[Drakos] (定義), [Drakos] (分析),

Graph 圖

graph: [Hung], [Drakos], [Holte], [Morris],

Collections and Iterators

collections: [Morris]