C语言链表实现仓库空间压缩功能的问题求助

问题分析 #

现有reducespaces函数仅能压缩单个货架内的空单元格，无法实现跨货架物品合并及空货架删除。核心目标需完成：

• 收集仓库内所有非空单元格的物品
• 按顺序重新填充货架，填满一个货架的所有单元格后再使用下一个货架
• 删除所有无物品的空货架

实现步骤 #

1. 收集所有物品 #

遍历仓库全部货架与单元格，将非NULL的item_t*存入临时动态数组，同时清空原单元格的物品指针避免重复处理。

#include <stdlib.h>

// 收集所有物品到动态数组，末尾以NULL标记结束
item_t** collect_all_items(Shelf* shelf_head) {
    item_t** items = NULL;
    int item_count = 0;
    Shelf* curr_shelf = shelf_head;

    while (curr_shelf != NULL) {
        Cell* curr_cell = curr_shelf->cellhead;
        while (curr_cell != NULL) {
            if (curr_cell->itemInfo != NULL) {
                items = realloc(items, sizeof(item_t*) * (item_count + 1));
                items[item_count++] = curr_cell->itemInfo;
                curr_cell->itemInfo = NULL;
            }
            curr_cell = curr_cell->next;
        }
        curr_shelf = curr_shelf->next;
    }

    // 添加结束标记
    items = realloc(items, sizeof(item_t*) * (item_count + 1));
    items[item_count] = NULL;
    return items;
}

2. 重新填充物品并清理空货架 #

从首个货架开始，依次将收集到的物品填充单元格；填满当前货架后切换至下一个，剩余未被填充的空货架直接删除，最后重新编号货架保证连续性。

void refill_items(Shelf** shelf_head, item_t** items) {
    if (!items || !*items) {
        // 无物品时删除所有货架
        while (*shelf_head != NULL) {
            Shelf* temp_shelf = *shelf_head;
            // 先释放货架内所有单元格
            while (temp_shelf->cellhead != NULL) {
                Cell* temp_cell = temp_shelf->cellhead;
                temp_shelf->cellhead = temp_shelf->cellhead->next;
                free(temp_cell);
            }
            *shelf_head = (*shelf_head)->next;
            free(temp_shelf);
        }
        return;
    }

    Shelf* curr_shelf = *shelf_head;
    int item_idx = 0;

    while (items[item_idx] != NULL && curr_shelf != NULL) {
        Cell* curr_cell = curr_shelf->cellhead;
        // 填充当前货架的所有单元格
        while (curr_cell != NULL && items[item_idx] != NULL) {
            curr_cell->itemInfo = items[item_idx++];
            curr_cell = curr_cell->next;
        }
        // 当前货架填满，切换至下一个
        if (items[item_idx] != NULL) {
            curr_shelf = curr_shelf->next;
        }
    }

    // 删除剩余空货架
    while (curr_shelf != NULL) {
        Shelf* temp_shelf = curr_shelf;
        // 释放货架内单元格
        while (temp_shelf->cellhead != NULL) {
            Cell* temp_cell = temp_shelf->cellhead;
            temp_shelf->cellhead = temp_shelf->cellhead->next;
            free(temp_cell);
        }
        curr_shelf = curr_shelf->next;
        free(temp_shelf);
    }

    // 重新编号货架，从0开始连续递增
    curr_shelf = *shelf_head;
    int new_shelf_num = 0;
    while (curr_shelf != NULL) {
        curr_shelf->shelfnum = new_shelf_num++;
        curr_shelf = curr_shelf->next;
    }
}

3. 整合为完整的reducespaces函数 #

将收集与填充逻辑整合，同时处理内存释放。

void reducespaces(Shelf** shelf_head) {
    if (!shelf_head || !*shelf_head) {
        return;
    }

    item_t** collected_items = collect_all_items(*shelf_head);
    if (!collected_items) {
        return;
    }

    refill_items(shelf_head, collected_items);
    free(collected_items);
}

关键注意事项 #

• 内存安全：收集物品仅转移指针，避免重复释放；删除货架前需先释放其下所有单元格。
• 编号一致性：重新填充后必须更新货架编号，保证编号连续且从0开始。
• 边界处理：无物品场景需清空所有货架；若物品数量超过现有货架总单元格数，可根据需求扩展货架（本例默认现有货架容量足够）。

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