您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C語言雙層鏈表實現：節點嵌套節點的動態數據結構設計與完整代碼

編輯：C 語言入門

什麼是雙層鏈表？

雙層鏈表：外層鏈表的每個節點，其數據域不再是基礎類型，而是另一條完整的內層鏈表頭指針。形成「鏈表的鏈表」結構，適用於二維動態數據（如矩陣、圖鄰接表、多級菜單、分塊存儲）。

數據結構定義


// 內層節點：存放實際數據
struct SmallNode {
    int num;                // 內層索引
    int data;               // 業務數據
    struct SmallNode *next; // 指向下一個內層節點
};
typedef struct SmallNode SmallNode;

// 外層節點：頭指針指向一條內層鏈表
struct BigNode {
    int num;                    // 外層索引
    SmallNode *headSmall;       // 內層鏈表頭指針
    struct BigNode *next;       // 指向下一個外層節點
};
typedef struct BigNode BigNode;

構建算法：雙重循環動態分配

BigNode *build_double_list(int outer_size, int inner_size, int *data_source) {
    BigNode *headBig = NULL, *tailBig = NULL;
    
    for (int i = 0; i < outer_size; ++i) {
        // 1. 分配外層節點
        BigNode *big = malloc(sizeof(BigNode));
        big->num = i;
        big->next = NULL;
        big->headSmall = NULL;
        
        // 2. 構建內層鏈表
        SmallNode *headSmall = NULL, *tailSmall = NULL;
        for (int j = 0; j < inner_size; ++j) {
            SmallNode *small = malloc(sizeof(SmallNode));
            small->num = j;
            small->data = data_source[i * inner_size + j]; // 或隨機生成
            small->next = NULL;
            
            if (!headSmall) headSmall = tailSmall = small;
            else { tailSmall->next = small; tailSmall = small; }
        }
        big->headSmall = headSmall;
        
        // 3. 掛入外層鏈表
        if (!headBig) headBig = tailBig = big;
        else { tailBig->next = big; tailBig = big; }
    }
    return headBig;
}

遍歷與訪問

void print_double_list(BigNode *head) {
    for (BigNode *b = head; b; b = b->next) {
        printf("外層節點 %d (地址 %p) → 內層: ", b->num, (void*)b);
        for (SmallNode *s = b->headSmall; s; s = s->next) {
            printf("[%d:%d] ", s->num, s->data);
        }
        puts("");
    }
}

// 訪問指定座標 (i, j)
int get_value(BigNode *head, int i, int j) {
    BigNode *b = head;
    for (int k = 0; k < i && b; ++k) b = b->next;
    if (!b) return -1; // 越界
    
    SmallNode *s = b->headSmall;
    for (int k = 0; k < j && s; ++k) s = s->next;
    return s ? s->data : -1;
}

內存釋放：遞歸/雙層釋放

void free_double_list(BigNode *head) {
    BigNode *b = head;
    while (b) {
        // 釋放內層鏈表
        SmallNode *s = b->headSmall;
        while (s) {
            SmallNode *tmp = s;
            s = s->next;
            free(tmp);
        }
        // 釋放外層節點
        BigNode *tmp = b;
        b = b->next;
        free(tmp);
    }
}

完整可運行示例（C99）

#include 
#include 

struct SmallNode { int num, data; struct SmallNode *next; };
struct BigNode { int num; struct SmallNode *headSmall; struct BigNode *next; };

int main() {
    const int OUTER = 3, INNER = 4;
    int src[] = {1,2,3,4, 10,20,30,40, 100,200,300,400};
    
    struct BigNode *head = NULL, *tail = NULL;
    
    // 構建
    for (int i = 0; i < OUTER; ++i) {
        struct BigNode *b = malloc(sizeof(*b));
        b->num = i; b->next = NULL; b->headSmall = NULL;
        
        struct SmallNode *hs = NULL, *ts = NULL;
        for (int j = 0; j < INNER; ++j) {
            struct SmallNode *s = malloc(sizeof(*s));
            s->num = j; s->data = src[i*INNER+j]; s->next = NULL;
            if (!hs) hs = ts = s;
            else { ts->next = s; ts = s; }
        }
        b->headSmall = hs;
        
        if (!head) head = tail = b;
        else { tail->next = b; tail = b; }
    }
    
    // 遍歷驗證
    for (struct BigNode *b = head; b; b = b->next) {
        printf("Big[%d] @%p: ", b->num, (void*)b);
        for (struct SmallNode *s = b->headSmall; s; s = s->next)
            printf("Small[%d]=%d ", s->num, s->data);
        puts("");
    }
    
    // 釋放
    free_double_list(head);
    return 0;
}

輸出結果

Big[0] @0x55a1a3c2e2a0: Small[0]=1 Small[1]=2 Small[2]=3 Small[3]=4 
Big[1] @0x55a1a3c2e2d0: Small[0]=10 Small[1]=20 Small[2]=30 Small[3]=40 
Big[2] @0x55a1a3c2e300: Small[0]=100 Small[1]=200 Small[2]=300 Small[3]=400

進階變體與應用場景

變體	結構調整	典型應用
雙向雙層	內/外層均加 `prev` 指針	需反向遍歷的矩陣、文本編輯器行/字符雙層
不規則內層長度	每外層節點內層長度不同	鋸齒數組、稀疏矩陣、圖鄰接表
內層為動態數組	`int *data; int size, capacity;`	高性能隨機訪問 + 外層動態增刪
環狀雙層	外層尾接頭、內層尾接頭	輪詢調度、循環緩衝區矩陣