我如何处理这个 C 90 代码中的内存泄漏？

Question

代码大致是这样的： 输入给出一个矩阵及其列和行的值，算法会搜索最短路径，并优先选择某些单元格继续移动。

这是我正在谈论的代码部分：

/* Function to find the shortest path in the matrix using BFS */
void findShortestPath(Matrix *matrix, Result *bestResult) {
    int numRows = matrix->rows;
    int numCols = matrix->cols;
    int **visited = (int **)malloc(numRows * sizeof(int * ));
    int i, newDistance, newBadCells, newNegativeCells, row, col, distance, badCells, negativeCells;
    int dx[] = {
        -1,
        1,
        0,
        0
    };
    int dy[] = {
        0,
        0,
        -1,
        1
    };
    BFSNode currentNode;
    BFSNode *queue = (BFSNode *)malloc(numRows * numCols * sizeof(BFSNode));
    int queueSize = 0;
    char *path;
    char *check = "";

    for (i = 0; i < numRows; i++) {
        visited[i] = (int *)malloc(numCols * sizeof(int));
        memset(visited[i], 0, numCols * sizeof(int));
    }

    enqueue(queue, & queueSize, createBFSNode(0, 0, 0, 0, 0, ""));

    while (queueSize > 0) {
        qsort(queue, queueSize, sizeof(BFSNode), priorityCompare);

        currentNode = dequeue(queue, & queueSize);
        row = currentNode.point.row;
        col = currentNode.point.col;
        distance = currentNode.distance;
        badCells = currentNode.badCells;
        negativeCells = currentNode.negativeCells;
        path = currentNode.path;

        if (row == numRows - 1 && col == numCols - 1) {
            if (bestResult -> distance == -1 || distance < bestResult->distance) {
                bestResult->distance = distance;
                bestResult->badCells = badCells;
                bestResult->negativeCells = negativeCells;
                free(bestResult -> path);
                bestResult->path = strdup(path);
            } else if (distance == bestResult->distance && negativeCells > bestResult->negativeCells) {
                bestResult->badCells = badCells;
                bestResult->negativeCells = negativeCells;
                free(bestResult->path);
                bestResult->path = strdup(path);
            }

            continue;
        }

        visited[row][col] = 1;

        for (i = 0; i < 4; i++) {
            int newRow = row + dy[i];
            int newCol = col + dx[i];

            if (isValidMove(matrix, newRow, newCol, visited)) {
                char *newPath = (char *)malloc((strlen(path) + 2) * sizeof(char));
                if (newPath == NULL) {
                    fprintf(stderr, "Memory allocation error.\n");
                    exit(EXIT_FAILURE);
                }
                strcpy(newPath, path);

                if (i == 0) {
                    newPath[strlen(path)] = 'O';
                } else if (i == 1) {
                    newPath[strlen(path)] = 'E';
                } else if (i == 2) {
                    newPath[strlen(path)] = 'N';
                } else if (i == 3) {
                    newPath[strlen(path)] = 'S';
                }
                newPath[strlen(path) + 1] = '\0';

                newDistance = distance + 1;
                newBadCells = badCells + (matrix->matrix[newRow][newCol] == 0);
                newNegativeCells = negativeCells + (matrix->matrix[newRow][newCol] == -1);

                enqueue(queue, & queueSize, createBFSNode(newRow, newCol, newDistance, newBadCells, newNegativeCells, newPath));
                visited[newRow][newCol] = 1;
            }
        }

        if (path == check) {} else {
            free(path);
        }

    }

    for (i = 0; i < numRows; i++) {
        free(visited[i]);
    }
    free(visited);
    free(queue);
}

这个导致内存泄漏的变量是newPath但是没那么简单，我来解释一下

内存分配的工作原理如下： 队列以空/起始节点开始，没有为路径分配内存 然后，对于后面的每个节点，每次在将节点入队之前都会将路径分配为“newPath”，并且稍后在使节点出队时将其释放为“path”。

通过调试发现

**free**()

的数量比

**malloc**()

的数量少了一位，所以最终无法释放一块内存

所有其他内存均已正确分配和释放

我尝试了许多不同的实现来解决问题，但都失败了

其中一些是：

 while (queueSize > 0) {
     qsort(queue, queueSize, sizeof(BFSNode), priorityCompare);

     currentNode = dequeue(queue, & queueSize);
     row = currentNode.point.row;
     col = currentNode.point.col;
     distance = currentNode.distance;
     badCells = currentNode.badCells;
     negativeCells = currentNode.negativeCells;
     /* With a switch check if it's the first node or not then free path before the new value is assigned */
     path = currentNode.path;

或

一段时间结束后再次释放路径

编辑 希望现在缩进已修复

newPath 通过 path 释放，因为它们共享相同的内存分配

你们中有人能帮我想出解决这个问题的方法吗？ 感谢大家的时间和帮助！

Answer 1

连接方法是假的：

                strcpy(newPath, path);

                if (i == 0) {
                    newPath[strlen(path)] = 'O';
                } else if (i == 1) {
                    newPath[strlen(path)] = 'E';
                } else if (i == 2) {
                    newPath[strlen(path)] = 'N';
                } else if (i == 3) {
                    newPath[strlen(path)] = 'S';
                }
                newPath[strlen(path) + 1] = '\0';

在

newPath[strlen(path)]

设置字节后，

newPath

不再是空终止字符串，因此

newPath[strlen(path) + 1] = '\0';

具有未定义的行为。你应该写：

                strcpy(newPath, path);
                if (i == 0) {
                    strcat(newPath, "O");
                } else if (i == 1) {
                    strcat(newPath, "E");
                } else if (i == 2) {
                    strcat(newPath, "N");
                } else if (i == 3) {
                    strcat(newPath, "S");
                }

另请注意，

malloc(numRows * numCols * sizeof(BFSNode))

很容易出错，因为

numRows

和

numCols

的类型为

int

，因此

numRows * numCols

可能会溢出。你应该写：

    BFSNode *queue = malloc(sizeof(*queue) * numRows * numCols);