数据结构 迷宫问题

#include <stdioh>

#include <malloch>

#include <conioh>

typedef struct pos /描述迷宫当前位置和方向/

{

int x;

int y;

int way; /0:无效,1:左,2:下,3:右,4:上/

}P;

typedef struct LinkNode /链表结构,用于栈的元素类型/

{

P pos;

struct LinkNode next;

}LinkNode;

typedef struct stack /链式栈,用于存储迷宫路径信息/

{

LinkNode head; /头指针/

}Stack;

int row=0; /迷宫的行数/

int line=0; /迷宫的列数/

void InitStack(Stack s) /栈置空/

{

s->head=NULL;

}

void Push(Stack s,P p) /数据入栈/

{

LinkNode LN=(LinkNode )malloc(sizeof(LinkNode));

LN->pos=p;

LN->next=s->head;

s->head=LN;

}

P Pop(Stack s) /栈顶元素出栈/

{

P pos;

LinkNode LN;

LN=s->head;

s->head=s->head->next;

pos=LN->pos;

delete LN;

return pos;

}

P GetPop(Stack s) /读取栈顶元素/

{

return shead->pos;

}

int Empty(Stack s) /判空/

{

if(shead==NULL)

return 1;

else

return 0;

}

int InitMaze() /返回迷宫的二维指针/

{

int maze=NULL;

int i;

int j;

printf("请输入迷宫的行跟列(x,y):");

scanf("%d,%d",&row,&line); /输入迷宫的行和列/

maze=(int )malloc((row+2)sizeof(int ));

for(i=0;i<row+2;i++)

{

maze[i]=(int )malloc(sizeof(int)(line+2));

}

printf("请输入迷宫\n"); /输入迷宫,1代表路障,0代表通行/

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

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

scanf("%d",&maze[i][j]);

for(i=0;i<line+2;i++) /将迷宫的四周都变为1/

maze[0][i]=1;

for(i=0;i<line+2;i++)

maze[row+1][i]=1;

for(i=0;i<row+2;i++)

maze[i][0]=1;

for(i=0;i<row+2;i++)

maze[i][line+1]=1;

for(i=0;i<row+2;i++) /输出迷宫/

{

for(j=0;j<line+2;j++)

printf("%3d",maze[i][j]);

printf("\n");

}

return maze;

}

void PrintWay(Stack p) /输出路径/

{

P pos;

Stack t; /临时栈,用于存储从入口到出口的路径/

LinkNode temp;

int a,b;

InitStack(&t);

temp=(LinkNode )malloc(sizeof(LinkNode));

temp->pos=Pop(&p); /取栈顶元素,即出口/

Push(&t,temp->pos); /入栈/

free(temp);

while(!Empty(p))

{

temp=(LinkNode )malloc(sizeof(LinkNode));

temp->pos=Pop(&p); /获取下一个元素/

a=GetPop(t)x-temp->posx; /左:a=0,b=1; 下:a=1,b=0/

b=GetPop(t)y-temp->posy; /右:a=0,b=-1 上:a=-1,b=0;/

if(b==1)

temp->posway=1;

else if(a==1)

temp->posway=2;

else if(b==-1)

temp->posway=3;

else if(a==-1)

temp->posway=4;

Push(&t,temp->pos); /新位置入栈/

free(temp);

}

printf("迷宫的路径为:\n");

printf("前两个数字表示位置,最后一个数字表示方向\n");

printf("1表示向左,2表示向下,3表示向右,4表示向上,0表示无方向\n");

while(!Empty(t)) /输出路径/

{

pos=Pop(&t);

printf("%3d,%3d,%3d\n",posx,posy,posway);

}

}

int FindMaze(int maze,int r,int l) /寻找路径,找到返回1,没找到返回0/

