Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 Data Structure：四大主題完整整理 - Coggle Diagram
資料結構 Data Structure：四大主題完整整理
1 List：線性資料與動態儲存
定義與特性
順序資料：元素有位置
可變序列：新增刪改
List ADT：介面抽象化
底層表示
Python list：參照陣列
dynamic array：resize
linked list：Node + pointer
操作與複雜度
index / slicing 快速定位
append 平均 O(1)
insert / delete 中間 O(n)
Lab 與應用
Caesar cipher：ord / chr
High Scores / Insertion Sort
心得：語法背後有記憶體成本
2 Set / Dict / Table：雜湊查找與表格
定義與特性
Set：唯一、無序、去重
Dict：key-value mapping
Table：列欄或鍵值組織
Hash Table
hash function：key 轉 index
平均 O(1)：查找插刪
collision / load factor
表格與工具
list of lists：密集矩陣
dict sparse table：只存非空值
Counter / defaultdict / OrderedDict
Lab 與應用
hashlib：MD5 / SHA256
word frequency：字頻統計
心得：hashing 不等於 encryption
3 Tree / BST：階層資料與搜尋
樹的基本名詞
root / parent / child
leaf / internal node
ancestor / path / edge
深度高度與 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：逐步擴張
Kruskal：邊排序挑小邊
Union-Find 避免 cycle
AVL 平衡搜尋
balance factor 判斷失衡
|HL-HR| <= 1
LL/RR/LR/RL rotation
Heap 優先權
complete binary tree
min-heap / max-heap
heapq：heappush / heappop