迷宫问题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("(%d,%d) ",mazepath[i]->x,mazepath[i]->y);

i=mazepath[i]->pre; }while(i!=0); }

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

int zx[5],zy[5];

int i,j,x,y,z,front=1,rear=1,find=0; printf("Please input the exit :");

scanf("%d%d",&mazepath[1]->x,&mazepath[1]->y); mazepath[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; 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("no find any way!"); }

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("Please input maze's row and column(row,col

printf("you hava choice the computee's maze!\n\n"); for(i=1;i

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

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

int i,j,t;

printf("Please input your maze;\n"); for(i=1;i

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

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

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

int i,j;

printf("Please output your maze;"); for(i=1;i

printf("\n"); for(j=1;j

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

printf("\n"); }

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

int a,b;

printf("Please input the enter m and n:"); scanf("%d%d",&a,&b); *m=a; *n=b;}

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

char s[80]; int c;

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

printf("press any key enter menu ......\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/ clrscr(); /*清屏*/ gotoxy(1,1);

printf("***************MENU***************\n\n"); printf(" 0. make a maze by youself!\n"); printf(" 1. use the computer's maze!\n"); printf(" 2. Quit!\n");

printf("**********************************\n"); do{

printf("\n Enter you choice (0~2):\n"); /*提示输入选项*/ scanf("%s",s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整型*/ }while(c2); return c; }

4 函数调用关系

enter()

footprint

四、调试分析

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

⒉ 由于每次在迷宫的出口是固定的，这在用户用起来不怎么通用，因此为了解决这个问题我在pass()函数中加入了语句printf("Please input the exit :"); scanf("%d%d",&mazepath[1]->x,&mazepath[1]->y);就实现了通用性。

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

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

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

菜单函数中加入gotoxy(1,25); printf("press any key enter menu ......\n"); getch(); clrscr(); gotoxy(1,1);

7.在利用主菜单的时候发现有些输出提示语句不能正常的输出，一直没有找到时什么原因，例如在enter（）函数里printf("Please input the enter:");在结果镇南关不能输出。 8.算法的时空分析

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

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("Please input the enter:"); scanf("%d%d",&a,&b); *m=a; *n=b; }

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

{ printf("(%d,%d) ",sqmaze[i]->x,sqmaze[i]->y); i=sqmaze[i]->pre; }while(i!=0); }

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

int zx[5],zy[5];

int i,j,x,y,z,front=1,rear=1,find=0; printf("Please input the exit m and n:"); scanf("%d%d",&sqmaze[1]->x,&sqmaze[1]->y);

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();

/*mazepath[1]->x

和

while(frontx; 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("no find any way!"); }

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

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

int i,j,t;

printf("Please input your maze;\n"); for(i=1;i

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

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

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

int i,j;

printf("Please output your maze;");

for(i=1;i

{

printf("\n");

for(j=1;j

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

}

printf("\n");

}

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

int menu_select()

{

char s[80];

int c;

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

printf("press any key enter menu ......\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/

clrscr(); /*清屏*/

gotoxy(1,1);

printf("***************MENU***************\n\n");

printf(" 0. make a maze by youself!\n");

printf(" 1. use the computer's maze!\n");

printf(" 2. Quit!\n");

printf("**********************************\n");

do{

printf("\n Enter you choice (0~2):\n"); /*提示输入选项*/

scanf("%s",s); /*输入选择项*/

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

11

{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("Please input maze's row column(row,col

scanf("%d%d",&row,&col);

creatmaze(maze,row,col);

printmaze(maze,row,col);

pass();

break; }

case 1: { clrscr();

printf("you hava choice the computee's maze!\n\n"); for(i=1;i

for(j=1;j

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

printmaze(maze,8,8);

pass();

break; }

case 2: exit(0);

}

}

}

12 and