Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 Data Structure：四大主題完整整理 - Coggle Diagram
資料結構 Data Structure：四大主題完整整理
1 List：線性資料與動態儲存
基本定義與特性
順序資料：元素有固定位置
mutable sequence：可新增刪改
List ADT：操作介面抽象化
OOP 封裝：class + methods
底層與表示
Python list：參照陣列
dynamic array：容量不足 resize
compact array：同型資料省空間
linked list：Node + pointer
操作與複雜度
index / slicing：定位快速
append：平均 O(1)
insert / delete：中間 O(n)
linked list：已知位置插刪快
Lab、應用與心得
Caesar cipher：ord / chr
High Scores：維持排行
Insertion Sort：逐步插入
心得：語法背後有記憶體成本
2 Set / Dict / Table：雜湊查找與表格
基本定義與特性
Set：唯一、無序、去重
Dict：key-value 對應
Table：列欄或鍵值組織
適合快速查找與整理資料
Hash Table 機制
hash function：key 轉 index
平均 O(1)：查找插入刪除
collision：不同 key 同位置
load factor 影響 resize
表格與工具
list of lists：密集矩陣
dict sparse table：只存非空值
getitem
：模擬容器存取
Counter / defaultdict / OrderedDict
Lab、應用與心得
hashlib：MD5 / SHA256 校驗
word frequency：字頻統計
contacts dict：快速查聯絡人
心得：hashing 不等於 encryption
3 Tree / BST：階層資料與搜尋
基本名詞與階層
root / parent / child
sibling / ancestor / descendant
internal node / leaf
edge / path 表示連線關係
深度、高度與 ADT
depth：離 root 的距離
height：往下最大深度
Position：抽象節點位置
Tree ADT：隱藏底層實作
走訪與表示
DFS：往深處探索
BFS：逐層拜訪
preorder / postorder / inorder
array 表示：2i+1、2i+2
BST、工具與心得
BST：左小右大
search / insert / delete：O(h)
bigtree：list / dict 建樹
心得：平衡度決定效率
4 MST / AVL / Heap：最佳化與平衡
MST 最小生成樹
加權無向連通圖
連全部頂點且總權重最小
不能形成 cycle
應用：網路、道路、管線
Prim 與 Kruskal
Prim：逐步擴張生成樹
key / parent / mstSet 記錄狀態
Kruskal：邊排序後挑小邊
Union-Find：避免 cycle
AVL 平衡搜尋
balance factor 判斷失衡
|HL-HR| <= 1
LL / RR：單旋轉
LR / RL：雙旋轉
Heap 與優先權
complete binary tree
min-heap / max-heap
heapify / heappush / heappop
應用：排程、heap sort、圖演算法