迷宫问题实验报告用栈解决迷宫问题

数据结构实验报告

题目：用栈解决迷宫问题

一．需求分析

1．以结构体Maze表示迷宫，其中pos表示该位置是否有障碍； freq记录该位置被经过的次数；数组move表示下一步的方向。

2．本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有障碍，空符表示通路。

3．迷宫的入口为左上角，出口为右下角。

4．本程序只求出一条成功的通路。

二．概要设计

为了实现上述操作，以栈为存储结构。

本程序包含三个模块：

（1）主程序模块:实现人机交互。

（2）迷宫生产模块：随机产生一个12×12的迷宫。

（3）路径查找模块：实现通路的查找。

（4）求解迷宫中一条通路的伪代码：

do{

若当前位置可同，

则{

将当前位置插入栈顶；

若该位置是出口位置，则结束；

否则切换当前位置的东临方块为新的当前位置；

}

否则{

若栈不空且栈顶位置尚有其他方向未被探索，

则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块

若栈不空但栈顶位置的四周均不可通，

则{

删去栈顶位置；

若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出

栈至栈空。

}

}

} while(栈不空)

三．详细设计

栈的设计：

typedef struct

{

Node *base,*top;

int length;

}Stack;

Stack *initstack(); //初始化栈

void printstack(Stack *s); //打印栈

Status destroy(Stack *); //销毁整个栈

Status deltop(Stack *s); //出栈

Status pushelem(Stack *,ElemType ,ElemType); //进栈

1. 主程序模块：

int main()

{

printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：\n");

Maze a[N][N];

makemaze(a);

printf("输入回车键显示路径,*字符表示路径。\n");

getchar();

findpath(a);

while(1);

return 0;

}

2. 迷宫生产模块；

void makemaze(Maze (*p)[N])