{

Stack p,q; /栈p,q分别表示探索迷宫的路径和过程/

P temp1,temp2;

int a,b;

InitStack(&p);

InitStack(&q);

temp1x=1;

temp1y=1; //

maze[1][1]=-1; /标记已经走过/

Push(&p,temp1);

Push(&q,temp1);

while(!Empty(q))

{

temp2=GetPop(q);

if(!(GetPop(p)x==GetPop(q)x

&&GetPop(p)y==GetPop(q)y))

Push(&p,temp2); /若有新元素入栈,就把q的栈顶元素存入p中/

a=temp2x;

b=temp2y+1; /当前位置左方向相邻的方块/

if(maze[a][b]==0)

{

temp1x=a;

temp1y=b;

maze[a][b]=-1; /标记已走过/

Push(&q,temp1);

}

if(a==r&&b==l) /到达出口/

{

temp1way=0;

Push(&p,temp1);

PrintWay(p);

return 1;

}

a=temp2x+1;

b=temp2y; /当前位置下方向相邻的方块/

if(maze[a][b]==0)

{

temp1x=a;

temp1y=b;

maze[a][b]=-1; /标记已走过/

Push(&q,temp1);

}

if(a==r&&b==l) /到达出口/

{

temp1way=0;

Push(&p,temp1);

PrintWay(p);

return 1;

}

a=temp2x;

b=temp2y-1; /当前位置右方向相邻的方块/

if(maze[a][b]==0)

{

temp1x=a;

temp1y=b;

maze[a][b]=-1; /标记已走过/

Push(&q,temp1);

}

if(a==r&&b==l) /到达出口/

{

temp1way=0;

Push(&p,temp1);

PrintWay(p);

return 1;

}

a=temp2x-1;

b=temp2y; /当前位置上方向相邻的方块/

if(maze[a][b]==0)

{

temp1x=a;

temp1y=b;

maze[a][b]=-1; /标记已走过/

Push(&q,temp1);

}

if(a==r&&b==l) /到达出口/

{

temp1way=0;

Push(&p,temp1);

PrintWay(p);

return 1;

}

if(GetPop(p)x==GetPop(q)x

&&GetPop(p)y==GetPop(q)y) /若四个方向都走不通,则数据出栈,退回一格/

{

Pop(&p);

Pop(&q);

}

}

return 0; /探索迷宫失败/

}

void main()

{

int maze=InitMaze(); /初始化迷宫/

if(FindMaze(maze,row,line)) /探索路径/

printf("路径探索成功!\n");

else

printf("路径探索失败!\n");

getch();

}

看下我的程序,,要不是你要的

#include <iostream>

#include <iomanip>

using namespace std;

#define M 20

#define N 20

struct move{int dx,dy;};

move mazemove[8];

char ma[M][N];

int False=0;

void maze()

{int i,j,num;

for(i=1;i<M-1;i++)

{for(j=1;j<N-1;j++)

{num=(800(i+j)+1500)%327;

if((num<156)&&(i!=M||j!=N))

ma[i][j]='1';

else

ma[i][j]='0';

}

}

ma[1][1]='0';

ma[M-2][N-2]='0';

for(i=0;i<M;i++)

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

cout<<setw(3)<<ma[i][j];

cout<<endl;

}

}

void inimove()

{mazemove[0]dx=0;mazemove[0]dy=1;

mazemove[1]dx=1;mazemove[1]dy=1;

mazemove[2]dx=1;mazemove[2]dy=0;

mazemove[3]dx=1;mazemove[3]dy=-1;

mazemove[4]dx=0;mazemove[4]dy=-1;

mazemove[5]dx=-1;mazemove[5]dy=-1;

mazemove[6]dx=-1;mazemove[6]dy=0;

mazemove[7]dx=-1;mazemove[7]dy=1;

}

void outpath()

{int i,j,x,y,k;

i=1;j=1;k=0;

while((i!=(M-2))||(j!=(N-2)))

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

{x=i+mazemove[k]dx;

y=j+mazemove[k]dy;

if(ma[x][y]=='0'){k=0;break;}

}

if(k!=8)

{if(ma[i][j]=='8')ma[i][j]='2';

if(ma[i][j]=='0')ma[i][j]='>';

i=x;j=y;

}

else

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

{x=i+mazemove[k]dx;

y=j+mazemove[k]dy;

if(ma[x][y]=='8')break;

}

ma[i][j]='2';

i=x;j=y;

}

if((i==1)&&(j==1))

{False=0;

break;

}

else False=1;

}

}

int main()

{int i,j;

maze();

inimove();

outpath();

cout<<endl;

if(False==0)

cout<<"无法走出该迷宫!"<<endl;

else

{cout<<"走出迷宫的路径(用‘>’符号表示)为:"<<endl;

ma[M-2][N-2]='>';

for(i=0;i<M;i++)

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

{ {if(ma[i][j]=='2')ma[i][j]='>';

if(ma[i][j]=='0')ma[i][j]=' ';

if(ma[i][j]=='1')ma[i][j]='';

}

cout<<setw(3)<<ma[i][j];

}

cout<<endl;

}

}

