高分求：迷宫问题数据结构(C语言)

这个迷宫的路径不是唯一的，因此从不同方向开始试探执行结果也可能会不唯一。我写的是参考书上的，共有八个方向可以试探。

栈解决迷宫主要的几个问题：

1迷宫的存储

2栈的设计

3试探方向

4不重复到达某点，即不陷入死循环

如果对算法有什么疑问，或是我的回答有错误的地方，可以Hi我。

#define LINES 9 // 定义行数

#define COLS 8 // 定义列数

#include <stdioh>

#include <stdlibh>

#include <malloch>

typedef struct{

int line;

int col;

}MOVE; // 定义试探方向的结构体

MOVE to[8] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; // 定义数组，存放8个试探方向

typedef struct{ // 行、列、方向构成的三元组

int x;

int y;

int d;

}DataType;

typedef struct node{

DataType element;

struct node next;

}StackNode,LinkStack;

LinkStack InitStack(LinkStack s); // 栈初始化

LinkStack PushStack(LinkStack,DataType ); // 入栈函数

LinkStack PopStack(LinkStack,DataType ); // 出栈函数

int EmptyStack(LinkStack s); // 判定栈空

int path(int maze[][COLS+2]); // 打印路径

void printpath(LinkStack s,DataType t);

int main( void )

{

int i,j;

int maze[LINES+2][COLS+2] = // 定义存放迷宫的数组并初始化

{1,1,1,1,1,1,1,1,1,1,

1,0,0,1,0,0,0,1,0,1,

1,0,0,1,0,0,0,1,0,1,

1,0,0,0,0,1,1,0,1,1,

1,0,1,1,1,0,0,1,0,1,

1,0,0,0,1,0,0,0,0,1,

1,0,1,0,0,0,1,0,1,1,

1,0,1,1,1,1,0,0,1,1,

1,1,1,0,0,0,1,0,1,1,

1,1,1,0,0,0,0,0,0,1,

1,1,1,1,1,1,1,1,1,1

};

for(i=1;i<LINES+1;i++)

{

for(j=1;j<COLS+1;j++){

if( 0 == maze[i][j] ){

printf("□");

}

else{

printf("■");

}

}

printf("\n");

}

if( path(maze) ){

printf("找到一条路径\n");

for(i=1;i<LINES+1;i++)

{

for(j=1;j<COLS+1;j++)

{

if( 0 == maze[i][j] ){

printf("□");

}

else if( 1 == maze[i][j]){

printf("■");

}

else{

printf("☆");

}

}

printf("\n");

}

}

else{

printf("迷宫无路径\n");

}

return 0;

}

LinkStack InitStack(LinkStack s)

{

return NULL;

}

LinkStack PushStack(LinkStack s,DataType t)

{

StackNode p;

p = NULL;

p = (StackNode )malloc(sizeof(StackNode));

if(!p){

printf("申请结点失败\n");

exit(1);

}

p->element = t;

p->next = s;

s = p;

return s;

}

LinkStack PopStack(LinkStack s,DataType t)

{

StackNode p = NULL;

if( EmptyStack(s) ){

printf("栈空\n");

return NULL;

}

p = s;

t = p->element;

s = s->next;

free(p);

p = NULL;

return s;

}

int EmptyStack(LinkStack s)

{

if( NULL == s ){

return 1;

}

return 0;

}

int path(int maze[][COLS+2])

{

int i,j,x1,y1,v;

DataType temp;

LinkStack top;

tempx = 1;

tempy = 1;

tempd = -1;

top = InitStack(top);

top = PushStack(top,&temp);

while( !EmptyStack(top) )

{

top = PopStack(top,&temp);

// 入口为(1,1)，从0方向开始试探

x1 = tempx;

y1 = tempy;

v = tempd + 1;

while( v < 8 )

{

i = x1 + to[v]line;

j = y1 + to[v]col;

if( 0 == maze[i][j] ){ // 到达新点

tempx = x1;

tempy = y1;

tempd = v;

top = PushStack(top,&temp); // 坐标及方向入栈

x1 = i;

y1 = j;

maze[x1][y1] = -1; // 对已经到过的点做标记

if( x1 == LINES && y1 == COLS ){ // 到达出口

printpath(top,&temp); // 打印路径

return 1;

}

else{

v = 0;

}

}

else{

v++;

}

}

}

return 0;

}

void printpath(LinkStack s,DataType t)

{

while( !EmptyStack(s) )

{

printf("(%d, %d, %d)\n",s->elementx,s->elementy,s->elementd);

s = PopStack(s,t);

}

}

#include<stdioh>

int main(void)

{

int maze[100][100];

int MAZE[100][100];

int m,n;

int p,q;

printf("输入迷宫的行数m,列数n:\n");

scanf("%d%d",&m,&n);

for(p=0;p<=n+1;p++){

maze[0][p]=1;

maze[m+1][p]=1;

}

for(p=1;p<=m;p++){

maze[p][0]=1;

maze[p][n+1]=1;

printf("输入第%d行迷宫:\n",p);

for(q=1;q<=n;q++){

scanf("%d",&maze[p][q]);

MAZE[p][q]=maze[p][q];

}

}

struct location{

int row;

int col;

}way[100];

int movehoriz[8]={-1,0,1,1,1,0,-1,-1};

int movevert[8]={1,1,1,0,-1,-1,-1,0};

int endrow=m;

int endcol=n;

way[0]row=1;

way[0]col=1;

int start=3;

int i=0;

int k;

int j;

int found=0;

while(!found){

for(k=start;k<start+8;k++){

if((maze[way[i]row+movevert[k%8]][way[i]col+movehoriz[k%8]]==0)&&((i==0)||((way[i]row!=way[i-1]row)||(way[i]col!=way[i-1]col)))){

way[i+1]row=way[i]row+movevert[k%8];

way[i+1]col=way[i]col+movehoriz[k%8];

i++;

start=(k+5)%8;

break;

}

if((way[i]row==endrow)&&(way[i]col==endcol)){

break;

}

if((maze[way[i]row+movevert[k]][way[i]col+movehoriz[k]]==0)&&(way[i]row==way[i-1]row)&&(way[i]col==way[i-1]col)){

way[i]row=0;

way[i]col=0;

maze[way[i]row][way[i]col]=1;

i--;

start=(start+4)%8;

}

}

if(k>=start+8){

break;

}

if((way[i]row==endrow)||(way[i]col==endcol)){

found=1;

break;

}

}

if(found){

for(j=0;j<=i;j++){

printf("maze[%d][%d]\n",way[j]row,way[j]col);

}

}

else{

printf("The maze does not have a path\n");

}

}

QQ：366597114 不一定完全对。也许有小错误。有问题可以来问我哈

以上就是关于高分求：迷宫问题数据结构(C语言)全部的内容，包括:高分求：迷宫问题数据结构(C语言)、迷宫问题，C语言、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！