Data Structure Homework

資料結構課程作業。用純 C 實作多種資料結構,不依賴 STL,訓練指標、記憶體管理、演算法實作能力。

• Course: Data Structure
• Language: C99

---

Homework

HW1 — Stack / Heap / Graph

檔案	題目	實作
Hw1/Src/hw1_p1(a).c	Prefix → Infix expression conversion	自製 stack(char[][] array-based),從右往左掃描
Hw1/Src/hw1_p1(b).c	Postfix → Infix expression conversion	自製 stack,從左往右掃描
Hw1/Src/hw1_p2.c	Min-Heap insert / delete	Array-based binary heap,實作 bubble up / bubble down
Hw1/Src/hw1_p3.c	Graph BFS traversal	Linked-list queue + adjacency matrix

Sample I/O 在 Hw1/test_data/ 下。

HW2 — Hashing & Fibonacci Heap

檔案	題目	實作
Hw2/Src/HW2_1.c	Hash Table with linear probing	動態二維陣列,bucket x slot,支援 insert / delete / search
Hw2/Src/HW2_2.c	Fibonacci Heap	完整實作 insert, extract-min, decrease-key, delete,含 consolidate 與 cascading cut

Fibonacci heap 是進階題目,要處理:

• Circular doubly linked list 串接 root list 與 sibling list
• consolidate 時用 degree array 合併同 degree 的樹
• decrease-key 觸發 cut 與 cascading cut,維持 mark bit
• 用 Node* matrix[] 做 key → node 查表,讓 decrease / delete O(1) 找到節點

---

Repo Layout

.
├── Hw1/
│   ├── Src/         # 4 道題目的 C 原始碼
│   └── test_data/   # 公開 sample input/output
└── Hw2/
    └── Src/         # Hash table + Fibonacci heap

---

How to Build & Run

gcc Hw1/Src/hw1_p2.c -o hw1_p2
./hw1_p2 < Hw1/test_data/HW1_P2_Sample_In_Out.txt

---

What I Learned

• 指標操作與動態記憶體管理(malloc / free)
• 不靠 library 自製 stack / queue / heap
• 進階資料結構的攤銷分析直覺
• Fibonacci heap 的指標操作(child / parent / left / right / mark)