C 語言實現通用雙向鏈表與動態數組

項目背景

研讀《系統程序員成長計劃》時，作者強調雙向鏈表與動態數組是實戰項目中最高頻的數據結構。筆者曾在 SIP Trunk 項目中用鏈表實現電話請求隊列，深感其重要。書中要求實現「不限數據類型」的通用版本，本文先以整數版為切入點，梳理核心邏輯，並指出向通用化擴展的關鍵點。

一、雙向鏈表設計

1. 數據結構定義 (Line.h)

// 節點結構
typedef struct _lineNode {
    int data;                 // 數據域（通用版改為 void* ）
    struct _lineNode *prep;   // 前驅指針
    struct _lineNode *next;   // 後繼指針
} LineNode;

// 鏈表頭結構
typedef struct _lineHead {
    LineNode *head;           // 頭節點指針
    int NodeNum;              // 節點計數
} LineHead;

通用化關鍵：將 int data 改為 void* data，並引入銷毀回調函數指針，實現異構數據存儲。

2. 核心接口

• CreateLine() / DeleteLine()：創建/銷毀鏈表頭
• CreateNode(data)：創建節點
• PushNode(head, node)：尾插法添加節點
• PopNode(head)：彈出尾節點（調用者負責釋放）
• InsertNode(head, node, local)：指定位置插入（0-based）
• GetNode(head, local) / GetNodeData(head, local)：按索引獲取節點/數據
• ShowLine(head)：遍歷打印

3. 關鍵實現細節 (Line.c)

• 錯誤處理：定義錯誤碼枚舉，統一用 printf(__FILE__, __LINE__, errmsg) + exit(0)（生產環境建議改為斷言或返回錯誤碼）。
• 內存分配檢查：每次 malloc 後必判空。
• 指針維護：插入/刪除時仔細處理 prep/next 及頭節點指針，避免斷鏈。
• 傳出參數安全：PopNode/GetNode 返回前將節點指針域置 NULL，防止調用者誤訪問已釋放內存。

二、動態數組設計

1. 數據結構 (DArray.h / DArray.c)

struct _darray {
    int *data;        // 數據緩衝區（通用版改為 void** ）
    int size;         // 當前元素數
    int alloc_size;   // 已分配容量
};

採用「預分配 + 指數增長」策略：

// 擴容邏輯：alloc_size + alloc_size/2 + MIN_PRE_ALLOCATE_NR (10)
alloc_size = darray->alloc_size + (darray->alloc_size >> 1) + MIN_PRE_ALLOCATE_NR;

縮容策略：當 size < alloc_size/2 且 alloc_size > MIN_PRE_ALLOCATE_NR 時觸發，避免頻繁縮擴抖動。

2. 核心接口

• DArray_Create() / DArray_Destroy()
• DArray_Insert(darray, data, local)：指定位置插入（超尾則追加）
• DArray_Delete(darray, local)：刪除並觸發縮容檢查
• DArray_GetData/SetData：隨機訪問 O(1)
• DArray_Sort(darray, sort_func, cmp_func)：策略模式，外部注入排序算法（冒泡/快排/歸並）與比較函數

3. 排序算法示例

• 冒泡排序：教學用，O(n²)
• 快速排序：原地分區，平均 O(n log n)，內存數據首選
• 歸並排序：需額外 O(n) 空間，穩定，適合外部排序/大數據

所有排序均通過回調 DataCompareFunc 實現升/降序切換，體現「關注點分離」。

三、通用化遷移指南

1. 數據域改為 void*，頭結構增加 void (*free_func)(void*) 銷毀回調。
2. 插入/設置函數改為接收 void*，內部僅拷貝指針（淺拷貝），所有權語義由調用方定義。
3. 比較函數簽名改為 int (*cmp)(const void*, const void*)，排序時傳遞元素地址。
4. 提供 DArray_ForEach(darray, callback, ctx) 遍歷接口，替代硬編碼打印。

四、總結與反思

雙向鏈表適合頻繁頭尾插刪、不需要隨機訪問的場景；動態數組適合隨機訪問多、尾部增刪為主的場景。兩者通用化核心在於 void* + 回調函數，將數據類型知識下沉至調用層。代碼雖有簡陋處（錯誤處理、無迭代器），但架構清晰，是進階系統級 C 開發的紮實練習。