C99嵌套盒子最大套娃序列求解代码测试异常求助

代码问题诊断 #

1. 核心逻辑错误 #

你当前使用的贪心策略完全错误：box->inside.count是当前盒子可直接容纳的盒子总数，而非「以该盒子为起点的最大嵌套深度」。局部选择直接容纳数量最多的盒子，无法得到全局最长的嵌套序列。
举个简单的反例：盒子A可直接放10个盒子，但这10个盒子都无法互相嵌套，最大嵌套长度仅为2；盒子B只能直接放3个盒子，但其中一个盒子可再嵌套4层，总长度可达6。你的代码会错误选择A，导致结果比预期短。

2. 内存分配类型错误 #

main函数中初始化boxes.elements时，分配的内存类型错误：elements是struct Box**指针数组，你分配的是sizeof(struct Box)，应该改为sizeof(struct Box*)，n较大时会直接触发内存越界崩溃。

修复方案 #

第一步：扩展Box结构体字段，记录深度和路径 #

struct Box {
    int id;
    double x;
    double y;
    double z;
    struct Array inside;
    int max_depth; // 新增：以当前盒子为最外层的最大嵌套深度
    struct Box *next_inner; // 新增：最长序列中当前盒子的下一个内层盒子
};

第二步：新增递归计算最大深度的函数 #

int calc_max_depth(struct Box *box) {
    // 已计算过深度直接返回
    if (box->max_depth != 0) return box->max_depth;
    // 初始深度为1（仅盒子自身）
    box->max_depth = 1;
    box->next_inner = NULL;
    // 遍历所有可直接放入的内部盒子，找能得到最长序列的选项
    for (int i = 0; i < box->inside.count; i++) {
        struct Box *inner = box->inside.elements[i];
        int inner_depth = calc_max_depth(inner);
        if (inner_depth + 1 > box->max_depth) {
            box->max_depth = inner_depth + 1;
            box->next_inner = inner;
        }
    }
    return box->max_depth;
}

第三步：修改main逻辑，选择全局最长序列的最外层盒子 #

修正内存分配错误，同时替换原来的最优盒子选择逻辑：

int main(int argc, char *argv[]) {
    FILE *file = fopen(argv[1], "r");
    if (!file) {
        printf("No input or can't open the input file");
        return EXIT_FAILURE;
    }

    fscanf(file, "%d\n", &n);
    double x, y, z;
    // 修正内存分配错误
    Boxes boxes = {n, malloc(n * sizeof(struct Box*))};

    for (int i = 0; fscanf(file, "%lf%lf%lf", &x, &y, &z) != EOF; i++) {
        struct Box *box = malloc(sizeof(struct Box));
        box->id = i;
        box->x = x;
        box->y = y;
        box->z = z;
        box->max_depth = 0;
        box->next_inner = NULL;
        boxes.elements[i] = box;
    }
    fclose(file);

    for (int i = 0; i < boxes.count; ++i) {
        struct Box *box = boxes.elements[i];
        box->inside = find_inside_boxes(boxes, box);
    }

    // 遍历所有盒子找全局最长序列的起点
    int global_max_depth = 0;
    struct Box *best = NULL;
    for (int i = 0; i < boxes.count; ++i) {
        int cur_depth = calc_max_depth(boxes.elements[i]);
        if (cur_depth > global_max_depth) {
            global_max_depth = cur_depth;
            best = boxes.elements[i];
        }
    }

    print_inside_boxes(best);

    return EXIT_SUCCESS;
}

第四步：修改输出逻辑，按路径输出序列 #

void print_inside_boxes(struct Box *box) {
    Boxes boxes = {0, NULL};
    while (box != NULL) {
        array_append(&boxes, box, true);
        box = box->next_inner;
    }
    print_boxes(boxes);
}

原来的find_best_box函数已经不需要使用，可以直接删除。

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