此代码的目的是使用回溯算法来解决迷宫问题。
为算法提供的伪代码为：
read in the maze;
initialize the list;
goalCell = the position of the escape hatch in the maze;
startCell = the initial position of the mouse in the maze;
currentCell = startCell;
while currentCell is not the goalCell
mark currentCell as visited;
add to the list the unvisited open neighbours of currentCell;
if the list is empty
the mouse is trapped: we tried all routes and failed to find an escape;
else
get the next cell from the list and make it currentCell;
end while;
the mouse can escape the maze: we reached the goal cell.
无论我尝试什么，我的代码都不会超过星线。我没有用if语句运行它，它仍然没有超过那一行。
我在终端中编译它，它没有显示错误或警告。在终端运行后，输出为：
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 . 1 0 1
1 0 0 0 1
1 1 1 1 1
Segmentation fault: 11
文件“testMaze.txt”如下：
6 5
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
我补充道：
printf（“mazeRows是%d，unvisitedCell.row是%d\n”，mazeRows，unvisitedCell.row）；
assert( unvisitedCell.row < mazeRows );
assert( unvisitedCell.column < mazeCols );
printf( "the char is %c\n", maze[unvisitedCell.row][unvisitedCell.column] );
并将if语句更改为：
if ( maze[unvisitedCell.row][unvisitedCell.column] == '0' )
在终点站运行。我得到的结果是：
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 m 1 0 1
1 0 0 0 1
1 1 1 1 1
1 1 1 1 1
1 0 0 e 1
1 1 1 0 1
1 . 1 0 1
1 0 0 0 1
1 1 1 1 1
mazeRows is 5, and unvisitedCell.row is 4
the char is 0
Segmentation fault: 11
使用Xcode编写的整个代码是：
#include "Maze.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//-------------------------------------------------------------------------------------
// CONSTANTS and TYPES
//-------------------------------------------------------------------------------------
#define MAX_DIMENSION 20
// constant definitions for the different cell states
const char WALL = '1';
const char SPACE = '0';
const char VISITED = '.';
const char MOUSE = 'm';
const char EXIT = 'e';
typedef enum BOOL { false, true } Boolean;
struct CELL
{
int row;
int column;
};
typedef struct CELL Cell;
typedef struct CELL_NODE CellNode;
struct CELL_NODE
{
Cell cell;
CellNode *next;
};
//-------------------------------------------------------------------------------------
// VARIABLES
//-------------------------------------------------------------------------------------
CellNode *top = NULL;
// a 2D array used to store the maze
char maze[MAX_DIMENSION][MAX_DIMENSION];
int mazeRows;
int mazeCols;
// holds the location of the mouse and escape hatch
Cell mouse;
Cell escape;
//-------------------------------------------------------------------------------------
// PROTOTYPES
//-------------------------------------------------------------------------------------
// basic cell manipulation
Boolean equalCells(const Cell cell1, const Cell cell2);
Cell makeCell(const int row, const int col);
Boolean validCell(const Cell theCell);
// routines for managing our backtracking
Boolean noMoreCells();
Cell nextCell();
void addCell(const Cell cell);
void printMaze();
void loadMaze();
Boolean solveMaze();
// our invariant checker
void checkState();
//-------------------------------------------------------------------------------------
// FUNCTIONS
//-------------------------------------------------------------------------------------
int main( int argc, char *argv[] )
{
loadMaze();
printMaze();
if ( solveMaze() )
printf( "The mouse is free!!!!\n" );
else
printf( "The mouse is trapped!!!!\n" );
printf( "\nEnd of processing\n" );
return EXIT_SUCCESS;
}
//////////////////////////////////////////////
// Cell routines
//////////////////////////////////////////////
Boolean equalCells( const Cell cell1, const Cell cell2 )
{
//assert( cell1.row != cell2.row && cell1.column != cell2.column );
if ( cell1.row == cell2.row && cell1.column == cell2.column )
return true;
else
return false;
}
Cell makeCell( const int row, const int col )
{
Cell newCell;
newCell.row = row;
newCell.column = col;
return newCell;
}
Boolean validCell( const Cell theCell )
{
if ( theCell.row < mazeRows && theCell.column < mazeCols )
return true;
else
return false;
}
Boolean noMoreCells()
{
if ( top->next == NULL )
return true;
else
return false;
}
Cell nextCell()
{
return top->cell;
}
void addCell( const Cell cell )
{
CellNode *cellToAdd = NULL;
cellToAdd->cell = cell;
cellToAdd->next = top;
top->next = cellToAdd;
}
//////////////////////////////////////////////
// List routines
//////////////////////////////////////////////
Boolean solveMaze()
{
Boolean solved = false;
CellNode *mazePaths = NULL, *cellToAdd = NULL;
Cell currentCell, unvisitedCell;
char ch, position;
int row, col;
for ( row = 0; row < mazeRows; row++ ) //checked and works
{
for ( col = 0; col < mazeCols; col++ )
{
ch = maze[row][col];
if ( ch == 'm' )
{
mouse.row = row;
mouse.column = col;
currentCell.row = row;
currentCell.column = col;
}
else if ( ch == 'e' )
{
escape.row = row;
escape.column = col;
}
}
}
while ( maze[currentCell.row][currentCell.column] != maze[escape.row][escape.column] )
{
maze[currentCell.row][currentCell.column] = '.';
printf("\n");
printMaze();
//if the one below current
unvisitedCell.row = currentCell.row + 1; //works
unvisitedCell.column = currentCell.column; //works
printf("mazeRows is %d, and unvisitedCell.row is %d\n", mazeRows, unvisitedCell.row );
assert( unvisitedCell.row < mazeRows );
assert( unvisitedCell.column < mazeCols );
printf( "the char is %c\n", maze[unvisitedCell.row][unvisitedCell.column] );
if ( maze[unvisitedCell.row][unvisitedCell.column] == '0' ) //gives "Segmentation fault: 11"
{
***************************************************************************
printf("gets into first if");
cellToAdd->cell = unvisitedCell;
cellToAdd->next = top;
mazePaths->next = cellToAdd;
maze[unvisitedCell.row][unvisitedCell.column] = 'A';
}
//if one above current
unvisitedCell.row = currentCell.row - 1;
unvisitedCell.column = currentCell.column;
position = maze[unvisitedCell.row][unvisitedCell.column];
printf("the pos is %c\n", position);
if ( position == '0' )
{
printf("gets into second if");
cellToAdd->cell = unvisitedCell;
cellToAdd->next = top;
mazePaths->next = cellToAdd;
maze[unvisitedCell.row][unvisitedCell.column] = 'B';
}
//if one to the right of current
unvisitedCell.row = currentCell.row;
unvisitedCell.column = currentCell.column + 1;
position = maze[unvisitedCell.row][unvisitedCell.column];
printf("the pos is %c\n", position);
if ( position == '0' )
{
printf("gets into third if");
cellToAdd->cell = unvisitedCell;
cellToAdd->next = top;
mazePaths->next = cellToAdd;
maze[unvisitedCell.row][unvisitedCell.column] = 'R';
}
//if one to the left of current
unvisitedCell.row = currentCell.row;
unvisitedCell.column = currentCell.column - 1;
position = maze[unvisitedCell.row][unvisitedCell.column];
printf("the pos is %c\n", position);
if ( position == '0' )
{
printf("gets into fourth if");
cellToAdd->cell = unvisitedCell;
cellToAdd->next = top;
mazePaths->next = cellToAdd;
maze[unvisitedCell.row][unvisitedCell.column] = 'L';
}
if ( noMoreCells() )
{
printf( "The mouse is trapped: we tried all routes and failed to find an escape!" );
}
else
{
printf("there are still more cells\n");
currentCell.row = mazePaths->cell.row;
currentCell.column = mazePaths->cell.column;
}
}
return solved;
}
void checkState()
{
}
//////////////////////////////////////////////
// Maze routines
//////////////////////////////////////////////
void loadMaze() //checked and works
{
char input[MAX_DIMENSION];
char ch;
int column, index, stringIndex;
char *line = NULL;
size_t buffer = MAX_DIMENSION;
FILE *maze_input = fopen( "testMaze.txt", "r" );
getline( &line, &buffer, maze_input );
//to find columns
stringIndex = 0;
index = 0;
ch = line[index];
while ( ch != ' ' )
{
input[stringIndex] = ch;
stringIndex++;
index++;
ch = line[index];
}
mazeCols = atoi( input );
//to find rows
stringIndex = 0;
ch = line[index];
while ( ch != '\0' )
{
input[stringIndex] = ch;
stringIndex++;
index++;
ch = line[index];
}
mazeRows = atoi( input );
//reads in the actual maze
for ( int row = 0; row <= mazeRows; row++ )
{
getline( &line, &buffer, maze_input );
ch = line[0];
column = 0;
index = 0;
while ( ch != '\0' )
{
maze[row][column] = ch;
index += 2;
column++;
ch = line[index];
}
}
}
void printMaze() //checked and works
{
for ( int row = 0; row <= mazeRows; row++ )
{
for ( int column = 0; column < mazeCols; column++ )
{
printf( "%c ", maze[row][column] );
}
printf( "\n" );
}
}
最佳答案
如果分段错误发生在这里，则表示您正试图从边界之外的二维数组访问数据。以下行导致分段错误。position = maze[unvisitedCell.row][unvisitedCell.column];
您需要调试程序，并确保unvisitedCell.row和unvisitedCell.column小于最大维度（MAX_DIMENSION和MAX_DIMENSION）。
还要注意：
指针cellToAdd初始化为NULL，但从未初始化为指向CellNode。
所以您正试图访问NULL语句之后的if指针：cellToAdd->cell = unvisitedCell;。这将导致另一个分割错误。
注意，对于mazePaths
关于c - if语句导致C中的“段错误:11”，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35605841/