一、复杂数据结构序列化：链表、树、图的文件存储与恢复

说实话，序列化这个话题，我当年刚入行时觉得很简单——不就是把数据写到文件里嘛。直到有一次，我负责一个网络设备的配置管理系统，需要把一棵复杂的路由树持久化到磁盘。嗯，那次差点翻车。今天我就把这些年踩过的坑和总结的经验，一次性说清楚。

1. 什么是序列化？为什么要序列化？

序列化，说白了就是把内存里的复杂数据结构，比如链表、树、图，转换成一种可以存储或传输的格式。反过来，从文件恢复成内存结构，就叫反序列化。

你想想看，程序一退出，内存里的数据就没了。如果你想让数据“活”下来，就得把它写到文件里。但链表、树这些结构，节点之间都是指针相连的，指针是内存地址，换个进程、换个时间，地址就变了。所以你不能直接存指针，得存“关系”。

2. 链表的序列化与反序列化

链表是最简单的。我个人的习惯是，用“前序遍历 + 特殊标记”的方式。比如单向链表，每个节点存一个值和一个next指针。序列化时，我按顺序把每个节点的值写进去，节点之间用逗号或换行分隔。反序列化时，按顺序读出来，一个个创建节点，再连起来。

但这里有个坑：如果链表有环呢？

我曾经在一个内存池管理模块里遇到过循环链表。如果按普通方式序列化，就会死循环。解决办法是：记录每个节点的“访问序号”，第一次遇到就写序号+值，第二次遇到只写序号。反序列化时，先创建所有节点，再根据序号重建连接。

// 链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 序列化：简单无环链表
void serialize_list(Node* head, FILE* fp) {
    Node* cur = head;
    while (cur) {
        fprintf(fp, "%d\n", cur->data);
        cur = cur->next;
    }
    fprintf(fp, "#\n");  // 结束标记
}

// 反序列化
Node* deserialize_list(FILE* fp) {
    Node dummy;
    Node* tail = &dummy;
    char line[32];
    
    while (fgets(line, sizeof(line), fp)) {
        if (line[0] == '#') break;
        Node* node = (Node*)malloc(sizeof(Node));
        sscanf(line, "%d", &node->data);
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    return dummy.next;
}

3. 树的序列化与反序列化

树比链表复杂一点，但思路类似。我常用的是“前序遍历 + 空节点标记”。比如二叉树，遍历时遇到空节点就写一个特殊符号（比如 '#'），这样反序列化时就能唯一重建。

你可能会问：为什么不用中序或后序？嗯，前序的好处是，第一个节点就是根节点，反序列化时可以直接创建根，然后递归构建左右子树。后序的话，最后一个才是根，处理起来稍微绕一点。

// 二叉树节点
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 前序序列化
void serialize_tree(TreeNode* root, FILE* fp) {
    if (!root) {
        fprintf(fp, "# ");
        return;
    }
    fprintf(fp, "%d ", root->val);
    serialize_tree(root->left, fp);
    serialize_tree(root->right, fp);
}

// 前序反序列化
TreeNode* deserialize_tree(FILE* fp) {
    char token[16];
    if (fscanf(fp, "%s", token) != 1) return NULL;
    if (token[0] == '#') return NULL;
    
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = atoi(token);
    node->left = deserialize_tree(fp);
    node->right = deserialize_tree(fp);
    return node;
}

4. 图的序列化与反序列化

图是最复杂的。因为图可能有环，而且节点之间的连接关系是任意的。我个人的做法是：

1. 节点列表：先存所有节点的信息（比如ID、值）。
2. 边列表：再存所有边的信息（起点ID、终点ID、权重等）。

举个例子，一个社交关系图，每个人是一个节点，好友关系是边。序列化时，我先写节点数，再写每个节点的ID和名字，然后写边数，再写每条边的两个ID。

// 图节点
typedef struct GraphNode {
    int id;
    char name[32];
    struct GraphNode** neighbors;
    int neighbor_count;
} GraphNode;

// 序列化图（简化版）
void serialize_graph(GraphNode** nodes, int node_count, FILE* fp) {
    // 先写节点数
    fprintf(fp, "%d\n", node_count);
    
    // 写每个节点
    for (int i = 0; i < node_count; i++) {
        fprintf(fp, "%d %s\n", nodes[i]->id, nodes[i]->name);
    }
    
    // 写边数（先统计）
    int edge_count = 0;
    for (int i = 0; i < node_count; i++) {
        edge_count += nodes[i]->neighbor_count;
    }
    fprintf(fp, "%d\n", edge_count / 2);  // 无向图每条边算了两次
    
    // 写每条边（避免重复）
    for (int i = 0; i < node_count; i++) {
        for (int j = 0; j < nodes[i]->neighbor_count; j++) {
            if (nodes[i]->id < nodes[i]->neighbors[j]->id) {
                fprintf(fp, "%d %d\n", nodes[i]->id, 
                        nodes[i]->neighbors[j]->id);
            }
        }
    }
}

5. 知识体系总览

下面这张图，是我总结的序列化核心逻辑。你看一眼，基本就明白整体脉络了。

6. 通用序列化格式建议

在实际项目中，我建议你考虑以下几种格式：

格式	优点	缺点	适用场景
纯文本（自定义）	简单、可读性强	解析慢、易出错	小数据量、调试用
JSON	标准、跨语言	体积大、无类型	配置文件、网络传输
二进制（自定义）	体积小、速度快	不可读、跨平台需注意字节序	高性能场景、嵌入式
Protocol Buffers	高效、强类型、可扩展	需要预定义schema	大型系统、微服务

7. 总结

序列化这件事，说白了就是“把内存里的关系，变成文件里的数据”。链表、树、图，复杂度依次递增，但核心思路是一样的：

• 存什么：节点的值 + 节点之间的关系（用ID代替指针）。
• 怎么存：顺序、前序、层序，选一种能唯一重建的顺序。
• 注意什么：环、空节点、孤立节点、递归深度、字节序。

嗯，差不多就这些。如果你在实际项目中遇到什么奇葩的序列化问题，欢迎来交流。毕竟，踩坑是成长的必经之路嘛。

---