return 0;

}

分类: 电脑/网络 >> 程序设计 >> 其他编程语言

问题描述:

程序如下：

#include"stdioh"

#include"stdlibh"

#define m 4

#define n 4

struct stype

{int x,y;

}stack[400];

int mg[m+2][n+2];

int zx[9],zy[9];

void printlj(int TOP)

{int i;

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

{printf("(%d,%d)",stack[i]x,stack[i]y);

}

}

void mglj()

{int i,j,x,y,top,find,v;

top=1;stack[1]x=1;stack[1]y=1;find=0; mg[1][1]=-1;

while(top>=1&&!find)

{x=stack[top]x; y=stack[top]y;

for(v=1;v<=8;v++)

{i=x+zx[v];

j=y+zy[v];

if(mg[i][j]==0)

{top++;

stack[top]x=i;

stack[top]y=j;

mg[i][j]=-1;

break;

}

if(v==8) top--;

}

if((stack[top]x ==m)&&(stack[top]y ==n))

{printlj(top);

find=1;

}

}

if(!find) printf("no way\n");

}

void main()

{int i,j;

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

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

scanf("%d",&mg[i][j]);

for(i=0;i<=m+1;i++)

{mg[i][0]=1;mg[i][n+1]=1;}

for(j=0;j<=n+1;j++)

{mg[0][j]=1;mg[m+1][j]=1;}

zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;

zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;

mglj();

}

解析:

我看了一下,算法应该是一样的,下面是我以前用C++写的

相信你能看得懂

/

/迷宫求解

作者:baihacker/

/时间:11102006/

/

/class:

Matrix:矩阵类

offsets:搜索偏移

enum directions:四个方向

struct item:搜索节点

Migong:迷宫类

1创建一个Migong对象

2使用用Create方法输入数据

3使用Solve方法进行求解

4ShowSolve方法显示解

5可以重复使用Create方法

6入口只能在左上角

7默认出口在右下角

ShowAllPath:穷举所有的路径

备注:

由于算法原因,这里的所有路径应该是指

介于:

a如果两条路存在某个点不同那么就是不同的路

b如果在一条路中去掉一个或者一个以上的圈,那么他们是同一条路

之间意义上的路

/

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

#ifndef MIGONG_H

#define MIGONG_H

/

/矩阵类

/

class Matrix{

int m;

int row, col;

bool iscreate;

public:

Matrix(){m=0;iscreate=false;};

~Matrix() {Release();};

bool Create(int, int);

int& operator () (int, int);

int GetRow(){return row;};

int GetCol(){return col;};

void Release();

void Show(char, char );

};

bool Matrix::Create(int r, int c)

{

if( r<=0 || c<=0) return false;

Release();

row = r;

col = c;

m = new int[rowcol];

for (int i=0;i<rowcol;i++)

{

(m+i) = 0;

}

iscreate = true;

return true;

}

int& Matrix::operator ()(int r, int c)

{

return (m+rcol+c);

}

void Matrix::Release()

{

if (iscreate)

{

row = col = 0;

if (m) delete[] m;

m = 0;

}

iscreate = false;

}

void Matrix::Show(char blk='#', char nblk=' ')

{

int i, j;

for (i=0;i<row;i++)

{

for (j=0;j<col;j++)

{

if ((m+icol+j) == 0)

cout<<nblk;

else

cout<<blk;

}

cout<<endl;

}

}

/

迷宫相关数据结构的定义/

/

struct offsets{

int a, b;

};

enum directions{

_S = 0,

_E,

_N,

_W

};

struct item{

int row, col, dir;

};

class Migong{

static offsets move[4];

Matrix maze;

Matrix mark;

int row;

int col;

int desr;

int desc;

stack<item> stk;

bool iscreate;

int pathlength;

bool GetPath();

bool IsInPath(int, int);

public:

Migong(){issolved=false;result=0;pathlength=row=col=0;iscreate=false;};

~Migong(){Release();};

bool Create(int , int , int , int , int );

void Solve();

void Release();

void OutputMaze();

void ShowSolve(char, char );

public:

bool issolved;

item result;

};

