演算法和資料結構

1. 概念介紹

從 JavaScript 資料結構到 C 實現

在 JavaScript 中，你有內建的陣列、物件和高階資料結構。而在 C 語言中，你必須從頭實現資料結構，這給你對記憶體佈局和效能特徵的完全控制。

💡 核心概念：C 資料結構實現提供最大的效能和記憶體效率，但需要仔細的記憶體管理和演算法設計。

2. 線性資料結構

3. 鏈表

4. 排序演算法

5. 搜尋演算法

6. 常見陷阱

• 記憶體洩漏：始終釋放資料結構中分配的記憶體
• 緩衝區溢位：在存取元素前檢查陣列邊界
• 空指標解參考：始終檢查空指標
• 演算法複雜度：注意時間和空間複雜度
• 資料結構選擇：為問題選擇適當的結構

7. 練習題

1. 使用陣列或鏈表實現堆疊資料結構。
2. 撰寫函數以迭代和遞迴方式反轉鏈表。
3. 實現合併排序並與快速排序比較效能。
4. 建立帶衝突解決的雜湊表實現。

8. 效能分析

• 陣列：O(1) 存取，O(n) 插入/刪除
• 鏈表：O(n) 存取，O(1) 在兩端插入/刪除
• 氣泡排序：O(n²) 時間複雜度
• 快速排序：O(n log n) 平均，O(n²) 最壞情況
• 線性搜尋：O(n) 時間複雜度
• 二分搜尋：O(log n) 時間複雜度

---

小結：C 演算法和資料結構的實現提供最大的控制和效能。理解記憶體管理、演算法複雜度和選擇適當的資料結構對高效的 C 程式設計至關重要。