{

int i,j,conter;

for(i=0;i

for(j=0;j

{

(*(p+i)+j)->pos=0;

(*(p+i)+j)->freq=0;

(*(p+i)+j)->move[0]=0;

(*(p+i)+j)->move[1]=0;

(*(p+i)+j)->move[2]=0;

(*(p+i)+j)->move[3]=0;

}

for(j=0;j

{

(*p+j)->pos='X';

(*(p+N-1)+j)->pos='X';

}

for(i=1;i

{

(*(p+i))->pos='X';

(*(p+i)+N-1)->pos='X';

}

srand((int)time(NULL));

for(conter=0;conter<20;++conter)

{

i=rand()%(N-2);

j=rand()%(N-2);

(*(p+i)+j)->pos='X';

if(i==1&&j==1||i==N-1&&j==N-1)

{

(*(p+i)+j)->pos=0;

}

}

printmaze(p);

}

3.路径查找模块。

Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j)

{

Maze *q=NULL;

int select=0;

*i=*j=0;

for(;q==NULL&&select<4;++select)//在可行的方向上只选一个

{

switch(select)

{

case 0:

if( (*(p+s->top->x)+s->top->y)->move[0]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[0]=1;

q=*(p+s->top->x)+s->top->y+1;

*i=s->top->x+0;

*j=s->top->y+1;

}// 退回前一步检查东方向是否可通

break;

case 1:

if( (*(p+s->top->x)+s->top->y)->move[1]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[1]=1;

q=*(p+s->top->x+1)+s->top->y;

*i=s->top->x+1;

*j=s->top->y+0;

}// 退回前一步检查南方向是否可通

break;

case 2:

if( (*(p+s->top->x)+s->top->y)->move[2]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[2]=1;

q=*(p+s->top->x)+s->top->y-1;

*i=s->top->x+0;

*j=s->top->y-1;

}// 退回前一步检查西方向是否可通

break;

case 3:

if( (*(p+s->top->x)+s->top->y)->move[3]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[3]=1;

q=*(p+s->top->x-1)+s->top->y;

*i=s->top->x-1;

*j=s->top->y+0;

}// 退回前一步检查北方向是否可通

}

}

return q;

}

void printpath(Stack *s,Maze (*p)[N])

{

Node *n;

int i,j,conter;

conter=0;

n=s->base;

for(;n;n=n->next)

{

(*(p+n->x)+n->y)->pos='*';

}

for(i=0;i

for(j=0;j

{

++conter;

printf(FORMAT,(*(p+i)+j)->pos);

if(conter%12==0) TURNLINE;

}

TURNLINE;

}

完整的程序：

maze.h

#ifndef MAZE_H

#define MAZE_H

#include "mazepath.h"

#include

#define N 12//10+2

#define FORMAT "%2c"

#define TURNLINE printf("\n")

typedef struct

{

char pos;

int freq;

int move[4];

}Maze;

void makemaze(Maze (*p)[N]);

void printmaze(Maze (*p)[N]);

void findpath(Maze (*p)[N]);

Maze *testnewpos(Maze (*p)[N],Stack *,int *,int *); void printpath(Stack *s,Maze (*p)[N]);

void makemaze(Maze (*p)[N])

{

int i,j,conter;

for(i=0;i

for(j=0;j

{

(*(p+i)+j)->pos=0;

(*(p+i)+j)->freq=0;

(*(p+i)+j)->move[0]=0;

(*(p+i)+j)->move[1]=0;

(*(p+i)+j)->move[2]=0;

(*(p+i)+j)->move[3]=0;

}

for(j=0;j

{

(*p+j)->pos='X';

(*(p+N-1)+j)->pos='X';

}

for(i=1;i

{

(*(p+i))->pos='X';

(*(p+i)+N-1)->pos='X';

}

srand((int)time(NULL));

for(conter=0;conter<20;++conter)

{

i=rand()%(N-2);

j=rand()%(N-2);

(*(p+i)+j)->pos='X';

if(i==1&&j==1||i==N-1&&j==N-1)

{

(*(p+i)+j)->pos=0;

}

}

printmaze(p);

}

void printmaze(Maze (*p)[N])

{

int i,j,conter;

conter=0;

for(i=0;i

for(j=0;j

{

++conter;

printf(FORMAT,(*(p+i)+j)->pos);

if(conter%12==0) TURNLINE;

}

TURNLINE;

}

void findpath(Maze (*p)[N])

{

Maze *q=NULL;

int i=1,j=1,*pi=&i,*pj=&j,success=0;

Stack *s;

s=initstack();//初始化用来存储路径的栈

q=*(p+1)+1;//初始化当前位置为入口位置

do

{

if(q->pos!='X'&&!(q->freq))//当前位置通且在当前路径中未被访问过，则入栈 {

if(i==N-2&&j==N-2)

{

pushelem(s,N-2,N-2);

success=1;

}

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

pushelem(s,i,j);

q->freq=1;//当前位置已经进栈，作标记，不能再入栈，不然就只能兜死胡同了

q->move[0]=1;//切换下一位置为东邻位置,并做标记，东邻位置已经使用

i=s->top->x+0;

j=s->top->y+1;

q=*(p+i)+j;

}

else

{

pushelem(s,i,j);

q->freq=1;

q=*(p+i)+j;

}

}

else//当前位置不通，则在前一步(栈顶)检查是否有其他方向可行

{

//printf("step here...");

if(s->base!=s->top)

{

do//查找新的通路直到新通路出现或者回到初始位置

{

q=testnewpos(p,s,&i,&j);//返回其它三个方向的其中一个和新的当前位置的坐标

if(q==NULL) deltop(s);//栈顶没有可继续往下走的通路，删除栈顶，在新的栈顶找

}while(q==NULL&&s->base!=s->top);

}

}

}while(success!=1);

printpath(s,p);

}

Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j)

{

Maze *q=NULL;

int select=0;

*i=*j=0;

for(;q==NULL&&select<4;++select)//在可行的方向上只选一个{

switch(select)

{

case 0:

if( (*(p+s->top->x)+s->top->y)->move[0]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[0]=1;

q=*(p+s->top->x)+s->top->y+1;

*i=s->top->x+0;

*j=s->top->y+1;

}// 退回前一步检查东方向是否可通

break;

case 1:

if( (*(p+s->top->x)+s->top->y)->move[1]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[1]=1;

q=*(p+s->top->x+1)+s->top->y;

*i=s->top->x+1;

*j=s->top->y+0;

}// 退回前一步检查南方向是否可通

break;

case 2:

if( (*(p+s->top->x)+s->top->y)->move[2]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[2]=1;

q=*(p+s->top->x)+s->top->y-1;

*i=s->top->x+0;

*j=s->top->y-1;

}// 退回前一步检查西方向是否可通

break;

case 3:

if( (*(p+s->top->x)+s->top->y)->move[3]!=1 )

{

(*(p+s->top->x)+s->top->y)->move[3]=1;

q=*(p+s->top->x-1)+s->top->y;

*i=s->top->x-1;

*j=s->top->y+0;

}// 退回前一步检查北方向是否可通

}

}

return q;

}

void printpath(Stack *s,Maze (*p)[N]) {

Node *n;

int i,j,conter;

conter=0;

n=s->base;

for(;n;n=n->next)

{

(*(p+n->x)+n->y)->pos='*';

}

for(i=0;i

for(j=0;j

{

++conter;

printf(FORMAT,(*(p+i)+j)->pos);

if(conter%12==0) TURNLINE;

}

TURNLINE;

}

#endif

mazepath.h

#ifndef MAZEPATH_H

#define MAZEPATH_H

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int ElemType;

typedef int Status;

typedef struct node

{

ElemType x;

ElemType y;

struct node *next;

struct node *prior;

}Node,*Postion;

typedef struct

{

Node *base,*top;

int length;

}Stack;

Stack *initstack(); //初始化栈

void printstack(Stack *s); //打印栈

Status destroy(Stack *); //销毁整个栈

Status deltop(Stack *s); //出栈

Status pushelem(Stack *,ElemType ,ElemType); //进栈

Stack *initstack()

{

Stack *s;

s=(Stack *)malloc(sizeof(Stack));

if(!s) return ERROR;

s->base=s->top=NULL; //栈空

s->length=0;

return s;

}

void printstack(Stack *s)

{

Node *N;

N=s->base;

for(;N;N=N->next)

{

printf("%2d %2d ",N->x,N->y);

}

printf("\n\n");

}

Status destroy(Stack *s)

{

Node *p;

p=s->base;

while(s->base->next)

{

s->base=s->base->next; //N=N->next和free(P)不能倒换位置，当释放p时， free(p); //如果不将N移向下一个位置，将导致N指向的内存释放，N->next 不再有效

p=s->base;

}

s->base=s->top=NULL;

s->length=0;

return OK;

}

Status deltop(Stack *s)

{

Node *p;

if(!s->length)

printf("Underflow\n"); //已经是空栈

else

{

p=s->top;

s->top=p->prior;

free(p);

--s->length;

s->top->next=NULL;

}

return OK;

}

Status pushelem(Stack *s,ElemType i,ElemType j) {

Node *n;

n=(Node *)malloc(sizeof(Node));

if(!n) return ERROR;

n->x=i;

n->y=j；

if(s->length==0)

{

s->base=s->top=n;

n->prior=NULL;

}

else

{

n->prior=s->top;

s->top->next=n;

s->top=n;

}

n->next=NULL;

++s->length;

return OK;

}

#endif

MyMain.cpp

#include "maze.h"

int main()

{

printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：\n");

Maze a[N][N];

makemaze(a);

printf("输入回车键显示路径,*字符表示路径。\n");

getchar();

findpath(a);

while(1);

return 0;

}

四．调试结果及说明

1．说明:本程序的运行环境为VC++6.0，执行文件为MgProblem.exe。

2．测试结果

实际程序执行过程如下图所示：

数据结构迷宫问题实验报告

《数据结构与算法设计》迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航

一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元

StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障 碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上 的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块 a、主程序模块

数据结构之迷宫求解实验报告武汉大学

数据结构实验报告—— 迷宫求解问题实验 上机环境： DevC++ 二、程序设计相关信息 （1）实验题目：迷宫求解问题 问题描述： 实验题3.5 改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。 （2）实验项目组成： 本项目由一个原程序mg.cpp及mg.exe文件组成。 （3）实验项目的程序结构： （4）实验项目包含的函数的功能描述： mg[M+1][N+1] //构造迷宫二维数组，1表示墙不可走方块，0表示通道 mgpath(int xi,int yi,int xe,int ye) //求解路径为：（xi,yi）->（xe,ye） //采用顺序栈存储，进栈，回溯，退栈等

（5）算法描述： 求解迷宫从入口到出口的所有路径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈，并将这个可走发方位保存，且top+1，然后试探下一个方块，若下一个方块能走通则继续，否则则回溯到前一个方块，且top-1。为记录所有的路径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较top值找到一条最短路径并输出。 试探路径过程的算法利用了“广度优先搜索遍历”算法。 流程图： （6）实验数据： 迷宫数组如下： int mg[M+1][N+1]={ {1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1}, {1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}}; 实验结果：

三、程序代码： #include #include #define M 6 #define N 6 #define Maxsize 100 int mg[M+1][N+1]={ {1,1,1,1,1,1}, {1,0,0,0,1,1}, {1,0,1,0,0,1}, {1,0,0,0,1,1}, {1,1,0,0,0,1}, {1,1,1,1,1,1} }; struct { int i; int j; int di; }Stack[Maxsize],Path[Maxsize]; int top=-1; int count=1; int min=Maxsize; int mgpath() {

利用栈实现迷宫地求解

利用栈实现迷宫的求解 一、要解决的问题： 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 二：算法基本思想描述: 用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第n列元素置成“0”，表示迷宫的入口和出口走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置； 用二维数组move记录4个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： Px=x+move[i][0] Py=y+move[i][1] 如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索； 如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 三：设计： 1：数据结构的设计： （1）定义三元数组元素的结构 typedef struct MazeDirect { int Dx; //行标 int Dy; //列标 int direct; //走到下一个坐标点的方向 }MazeDirect; （2）定义链表节点的结构组成 typedef struct LinkNode { elemtype data; //数据域 struct LinkNode *next; //指针域 }LinkNode; （3）定义链栈的头指针 typedef struct {

人因工程模板(0803607张永梅迷宫实验报告)

实验报告——迷宫实验 实验目的： 1、测定睁眼闭眼时学习效果的不同。 2、学习效果随实验次数的变化。 实验地点：杭州电子科技大学现代工业工程实验室（第9教学科研楼401-407室） 实验时间：实验仪器：EP713型迷宫实验 指导老师：蔡敏 实验人员： 所学专业姓名性别年龄籍贯2008级工业工程张永梅 1. 实验设计（必须） 本实验测量被试迷宫学习的学习曲线，学会的标准是连续三次不发生错误（即没有一次进入盲巷）走出迷宫，学习的效果用每遍内错误（走入盲巷）的次数和走一遍所用的时间为指标，并记录学会迷宫总共用的学习遍数。 变量控制（可选） (1) 实验仪器都是正常工作的，不存在差异性。 (2) 实验进行的外部条件（包括温度、亮度等）都是适宜的，假定其保持不变。 (3) 在实验进行前，已详细地向其解释实验操作过程，并事先熟悉、练习一遍，以排 除熟悉度对于动作稳定实验的影响。 对照设置（可选） A.测定睁眼闭眼时学习效果的差异 理论上控制其它的各种因素，将睁眼、闭眼作为实验中的唯一自变量，以准确反映其对因变量（所用时间和出错次数）的影响。

B.测定学习次数的增加对于学习效果的影响 让一名被试连续做多次实验，记录每次实验所用的时间以及出错的次数，分析实验次数的增加是否对学习效果产生影响。 2. 实验过程（必须） （1）将随机附件电源变换器输出插头插入仪器的电源伸入端，然后将电源变换器插入交流220V供电电网的插座 （2）合上仪器的电源开关，仪器数字显示的计时状态，使用者可按动N/T按钮选择仪器数字显示计时状态（）或计数状态（000） （3）拉出小抽板，拿出试笔，被试者手握试笔，试笔尽量和迷宫平面保持垂直，开始实验前，被试者作为第一次学习，应仔细观察迷宫的走道和盲道 （4）开始实验，将试笔在迷宫内滑动，计时器开始计时，如试笔进入盲道并到短点，计数器加1，当试笔到达终点时，仪器内的蜂鸣器鸣响，计时计数器停止工作，按动N/T按钮，数字显示实验时间和出错次数 （5）主试记录数据，被试取下眼罩 （6）按仪器的RET按钮，仪器复位，数字显示 （7）第二次实验，被试再一次观察迷宫的走道和盲道，作为第二次学习，然后按照第一次的步骤，再戴上眼罩，重复上一次实验 （8）被试连续三次无错误地走完整个迷宫后，即可根据实验数据绘制出时间曲线和出错曲线 3. 3. 实验结果（必须） 实验结果记录（必须） 实验结果记录如下表所示： 表1 闭眼时走完迷宫所需时间和错误次数随着学习次数的变化

迷宫问题c++实验报告

数据结构实验报告 班级： 姓名： 学号： 组员： 问题描述： 迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的

门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计功能要求： 迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 算法输入：代表迷宫入口的坐标 算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路 任务分派 为了达到锻炼大家独立设计算法的能力，大家一致决定，先自己独立设计算法，不论算法的好坏、难易，完完全全出自于自己的手中。 在大家独立完成算法后，进行小组集中讨论，将自己的算法思想与大家交流，特别是自己最自豪的部分或是自己觉得可以改进的地方，之后得出最优结果。 独立设计 求解思想： 利用递归的方式进行求解。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 如果现在位置(i,j)处于迷宫的边界位置，则有2种或3种可能的走法，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 struct Pos { int x,y; int di; }; 其中x、y分别表示横纵坐标值、di表示前进的方向。 在已经某一位置（i, j, d）的情况下，其下一个位置横、纵坐标的取值如表4-2所示。 而走到一个新位置时，其方向值初始置为1。 代码 #include "iostream" #include "iomanip" using namespace std; struct Pos { int x,y; int di; };

利用栈实现迷宫的求解

利用栈实现迷宫的求解 一、要解决的四个问题： 1、表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 如图3.4表示的迷宫是一个6×8的迷宫。入口坐标为（1，1），出口坐标为（m，n）。 入口(1,1) 图 1 用maze[m+2][n+2]表示的迷 宫 迷宫的定义如下： #define m 6 /* 迷宫的实际行 */ #define n 8 /* 迷宫的实际列 */ int maze [m+2][n+2] 2 、试探方向： 在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元 m n 素有两个域组成，x：横坐标增量，y：纵坐标增量。Move数组如图3所示。 move数组定义如下： typedef struct { int x //行 int y //列 } item item move[4] 这样对move的设计会很方便地求出从某点 (x，y) 按某一方向 v (0≤v≤3) 到达的新点（i，j）的坐标：i =x + move[v].x ，j = y + move[v].y 。 3．栈的设计： 当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为： 栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走

数据结构-迷宫实验报告

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 实验难度 A □ B □ C □ 承担任务 （难度为C时填写） 指导教师评分（签名） 【实验题目】 实验4.数组的表示极其应用 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。?

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识） 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。 可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。? 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1. 设定迷宫的抽象数据类型定义： ADT Maze { 数据对象：D = { a i, j | a i, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、 ‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 } 数据关系：R = { ROW, COL } ROW = { < a i-1, j , a i, j > | a i-1, j , a i, j ∈D, i=1, … , row+1, j=0, … , col+1} COL = { < a i, j-1, a i, j > | a i, j-1 , a i, j ∈D, i=0, … , row+1, j=1, … , col+1} 基本操作： Init_hand_Maze( Maze, row, col) 初始条件：二维数组Maze[][]已存在。

c语言迷宫问题的求解(栈和递归)

实验报告 【实验名称】项目一迷宫问题的求解 【实验目的】 1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体 的运用。 2.学会用栈或者递归方法解决迷宫问题。 【实验原理】 1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。 2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。 3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。 4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。 【实验内容】 1.需求分析 （1）问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。

（2）基本要求 （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。 2.概要设计 （1）栈的抽象数据类型 ADT Stack{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={|ai-1,ai∈D, i=1,2, …,n } 约定an端为栈顶，a1端为栈底。 基本操作： InitStack( &S ) 操作结果：构造一个空栈S。 DestroyStack ( &S ) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack( &S ) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty( S ) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 StackLength( S ) 初始条件：栈S已存在。 操作结果：返回S的数据元素个数，即栈的长度。 GetTop( S, &e ) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push( &S, e ) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop( &S, &e ) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 }ADT Stack （2）程序模块

迷宫实验报告

一、实验内容 3、迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。 （1）用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。 （2）设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。 （3）输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。 （4）要求输出模拟迷宫的二维数组；若存在最短路径，则有出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如（1,1），......，（i,j），......，（m,n）；若没有路径，则打印“No path”。 （5）迷宫的任一位置（i,j）上均有八个可移动的方向，用二维数组Direction存放八个方向的位置偏移量。 Direction[8][2]={{0,1}，{1,1}，{0，-1}，{-1，-1}，{1,-1}，{1,0}，{-1,0}，{-1,1}}； （6）为避免出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK[i][j]置为1。 （7）为了记录查找过程中到达位置（i，j）及首次到达（i,j）的前一位置（i_pre,j_pre），需要记住前一位置（i_pre,j_pre）在队列中的序号pre，即队列中数据元素应该是一个三元组（i,j,pre）。 （8）搜索过程简单下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置（i,j,pre）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，...，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。 二、实验过程及结果 一、需求分析 1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。 2、以二维数组M[m+2][n+2]表示迷宫，M[i][j] 表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。 3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示： 如下所示：

最简单的c语言迷宫游戏实验报告

一、内容： 1、本游戏主要实现了人控制键盘方向键使小人（*）走出迷宫。 2、具有的功能： 1）、在游戏菜单里人可以选择不同难度的游戏进行游戏； 2）、在游戏过程中，可以通过键盘方向键使小人移动，走出迷宫； 3）、在游戏过程中，当人碰到墙壁（#）的时候小人过不去； 4）、当人顺利完成游戏之后，输出“========you are win!======”字样，30秒钟后自动返回到游戏菜单； 5）、在游戏过程中，人可以通过按Esc键返回游戏菜单；也可以可以按0直接退出游戏； 6）、在游戏菜单里，按0键可以退出游戏。 3、具体应用： 1）、人主要同过键盘的1,2,3数字键来选择游戏难度； 2）、在游戏中通过Esc键来返回菜单； 3）、同过0键退出游戏。 二、上机环境 操作系统：windows7 开发工具:VC6.0 三、函数调用关系图

四、各函数功能说明 main() 主函数； menu() 游戏菜单； roadcake() 消去小人路径； introduce() 游戏介绍； system(“cls”) 消屏函数； exit(0) 退出游戏； drawmg1() 画初级难度迷宫； drawmg2() 画中级难度迷宫； drawmg3() 画高级难度迷宫； control1() 控制初级难度游戏； control2() 控制中级难度游戏； control3() 控制高级难度游戏； 五、算法流程图 首先定义三个全局数组mg1[20][20]、mg2[30][30]、mg3[30][30]用于画出迷宫的地图；1表示墙（#），0表示空地（）； Introduce( )函数里如果按Enter键，则调用menu( )函数，从键盘中输入相应的提示数字，进入难度不同的游戏；游戏的执行在此只初级难度进行描述，其余的难 度与其类似； 选了1后调用system（”cls”）进行清屏；drawmg1()函数进行迷宫的地图的绘

栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行)

#include #include #include #define STACK_INIT_SIZE 100 #define INCREMENT 10 typedef struct { int r; int c; }zuobiao; typedef struct { int ord; //在当前坐标上的“标号” zuobiao seat; //坐标 int di; //走向下一通道的方向 }lujing; typedef struct { int sz[10][10]; }Maze; typedef struct SqStack { lujing *base; lujing *top; int size; }SqStack; int initStack(SqStack *s) { s->base = (lujing *)malloc(STACK_INIT_SIZE*sizeof(lujing) ); if(!s->base) return -1; s->top = s->base; s->size = STACK_INIT_SIZE; return 0; } int push(SqStack *s, lujing e) {

if(s->top - s->base >= s->size) { s->base = (lujing *)realloc(s->base, (s->size+INCREMENT)*sizeof(lujing)); if(!s->base) return -1; s->top = s->base+s->size; s->size += INCREMENT; } *s->top++ = e; return 0; } int pop(SqStack *s,lujing *e) { if(s->top == s->base) return -1; *e = *(--s->top); return 0; } int isEmpty(SqStack *s) { if(s->base == s->top) return 1; else return 0; } int pass( Maze maze,zuobiao dqzb) { if (maze.sz[dqzb.r][dqzb.c]==1) return 1; // 如果当前位置是可以通过，返回1 else return 0; // 否则返回0 } void footPrint(Maze &maze,zuobiao dqzb) { maze.sz[dqzb.r][dqzb.c]=9; } void markPrint(Maze &maze,zuobiao dqzb) { maze.sz[dqzb.r][dqzb.c]=4; } zuobiao nextPos(zuobiao dqzb, int Dir) {

c++迷宫游戏实验报告

1、问题描述 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。 基本要求： （1）老鼠形象可以辨认，可用键盘操纵老鼠上下左右移动； （2）迷宫的墙足够结实，老鼠不能穿墙而过； （3）正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，并给出一条路径，否则提示失败。 提高要求： （1）添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； （2）增加闯关和计分功能； （3）找出走出迷宫的所有路径，以及最短路径。 。 2．需求分析 软件的基本功能：通过键盘控制光标移动实现老鼠在迷宫中的行走、全部路径和最短路径的显示、自定义地图（墙变路，路变墙）。在老鼠闯关只能在地图显示是路的地方行走，不能穿墙，有计时功能，当时间结束时若没有到达指定地点，显示game over，查看排行榜，游戏结束，若成功到达指定位置，进去下一关，直到所有关结束，程序结束；。 输入/输出形式：用户可以通过控制台，根据输入提示。 输入形式： ①方向键、空格键、enter键 输出形式： ①输出地图菜单。 ②输出地图 ③输出是否成功信息、输出排行榜 3．概要设计 （1）主程序流程

图1：主程序流程图 （3）模块调用关系: 本程序中函数包括：main函数，menu函数，menu2函数，mouse类内函数，path 类内函数，change函数， 函数调用关系如下：

图2：函数调用关系 4．详细设计 （1）实现概要设计的数据类型： Mouse类 class mouse { private: int m_x; int m_y; time_t begin ,stop; public: int move_up(int map[x][y],int end);//向上移动 int move_down(int map[x][y],int end);//向下移动 int move_left(int map[x][y],int end);//左 int move_right(int map[x][y],int end);//右 void initialize(int map[x][y],int end){ m_x=S;m_y=S;map[end][end]=9;} void print(int map[x][y],int end);//打印地图

迷宫实验实验报告

迷宫实验 一．摘要 迷宫实验主要是要探讨研究一个人只靠自己的动觉，触觉和记忆获得信息的情况下，如何学会在空间中定向。本实验的被试是华东师范大学应用心理学系大二的一名女同学，本实验以学习遍数为自变量，以所用时间和错误次数为因变量，让被试在排除视觉条件下，用小棒从迷宫起点凹槽移动到达终点，其间小棒每次进入盲巷并与盲巷末端金属片接触算一次错误，学会的定义为连续三遍不出错。而且主试也不能给予被试任何提示或暗示。被试要运用动觉，思维，记忆等自己认为有效的方法独立完成。测试中为了控制疲劳带来的误差，若被试感到疲劳，可稍事休息再进行实验。分析实验数据可知，被试走完迷宫所用时间成减少趋势，错误次数也成减少趋势。在最初几次走迷宫时，错误次数会出现反复的时多时少的情况，所用时间也在反复，时多时少，这表明被试在摸索迷宫路线，处于对整个迷宫的整体定位中。随着学习遍数的增加，错误次数与走完一次迷宫所用的时间开始减少，这表明被试对于迷宫的整体情况有了比较清楚的了解。 关键词迷宫学习次数学习时间错误次数 二．引言 人类从十九世纪末就开始研究迷宫学习了。1899 年,斯莫尔(W. S. Small ) 让白鼠学习一条相当复杂的迷津通路。通过研究他认为,白鼠迷宫学习所依靠的主要是触觉和动觉记忆。1912 年希克思(V. C. Hicks) 和卡尔把迷宫用于研究人类学习。泊金斯（Perkins，1927）最早使用这种在手指迷宫的基础上发展起来的最简便、最常用的触棒迷宫（pencil maze）。近年来，学者们则利用迷宫进行逆反学习能力的研究。而在特殊教育领域，也利用迷宫队正常人和盲人进行了触棒迷宫的对比试验，并得出了盲人心理的巨大补偿作用和学习潜能的结论。 迷宫是研究一个人只靠自己的动觉、触觉和记忆获得信息的情况下，如何学会在空间中定向。迷宫的种类很多，结构方式也不一样，但是有一个特征，这就是有一条从起点到终点的正确途径与从此分出的若干条盲巷。被试的任务是寻找与巩固掌握这条正确途径。迷宫的学习一般可分为四个阶段：1.一般方位辨认。2.掌握迷宫的首段、尾段和中间的一、二部分。3.扩大可掌握的部分，直至全部掌握空间图形。4.形成集体对空间图形的自动化操作。迷宫学习与被试的智商有关，它涉及被试的空间定向能力、思维、记忆诸多方面。 在此迷宫实验中，被试排除视觉条件，用小棒从迷宫起点沿凹槽移动到达终点。在此过程中，被试要运用动觉，思维，记忆等自己认为有效

迷宫实验报告

实习报告、 题目：编制一个求解迷宫通路的程序 班级：计算机04（2）姓名：王金锭学号：04120087 完成日期：06.03.01 一．需求分析： 1．以二维数组Maze[m+2][n+2]表示迷宫,其中:Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]Maze[i][n+1](0<=i<=m+1)为添加的一圈障碍.数组中以元素值为0表 示通路,1表示障碍,限定迷宫的大小m,n<=10. 2．用户以文件的形式输入迷宫的数据:文件中的第一行的数据为迷宫的行数m和列数n；从第二行至第m+1(每行n个数)为迷宫值，同一行中的两个数字之间用空白 字符相隔。 3．迷宫的入口位置和出口位置可由用户随时设定。 4．若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件(即终端)上，其中，字符“＃”表示障碍，字符“＊”表示路径上的位置，字符“@” 表示“死胡同”，即曾途径然而不能到达出口的位置，余者用空格符印出。若设定 的迷宫不存在通路，则报告相应信息。 5．本程序给出一条成功的通路，并且可以通过用户输入把所有的通路输出到指定的文件中。 6．测试数据见原题，当入口位置为(1，1)，出口位置为(9，8)时，输出数据为： 二．概要设计： 1．设定栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai|ai∈IntSet,i=1,2….,n,n>=0} 数据关系：{ai-1,ai|ai-1,ai∈D,i=1,2…..n} 基本操作： InitStack(&S) 操作结果：构造一个空栈。 DestroyStack(&S)

初始条件：栈S已存在 操作结果：将S清空为空栈。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TURE，否则返回FAULE。 GetTop(S,&e) 初始条件：栈S已存在。 操作结果：若S不空，则以e返回栈顶元素。 Push(&S,e) 初始条件：栈S存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S,e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse(S,visit()) 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用visit()。 }ADT Stack 2. 求解迷宫中的一条通路的伪码算法 : 设定当前位置的初值为入口位置; do {若当前位置可通, 则{将当前位置插入栈顶; 若该位置是出口位置,则结束; 否则切换当前位置的东邻方块为新的当前位置; } 否则{ 若栈不空且栈顶位置尚有其他方向未被搜索, 则设定新的当前位置为沿顺时针方向旋转找到的栈顶苇子后的下一个相邻块;若栈不空但粘顶位置的四周均不可通, 则{删去栈顶位置; 若栈不空,则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至空栈; } } }while(栈不空); {栈空说明没有路径存在}

迷宫问题实验报告用栈解决迷宫问题

数据结构实验报告 题目：用栈解决迷宫问题 ．需求分析 1．以结构体 Maze 表示迷宫，其中 pos 表示该位置是否有障碍； freq 记录该位置被经过的次数；数组 move 表示下一步的方向。 2. 本程序自动随机生成一个12 × 12大小的迷宫，字符“ H”表示有障碍，空符表示通 路。 3. 迷宫的入口为左上角，出口为右下角。 4. 本程序只求出一条成功的通路。 .概要设计 为了实现上述操作，以栈为存储结构。 本程序包含三个模块： 1)主程序模块 :实现人机交互。 2)迷宫生产模块:随机产生一个12× 12的迷 宫。 3)路径查找模块：实现通路的查找。 4)求解迷宫中一条通路的伪代码： do{ 若当前位置可同，则{ 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；} 否则 { 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针 方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈 至栈空。 } } } while( 栈不空 ) 三. 详细设计栈的设计： typedef struct { Node *base,*top; int length; }Stack; Stack *initstack(); // 初始化栈 void printstack(Stack *s); // 打印栈 Status destroy(Stack *); // 销毁整个栈 Status deltop(Stack *s); // 出栈 Status pushelem(Stack *,ElemType ,ElemType); // 进栈 1. 主程序模块： int main() { printf(" 随机产生一个12× 12 的迷宫， X 字符表示障碍，空符表示通路： \n"); Maze a[N][N]; makemaze(a); printf(" 输入回车键显示路径 ,* 字符表示路径。 \n"); getchar(); findpath(a); while(1); return 0;

实验报告迷宫问题

实习2栈的应用 本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。 实验课时6课时 程序1：迷宫问题 ［问题描述］ 以一个m×n的长方阵表示迷宫，‘0’和‘1’分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 ［基本要求］ 首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），… ［测试数据］ 迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。[实现提示] 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道，可以二维数组存储迷宫数据。 [程序实现] #include #include //1.迷宫位置坐标类型 typedefstruct { intx;//行 inty;//列 }PosType; #defineMAXENGTH25//迷宫最大行列数位25 typedefintMazeType[MAXENGTH][MAXENGTH];//迷宫数列 typedefstruct//定义栈 { intord;//通道块在路径上的序号 PosTypeseat;//通道块在迷宫中的位置 intdi;//走向下一块的方向（0~3表示东、南、西、北） }SElemType;

求解迷宫问题

求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {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,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 伪代码： c语言描述如下：

void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /*栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,输出路径*/ { printf("迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); }