瀏覽章節
章節 0
程式基礎
資料結構筆記會反覆用到的語言與記憶體工具。
- 閱讀本節
0.1 Pointer、記憶體與 struct
重溫課程用來解釋資料結構行為的 C 語言工具：pointer、malloc、typedef 與 struct 佈局。
章節 1
ADT 與操作語義
由 ADT 規格走向 stack/queue 行為，再進入 dictionary 形式的 hashing 操作。
- 閱讀本節
1.1 ADT 操作：stack、queue 與 function pointer
以 ADT 角度精確理解 stack、queue 以及 C 語言中以 function pointer 進行操作分派的設計。
- 閱讀本節
1.2 Hash table 與 collision 策略
用 dictionary 操作、hash function、collision 與 chaining 去理解 hash table 為何以有序結構換取平均情況下的快速存取。
章節 2
List 與 recursion
遞歸 list 契約、head-tail 推理，以及受 representation 影響的操作成本。
- 閱讀本節
2.1 作為遞歸 ADT 的 list
把 list 讀成遞歸的 head-tail ADT，再比較 iterative 與 recursive 操作實作。
章節 3
複雜度與排序
漸進增長、成本比較與面向排序的複雜度推理。
- 閱讀本節
3.1 複雜度增長與演算法成本
在實作排序或選擇演算法前，先解讀漸進增長並比較成本。
- 閱讀本節
3.2 Selection、quickselect 與 linear-time sorting
分清 selection 與完整 sorting，再用 quickselect、counting sort、radix sort 理解額外結構何時改善複雜度。
章節 4
Trees 與 BST
Binary tree traversal、reconstruction 與 binary-search-tree operations。
- 閱讀本節
4.1 Binary tree traversal 與重建
透過 preorder、inorder 與 postorder traversal 理解 binary tree 的遞歸結構，再由充分的 traversal 資訊重建樹。
- 閱讀本節
4.2 Binary search tree 與核心操作
在 search、extrema、insertion、successor 與 deletion 中維持 binary-search-tree ordering invariant，並以樹高分析成本。
章節 5
Graph
Graph representation 與 traversal、minimum spanning tree、shortest path 及 topological ordering。
- 閱讀本節
5.1 Graph representation、DFS 與 BFS
比較 adjacency matrix 與 adjacency list，再以正確的 frontier 及 visited-state invariant 追蹤 DFS 與 BFS。
- 閱讀本節
5.2 Minimum spanning tree：Prim 與 Kruskal
以 Prim 與 Kruskal 的 greedy choice 建構 minimum spanning tree，並分清 MST objective 與 shortest path。
- 閱讀本節
5.3 Shortest path 與 Dijkstra algorithm
在非負 edge weight 前提下，用 relaxation 與 settled-vertex reasoning 以 Dijkstra algorithm 計算 single-source shortest path。
- 閱讀本節
5.4 DAG 的 topological sorting
以 Kahn indegree process 與 DFS finishing time 排列 DAG vertices，並由兩種方法辨認 directed cycle。
章節 6
Heap 與 greedy coding
Binary heap、priority queue、Huffman coding 與以 heap 實作的 multiway merging。
- 閱讀本節
6.1 Binary heap 與 priority queue
以 array 表示 complete binary tree，並透過 priority-queue operations 及 bottom-up construction 維持 min-heap order。
- 閱讀本節
6.2 Huffman coding 與 heap 應用
以反覆合併最低 frequency 建構 prefix-free Huffman code，再把 heap abstraction 用於高效 multiway merging。