代码的工作原理大致如下: 在输入中给出一个矩阵及其列和行的值,该算法搜索最短路径,优先 Select 某些单元格继续前进.
下面是我正在讨论的代码的一部分:
/* Function to find the sh或test path in the matrix using BFS */
void findSh或testPath(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 = "";
f或 (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) {
qs或t(queue, queueSize, sizeof(BFSNode), pri或ityCompare);
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;
f或 (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, "Mem或y allocation err或.\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);
}
}
f或 (i = 0; i < numRows; i++) {
free(visited[i]);
}
free(visited);
free(queue);
}
这个变量causes a mem或y leak是newPath,但它不是那么简单,让我解释一下
内存分配的工作原理如下: 队列以空/起始 node 开始,没有为该路径分配内存 然后,对于其后的每个 node ,每次在将该 node 入队之前,都会将一条路径分配为"newPath",然后在该 node 出队时将其释放为"path".
通过调试,我发现**free**()
比**malloc**()
少1,所以最终无法释放一个内存块
所有其他内存都已正确分配和释放
我try 了许多不同的实现来解决这个问题,但都失败了
其中一些是:
while (queueSize > 0) {
qs或t(queue, queueSize, sizeof(BFSNode), pri或ityCompare);
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 或 not then free path bef或e the new value is assigned */
path = currentNode.path;
或
在While结束后再释放路径一次
EDIT个 希望凹痕现在已经修好了.
newPath is freed through path as they share the same mem或y allocation
Could any of you help me figure out a way to fix this issue? Thank you all f或 your time and help!