offsets Migong::move[4]={ {1, 0}, {0, 1},

{-1, 0}, {0, -1}};

迷宫数据应该是不含边框的

bool Migong::Create(int m, int r, int c, int desrow=-1, int descol=-1)

{

if (r<=0 || c<=0) return false;

Release();

if (desrow==-1 || descol==-1)

{

desr = r;

desc = c;

}

else

{

desr = desrow;

desc = descol;

}

row = r;

col = c;

mazeCreate(r+2, c+2);

markCreate(r+2, c+2);

int i, j;

for (i=0;i<r+2;i++)

{

for (j=0;j<c+2;j++)

{

if (j==0 || j==c+1 || i==0 || i==r+1)

{

mark(i, j) = maze(i, j) = 1;

}else

{

mark(i, j) = 0;

maze(i, j) = m[((i-1)col+j-1)];

}

}

}

return iscreate = true;

}

bool Migong::GetPath()

{

mark(1,1) = 1;

item temp;

tempcol = 1;

temprow = 1;

tempdir = _S;

stkpush(temp);

while (!stkempty())

{

temp = stktop();

stkpop();

int i = temprow;

int j = tempcol;

int d = tempdir;

while (d<4)

{根据当前点的状态确定下一个搜索点

int g = i + move[d]a;

int h = j + move[d]b;

if (g==desr && h==desc)

{

return true;

}

如果这个点不是障碍点且没有被搜索过那么可以对这个点进行搜索

if (maze(g, h)==0 && mark(g, h)==0)

{

mark(g, h) = 1;

temprow = g;

tempcol = h;

tempdir = d+1;

stkpush(temp);

i = g;

j = h;

d = _S;对一下个点进行搜索

}

else d++;

}

}

return false;

}

void Migong::Solve()

{

issolved = GetPath();

if (issolved)

{

pathlength = stksize();

result = new item[pathlength];

for (int i=0;i<pathlength;i++)

{

(result+i) = stktop();

stkpop();

cout<<"("<<((result+i))row<<","<<((result+i))col<<")"<<endl;

}

}

while (!stkempty())

stkpop();

}

void Migong::Release()

{

if (iscreate)

{

mazeRelease();

markRelease();

row=col=0;

if (result)

delete [] result;

result = 0;

while (!stkempty())

stkpop();

}

iscreate = false;

issolved = false;

pathlength = 0;

}

void Migong::OutputMaze()

{

if (!iscreate) return;

mazeShow();

}

bool Migong::IsInPath(int r, int c)

{

if (!iscreate || !issolved)

return false;

item temp;

for (int i=0;i<pathlength;i++)

{

temp = (result+i);

if ((temprow==r) && (tempcol==c))

return true;

}

return false;

}

void Migong::ShowSolve(char blk='#',char s='o')

{

if (!iscreate) return;

if (!issolved)

{

cout<<"无解"<<endl;

}

else

{

int i, j;

for (i=0;i<row+2;i++)

{

for (j=0;j<col+2;j++)

{

if ((i==1 && j==1) || (i==desr && j==desc))

{

cout<<s;

}

else if (maze(i, j) == 1)

{

cout<<blk;

}else

{

if (IsInPath(i, j))

cout<<s;

else

cout<<' ';

}

}

cout<<endl;

}

}

}

穷举所有路径

offsets move[4]={ {1, 0}, {0, 1},

{-1, 0}, {0, -1}};

struct node

{

int row,col;

};

vector<node> path;

int count;

bool IsReachable( Matrix& maze, Matrix& mark, node beg, node des)

{

if (begrow==desrow&&begcol==descol)

{如果达到的话那么显示路径

count++;

cout<<"第"<<count<<"条路径:"<<endl;

for (int i=0;i<pathsize();i++)

cout<<"("<<path[i]row<<","<<path[i]col<<")";

cout<<"("<<desrow<<","<<descol<<")";

cout<<endl;

return false;

}

if (maze(begrow, begcol)==1 || mark(begrow, begcol)==1)

{

return false;

}

pathpush_back(beg);

mark(begrow, begcol) = 1;

node nextnode;

for (int i=_S;i<_W+1;i++)

{

nextnoderow = begrow + move[i]a;

nextnodecol = begcol + move[i]b;

IsReachable(maze, mark, nextnode, des);

}

pathresize(pathsize()-1);

mark(begrow, begcol) = 0;

return false;如果不是穷举的话应该根据for循环的结果重新设置返回值

}

