你的進度
0/ 14 節已標記完成
下一節: 0.1 指標、記憶體與結構體
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI2520 筆記裏的內容
數字只算這門課 14 節公開筆記裏寫了甚麼，不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 34 · 定義 47
第 0 章 · 1 節
程式基礎
資料結構筆記會反覆用到的語言與記憶體工具。
- 0.1
指標、記憶體與結構體
重溫課程用來解釋資料結構行為的 C 語言工具：指標、malloc 動態配置、typedef 型別別名與 struct 結構體佈局。
第 1 章 · 2 節
ADT 與操作語義
由 ADT 規格走向 stack/queue 行為，再進入 dictionary 形式的 hashing 操作。
- 1.1
ADT 操作：堆疊、佇列與函式指標
以抽象資料型別（ADT）的角度精確理解堆疊、佇列，以及 C 語言中以函數指標進行操作分派的設計。
- 1.2
雜湊表與碰撞處理策略
用字典操作、雜湊函數、碰撞與鏈結法去理解雜湊表為何以有序結構換取平均情況下的快速存取。
第 2 章 · 1 節
串列與遞迴
遞歸 list 契約、head-tail 推理，以及受 representation 影響的操作成本。
- 2.1
作為遞迴 ADT 的串列
把串列讀成遞迴的頭尾（head-tail）抽象資料型別，再比較迭代與遞迴兩種操作實作。
第 3 章 · 2 節
複雜度與排序
漸進增長、成本比較與面向排序的複雜度推理。
- 3.1
複雜度增長與演算法成本
在實作排序或選擇演算法前，先解讀漸進增長並比較成本。
- 3.2
選擇問題、快速選擇與線性時間排序
分清選擇與完整排序，再用快速選擇、計數排序、基數排序理解額外結構何時改善複雜度。
第 4 章 · 2 節
樹與二元搜尋樹
Binary tree traversal、reconstruction 與 binary-search-tree operations。
- 4.1
二元樹遍歷與重建
透過前序、中序與後序走訪理解二元樹的遞迴結構，再由充分的走訪資訊重建樹。
- 4.2
二元搜尋樹與核心操作
在搜尋、極值、插入、後繼與刪除操作中維持二元搜尋樹的排序不變式，並以樹高分析成本。
第 5 章 · 4 節
圖
Graph representation 與 traversal、minimum spanning tree、shortest path 及 topological ordering。
- 5.1
圖的表示、深度優先搜尋與廣度優先搜尋
比較鄰接矩陣與鄰接串列，再以正確的邊界與已訪問狀態不變式追蹤深度優先搜尋（DFS）與廣度優先搜尋（BFS）。
- 5.2
最小生成樹：Prim 與 Kruskal
以 Prim 與 Kruskal 的貪心選擇建構最小生成樹，並分清最小生成樹的目標與最短路徑。
- 5.3
最短路徑與 Dijkstra 演算法
在邊權非負的前提下，用鬆弛與已定案頂點的推理，以 Dijkstra 演算法計算單源最短路徑。
- 5.4
有向無環圖的拓撲排序
以 Kahn 入度流程與 DFS 完成時間排列有向無環圖（DAG）的頂點，並由兩種方法辨認有向環。
第 6 章 · 2 節
堆與貪心編碼
Binary heap、priority queue、Huffman coding 與以 heap 實作的 multiway merging。
- 6.1
二元堆與優先佇列
以陣列表示完全二元樹，並透過優先佇列操作及自底向上建堆維持最小堆的次序。
- 6.2
Huffman 編碼與堆的應用
以反覆合併最低頻率建構無前綴的 Huffman 編碼，再把堆的抽象用於高效的多路合併。