C語言動態內存與鏈表：從堆管理到數據結構實戰

編輯：關於C語言

動態數組的困境與鏈表的誕生

C 語言不支持變長數組（VLA 在 C99 標準化但非必須，且棧空間有限）：

int n; scanf("%d", &n);
int arr[n]; // 錯誤：編譯期無法確定大小

解決方案：堆內存動態分配 + 鏈表數據結構。

一、堆內存深度解析

1. 堆與棧的內存佈局

棧：向低地址增長，自動管理，存局部變量、函數參數、返回地址。
堆：向高地址增長，手動管理，存動態分配數據。
兩者相向生長，中間為自由區。防止棧堆碰撞導致崩潰。

典型小內存模型佈局（64KB 總空間）：

代碼段
數據段
BSS段
堆  ← 向上增長
自由空間
棧  ← 向下增長
遠堆

2. 核心堆管理函數

函數	原型	功能	關鍵點
`malloc`	`void* malloc(size_t size)`	分配 size 字節，不初始化	返回 void*，需強制轉型；失敗返回 NULL
`calloc`	`void* calloc(size_t n, size_t size)`	分配 nsize 字節，零初始化*	適合數組/結構體分配
`realloc`	`void* realloc(void* ptr, size_t newsize)`	調整已分配塊大小	可能移動內存，舊指針失效
`free`	`void free(void* ptr)`	釋放內存	ptr 必須來自 malloc 系；雙重釋放導致崩潰

3. 實戰：基於堆的棧實現

#include <stdio.h>
#include <stdlib.h>

#define MAX 50

int *stack = NULL, *top = NULL;

void push(int v) {
    if (top == stack + MAX) { puts("Stack overflow"); exit(1); }
    *++top = v;
}

int pop() {
    if (top == stack) { puts("Stack underflow"); exit(1); }
    return *top--;
}

int main() {
    stack = (int*)malloc(MAX * sizeof(int));
    if (!stack) { puts("Allocation failed"); return 1; }
    top = stack - 1; // 空棧

    int v;
    while (1) {
        printf("Input value (0=pop, -1=exit): ");
        scanf("%d", &v);
        if (v == -1) break;
        if (v != 0) push(v);
        else printf("Popped: %d\n", pop());
    }
    free(stack);
    return 0;
}

二、鏈表：動態數據的終極形態

1. 核心概念

節點 = 數據域 + 指針域（指向下一節點）。
頭指針指向首節點，末節點指針為 NULL。
物理存儲不連續，邏輯連續。
查找需從頭遍歷，O(n)；插入刪除僅調整指針，O(1)（已知前驅）。

2. 節點定義範例

struct Address {
    char name[30];
    char street[40];
    char city[20];
    char state[10];
    char zip[6];
    struct Address *next; // 自引用指針
};

3. 基本操作模板

// 創建節點
struct Address* createNode() {
    return (struct Address*)malloc(sizeof(struct Address));
}

// 尾插法建表
struct Address* append(struct Address* head, struct Address* node) {
    if (!head) return node;
    struct Address* p = head;
    while (p->next) p = p->next;
    p->next = node;
    return head;
}

// 遍歷
void traverse(struct Address* head) {
    for (struct Address* p = head; p; p = p->next) {
        printf("%s @ %s\n", p->name, p->street);
    }
}

// 釋放整表
void freeList(struct Address* head) {
    while (head) {
        struct Address* tmp = head;
        head = head->next;
        free(tmp);
    }
}