Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 Data Structure：從線性資料到最佳化結構 - Coggle Diagram
資料結構 Data Structure：從線性資料到最佳化結構
1 線性結構：List
承接邏輯
先用 ADT 思考「能做什麼操作」
List 建立順序、索引、插入刪除的基本觀念
基本定義與特性
有序集合；元素可重複；可用 index 存取
Python list 是 Dynamic Array，容量會自動擴充
資料結構關聯
Array：連續記憶體，索引快但插刪要搬移
Linked List：Node + pointer，插刪彈性高但查找要走訪
操作與演算法
append 均攤 O(1)；insert/delete 常需 O(n)
extend、reverse、slice、insertion sort
應用案例
Scoreboard/High Scores 依順序保存成績
Stack、Queue、Deque 可由 List/Linked List 延伸
Lab 實作與心得
Caesar Cipher 用 ord()/chr() 處理字元位移
心得：pointer 更新錯一個，linked list 就會斷
2 查找結構：Set / Dict / Table
承接邏輯
List 線性搜尋太慢時，需要用 key 快速定位
從「順序」進到「唯一性、映射、表格化」
基本定義與特性
Set：元素唯一、無序、不能用 index
Dict：key-value mapping；Python 3.7+ 保留插入順序
資料結構關聯
List 重順序；Set 重唯一；Dict 重查找；Table 重 row/column
Hash Function 將 key 映射到 table index
操作與演算法
Set：add/remove/contains；union/intersection/subset
Dict：get/update/delete/loop；collision 可用 chaining
應用案例
Unique Emails 去重；Contacts 通訊錄
Word Frequency 用 dict/Counter 統計
Lab 實作與心得
hashlib 產生 MD5；理解 Hash 不等於 Encryption
心得：Hash 適合驗證與快速查找，但不是加密
3 階層結構：Tree / BST
承接邏輯
表格能查一筆資料，但階層關係要用 Tree 表示
Tree 讓資料從線性/表格走向 parent-child 結構
基本定義與特性
root、parent、child、sibling、internal、external/leaf
depth 看離 root 多遠；height 看往下最長路徑
資料結構關聯
Binary Tree 每節點最多兩個 children
BST 以左小右大保存排序關係
操作與演算法
Traversal：DFS、BFS、preorder、postorder、breadthfirst
BST search/insert/delete 取決於高度 h；最壞 O(n)
應用案例
File System：root、directory、file 是典型樹
分類、組織圖、family tree、ordered map/search
Lab 實作與心得
bigtree、TreeNode、find/findall、Graphviz 匯出
心得：BST 要注意插入順序，否則會退化
4 最佳化結構：MST / AVL / Heap
承接邏輯
BST 若不平衡會退化，因此需要穩定效率
圖的連接成本與排程優先權，需要進階結構處理
基本定義與特性
MST：連通加權無向圖中總權重最小的生成樹
AVL 用 balance factor 維持平衡；Heap 是 complete binary tree
資料結構關聯
MST 是從 Graph 選出 Tree，無 cycle 且有 V-1 edges
AVL 修正 BST；Heap 重 priority，不保證全域排序
操作與演算法
Prim 從 vertex 擴張；Kruskal 排 edges + Union-Find
AVL rotations：LL/LR/RR/RL；Heap push/pop O(log n)
應用案例
MST：網路佈線、道路/管線最小成本連接
Heap：priority queue、task scheduling、最小/最大值管理
Lab 實作與心得
Prim 的 key/parent/mstSet；Kruskal 的 path compression/rank
心得：進階結構是在控制成本、平衡與效率