/

参数maze,mark为迷宫长宽均加二的矩阵

desr,desc为出口点

/

void FindAllPath( Matrix& maze, Matrix& mark, int desr, int desc)

{

node first, last;

firstrow = 1;

firstcol = 1;

lastrow = desr;

lastcol = desc;

IsReachable(maze, mark, first, last);

pathclear();

}

/

m迷宫矩阵数据

r,c行和列的大小

desr,desc目标位置

/

void ShowAllPath(int m, int r, int c, int desr=-1, int desc=-1)

{

Matrix maze, mark;

mazeCreate(r+2, c+2);

markCreate(r+2, c+2);

if (desr==-1 || desc==-1)

{

desr = r;

desc = c;

}

int i, j;

for (i=0;i<r+2;i++)

{

for (j=0;j<c+2;j++)

{

if (j==0 || j==c+1 || i==0 || i==r+1)

{

mark(i, j) = maze(i, j) = 1;

}else{

mark(i, j) = 0;

maze(i, j) = m[((i-1)c+j-1)];

}

}

}

count = 0;

FindAllPath(maze, mark, desr, desc);

mazeRelease();

markRelease();

}

#endif

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现

用的是深度优先的算法，可以寻找到走出迷宫的路径

但本题要求求出最短的路径，这就要使用广度优先的算法

一般在程序中需要用到先进先出的队列数据结构

下面是程序的代码，主要原理是用到

quei，quej和prep三个数组来构成队列

分别储存路径的行，列坐标和上一个节点在队列中的位置

大致算法如下，右三个嵌套的循环实现

首先是第一个节点进入队列

当队列不空（循环1）

｛

   遍历队列中每节点(循环2）

｛

       将八个方向能够走的节点加入队列（循环3）

｝

   旧的节点出列

｝

#include<ctime> 

using namespace std; 

#define MAXNUM 50

void main() 

{

int m,n,i,j,x;

cout<<"请输入迷宫大小"<<endl;

cin>>m>>n;

int maze[MAXNUM][MAXNUM];

srand((int)time(NULL));

for(i=0;i<=m+1;i++){

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

if(i==0||j==0||i==m+1||j==n+1)

maze[i][j]=1;

else

{

x=rand()%1000;

if(x>700){maze[i][j]=1;} //控制矩阵中1的个数，太多1迷宫很容易走不通

else{maze[i][j]=0;}

}

cout<<maze[i][j]<<' ';

}

cout<<endl;

}

//以上是输入和迷宫生成，一下是走迷宫

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

int quei=new int[mn];//储存行坐标队列

int quej=new int[mn];//储存列坐标队列

int prep=new int[mn];//储存之前一步在队列中的位置

int head,rear,length;//队列头，队列尾，队列长度

head=0;rear=1;length=1;

quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列

int pos;//当前节点在队列中的位置，

int ii,jj,ni,nj;//当前节点的坐标，新节点的坐标

int dir;//移动方向

if(maze[1][1]==1)length=0;//第一点就不能通过

else maze[1][1]=1;

while(length)//队列非空继续

{

for(pos=head;pos<head+length;pos++)//寻找这一层所有节点

{

ii=quei[pos];jj=quej[pos];//当前位置坐标

if(ii==m&&jj==n)break;

for(dir=0;dir<8;dir++)//寻找8个方向

{

ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标

if(maze[ni][nj]==0)//如果没有走过

{

quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队

rear=rear+1;

maze[ni][nj]=1;//标记已经走过

}

}

}

if(ii==m&&jj==n)break;

head=head+length;

length=rear-head;//这一层节点出列

}

if(ii==m&&jj==n)

{

while(pos!=-1)

{

cout<<'('<<quei[pos]<<','<<quej[pos]<<')';

pos=prep[pos];

if (pos!=-1)cout<<',';

}

}

else

{

cout<<"THERE IS NO PATH"<<endl;

}

delete []quei;

delete []quej;

delete []prep;

}

请把C++的注释风格改成风格的,两个程序都调试通过!

////////////////////////////////////////////////////////////////////////////////

程序1

#include<stdioh>

