使用Zig构建哈夫曼编码时触发Segmentation fault错误求助

问题重现 #

构建哈夫曼编码时触发段错误：Segmentation fault at address 0x7ff700000002。打印树节点信息时，第二行输出出现异常值（.freq = 32）并崩溃，预期与实际输出差异如下：

预期输出 #

tree: huffman.Node{ .freq = 15, .value = null, .left = huffman.Node{ .freq = 9, .value = null, .left = huffman.Node{ .freq = 0, .value = 328965, .left = huffman.Node{ ... }, .right = huffman.Node{ ... } }, .right = huffman.Node{ .freq = 2977642760, .value = 32759, .left = huffman.Node{ ... }, .right = null } }, .right = huffman.Node{ .freq = 2977642800, .value = 32759, .left = huffman.Node{ .freq = 3, .value = 197379, .left = null, .right = null }, .right = huffman.Node{ .freq = 2977643128, .value = null, .left = huffman.Node{ ... }, .right = huffman.Node{ ... } } } }
tree: huffman.Node{ .freq = 9, .value = null, .left = huffman.Node{ .freq = 5, .value = 328965, .left = null, .right = null }, .right = huffman.Node{ .freq = 4, .value = 263172, .left = null, .right = null } }

实际输出 #

tree: huffman.Node{ .freq = 15, .value = null, .left = huffman.Node{ .freq = 9, .value = null, .left = huffman.Node{ .freq = 0, .value = 328965, .left = huffman.Node{ ... }, .right = huffman.Node{ ... } }, .right = huffman.Node{ .freq = 2977642760, .value = 32759, .left = huffman.Node{ ... }, .right = null } }, .right = huffman.Node{ .freq = 2977642800, .value = 32759, .left = huffman.Node{ .freq = 3, .value = 197379, .left = null, .right = null }, .right = huffman.Node{ .freq = 2977643128, .value = null, .left = huffman.Node{ ... }, .right = huffman.Node{ ... } } } }
tree: huffman.Node{ .freq = 9, .value = null, .left = huffman.Node{ .freq = 32, .value = 0, .left = huffman.Node{ .freq = Segmentation fault at address 0x7ff700000002

问题根源 #

核心原因是悬挂指针访问失效栈内存：

• 在build_tree函数中，tmp、new_node、item等均为栈上局部变量，函数执行过程中或返回后，这些变量的栈内存会被回收或覆盖，但代码将它们的地址赋值给了Node的left/right指针，形成悬挂指针。
• traverse_tree函数接收Node值而非指针，每次调用都会复制结构体，但指针指向的仍是已失效的栈内存，访问时就会出现垃圾值或触发段错误。
• 虽然build_tree内打印current正常，是因为此时局部变量的栈内存尚未被覆盖，函数返回后栈空间被释放，后续访问就会出问题。

修复方案 #

改用堆内存分配Node节点，确保内存生命周期与树的生命周期一致，同时调整函数逻辑避免悬挂指针。

1. 修改Node结构体，添加堆分配方法 #

const Node = struct {
    freq: u32,
    value: ?u32,
    left: ?*Node,
    right: ?*Node,

    // 堆分配并初始化Node
    fn create(gpa: std.mem.Allocator, freq: u32, value: ?u32, left: ?*Node, right: ?*Node) !*Node {
        const node = try gpa.create(Node);
        node.* = .{
            .freq = freq,
            .value = value,
            .left = left,
            .right = right,
        };
        return node;
    }
};

2. 重构build_tree函数，使用堆分配 #

fn build_tree(gpa: std.mem.Allocator, array: []const Node) !*Node {
    var i: u32 = 1;
    // 初始化根节点为堆分配的第一个数组元素
    var current = try Node.create(gpa, array[0].freq, array[0].value, array[0].left, array[0].right);

    while (i < (array.len - 1)) {
        if (array[i + 1].freq < current.freq) {
            var starting_i = i;
            var ending_i = i;
            while (i < array.len and array[i].freq < current.freq) {
                ending_i += 1;
                i += 1;
            }
            var new_node = try build_tree(gpa, array[starting_i..ending_i]);
            // 堆分配父节点，关联左右子节点
            const parent = try Node.create(gpa, current.freq + new_node.freq, null, new_node, current);
            current = parent;
        } else {
            // 堆分配数组元素节点
            const item = try Node.create(gpa, array[i].freq, array[i].value, array[i].left, array[i].right);
            const parent = try Node.create(gpa, current.freq + item.freq, null, item, current);
            current = parent;
            i += 1;
        }
    }

    if (i < array.len) {
        const last = try Node.create(gpa, array[array.len - 1].freq, array[array.len - 1].value, array[array.len - 1].left, array[array.len - 1].right);
        const parent = try Node.create(gpa, current.freq + last.freq, null, last, current);
        current = parent;
    }

    return current;
}

3. 修改traverse_tree函数，接收Node指针 #

fn traverse_tree(code: u32, tree: *Node, map: *std.HashMap(u32, u32, hash_u32, std.hash_map.default_max_load_percentage)) !void {
    std.debug.print("tree: {?} \n", .{tree.*});
    if (tree.value != null) {
        try map.put(tree.value.?, code);
    } else {
        if (tree.left) |left| try traverse_tree(code * 2, left, map);
        if (tree.right) |right| try traverse_tree(code * 2 + 1, right, map);
    }
}

4. 调整调用逻辑，添加内存释放 #

// 构建树
var tree = try build_tree(gpa, array);
// 递归释放树内存，避免泄漏
defer deallocate_tree(gpa, tree);

var code_map = std.HashMap(u32, u32, hash_u32, std.hash_map.default_max_load_percentage).init(gpa);
defer code_map.deinit();

try traverse_tree(1, tree, &code_map);
return code_map;

5. 实现树内存释放函数 #

fn deallocate_tree(gpa: std.mem.Allocator, node: *Node) void {
    if (node.left) |left| deallocate_tree(gpa, left);
    if (node.right) |right| deallocate_tree(gpa, right);
    gpa.destroy(node);
}

内容的提问来源于stack exchange，提问作者BelMat