Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 Data Structure - Coggle Diagram
資料結構 Data Structure
串列 List
基本定義與特性
List 是有序 ADT，可插入、刪除、取值、走訪
Python list 底層是 Dynamic Array，不是 Linked List
Referential Array 儲存物件參照；array 模組是 Compact Array
關聯比較
Array：連續記憶體，索引 O(1)，插刪需搬移
Linked List：Node+pointer，插刪彈性高，查找需走訪
Deque 可用 Doubly Linked List + sentinels 實作
操作與演算法
append 均攤 O(1)；resize 偶爾 O(n)
insert/delete O(n)：陣列搬移或鏈結走訪
extend、reverse、slice、insertion sort
應用案例
Game High Scores / Scoreboard
排序資料、Stack/Queue 的基礎
適合需要順序與索引的資料清單
Lab 心得
Caesar Cipher 使用 ord()/chr() 位移字元
Node 類別包含 data 與 next
心得：插入刪除的核心是正確更新指標
表格與雜湊
基本定義與特性
Set：不重複、無序、不能用索引
Dict：key-value mapping，Python 3.7+ 保留插入順序
Hash Function 將 key 映射到 table index
關聯比較
List 保順序；Set 重唯一；Dict 重快速查找
Table 是 row/column；Dict 可表示一筆資料
Collision 可用 Chaining 串接處理
操作與演算法
Set：add/remove/discard/contains
Set 運算：union/intersection/subset/superset
Dict：get/update/delete/loop；[] 與 get() 差異
應用案例
Unique Emails 去除重複
Contacts 通訊錄與 nested dictionary
Word Frequency 字頻統計、MD5 檔案驗證
Lab 心得
hashlib 產生 MD5 hash
Hash 是單向；不同於 Encryption 可還原
collections：Counter、OrderedDict、defaultdict
樹與 BST
基本定義與特性
Tree 是非線性 parent-child 階層結構
root、leaf/external、internal、sibling
depth 從 root 算；height 到 leaf 最長路徑
關聯比較
Tree 表階層；List 表線性順序
Binary Tree 每節點最多兩個 children
BST 左小右大，可做 ordered search/map
操作與演算法
Traversal：DFS、BFS、preorder、postorder
BST search/insert/delete；刪除需找 successor
Array 表示：parent floor((i-1)/2)，children 2i+1、2i+2
應用案例
File System：root/subdirectory/file
Org chart、family tree、classification
bigtree 可由 list/dict 建樹並匯出 Graphviz
Lab 心得
TreeNode value + children 適合遞迴處理
find/findall 可依屬性找節點
BST 若依序插入會退化成 linked list，最壞 O(n)
進階樹與圖演算法
基本定義與特性
MST：連通加權無向圖中總權重最小的生成樹
AVL：以 height/balance factor 維持平衡
Heap：Complete Binary Tree + heap property
關聯比較
MST 是從 Graph 選出 Tree，無 cycle、V-1 edges
AVL 修正 BST 歪斜，維持 O(log n)
Heap 重視 priority，不保證完整排序查找
操作與演算法
Prim：從起點成長，每次選最小 crossing edge
Kruskal：排序 edges，Union-Find 防 cycle
AVL rotations：LL/LR/RR/RL；Heap push/pop/heapify
應用案例
MST：網路佈線、道路/管線最小成本連接
Heap：Priority Queue、task scheduling
AVL/Balanced tree：需要穩定查找效率
Lab 心得
Prim 用 key、parent、mstSet 管理已選節點
Kruskal 的 find/union 可配 path compression/rank
AVL 旋轉先找 middle/pivot；Heap 可用 array index 實作