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 連續記憶體，查 index 快但插刪要搬移
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 與講稿句
Lab：Caesar Cipher 用 ord()/chr() 處理字元位移
講稿：先用 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
Dict：get/update/delete/loop；collision 可用 chaining
應用與案例
Unique Emails 去重；Contacts 通訊錄
Word Frequency 用 dict/Counter 統計
Lab 與講稿句
Lab：hashlib 產生 MD5，理解 Hash 不等於 Encryption
講稿：查找需求增加時，Hash/Table 讓資料直接被找到
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 與講稿句
Lab：bigtree、TreeNode、find/findall、Graphviz 匯出
講稿：Tree 解決階層，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 與講稿句
Lab：Prim 的 key/parent/mstSet；Kruskal 的 path compression/rank
講稿：最後用平衡、優先權與最小成本收束整門課