C语言 在链表中搜索

Question

首先，我要感谢所有将回答这个问题的人。

问题在编辑中

问题是这样的，我必须创建一个从.txt文件生成迷宫的 C 程序，在.txt文件中我们有行数和列数以及迷宫方案(我将在此处附加一个文件作为参考(。

20//行数

20//列数

可以改变的迷宫方案

XXXXXXXXXXXXXXXXXXXX
X     X    X       X
X XXXXX XXXX XXX XXX
X       X      X X X
X XXXXXXXXXXXX X X X
X X   X        X X X
X XXX XXXXXX XXXXX X
X XXX    X X X     X
X    XXX       XXXXX
X XXX   XXXXXX     X
X   XXX X X    X X X
XXX XXX X X XXXX X X
X     X X   XX X X X
XXXXX     XXXX X XXX
X     X XXX    X   X
X XXXXX X XXXX XXX X
X X     X  X X     X
X X XXXXXX X XXXXX X
X X                X
XXXXXXXXXXXXXXXXXX X

X是墙壁。

玩家是 *，它从位置 (1,1( 开始，出口总是在 (18,19(

代码中有 3 种结构：

1. 位置表示迷宫网格内的位置
2. 单元格是描述哪个字符存在于 定位网格的位置。该结构使访问的可用 布尔变量在从 迷宫，变量表示搜索已经 是否访问了网格的特定位置。
3. 必须使用节点结构来创建链表 包含一条可行的道路来退出迷宫。

typedef struct{
int x, y;
} position;
typedef struct{     
pos;
char ch;
bool visited;
} cell;
typedef struct {
position pos;
struct node *next;
} node;

这是我发现一些问题的功能。

node *search(cell *grid, position pos, position goal, int rows, int columns)

此函数必须递归搜索通往 (18,19( 中出口的可行道路，同时使用函数bool isEmpty以查看节点是否为空

bool isEmpty(node *list) {
if(list ->  next== NULL) {
return true;
} else {
return false;
}
}

我以为这个功能可能是这样的

node *search(cell *grid, position pos, position goal, int rows, int columns){
node* new_node = (node)malloc(sizeof(node));
//if the last element equals goal position the search finishes
if (new_node->pos.x == goal.x && new_node->pos.y == goal.y ) {
return new_node;
} else {
return  *search(cell *grid, position pos, position goal, int rows, int columns);
}
}

但是当我运行程序时，它会崩溃。如何修复此搜索？

[编辑]

首先，我不能更改结构，因为这是一个项目规范。

函数

node *search(cell *grid, position pos, position goal, int rows, int columns)

必须使用递归算法来识别通往单元格(18,19(//出口的道路 此功能必须返回玩家 (*( 必须访问才能退出的位置的链接列表。因此，返回值(将适当地保存在 main 中(将是此链表的头节点，此功能使用另外 2 个功能：

1(

bool isEmpty(node∗ list) 

如果列表为空，则此功能返回 true，否则为 false。

2(

node∗ push_list (node∗ list , position pos) 

这是用于管理列表的经典推送功能。它在列表的头部添加一个包含位置位置的新节点 pos

下面是我制作的代码

node *search(cell *grid, position pos, position goal, int rows, int columns)
{
//base case
if(pos.x == goal.x && pos.y == goal.y)
{
//dont know how to return the position cause im in a multidimentional array
}
}

bool isEmpty(node *list)
{
if(list ->  next== NULL)
{
return true;
}else{
return false;
}
}

这就是我拯救迷宫的方式

cell *read_grid(char *filename, int *rows, int *columns)

{

int i,j;
//steam file
FILE *fp;


fp = fopen("grid.txt", "r+");

fscanf(fp, "%dn%dn", rows, columns);
fprintf(stdout, "%dn%dn", *rows, *columns);
cell grid[*rows][*columns];
cell *temp = (cell*)malloc(sizeof(cell));
assert(*grid != NULL);
if(fp == NULL)
{
printf("errorn");
exit(EXIT_FAILURE);
}


for(i = 0; i < *rows; i++)
{
for(j = 0; j < *columns; j++)
{
fscanf(fp, "%c", &(grid[i][j]).ch);
grid[i][j].pos.x =i;
grid[i][j].pos.y =j;
}
fscanf(fp, "n");
}


fclose(fp);
temp = *grid;
return temp;

}

Answer 1

这几乎正是您所需要的，我从这里获取了代码！ 但稍微修改了它以根据需要将迷宫绘制到测试.txt文件。我希望它有所帮助。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef struct
{
int x, y; 
void *parent; //Pointer to parent node
char c; //Character to be displayed
char dirs; //Directions that still haven't been explored
} Node;
Node *nodes; 
int width, height; //Maze dimensions

int init( )
{
int i, j;
Node *n;
//Allocate memory for maze
nodes = calloc( width * height, sizeof( Node ) );
if ( nodes == NULL ) return 1;
//Setup crucial nodes
for ( i = 0; i < width; i++ )
{
for ( j = 0; j < height; j++ )
{
n = nodes + i + j * width;
if ( i * j % 2 ) 
{
n->x = i;
n->y = j;
n->dirs = 15; //Assume that all directions can be explored (4 youngest bits set)
n->c = ' '; 
}
else n->c = '#'; //Add walls between nodes
}
}
return 0;
}
Node *link( Node *n )
{
//Connects node to random neighbor (if possible) and returns
//address of next node that should be visited
int x, y;
char dir;
Node *dest;
//Nothing can be done if null pointer is given - return
if ( n == NULL ) return NULL;
//While there are directions still unexplored
while ( n->dirs )
{
//Randomly pick one direction
dir = ( 1 << ( rand( ) % 4 ) );
//If it has already been explored - try again
if ( ~n->dirs & dir ) continue;
//Mark direction as explored
n->dirs &= ~dir;
//Depending on chosen direction
switch ( dir )
{
//Check if it's possible to go right
case 1:
if ( n->x + 2 < width )
{
x = n->x + 2;
y = n->y;
}
else continue;
break;
//Check if it's possible to go down
case 2:
if ( n->y + 2 < height )
{
x = n->x;
y = n->y + 2;
}
else continue;
break;
//Check if it's possible to go left 
case 4:
if ( n->x - 2 >= 0 )
{
x = n->x - 2;
y = n->y;
}
else continue;
break;
//Check if it's possible to go up
case 8:
if ( n->y - 2 >= 0 )
{
x = n->x;
y = n->y - 2;
}
else continue;
break;
}
//Get destination node into pointer (makes things a tiny bit faster)
dest = nodes + x + y * width;
//Make sure that destination node is not a wall
if ( dest->c == ' ' )
{
//If destination is a linked node already - abort
if ( dest->parent != NULL ) continue;
//Otherwise, adopt node
dest->parent = n;
//Remove wall between nodes
nodes[n->x + ( x - n->x ) / 2 + ( n->y + ( y - n->y ) / 2 ) * width].c = ' ';
//Return address of the child node
return dest;
}
}
//If nothing more can be done here - return parent's address
return n->parent;
}
void draw(FILE *fp)
{
int i, j;
//Outputs maze to terminal - nothing special
for ( i = 0; i < height; i++ )
{
for ( j = 0; j < width; j++ )
{
fprintf(fp, "%c", nodes[j + i * width].c );
}
fprintf(fp, "n" );
}
}
int main( int argc, char **argv )
{
Node *start, *last;
//Check argument count
if ( argc < 3 )
{
fprintf( stderr, "%s: please specify maze dimensions!n", argv[0] );
exit( 1 );
}
//Read maze dimensions from command line arguments
if ( sscanf( argv[1], "%d", &width ) + sscanf( argv[2], "%d", &height ) < 2 )
{
fprintf( stderr, "%s: invalid maze size value!n", argv[0] );
exit( 1 );
}
//Allow only odd dimensions
if ( !( width % 2 ) || !( height % 2 ) )
{
fprintf( stderr, "%s: dimensions must be odd!n", argv[0] );
exit( 1 );
}

//Do not allow negative dimensions
if ( width <= 0 || height <= 0 )
{
fprintf( stderr, "%s: dimensions must be greater than 0!n", argv[0] );
exit( 1 );
}
//Seed random generator
srand( time( NULL ) );
//Initialize maze
if ( init( ) )
{
fprintf( stderr, "%s: out of memory!n", argv[0] );
exit( 1 );
}
//Setup start node
start = nodes + 1 + width;
start->parent = start;
last = start;
FILE *fptr;
// use appropriate location if you are using MacOS or Linux
fptr = fopen("./test.txt","w");   
//Connect nodes until start node is reached and can't be left
while ( ( last = link( last ) ) != start );
draw(fptr);
}