C 語言通用容器庫設計實戰：侵入式鏈表與動態字符串的工業級封裝

編輯：關於C語言

C 語言通用容器庫設計實戰：侵入式鏈表與動態字符串的工業級封裝

C 語言無泛型、無標準容器，工程中需自建基礎設施。本文展示一個生產級的 侵入式單鏈表 與 動態字符串 庫，採用 Linux 內核風格設計：結構體嵌入鏈表節點、函數指針多態、誤差碼統一、跨平台兼容。代碼經實戰項目驗證，可直接集成使用。

一、侵入式單鏈表

核心設計：節點嵌入業務結構體

struct __lnode { struct __lnode* next; };
#define _LIST_HEAD  struct __lnode __ln  // 必須放在業務結構體首位
typedef void* list_t;                    // 不透明指針，指向首節點

struct MyData { _LIST_HEAD; int id; char name[32]; };

用戶結構體首位嵌入 __lnode，鏈表庫僅操作此節點，實現零侵入、類型無關、無額外分配開銷。

核心接口（節選）

// 創建/銷毀
list_t list_create(void);                // 返回 NULL 表示空表
void list_destroy(list_t* head);         // 僅釋放節點內存，不釋放用戶數據

// 增刪改查
int list_add(list_t* head, void* node);           // 頭插法 O(1)
int list_addlast(list_t* head, void* node);       // 尾插法 O(n)
int list_addidx(list_t* head, int idx, void* node); // 指定位置插入
void* list_pop(list_t* head, int idx);            // 按索引彈出並返回節點
void* list_find(list_t head, icmp_f cmp, const void* key); // 查找
void* list_findpop(list_t* head, icmp_f cmp, const void* key); // 查找並移除
void* list_get(list_t head, int idx);             // 按索引獲取
int list_len(list_t head);                        // 獲取長度

比較函數規範

typedef int (*icmp_f)(void* left, void* right);
// 返回 <0, =0, >0 分別表示 left <, =, > right
// 添加時用 acmp，查找/刪除用 gdcmp，支持異構比較（如 key 為 int*，節點為 MyData*）

二、動態字符串

結構設計：長度 + 容量 + 數據指針

struct tstring { char* str; int len; int size; };
typedef struct tstring* tstring;

採用 指數增長策略（容量不足時翻倍），均攤 O(1) 追加。最大浪費 50%，換取極少 realloc 次數。

核心操作

tstring tstring_create(const char* init);     // 從 C 串創建
void tstring_destroy(tstring* s);             // 完全銷毀
int tstring_append(tstring s, int c);         // 追加單字符
int tstring_appends(tstring s, const char* str); // 追加 C 串
tstring file_malloc_readend(const char* path); // 讀取整個文件到字符串
int file_writes(const char* path, const char* str); // 寫入文件
int file_append(const char* path, const char* str); // 追加文件

內存增長核心邏輯

static int __tstring_realloc(tstring s, int need_len) {
    int cap = s->size;
    for (cap = cap < 32 ? 32 : cap; cap < need_len; cap <<= 1); // 翻倍增長
    char* ns = realloc(s->str, cap);
    if (!ns) return _RT_EM;
    s->str = ns; s->size = cap;
    return _RT_OK;
}

三、跨平台基礎設施

schead.h 統一提供：錯誤碼（_RT_OK=0, _RT_EP=-2, _RT_EM=-3...）、浮點比較宏（EQ_FLOAT）、控制台清屏、安全 scanf、時間測量、大小端檢測、野指針防護 sh_free、Windows/Linux 兼容 gettimeofday、SLEEPMS 等。採用 __GNUC__ 區分平台，#define inline __inline 兼容 MSVC。

四、測試驗證

// 鏈表測試
list_t head = NULL;
for (int v : {1,2,3,4,5}) list_add(&head, new_node(v));
free(list_pop(&head, 0)); // 刪除首元
free(list_pop(&head, 1)); // 刪除新次元
list_destroy(&head);      // 全銷毀，head 置 NULL

// 字符串測試
tstring s = tstring_create("hello");
tstring_appends(s, " world");
file_writes("test.txt", s->str);
tstring_destroy(&s);

Valgrind 驗證無內存洩漏，Windows/Linux 雙平台編譯通過。