#define N1 11

#define N2 10

int getpath(int maze[N1][N2])//在迷宫中探路的函数

{

int stack[N1N2][2];

int i,x=1,y=1,ok,top=0;//可通路径上第一个点（入口点）的坐标进入路径数组stack

stack[top][0]=x;

stack[top][1]=y;//循环探路。加1则向前，减1则退回一步

while (1)

{

ok=0;//标志能否向前

if (maze[x][y+1]==0)

{y=y+1;ok=1;}//向右

else

if (maze[x+1][y]==0)

{x=x+1;ok=1;}//向下

else

if (maze[x][y-1]==0)

{y=y-1;ok=1;}//向左

else

if (maze[x-1][y]==0)

{x=x-1;ok=1;}//向上

if (!ok)//4方向均不通

{

top--;

if (top==0)//栈空，无出路

{

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

return 0;

}

x=stack[top][0];//回退后路径上最后一个点的X坐标存入X

y=stack[top][1];//回退后路径上最后一个点的Y坐标存入Y

}

else//若能走通，

{

maze[x][y]=2;//将已经走过的点标记为2

top++;

stack[top][0]=x;//新进入的点的X坐标进入路径数组

stack[top][1]=y;//新进入的点的Y坐标进入路径数组

if (x==N1-2&&y==N2-2)//到达出口

{

printf("路径为：\n");

for(i=0;i<top;i++)

{

printf("(%d,%d)-->",stack[i][0],stack[i][1]);

if((i+1)%5==0)

printf("\n");

}

printf("(%d,%d)\n",stack[top][0],stack[top][1]);

return 1;

}

}

}

}

void printmaze(maze)//输出迷宫数组函数

int maze[N1][N2];

{

int i,j;

printf("迷宫数组为：\n");

for (i=0;i<N1;i++)

{

for (j=0;j<N2;j++)

printf("%2d",maze[i][j]);

printf("\n");

}

}

main()

{

int A[N1][N2]=

{

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};

printmaze(A);

getpath(A);

}

//////////////////////////////////////////////////////////////////////

程序2

#include<stdioh>

#include<stdlibh>

#define OVERFLOW -1

#define MAX 100

#define N 11

typedef struct

{

int x;

int y;

int d;

}Data;

typedef struct

{

int pos;

Data data[MAX];

}SNode,Stack;

Stack InitStack()

{

Stack pStack;

pStack=(Stack)malloc(sizeof(SNode));

if(!pStack)

exit(OVERFLOW);

pStack->pos=-1;

return pStack;

}

int IsEmpty(Stack stack)

{

return stack->pos==-1;

}

void Push(Stack pStack,Data x)

{

if(pStack->pos>=MAX-1)

exit(OVERFLOW);

else

{

pStack->pos++;

pStack->data[pStack->pos]=x;

}

}

void Pop(Stack pStack)

{

if(pStack->pos==-1)

exit(OVERFLOW);

else

pStack->pos--;

}

Data GetTop(Stack pStack)

{

return pStack->data[pStack->pos];

}

Data SetStackElem(int x,int y,int d)

{

Data element;

elementx=x;

elementy=y;

elementd=d;

return element;

}

void DisplayPath(Stack pStack)

{

Data element;

printf("The path is:\n");

while(!IsEmpty(pStack)) //多了个;

{

element=GetTop(pStack);

Pop(pStack);

printf("The node is: %d %d\n",elementx,elementy);

}

}

void MazePath(int maze[][N],int direction[][2],int x1,int y1,int x2,int y2)

{

int i,j,k,g,h;

Stack pStack;

Data element;

pStack=InitStack();

maze[x1][y1]=2;

Push(pStack,SetStackElem(x1,y1,0));

while(!IsEmpty(pStack))//以前多了一个;

{

element=GetTop(pStack);

Pop(pStack);

i=elementx;

j=elementy;

k = elementd;

while (k<=3)//用while

{

g=i+direction[k][0];

h=j+direction[k][1];

if(g==x2&&h==y2&&maze[g][h]==0)

{

Push(pStack,SetStackElem(i,j,k));//把路径上最后一个点放入

DisplayPath(pStack);

return;//怎么会有返回值

}

if(maze[g][h]==0)

{

maze[g][h]=2;

Push(pStack,SetStackElem(i,j,k+1));

i=g;

j=h;

k=0;

}

else

k++;

}

}

printf("The path has not been found\n");

}

