仓库间货物搬运程序的内存分配问题求解

问题描述 #

任务说明 #

• 现有M个仓库（M ≤ 100000），每个仓库内有若干带重量的货物。输入先给出M行数据，每行格式为：t a1 a2 a3...，其中t为仓库内货物数量（t ≤ 1000000），a1等为货物重量（重量 ≤ 2147483647）。
• 随后给出Q个查询（Q ≤ 200000），分为两类：
  1. K：输出每个仓库内货物的总重量；
  2. R mz md tp tk：将编号为mz的仓库中，索引从tp到tk（包含两端）的所有货物移动到编号为md的仓库末尾。
• 其中mz、md ≤ 100000，-255 ≤ tp、tk ≤ 255。索引从1开始，负索引-n表示从末尾数第n个货物（如-1为最后一个货物）。

现有代码问题 #

原代码使用静态二维数组long int warehouses[M+1][1000];存在以下问题：

• 内存浪费：每个仓库固定分配1000个元素空间，实际货物数量可能远小于或大于这个值；
• 空间不足：当仓库货物数量超过1000时会越界，且无法动态扩展；
• 需求：改为指针数组实现的动态二维数组，支持根据货物搬运动态调整内存，同时需要原理讲解。

现有代码 #

#include <stdio.h>
int main() {

    long int M,Q,t,ware;
    if (scanf("%ld %ld",&M,&Q) != 2)
    {
        printf("Invalid Input");
    }
    char check;
    //declaration of warehouse size - subject to change
    long int warehouses[M+1][1000];
    //array with sums of weights of items in each warehouse
    long long int sumy[M+1];
    //array with sizes of each warehouse
    long int length[M+1];
    for (int i = 1; i<M+1;i++)
    {
        if (scanf(" %ld",&t) != 1)
        {
            printf("Invalid Input");
        }
        length[i] = t;
        for (int j = 1; j<t+1;j++)
        {
            if (scanf(" %ld",&ware) != 1)
            {
                printf("Invalid Input");
            }
            warehouses[i][j] = ware;
            sumy[i] += ware;
        }
    }
    long int mz,md;
    int tp,tk;
    for (int k = 0;k<Q;k++)
    {
        if (scanf(" %c",&check) != 1)
        {
            printf("Invalid Input");
        }
        if (check == 'K')
        {
            for (int ki = 0; ki < M;ki++)
            {
                printf("%lld",sumy[ki+1]);
                printf(" ");
            }
             printf("\n");
        }else
        {
            //indexes of "from warehouse" and "to warehouse"
            if (scanf(" %ld %ld",&mz,&md) != 2)
            {
                printf("Invalid Input");
            }
            //indexes of the range of items we want to transport
             if (scanf(" %d %d",&tp,&tk) != 2)
             {
                 printf("Invalid Input");
             }
            if (tp < 0)
            {
                tp = length[mz] + tp + 1;
            }
            if (tk < 0)
            {
                tk = length[mz] + tk + 1;
            }
            for (int kj = 0; kj <= tk - tp ;kj++)
            {
                //moving items - subject to change
                warehouses[md][length[md]+1] = warehouses[mz][tp + kj];
                sumy[mz] -= warehouses[mz][tp + kj];
                sumy[md] += warehouses[mz][tp + kj];
                warehouses[mz][tp + kj] = 0;
                length[md] += 1;
                length[mz] -= 1;

            }
        }
    }
    return 0;
}

解决方案 #

核心原理讲解 #

1. 指针数组实现动态二维数组：
   • 用long int **warehouses声明指针数组，其中每个元素是指向对应仓库货物数组的指针；
   • 先为指针数组分配M+1个元素（仓库编号从1开始），再为每个仓库单独分配对应数量的内存，避免固定大小的内存浪费。
2. 动态内存调整：
   • 当需要向仓库添加货物时，用realloc重新分配更大的内存空间；
   • 当从仓库移除连续货物时，调整剩余元素的位置并重新分配更小的内存，节省空间（也可选择不立即缩容，后续再添加时直接扩容）。
3. 索引处理：保持原逻辑，将负索引转换为正索引，适配索引从1开始的特性。

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

