Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 Data Structure：四大主題整合 - Coggle Diagram
資料結構 Data Structure：四大主題整合
1 List：線性資料與動態儲存
定義與特性
順序資料：每個元素有位置
可變序列：能新增、刪除、更新
List ADT：只暴露操作介面
底層可用 array 或 linked list
OOP 連結：class 封裝資料與方法
Python list 底層
參照陣列：存物件 reference
可混合型別：因為指向物件
動態陣列 resize
append 平均 O(1)，偶爾搬移
compact array：同型資料較省空間
操作與複雜度
index / slicing：快速取得位置
append / extend：適合尾端加入
insert / delete：中間操作 O(n)
reverse / sort：改變資料順序
Linked List 對比
Node：data + next reference
走訪查找 O(n)
已知位置插刪 O(1)
doubly list / deque：兩端操作方便
sentinel：簡化邊界判斷
演算法與 Lab
Caesar cipher：ord/chr 字元位移
自寫 Array：練習 shift 與容量
High Scores：維持排行榜順序
Insertion Sort：逐步插入正確位置
Linked List：append / insert / remove
應用與心得
適合：成績、紀錄、文字序列
索引需求高：list 很合適
插刪頻繁：考慮 linked list / deque
學到：語法背後有記憶體成本
2 Set / Dict / Table：雜湊查找與表格
Set 集合
元素唯一：自動去重
無序：不靠 index 存取
containment 快：適合 in 判斷
frozenset：不可變集合，可當 key
Dict 與 Hash Table
key-value 對應：用 key 找 value
hash function：key 轉 table index
key 通常需 immutable
平均 O(1)：查找、插入、刪除
碰撞多時可能退化
Collision 處理
collision：不同 key 同位置
chaining：同格接成串列
open addressing：往其他格探測
load factor：影響 resize 與效率
Table 表格化資料
list of lists：密集矩陣
dict sparse table：只存非空資料
nested dict：多層 key 組織
Table class：用
getitem
模擬容器
工具與 Lab
[] vs get()：KeyError 與預設值
Counter：統計字頻
defaultdict：自動建立預設資料
OrderedDict / ChainMap：保序與多 mapping
hashlib：MD5 / SHA256 檔案校驗
應用與心得
email 去重、黑名單檢查
聯絡人字典：用 key 快速查
快取與索引：用空間換速度
hashing 不等於 encryption：雜湊不可逆
3 Tree / BST：階層資料與搜尋
Tree 基本概念
root：整棵樹起點
parent / child / sibling：上下與同層
internal node / leaf：有無子節點
ancestor / descendant：前代與後代
edge / path：連線與路徑
深度、高度與平衡
depth：離 root 的距離
height：往下最深層數
balanced tree：高度低，搜尋快
不平衡時：可能接近 linked list
Tree ADT 與 bigtree
Position：抽象節點位置
root / parent / children 介面
is_root / is_leaf 判斷
list / dict / dataframe 建樹
可輸出 dict、dot、image
Traversal 走訪
DFS：往深處探索
BFS：一層一層拜訪
preorder：先根再子樹
postorder：先子樹再根
inorder：BST 可得到排序
Binary Tree 表示
每節點最多兩個 children
linked：left / right reference
array：root 在 index 0
left=2i+1，right=2i+2
parent=floor((i-1)/2)
BST 操作與應用
左小右大：決定搜尋方向
search / insert / delete：成本 O(h)
刪兩子節點：找 inorder successor
平衡時 O(log n)，歪斜時 O(n)
應用：目錄、分類、索引、決策
4 MST / AVL / Heap：最佳化與平衡
MST 最小生成樹
來源：加權無向連通圖
目標：連全部頂點且總權重最小
特性：不能形成 cycle
graph 中選出 tree
應用：網路、道路、管線、分群
Prim 演算法
從任一 vertex 開始
每次選最小 crossing edge
key：目前連入成本
parent：記錄前驅
mstSet：避免重複與 cycle
Kruskal 演算法
先排序所有 edges
小邊優先，但不能成 cycle
Union-Find 判斷集合
path compression：加速 find
union by rank：降低高度
AVL Tree
平衡條件：|HL-HR| <= 1
balance factor：判斷是否失衡
LL / RR：單旋轉
LR / RL：雙旋轉
維持 search / insert / delete O(log n)
Heap 與 Priority Queue
complete binary tree：由左到右填
min-heap / max-heap：root 最小或最大
array mapping：2i+1、2i+2
heapify / heappush / heappop
應用：排程、事件、heap sort、圖演算法
整體心得
MST：用貪婪法找最低成本連線
AVL：用旋轉維持穩定效率
Heap：用樹形狀管理優先權
選結構要看操作頻率與資料關係