void main()

{

int direction[][2]={0,1,1,0,0,-1,-1,0};

int maze[][N]=

{

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

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

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

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

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

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

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

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

};

MazePath(maze,direction,1,1,6,9);

}

核心算法是搜索，这里如果要求用栈实现那就是深度优先搜索。 如果他不指定是用栈， 那么用队列来做就是广度优先搜索。

正常的深度优先搜索是可以用递归来实现的， 即然要求你非递归 你可以用栈来模拟递归的效果，毕竟函数的递归调用本质也是用栈来实现的

// Migong_Queuecpp : 定义控制台应用程序的入口点。

#include "stdafxh"

#include "stdlibh"

#define MaxSize 100

struct

{

int i,j;

int pre;

}Qu[MaxSize];

int front = -1,rear = -1;

int mgpath(int ,int ,int ,int ,int);

void print(int);

int _tmain(int argc, _TCHAR argv[])

{

int l,h;

FILE migong=fopen("C:\\Users\\Administrator\\Documents\\Visual Studio 2010\\Projects\\数据结构实验\\Migong_Queue\\migongtxt","r");

if(migong==NULL)

{

printf("Can't open the file!!!");

exit(0);

}

char ch=fgetc(migong);

l=0;

while(ch!='\n')

{

if(ch!=',')

l++;

ch=fgetc(migong);

}//l为迷宫的长度

rewind(migong);

//接下来是算出迷宫的高度h！~~

h=0;

ch=fgetc(migong);

while(!feof(migong))

{

if(ch=='\n')

h++;

ch=fgetc(migong);

}

if(l<5||h<5)

{

printf("It's too small!");

exit(0);

}

rewind(migong);

int mg=(int )malloc(sizeof(int )h);

for(int h_=0;h_<h;h_++)

{

mg[h_]=(int )malloc(sizeof(int)l);

}

for(int h_=0;h_<h;h_++)

{

for(int l_=0;l_<l;)

{

ch=fgetc(migong);

if(ch!=',')

{mg[h_][l_]=ch-'0';l_++;}

}

ch=fgetc(migong);

}

fclose(migong);

printf("The map is presented as follows:\n");

for(int _x=0;_x<h;_x++)

for(int _y=0;_y<l;_y++)

{

printf("%d ",mg[_x][_y]);

if((_y+1)%l==0)

printf("\n");

}

mgpath(mg,1,1,8,8);

return 0;

}

int mgpath(int mg,int xi,int yi,int xe,int ye)

{

int i,j,find=0,di;

rear++;

Qu[rear]i=xi;

Qu[rear]j=yi;

Qu[rear]pre=-1;

mg[xi][yi]=-1;

while(front<=rear&&!find)

{

front++;

i=Qu[front]i;j=Qu[front]j;

if(i==xe&&j==ye)

{

find=1;

print(front);

return 1;

}

for(di=0;di<4;di++)

{

switch(di)

{

case 0:i=Qu[front]i-1;j=Qu[front]j;break;

case 1:i=Qu[front]i;j=Qu[front]j+1;break;

case 2:i=Qu[front]i+1;j=Qu[front]j;break;

case 3:i=Qu[front]i;j=Qu[front]j-1;break;

}

if(mg[i][j]==0)

{

rear++;

Qu[rear]i=i;Qu[rear]j=j;

Qu[rear]pre=front;

mg[i][j]=-1;

}

}

}

return 0;

}

void print(int front)

{

int k=front,j,ns=0;

printf("\n");

do

{

j=k;

k=Qu[k]pre;

Qu[j]pre=-1;

}while(k!=0);

printf("迷宫路径如下：\n");

k=0;

while(k<MaxSize)

{

if(Qu[k]pre==-1)

{

ns++;

printf("\t(%d,%d)",Qu[k]i,Qu[k]j);

if(ns%5==0)printf("\n");

}

k++;

}

printf("\n");

}

我是从文件中读取迷宫数组的！

你也可以改为直接输入！

希望对你有帮助！谢谢！

以上就是关于数据结构 迷宫问题全部的内容，包括:数据结构 迷宫问题、数据结构课程设计的迷宫问题~~~~急！！！、求C语言迷宫程序的解释说明！！！等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！