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

C語言入門：堆內存管理與鏈表實現詳解

編輯：C 語言入門

在 C 語言中，若需根據運行時輸入的整數動態確定數組大小，直接寫 int n, array[n]; 在 Turbo C 等編譯器中是非法的，因為不支援變長數組（VLA）。此時必須借助堆內存動態分配，並結合鏈表數據結構來實現動態數據存儲。

一、堆內存詳解

堆是動態存儲結構，實際上是數據段中的自由存儲區。堆分配以 2 字節整數倍進行，地址向高位增長。堆與棧相向生長：棧向低地址增長，堆向高地址增長，中間為自由空間。防止雙方過度增長導致覆蓋至關重要。

小內存模式下的內存佈局

________________
| 代碼段       |
|--------------|
| 數據段       |
|--------------|
| BSS段        |
|--------------|
| 堆           |
|--------------| 自由空間
|--------------|
| 棧           |
|--------------|
| 遠堆         |
|--------------|
|______________| 自由空間

堆、棧之間及遠堆之後均為自由空間，總共 64KB。

堆管理核心函數

獲取剩餘空間：coreleft()（小模式返回 unsigned，大模式返回 unsigned long），遠堆用 farcoreleft()。
分配堆空間：void *malloc(unsigned size) 分配 size 字節，返回 void* 需強轉類型。如 struct addr *info = (struct addr*)malloc(sizeof(record));。空間不初始化，失敗返回 NULL。
分配並初始化：void *calloc(unsigned n, unsigned size) 分配 n*size 字節並零初始化，失敗返回 NULL。
重新分配：void *realloc(void *ptr, unsigned newsize) 調整 ptr 指向空間大小為 newsize。
釋放空間：void free(void *ptr)。

綜合示例：用堆實現棧

void push(int); int pop();
int *pi, *tos;

main() {
    int v;
    pi = (int*)malloc(50 * sizeof(int));
    if (!pi) { printf("allocation failure\n"); exit(0); }
    tos = pi;
    do {
        printf("please input value, push it; enter 0 then pop; (enter -1 then stop)\n");
        scanf("%d", &v);
        if (v != 0) push(v);
        else printf("pop this is it %d\n", pop());
    } while (v != -1);
}

void push(int i) {
    pi++;
    if (pi == (tos + 50)) { printf("stack overflow\n"); exit(0); }
    *pi = i;
}

int pop() {
    if (pi == tos) { printf("stack underflow\n"); exit(0); }
    pi--;
    return *(pi + 1);
}

程序分配 100 字節堆空間模擬棧，演示後進先出特性。

二、鏈表詳解

鏈表是動態數據的典型例子。若干數據項按邏輯順序鏈接，每項含指向下一項的指針，最後一項指針為 NULL。鏈表節點在內存中可不連續，通過指針串聯。查找節點必須從頭節點遍歷。鏈表在數據庫建立管理中廣泛應用。

節點結構定義

struct address {
    char name[30];
    char street[40];
    char city[20];
    char state[10];
    char zip[6];
    struct address *next;  // 指向同類型下一節點
} list_entry;

1. 建立鏈表

用 malloc 分配節點空間，將地址賦給指針。首節點地址賦給頭指針，後續節點地址賦給前一節點的 next，逐步鏈接。

void dls_store(struct address *in) {
    static struct address *last = NULL;  // 靜態變量保持尾指針
    if (!last) last = in;                // 首節點
    else last->next = in;                // 鏈接到尾部
    in->next = NULL;
    last = in;                           // 更新尾指針
}

last 為靜態局部變量，初始化一次，生命周期贯穿整個程序，避免了全局變量污染。

2. 鏈表插入與刪除

假設鏈表已按升序排列，插入新節點 in 有三種情況：

小於首項：in->next = top; 成為新頭
大於尾項：old->next = in; in->next = NULL; 成為新尾
中間插入：old->next = in; in->next = top;

刪除節點 in（前驅 old，後繼 top）：old->next = top->next; 並 free(in) 釋放空間。

void delete(struct address *info, struct address *old) {
    if (info) {
        if (info == start) start = info->next;
        else { old->next = info->next; last = old; }
        free(info);
    }
}

struct address *search(struct address *top, char *n) {
    while (top) {
        if (!strcmp(n, top->name)) return top;
        top = top->next;
    }
    return NULL;
}

void display(struct address *top) {
    while (top) { printf("%s\n", top->name); top = top->next; }
}