C語言結構體與動態內存：鏈表實戰指南

C語言結構體與動態內存：鏈表實戰指南

聲明：原創作品，轉載時請注明文章來自SAP師太博客，並以超鏈接形式標明文章原始出處，否則將追究法律責任！

第八章 結構體與聯合體詳解

結構體聲明與類型等價性

結構體將不同類型數據組合。帶標籤聲明創建類型，可複用：

struct SIMPLE { int a; char b; float c; };
struct SIMPLE x, y[10], *z; // 同一類型

無標籤聲明每次創建新類型，即使成員相同也不兼容。typedef 可創建類型別名簡化聲明。

結構體訪問與自引用

變量用 .，指針用 ->（p->m 等價 (*p).m）。自引用必須用指針，否則大小無限遞歸：

struct NODE { int val; struct NODE *next; }; // 合法
struct BAD { int val; struct BAD next; };   // 非法

相互引用與不完整聲明

相互引用結構需前向聲明：struct B; struct A { struct B *p; };。指針聲明不需完整類型定義。

內存對齊與大小優化

編譯器按聲明順序分配內存，為滿足對齊要求插入填充字節。sizeof 包含填充，offsetof 獲取成員偏移。將成員按類型大小降序排列可最小化浪費：

// 差：char, int, char → 12 字節
// 優：int, char, char → 8 字節

結構體地址等於首成員地址，利用此特性可實現容器指針計算（如 container_of 宏）。

位段

位段將整型按位劃分，節省空間並便於硬件寄存器操作：

struct DISK_REG {
    unsigned cmd:5, sector:5, track:9, err:8;
    unsigned ready:1, wp:1, spin:1, err_occ:1, hd_ld:1;
};
#define DISK_REG ((struct DISK_REG*)0xC0200142)
// 直接操作位段：DISK_REG->cmd = READ;

注意：位段分配順序（左→右或右→左）、int 符號性、最大位寬均依賴實現，移植性較弱。

聯合體

聯合體成員共享同一內存區塊，大小等於最大成員。可通過不同成員解讀相同位模式。初始化只能針對首個成員。若成員大小差異大，建議存儲指針而非值以節省空間。

第九章 動態內存分配

核心函數

• malloc(size)：分配未初始化內存，返回 void*
• calloc(n, size)：分配並歸零
• realloc(ptr, new_size)：調整大小，可能移動內存，必須用返回值更新指針
• free(ptr)：釋放，參數必須為 malloc 系列返回值或 NULL

常見錯誤與防範

• 解引用 NULL 或未初始化指針
• 越界訪問
• 釋放非動態內存或同一塊內存兩次
• 釋放後繼續使用（懸空指針）
• 內存洩漏（分配後未釋放）

安全分配器封裝

宏 MALLOC(n, type) 封裝類型轉換與錯誤檢查，內部調用 alloc() 統一處理失敗退出：

#define MALLOC(num, type) (type*)alloc((num) * sizeof(type))
void *alloc(size_t size) {
    void *p = malloc(size);
    if (!p) { fprintf(stderr, "Out of memory\n"); exit(1); }
    return p;
}

動態字符串複製

strdup 示範運行時確定長度分配：

char *strdup(const char *s) {
    char *p = malloc(strlen(s) + 1);
    if (p) strcpy(p, s);
    return p;
}

第十章 鏈表實現：單向與雙向

單向鏈表插入（有序）

使用二級指針 Node **rootp 統一處理頭節點插入：

int sll_insert(Node **linkp, int val) {
    Node *next = *linkp;
    while (next && next->val < val) {
        linkp = &next->link; // 關鍵：保存指向 link 域的指針
        next = *linkp;
    }
    Node *new = MALLOC(1, Node);
    new->val = val; new->link = next;
    *linkp = new; // 統一修改：或是根指針，或是前驅的 link
    return 1;
}

優化核心：linkp 始終指向「指向當前節點的指針」，消除頭插特殊情況。

雙向鏈表

根節點含 fwd（指向首節點）和 bwd（指向尾節點）。插入需維護四種情況：空表、頭插、尾插、中間插，分別更新相關節點的 fwd/bwd。根節點動態分配時可省略 value 成員：malloc(sizeof(Node) - sizeof(int))。

// 遍歷示例
for (Node *p = root->fwd; p; p = p->fwd) printf("%d ", p->val); // 正向
for (Node *p = root->bwd; p; p = p->bwd) printf("%d ", p->val); // 反向