在處理單向鏈表時,節點插入是最基礎也最容易出錯的操作之一。許多初學者在寫插入函數時,都會遇到一個棘手的問題:插入頭節點與插入非頭節點的邏輯截然不同。前者需要修改頭指標本身,後者則修改前驅節點的 link 欄位。這導致代碼中充斥著 if (pos == head) ... else ... 的分支判斷,不僅冗餘,還增加了出錯概率。
《C和指標》一書提供了一個優雅的解決思路:換個角度看問題。鏈表中每個節點都有一個指標指向它——對於第一個節點,這個指標就是頭指標 head;對於其他節點,則是前驅節點的 link 域。既然「每個節點都有一個指標指向它」,那麼我們就可以用完全一致的方式去修改這個指標,而無需關心它是頭指標還是某個節點的 link 域。
要實現這種統一操作,函數參數必須接收指標的地址,即 Node **linkp。這樣在函數內部通過 *linkp 就能統一訪問並修改「指向目標節點的那個指標」,無論它是 head 還是 prev->link。
int insert(register Node **linkp, int new_value) {
register Node *current;
register Node *new_node;
/* 1. 尋找插入位置:遍歷直到找到值大於等於新值的節點 */
while ((current = *linkp) != NULL && current->value < new_value)
linkp = ¤t->link; // 關鍵:linkp 移動到「下一個節點的指標位置」
/* 2. 分配新節點內存 */
new_node = (Node *)malloc(sizeof(Node));
if (new_node == NULL) return FALSE;
new_node->value = new_value;
/* 3. 插入節點:統一邏輯,無特殊分支 */
new_node->link = current;
*linkp = new_node; // 修改「指向 current 的那個指標」,指向新節點
return TRUE;
}
insert(&head, 3),linkp 指向 head。current = *linkp 取出頭節點地址;若需繼續往後,linkp = ¤t->link 使 linkp 指向當前節點的 link 域。此時 linkp 不再指向 head,而是指向某個節點內部的 link 欄位。*linkp = new_node 修改的正是 linkp 當前指向的那個指標(可能是 head,也可能是某 prev->link),完美統一。初看代碼時,我擔心:*linkp = new_node 若修改了 head,那麼原本的頭節點豈不丟失?實際測試證明鏈表完好無損。經高人指點才恍然大悟:當插入位置非頭節點時,linkp 已在循環中被更新為 ¤t->link,不再指向 head! 因此最後賦值修改的是前驅節點的 link,head 根本未被觸動。這正是「指標的指標」威力所在——它動態追蹤「應該修改哪個指標」。
register 關鍵字建議編譯器將變量存入寄存器,提升熱點循環效率(現代編譯器通常會自動優化)。這段代碼調試過程雖曲折,但最終通關的暢快,比書本上的現成答案更寶貴。希望這份分析能幫助正在學習 C 指標的同行少走彎路。