數據結構：動態存儲管理 - 存儲緊縮算法實現 (嚴蔚敏版)

編輯：關於C語言

數據結構：動態存儲管理 - 存儲緊縮算法實現 (嚴蔚敏版)

本文介紹《數據結構》(嚴蔚敏、吳偉民版) 第 8 章「動態存儲管理」中「存儲緊縮」算法的 C 語言完整實現，包含頭檔、核心源碼、測試主程式與運行結果展示。

算法原理：堆結構與存儲緊縮

堆：一塊地址連續的可利用存儲區，由堆指標指向最低/最高地址
分配：堆指標向高位移動 N 個單位，原指標值為分配塊起始地址
回收/緊縮：釋放塊必須合併回堆，將所有佔用塊移向低地址，高地址形成大塊連續空閒區
觸發時機：即時回收 vs 空間不足時批量緊縮

源碼結構

StorageCompacting/
├── StorageCompacting.h    // 數據結構定義
├── StorageCompacting.c    // 核心算法實現
└── StorageCompacting-main.c  // 測試驅動程式

1. 頭檔：StorageCompacting.h

StorageCompacting.h

定義塊描述符、堆管理結構、操作介面：

Block：{ addr, size, tag } (tag=0 空閒, 1 佔用)
Heap：{ base, size, blocks[], count }
操作：InitHeap、Alloc、Free、Compact、PrintHeap

2. 核心實現：StorageCompacting.c

StorageCompacting.c 部分

關鍵函數邏輯：

// 緊縮核心：將所有佔用塊向低地址移動
void Compact(Heap *h) {
    int free_pos = 0;  // 下一個空閒位置
    for (int i = 0; i < h->count; i++) {
        if (h->blocks[i].tag == OCCUPIED) {
            if (i != free_pos) {
                // 移動數據內容 (memmove 處理重疊)
                memmove(h->base + free_pos * UNIT_SIZE,
                        h->base + h->blocks[i].addr * UNIT_SIZE,
                        h->blocks[i].size * UNIT_SIZE);
                h->blocks[i].addr = free_pos;
            }
            free_pos += h->blocks[i].size;
        }
    }
    // 合併尾部空閒塊
    // 更新 blocks 陣列...
}