C++ 學習路線圖與經典算法實現全攻略

經典 C++ 學習路線圖

C++ Primer → C++ 標準程序庫 → Effective C++ → Effective STL → 深度探索 C++ 對象模型

夯實基礎、掌握標準庫、內化最佳實踐、精通 STL、洞悉對象模型——這是從入門到精通的黃金路徑。

十大基礎算法 C 實現

1. 計數、求和、階乘

隨機生成 100 個 0~99 整數，統計個位數字分布。關鍵：循環變量初值、終值、累加器初值。

2. 最大公約數與最小公倍數（輾轉相除法）

gcd(m,n)：m%n=r; while(r){ m=n; n=r; r=m%n; } return n;
lcm = m*n/gcd。

3. 素數判斷

試除法至 sqrt(m)。封裝為 int prime(int m) 返回 1/0。

4. 驗證哥德巴赫猜想

偶數 n>=6 分解為兩素數之和。從 3 開始枚舉 n1，檢查 n1 和 n-n1 是否均為素數。

5. 三大排序算法

• 選擇排序：每輪選最小值換到前端，O(n²)。
• 冒泡排序：相鄰比較交換，大值沉底，O(n²)。
• 歸併排序：雙指針合併兩有序數組，O(n) 空間，O(n log n) 時間。

6. 查找算法

• 順序查找：線性掃描，O(n)。
• 折半查找：要求有序，雙指針收斂，O(log n)。

7. 有序數組插入

定位插入位置 p，後移元素騰出空間，插入 x。

8. 矩陣運算

• 加減：對應元素運算。
• 乘法：C[i][j] = Σ A[i][k]*B[k][j]。
• 轉置：對角線交換 a[i][j] ↔ a[j][i]（僅遍歷上/下三角）。
• 求極值：雙層循環記錄行列號。

9. 迭代法求平方根

牛頓迭代：x₁ = 0.5*(x₀ + a/x₀)，直到 |x₁-x₀| < ε。

10. 進制轉換

連續除基取餘，逆序輸出字符（0-9, A-F）。

11. 字符串處理

• 凱撒加密：字母循環位移 K 位。
• 單詞計數：狀態機識別分隔符邊界。

12. 窮舉法

三層循環枚舉 5元/1元/5角 組合滿足 100張=100元。

遞歸：用自身定義自身

兩要素：終止條件 + 遞歸步驟向終止條件收斂。
例：int fac(int n){ return n==1?1:n*fac(n-1); }
實現靠棧：每層調用壓棧，終止後彈出回溯。

C 語言細節補充

• printf：%g 自適應精度，%% 輸出百分號，返回輸出字符數（含轉義字符）。
• scanf：%f 讀 float，%lf 讀 double；可限寬度（%3c），不可限精度。
• getchar/putchar：行緩衝導致輸入字符串後逐字符輸出；單字符即時交互需系統中斷支持。

作用域與符號表

局部變量遮蔽同名全局變量（需 :: 訪問全局）。嵌套作用域層層遮蔽。
編譯器構建符號表：名字、類型、存儲類別、作用域、可視性、存儲分配信息。
靜態存儲區（全局/靜態局部）vs 動態存儲區（棧/堆）。
static 全局變量限制文件作用域；static 局部變量延長生命周期；static 函數內部鏈接。