迷宫问题2

题目：假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为(1，1)，出口坐标为

(m，n)，试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。 要求：用栈和队列实现，不允许使用递归算法。

一、 需求分析

1. 用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的

通路，从而建立自己的迷宫；或则使用程序中提供的迷宫。其中用栈和队列的基本操作完成迷宫问题的求解；

2. 用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了，但是应该在合法范围内； 3. 用户进入菜单页面选择输入迷宫的状态（0：表示用户根据自己的需求创建迷宫： 1：

表示用户使用程序提供的迷宫； 2：表示退出程序状态） 4. 程序执行的命令包括：

（1）构造栈sqmaze （2）构造抽象迷宫数组maze （3）选择自己要的迷宫 （4）输出迷宫 （5）在迷宫中寻找一条最短的通路 （6）打印出所找到的最短通路（输出搜索结果）

二、概要设计

⒈ 为实现上述算法，需要线性表的抽象数据类型：

ADT Stack {

数据对象：D={ai:|ai∈ElemSet,i=1„n,n≥0} 数据关系：R1={|ai-1,ai∈D,i=2,„n≥0} 基本操作:

initstack(& S)

操作结果：构造一个空的栈S。 StackLength(S)

初始条件：栈S已经存在

操作结果：返回S中数据元素的个数。 Stackempty(S)

初始条件：栈S已经存在

操作结果：判断S中是否为空，若为空，则返回TURE，否则FALSE。 GetTop(S,&e)

初始条件：栈S已存在且不为空 操作结果：用e返回S的栈顶的元素。 Push(&S ,e)

初始条件：栈S已存在

操作结果：插入元素e为新的栈顶元素。 Pop(&S，&e)

初始条件：栈S已存在且不为空

操作结果：删除S的栈顶元素，并用e返回其值。

}ADT List

2. 本程序有三个模块：

⑴ 主程序模块

