鏈表的 C 語言實現（含動態記憶體分配）

上篇：動態記憶體分配基礎

為什麼需要動態記憶體分配？

靜態陣列需預先定義大小，常導致記憶體浪費或下標越界。動態記憶體分配在程式執行時依需求即時分配/釋放空間，特點：

1. 無需預先分配儲存空間。
2. 空間大小可隨程式需求動態擴增或縮減。

核心函數

1. malloc 函數

void *malloc(unsigned int size);

• 在動態儲存區分配連續 size 位元組，回傳起始位址指標。
• 失敗回傳 NULL，調用時必須檢查。

範例：動態分配 10 個整數陣列並賦值列印。

#include "malloc.h"
#include "stdlib.h"
int main() {
    int count, *array;
    array = malloc(10 * sizeof(int));
    if (array == NULL) { printf("Out of memory!\n"); exit(1); }
    for (count = 0; count < 10; count++) array[count] = count;
    for (count = 0; count < 10; count++) printf("%2d\n", array[count]);
    return 0;
}

2. free 函數

void free(void *p);

• 釋放指標 p 指向的記憶體區塊。
• 參數必須為 malloc 或 calloc 回傳的指標值，否則可能導致崩潰。
• 多個指標指向同一區塊時，任一指標皆可釋放（如 p2 = p1; free(p2);）。

中篇：單向鏈表實作

節點結構

typedef struct node {
    char name[20];
    struct node *link;
} stud;

含資料域 (name) 與鏈域 (link)，指向直接後繼節點。

帶表頭單向鏈表建立完整程式

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define N 10

typedef struct node {
    char name[20];
    struct node *link;
} stud;

stud *creat(int n) {
    stud *p, *h, *s;
    int i;
    if ((h = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("不能分配記憶體空間!"); exit(0);
    }
    h->name[0] = '\0'; h->link = NULL; // 表頭初始化
    p = h;
    for (i = 0; i < n; i++) {
        if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
            printf("不能分配記憶體空間!"); exit(0);
        }
        p->link = s;                 // 串聯
        printf("請輸入第%d個人的姓名", i+1);
        scanf("%s", s->name);        // 資料域賦值
        s->link = NULL;
        p = s;                       // 移動 p 到新節點
    }
    return h;
}

int main() {
    int number = N;
    stud *head = creat(number);
    return 0;
}

建議：動態分配程式務必檢查回傳值是否為 NULL。

下篇：循環鏈表與雙向鏈表

循環鏈表

最後一個節點指標指向表頭（或第一個節點），形成環狀。運算與單向鏈表類似，差異：

1. 建立時尾節點指向表頭而非 NULL；尾部插入新節點同理。
2. 判斷表尾條件為 node->link == head，而非 NULL。

雙向鏈表

節點含兩個鏈域：右鏈域 (rlink) 指向後繼，左鏈域 (llink) 指向前驅，解決單向鏈表查找前驅需從頭遍歷的缺點。

typedef struct node {
    int data;
    struct node *llink, *rlink;
} JD;

雙向鏈表適用於頻繁雙向遍歷、插入刪除的場景。