int main() {
    long int M, Q, t, ware;
    if (scanf("%ld %ld", &M, &Q) != 2) {
        printf("Invalid Input");
        return 1;
    }

    // 指针数组：warehouses[i]指向第i个仓库的货物数组
    long int **warehouses = (long int **)malloc((M + 1) * sizeof(long int *));
    if (warehouses == NULL) {
        printf("Memory Allocation Failed");
        return 1;
    }

    // calloc初始化，避免未初始化的垃圾值
    long long int *sumy = (long long int *)calloc(M + 1, sizeof(long long int));
    long int *length = (long int *)calloc(M + 1, sizeof(long int));
    if (sumy == NULL || length == NULL) {
        printf("Memory Allocation Failed");
        free(warehouses);
        return 1;
    }

    // 初始化每个仓库
    for (int i = 1; i <= M; i++) {
        if (scanf(" %ld", &t) != 1) {
            printf("Invalid Input");
            // 清理已分配的内存
            for (int j = 1; j < i; j++) free(warehouses[j]);
            free(warehouses);
            free(sumy);
            free(length);
            return 1;
        }
        length[i] = t;
        // 索引从1开始，分配t+1个元素（0位置空置）
        warehouses[i] = (long int *)malloc((t + 1) * sizeof(long int));
        if (warehouses[i] == NULL) {
            printf("Memory Allocation Failed");
            for (int j = 1; j < i; j++) free(warehouses[j]);
            free(warehouses);
            free(sumy);
            free(length);
            return 1;
        }
        for (int j = 1; j <= t; j++) {
            if (scanf(" %ld", &ware) != 1) {
                printf("Invalid Input");
                for (int j = 1; j <= i; j++) free(warehouses[j]);
                free(warehouses);
                free(sumy);
                free(length);
                return 1;
            }
            warehouses[i][j] = ware;
            sumy[i] += ware;
        }
    }

    long int mz, md;
    int tp, tk;
    char check;
    for (int k = 0; k < Q; k++) {
        if (scanf(" %c", &check) != 1) {
            printf("Invalid Input");
            // 清理所有内存
            for (int j = 1; j <= M; j++) free(warehouses[j]);
            free(warehouses);
            free(sumy);
            free(length);
            return 1;
        }
        if (check == 'K') {
            for (int ki = 1; ki <= M; ki++) {
                printf("%lld ", sumy[ki]);
            }
            printf("\n");
        } else if (check == 'R') {
            if (scanf(" %ld %ld %d %d", &mz, &md, &tp, &tk) != 4) {
                printf("Invalid Input");
                // 清理所有内存
                for (int j = 1; j <= M; j++) free(warehouses[j]);
                free(warehouses);
                free(sumy);
                free(length);
                return 1;
            }

            // 转换负索引为正索引
            if (tp < 0) {
                tp = length[mz] + tp + 1;
            }
            if (tk < 0) {
                tk = length[mz] + tk + 1;
            }
            // 检查索引合法性
            if (tp < 1 || tk > length[mz] || tp > tk) {
                printf("Invalid Index");
                continue;
            }

            int move_count = tk - tp + 1;
            long long int move_sum = 0;
            // 计算要移动的货物总重量
            for (int kj = tp; kj <= tk; kj++) {
                move_sum += warehouses[mz][kj];
            }

            // 1. 扩展目标仓库内存并复制货物
            long int *new_md = (long int *)realloc(warehouses[md], (length[md] + move_count + 1) * sizeof(long int));
            if (new_md == NULL) {
                printf("Memory Reallocation Failed");
                // 清理所有内存
                for (int j = 1; j <= M; j++) free(warehouses[j]);
                free(warehouses);
                free(sumy);
                free(length);
                return 1;
            }
            warehouses[md] = new_md;
            for (int kj = 0; kj < move_count; kj++) {
                warehouses[md][length[md] + 1 + kj] = warehouses[mz][tp + kj];
            }
            length[md] += move_count;
            sumy[md] += move_sum;
            sumy[mz] -= move_sum;

            // 2. 调整源仓库：移除指定范围元素并缩容
            int remaining = length[mz] - move_count;
            // 将tk之后的元素向前移动move_count位
            for (int kj = tk + 1; kj <= length[mz]; kj++) {
                warehouses[mz][kj - move_count] = warehouses[mz][kj];
            }
            // 重新分配源仓库内存（允许realloc失败时保留原内存）
            long int *new_mz = (long int *)realloc(warehouses[mz], (remaining + 1) * sizeof(long int));
            if (new_mz != NULL) {
                warehouses[mz] = new_mz;
            }
            length[mz] = remaining;
        }
    }

    // 释放所有动态分配的内存
    for (int j = 1; j <= M; j++) {
        free(warehouses[j]);
    }
    free(warehouses);
    free(sumy);
    free(length);

    return 0;
}

关键修改点说明 #

1. 动态内存分配：
   • 使用malloc为指针数组warehouses分配空间，每个仓库单独用malloc分配对应货物数量的内存；
   • calloc初始化sumy和length数组，避免未初始化的垃圾值。
2. 内存扩容与缩容：
   • 搬运货物时，用realloc为目标仓库扩展内存，容纳新增的货物；
   • 源仓库移除货物后，用realloc缩小内存空间，节省内存。
3. 错误处理：
   • 每次内存分配/重分配后检查是否成功，失败则清理已分配的内存并退出；
   • 增加索引合法性检查，避免越界访问。
4. 效率优化：
   • 先计算要移动的货物总重量，避免重复访问源仓库元素；
   • 批量移动货物，减少循环次数。

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