main(){ 初始化；

Switch（参数）{

Case 0 ： 接受命令； Case 1 ： 接受命令； Case 2： 接受命令； ｝ ｝ ⑵ 栈单元模块：实现栈抽象数据类型；

⑶ 迷宫数组单元模块：设计迷宫，实现迷宫抽象数据类型。 各模块之间的调用关系是：主程序模块——迷宫模块——栈模块

三、详细设计

⒈元素类型定义 typedef struct { int x; int y; int pre; }sqmaze[100];

int maze[M][M]; /*-----定义迷宫，1为墙壁，0为通路-----*/ sqmaze *mazepath; int *m,*n;

2.对抽象数据类型中的部分基本操作的伪码算法如下：

由于我定义的栈是用数组来实现的，因此与栈的基本操作的名称及操作有点不一样。 /*数组表示的栈的全部元素的出栈，并显示出来*/ void footprint(int seat) { int i; i=seat; do

{ printf(

/*这函数包含了栈的入栈和栈顶元素的出栈*/ void pass() {

int zx[5],zy[5];

int i,j,x,y,z,front=1,rear=1,find=0; printf(

scanf(

zx[1]=0; zx[2]=1; zx[3]=0; zx[4]=-1; zy[1]=1; zy[2]=0; zy[3]=-1; zy[4]=0; enter();

while(frontx; y=mazepath[front]->y; for(z=1;z

mazepath[rear]->x=i; mazepath[rear]->y=j; mazepath[rear]->pre=front; maze[i][j]=-1; }

if(i==*m && j==*n) { footprint(rear); find=1; } } front++; } if(!find)

printf(

3.主函数和其他函数的伪码算法 main() {

int row,col;

int b[10][10]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1},

{1,0,1,1,0,0,0,1,0,1}, {1,0,0,0,0,1,0,0,0,1}, {1,0,1,1,1,1,1,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}, }; int i,j;

clrscr(); /*清屏*/ for(;;){

switch(menu_select()){ case 0:{ clrscr();

printf(

printf(

/*-----创建迷宫-----*/

void creatmaze(int maze[M][M],int m,int n) {

int i,j,t;

printf(

{

scanf(

/*-----输出迷宫-----*/

void printmaze(int maze[M][M],int m,int n) {

int i,j;

printf(

printf(

printf(

printf(

/*-----输入进口的坐标-----*/ void enter() {

int a,b;

printf(

/*-----主菜单定义-----*/ int menu_select() {

char s[80]; int c;

gotoxy(1,25); /*将光标定在第25行第1列*/

printf(

printf(

printf(

printf(

printf(

4 函数调用关系

enter()

footprint

四、调试分析

⒈ 开始的时候将迷宫经过的用数组表示栈的定义sqmaze *mazepath;放在main（）函数中，在编译的时候会出现一个警告的提示“可能在*mazepath定义以前已经使用”，最后将次语句作为全局变量就解决了。

⒉ 由于每次在迷宫的出口是固定的，这在用户用起来不怎么通用，因此为了解决这个问题我在pass()函数中加入了语句printf(

5. 在定义函数pass（）的时候，开始的循环语句的结束条件不对，导致一直出现不了正确

的结果，最后一一检查和用实例迷宫一一执行pass函数的语句，发现是循环语句的条件少了！find即应该为while(front

6. 在设计主菜单的时候在改变选项一直不能很好的衔接，最后查找相关的书才知道要在主

菜单函数中加入gotoxy(1,25); printf(

7.在利用主菜单的时候发现有些输出提示语句不能正常的输出，一直没有找到时什么原因，例如在enter（）函数里printf(

各操作的算法时间复杂度比较合理

enter()为O(1) footprint（）为O(n), 其中n表示所经过的坐标数 creatmaze(),printmaze()和pass()为O(n*m)，其中m和n为迷宫的行列。

9.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使

调试也较顺利，各模块有较好的可重用性。

五、用户手册

1. 本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp1Prb3.c； 2. 在该程序的数组中，其中迷宫数组的第一个元素空间没有使用，因此下标是从1开始的。而且在输入迷宫数组的行列的时候注意应该在所输入的行列中加2，由于外围要设置为1表示墙壁。

3. 进入主菜单显示的用户界面为：

注：0：表示用户根据自己的需求创建迷宫； 1：表示用户使用程序提供的迷宫；

2：表示退出程序状态

4. 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面，用户根据妖气键入相应的数据，都能看完整个演示过程。

六、测试结果

按任意键进入主菜单界面，选择0进入自己建立一个迷宫： 其中输入的迷宫是 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 入口为（6,6）；出口为（2,3）。所经过的路径如图：

按任意键回到主菜单，选择1进入程序提供的迷宫，输入入口（9,9），出口为（2,2），经过的路径如图所示：

七、附录：源程序 #include #include #include #include #define STACKSIZE 100 #define M 100

/*-----用数组定义栈表示经过的路径-----*/ typedef struct { int x; int y;

int pre;

}sqmaze1[100];

int maze[M][M]; /*-----迷宫表示，1表示墙壁，0表示通路-----*/ sqmaze1 *sqmaze;

int *m,*n; /*------迷宮的入口坐标-----*/ /*-----迷宫的入口-----*/ void enter() {

int a,b;

printf(

/*-----输出一条通路-----*/ void footprint(int seat) { int i; i=seat; do

{ printf(

/*-----寻找一条最短的通路-----*/ void pass() {

int zx[5],zy[5];

int i,j,x,y,z,front=1,rear=1,find=0; printf(

mazepath[1]->y为迷宫的出口*/ sqmaze[1]->pre=0; maze[1][1]=-1;

zx[1]=0; zx[2]=1; zx[3]=0; zx[4]=-1; zy[1]=1; zy[2]=0; zy[3]=-1; zy[4]=0; enter();

while(frontx;

/*mazepath[1]->x

和

y=sqmaze[front]->y; for(z=1;z

sqmaze[rear]->x=i; sqmaze[rear]->y=j; sqmaze[rear]->pre=front; maze[i][j]=-1; }

if(i==*m && j==*n) { footprint(rear); find=1; } } front++; } if(!find)

printf(

/*-----创建迷宫-----*/

void creatmaze(int maze[M][M],int m,int n) {

int i,j,t;

printf(

scanf(

/*-----输出迷宫-----*/

void printmaze(int maze[M][M],int m,int n) {

int i,j;

printf(

for(i=1;i

{

printf(

for(j=1;j

printf(

}

printf(

}

/*-----主菜单定义-----*/

int menu_select()

{

char s[80];

int c;

gotoxy(1,25); /*将光标定在第25行第1列*/

printf(

clrscr(); /*清屏*/

gotoxy(1,1);

printf(

printf(

printf(

printf(

printf(

do{

printf(

scanf(

c=atoi(s); /*将输入的字符串转化为整型*/

}while(c2);

return c;

}

/*-----主函数-----*/

main()

{

int row,col;

int b[10][10]={ {1,1,1,1,1,1,1,1,1,1},

{1,0,0,1,0,0,0,1,0,1},

{1,0,1,1,0,0,0,1,0,1},

{1,0,0,0,0,1,0,0,0,1},

11

{1,0,1,1,1,1,1,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}, };

int i,j;

clrscr(); /*清屏*/

for(;;){

switch(menu_select()){

case 0: { clrscr();

printf(

scanf(

creatmaze(maze,row,col);

printmaze(maze,row,col);

pass();

break; }

case 1: { clrscr();

printf(

for(j=1;j

maze[i][j]=b[i-1][j-1];

printmaze(maze,8,8);

pass();

break; }

case 2: exit(0);

}

}

}

12 and