Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 - Coggle Diagram
資料結構
進階樹狀結構與圖形演算法
（Advanced Tree / Graph Algorithms）
MST（Minimum Spanning Tree，最小生成樹）
連接所有 vertices
總 weight 最小
不形成 cycle
若有 V 個 vertices，MST 有 V - 1 條 edges
Prim’s Algorithm（普林演算法
從一個 vertex 開始建立 MST
適合用 priority queue 優化
每次選目前 MST 連到外部 vertex 的最小 edge
Graph（圖）
Graph 由 vertices（頂點）和 edges（邊）組成
Connected Graph 表示任兩點之間都有路徑可到達
edge 可以有 weight（權重）
Kruskal’s Algorithm（克魯斯克爾演算法）
先將所有 edges 依 weight 排序
從最小 edge 開始選
不形成 cycle 才加入 MST
使用 Union-Find 判斷是否形成 cycle
Heap（堆積）
Heap 是 Complete Binary Tree
Min Heap：parent ≤ children，root 是最小值
常用於 Priority Queue 和 Heap Sort
Max Heap：parent ≥ children，root 是最大值
實際應用
AVL Tree：需要穩定搜尋效率的資料庫索引
Heap：工作排程、優先佇列、最短路徑演算法
Graph：地圖導航、社群網路、交通路線
MST：網路線路規劃、道路建設、通訊系統
Rotation（旋轉）
當 AVL Tree 不平衡時，需要做 rotation
LL：右旋
RR：左旋
LR：先左旋，再右旋
RL：先右旋，再左旋
學習心得
我學到不同資料結構適合不同問題
選對資料結構可以讓程式更有效率
AVL Tree（AVL 樹）
AVL Tree 是自我平衡的 Binary Search Tree
透過 Balance Factor 判斷是否平衡
BF = left height - right height
BF 必須是 -1、0、1 才算平衡
表格式資料結構（Table-like Structures)
Hash Table（雜湊表）
使用 hash function 將 key 對應到位置
可以快速搜尋資料
可能產生 collision（碰撞）
collision 可用 chaining 或 open addressing 處理
常見操作
set.add()
set.discard()
set.remove()
dict.get()
dict.keys()
dict.values()
dict.items()
Dictionary（字典）
Dictionary 使用 key-value pairs（鍵值對）儲存資料
key 不可重複
value 可以是不同資料型態
平均查找時間為 O(1)
實際應用
Set：刪除重複 email
Dictionary：通訊錄、學生資料、商品資料
Table：Excel、資料庫、矩陣資料
Hash：密碼儲存、資料完整性檢查
Set（集合）
Set 是不重複、無順序的資料結構
不能用 index 存取
適合去除重複資料
支援 union（聯集）、intersection（交集）、difference（差集）
Lab 學到的內容與心得
Hashing 是單向，Encryption 是雙向
defaultdict 可以避免 key 不存在時發生 KeyError
Dictionary 和 Hash Table 能讓資料查找更有效率
MD5 可用 hashlib 實作
Counter 可以快速統計元素出現次數
基本定義
Table-like Structures 用來儲存 key-value 或集合型資料
包含 Set、Dictionary、Hash Table、Table 等概念
樹狀結構（Tree）
重要名詞
Root：根節點，沒有 parent
Parent：父節點
Child：子節點
Sibling：兄弟節點
Leaf：葉節點
Internal Node：內部節點
Depth：從 root 到該節點的距離
Height：從該節點到最深 leaf 的距離
Binary Tree（二元樹
每個 node 最多有兩個 children
分為 left child 和 right child
可以用 array 表示
若 root index 為 0，left child = 2i + 1，right child = 2i + 2
基本定義
Tree 是一種階層式、非線性的資料結構
由 node（節點）和 edge（邊）組成
最上層節點稱為 root（根節點）
沒有 child 的節點稱為 leaf（葉節點）
Binary Search Tree（二元搜尋樹）
左子樹的值小於 root
右子樹的值大於 root
搜尋時小往左、大往右
inorder traversal 可以得到由小到大的結果
Tree Traversal（樹走訪）
Preorder：Root → Left → Right
Inorder：Left → Root → Right
Postorder：Left → Right → Root
BFS：一層一層走
DFS：一路往下走到底再回溯
實際應用
檔案系統
組織架構圖
家族樹
搜尋資料
HTML DOM
Lab / 實作心得
TreeNode 使用 value 和 children 儲存資料
add_child() 可以把子節點加入樹中
BST 的 search() 透過比較大小決定往左或往右
我學到 Tree 適合表示階層關係，也能提升搜尋效率
串列(List)
常見操作
append()：在尾端加入元素
extend()：把另一個 list 的元素加入
insert()：插入指定位置
remove()：刪除指定元素
pop()：移除最後一個元素
slicing：取出部分 list
核心觀念
append() 平均時間為 O(1)
List 適合需要順序、可重複資料的情境
insert() 或 remove() 在中間操作時需要 shifting（搬移），時間為 O(n)
重要特性
有順序 ordered
可重複 duplicates allowed
可修改 mutable
可用 index 取得元素
底層概念接近 dynamic array（動態陣列）
實際應用
儲存成績資料
排隊資料
遊戲分數紀錄
一般資料清單
基本定義
List 是一種有順序的線性資料結構
Python list 可以存放不同資料型態
List 是 mutable（可修改）的資料結構
可以用 index（索引）存取資料
Lab 學到的內容與心得
Caesar Cipher 使用 ord() 和 chr() 進行字母轉換
List 和 Linked List 都能存資料但底層存取方式不同
我學到資料結構不只看能不能存資料，也要看操作效率
Linked List 透過 Node 的 data 和 next 串接資料