圖的持久化存儲：從內存指釖結構到磁盤序列化的完整方案

一、問題背景：指針在外存中失效

前文定義的圖結構大量使用指針：

typedef struct _LINE  { int end, weight; struct _LINE* next; } LINE;
typedef struct _VECTEX { int start, number; LINE* neighbor; struct _VECTEX* next; } VECTEX;
typedef struct _GRAPH  { int count; VECTEX* head; } GRAPH;

核心難題：指針存儲的是虛擬內存地址，寫入磁盤後重新讀取時地址映射完全改變，原指針失效。

二、核心思路：指針 → 偏移量

將所有指針轉換為相對文件開頭的字節偏移量。存儲佈局規劃：

[ GRAPH頭部 ][ VECTEX數組 ][ LINE數組 ]
     ↓             ↓            ↓
  count          start         end
  head_offset    number        weight
                 neighbor_off  (無next，隱式連續)
                 (無next，隱式連續)

三、優化存儲結構：極致精簡

利用連續存儲特性消除冗餘偏移：

// 磁盤存儲結構（無指針）
typedef struct _LINE_DISK   { int end; int weight; } LINE_DISK;
typedef struct _VECTEX_DISK { int start; int number; int neighbor_offset; } VECTEX_DISK;
typedef struct _GRAPH_DISK  { int count; } GRAPH_DISK;  // head_offset 固定為 sizeof(GRAPH_DISK)

優化邏輯：

• GRAPH 固定在文件開頭，首個 VECTEX 緊隨其後 → head_offset 固定，無需存儲
• VECTEX 數組連續存放 → next 隱含為下一個結構體位置，無需存儲
• 同一頂點的所有 LINE 連續存放 → LINE.next 隱含為下一個 LINE 位置，無需存儲
• 僅保留 VECTEX.neighbor_offset 指向該頂點第一條邊的位置

四、序列化寫入算法

void save_graph(FILE* fp, GRAPH* graph) {
    // 1. 寫入 GRAPH 頭部
    GRAPH_DISK header = { graph->count };
    fwrite(&header, sizeof(GRAPH_DISK), 1, fp);
    
    // 2. 遍歷頂點，記錄每個頂點的邊起始位置
    VECTEX* v = graph->head;
    long* vtx_positions = malloc(graph->count * sizeof(long));
    long* edge_start_pos = malloc(graph->count * sizeof(long));
    
    for (int i = 0; i < graph->count; i++) {
        vtx_positions[i] = ftell(fp);
        VECTEX_DISK vd = { v->start, v->number, 0 }; // neighbor_offset 稍後回填
        fwrite(&vd, sizeof(VECTEX_DISK), 1, fp);
        v = v->next;
    }
    
    // 3. 寫入邊並回填 neighbor_offset
    v = graph->head;
    for (int i = 0; i < graph->count; i++) {
        edge_start_pos[i] = ftell(fp);
        LINE* e = v->neighbor;
        while (e) {
            LINE_DISK ld = { e->end, e->weight };
            fwrite(&ld, sizeof(LINE_DISK), 1, fp);
            e = e->next;
        }
        v = v->next;
    }
    
    // 4. 回填 neighbor_offset (需 fseek 回頂點區)
    for (int i = 0; i < graph->count; i++) {
        fseek(fp, vtx_positions[i] + offsetof(VECTEX_DISK, neighbor_offset), SEEK_SET);
        fwrite(&edge_start_pos[i], sizeof(int), 1, fp);
    }
    
    free(vtx_positions); free(edge_start_pos);
}

五、反序列化讀取算法

GRAPH* load_graph(FILE* fp) {
    // 1. 讀取頭部
    GRAPH_DISK header;
    fread(&header, sizeof(GRAPH_DISK), 1, fp);
    
    GRAPH* graph = malloc(sizeof(GRAPH));
    graph->count = header.count;
    graph->head = NULL;
    
    // 2. 讀取所有頂點到內存數組
    VECTEX_DISK* vtx_array = malloc(header.count * sizeof(VECTEX_DISK));
    fread(vtx_array, sizeof(VECTEX_DISK), header.count, fp);
    
    // 3. 讀取所有邊到內存數組 (需預知總邊數或分兩遍讀取)
    // 此處假設已知總邊數或使用動態數組
    
    // 4. 重建內存指針結構
    VECTEX* prev = NULL;
    for (int i = 0; i < header.count; i++) {
        VECTEX* v = malloc(sizeof(VECTEX));
        v->start = vtx_array[i].start;
        v->number = vtx_array[i].number;
        v->next = NULL;
        
        // 重建邊鏈表
        LINE* e_head = NULL, *e_tail = NULL;
        // 根據 vtx_array[i].neighbor_offset 讀取對應邊數據...
        
        v->neighbor = e_head;
        
        if (prev) prev->next = v;
        else graph->head = v;
        prev = v;
    }
    
    free(vtx_array);
    return graph;
}

六、工程落地關鍵點

七、總結

圖的持久化本質是指針豐富圖向扁平序列的轉換。關鍵技巧：

1. 拓撲排序確定寫入順序（先頂點後邊）
2. 偏移量替代指針，利用連續存儲消除冗餘
3. 兩遍寫入：首遍佔位，二遍回填偏移
4. 加載時重建指針拓撲，恢復內存操作便利性

此方案不僅適用於圖，對任意指針豐富的數據結構（樹、鏈表、NFA 圖等）均具通用指導意義。