C/C++ 學習之路（第 05 課）：路由表查找演算法完整實作

專案背景：模擬靜態路由器轉發決策

路由器核心功能之一是根據目的 IP 位址，在路由表中尋找最匹配的網路前綴，決定封包轉發介面。本專案以鏈結串列實作動態路由表，模擬「最長前綴匹配」邏輯，包含路由項目新增、顯示、封包轉發決策完整流程。

資料結構設計

typedef struct RouteNode {
    int ip[4];           // 網路位址 (如 192.168.1.0)
    int subnetMask[4];   // 子網路遮罩 (如 255.255.255.0)
    int port;            // 輸出介面編號
    struct RouteNode *next; // 下一筆路由記錄
} RouterTableList;

採用「表頭節點不存資料」的單向鏈結串列，便於插入與刪除操作。

核心演算法：最長前綴匹配

函式 findPort() 遍歷路由表，對每一項執行：

1. 將目的 IP 與該項子網路遮罩逐位元組做 AND 運算
2. 比較結果是否等於該項網路位址
3. 若全部 4 位元組匹配，回傳該項 port
4. 若遍歷完畢無匹配，回傳 -1 表示丟棄封包

int findPort(RouterTableList *rtl, int dist_ip[]) {
    RouterTableList *node = rtl->next;
    int i;
    while (node != NULL) {
        for (i = 0; i < 4; i++)
            if ((dist_ip[i] & node->subnetMask[i]) != node->ip[i]) break;
        if (i >= 4) return node->port; // 找到匹配
        node = node->next;
    }
    return -1; // 無匹配路由
}

完整程式碼結構

• routerTableArithmetic() — 主流程：建立路由表、輸入測試封包、呼叫查找、輸出結果
• inputRouterTable() — 硬編碼建立 3 筆測試路由 (192.168.1.0/24, 192.168.2.0/24, 192.168.3.0/24)
• addRouteNode() — 尾插法新增路由節點
• displayRouterTable() — 格式化列印路由表內容

執行結果範例

********** print route table **************
IP: 192.168.1.0   subnetMask: 255.255.255.0   port: 1
IP: 192.168.2.0   subnetMask: 255.255.255.0   port: 2
IP: 192.168.3.0   subnetMask: 255.255.255.0   port: 3
********** 數據包將從路由器的端口 2 轉發出去**************

擴充方向

• 支援 CIDR 表示法 (如 192.168.1.0/24) 輸入解析
• 實作最長前綴匹配 (Longest Prefix Match) — 當多條路由匹配時選擇遮罩最長者
• 加入動態路由協議模擬 (RIP, OSPF 簡化版)
• 使用 Trie 樹 (前綴樹) 優化查找效能至 O(32)

心得

花費三小時完成，過程中重溫了指標操作、位元運算、鏈結串列操作等核心技能。網路程式設計看似高深，拆解後皆是基礎資料結構與演算法的組合。建議初學者嘗試自行實作網路協議核心邏輯，是鞏固 C 語言功力的最佳途徑。