数据结构与算法----迷宫求解课程设计

课 程 设 计

课程设计名称： 迷宫求解 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ：

课程设计时间： 2010-6-20

专业课程设计任务书

学生姓名 题 目 课题性质 指导教师 专业班级 迷宫求解 学号 其它 课题来源 同组姓名 自拟课题 建立迷宫，在迷宫中寻找任意两坐标间是否存在路径，并显示出该路径。为了保证在任何位置上都能沿远路退回，需要用一个后进先出的结构来保存从主要内容 入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想。 1．应用数据结构基础知识进行实际问题求解与分析； 任务要求 2．编程实现算法 3．具有良好的界面，操作方便灵活、简洁高效。 4．按要求撰写课程设计报告和设计总结。 1．《数据结构》，严蔚敏，吴伟民，清华大学出版社， 2．《C程序设计（第二版）》，谭浩强，北京，清华大学出版社，1999. 3．《C++实用教程（第一版）》，杨明军、董亚卓、汪黎，人民邮电出版社，参考文献 2002. 4. 《Visual C++实用教程（第一版）》，张荣梅、梁晓林，冶金工业出版社，2004 指导教师签字： 审查意见 教研室主任签字： 年 月 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页

1 需求分析

本课程设计内容是解决迷宫问题。迷宫是一个矩形区域，有一个入口和出口。在迷宫内部不能穿越墙或障碍。输入一个m*n大小的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求寻找一条从入口到出口的路径。由于计算解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前进：否则沿原路退回，换一个方向再继续探索；直至所有可能的通路都探索为止。为了保证在任何位置上都能沿远路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想。

首先，在计算机中可以用0、1图表示迷宫。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道。假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方向均“不可通”，则应从“当前路径”上删除该通道。所谓“下一位置”指的是当前位置四周4个方向（东、南、西、北）“1”。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道”的操作即为“出栈”。

2 概要设计

1、主要设计思想

若当前位置可通，则纳入当前路径，并继续朝下一个位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块.设以栈记录当前路径，则栈顶中存放的是当前路径上最后一个通道块.由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的才操作即为出栈. 设顶当前位置的初值为入口位置；

1

Do{

若当前位置可通，

则{ 将当前位置插入栈顶； //纳入通路

若该位置是出口位置，则结束； //求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置； } 否则，

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

则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通； 则{ 删去栈顶位置； //从路径中删除该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空 2、数据结构设计考虑

1) 创建一个Int类型的二维数组Maze(i,j),用来存放0和1 ；创建一个堆栈，用来存储当前路径

2) 创造一个栈包括（*top表示栈顶，*base表示栈基址，stackSize表示栈容量）

堆栈中每个空间包括（ord表示当前位置在路径上的序号，seat表示当前坐标，di表示往下一坐标的方向）当前坐标包括（r表示行，c表示列） 3、主要采取三大模块：主程序模块、栈模块和迷宫模块 栈模块：实现迷宫数据的抽象化和对迷宫数据的处理； 迷宫模块：实现迷宫数据抽象类型； 主程序模块：初始化迷宫模块。 4、逻辑结构存储结构 a. 逻辑结构：

创建一个堆栈，含有（头指针 top,栈深stackSize） 堆栈中每个结点含有（指针next，行r, 列c） b. 存储结构：

2

堆栈结构： 坐标结构： 定义：

#define MAXNUM 100/* 栈中最大元素个数 */ #define N 11 /*地图的第一维长度*/ #include #include typedef struct { int x;/* 行下标 */ int y;/* 列下标 */ int d;/* 运动方向 */ } DataType;

struct SeqStack { /* 顺序栈类型定义 */ int top; /* 指示栈顶位置 */ DataType s[MAXNUM]; }

3 运行环境

Microsoft Visual C++6.0：

Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment,IDE）。Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。

4 开发工具和编程语言

编程语言为 C语言

5 详细设计

#include #include

#define STACK_INIT_SIZE 1000

3

int n=-1; int sumN=0;

一、栈模块 struct Stack {

int TheOriginali[STACK_INIT_SIZE];//保存进栈元素的坐标i. int TheOriginalj[STACK_INIT_SIZE];//保存进栈元素的坐标j. int top; int base; };

void initStack(struct Stack *p) {

p->top=p->base=0; }//初始化.

Push(struct Stack *p,int i,int j) {

sumN=sumN+1; n=n+1;

p->top=p->top+1; p->TheOriginali[n]=i; p->TheOriginalj[n]=j; }//进栈.

Pop(struct Stack *p,int readij[1]) {

sumN=sumN+1; n=n-1;

4

p->top=p->top-1;

readij[0]=p->TheOriginali[n]; readij[1]=p->TheOriginalj[n]; }//出栈并读出前一步的坐标.

二、迷宫模块

initMaze(int Maze[9][8])//建迷宫. { int i;

for (i=0;i<=8;i++) {Maze[0][i]=1;} for (i=0;i<=9;i++) {Maze[i][0]=1;} for (i=0;i<=8;i++) {Maze[9][i]=1;} for (i=0;i<=9;i++) {Maze[i][8]=1;}

Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]=1;

Maze[2][1]=1;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=0;

Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=1;

Maze[4][1]=1;Maze[4][2]=0;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4][6]=0;Maze[4][7]=1;

Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=0;Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;

Maze[6][1]=1;Maze[6][2]=0;Maze[6][3]=1;Maze[6][4]=1;Maze[6][5]=1;Maze[6][6]=1;Maze[6][7]=0;

Maze[7][1]=1;Maze[7][2]=0;Maze[7][3]=0;Maze[7][4]=0;Maze[7][5]=1;Maze[7][6]=1;Maze[7][7]=1;

Maze[8][1]=0;Maze[8][2]=0;Maze[8][3]=1;Maze[8][4]=0;Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0; }

5

Judgment(struct Stack *p,int Maze[9][8],int Entrancei,int Entrancej,int Exportsi,int Exportsj) { int i,j; int readij[1]; i=Entrancei; j=Entrancej;

printf(\"第%d步 (%d,%d)--->\\n\

if(i==Exportsi&&j==Exportsj) {printf(\"!!!OK\\n\");return 0;} //函数出口.

else if(Maze[i][j+1]==0) {j=j+1;Push(p,i,j);Maze[i][j-1]=1;Maze[i][j]=1;} else if(Maze[i+1][j]==0) {i=i+1;Push(p,i,j);Maze[i-1][j]=1;Maze[i][j]=1;} else if(Maze[i][j-1]==0) {j=j-1;Push(p,i,j);Maze[i][j+1]=1;Maze[i][j]=1;} else if(Maze[i-1][j]==0) {i=i-1;Push(p,i,j);Maze[i+1][j]=1;Maze[i][j]=1;} //东南西北探路.走过的路进栈后全都标志为1. else {

Pop(p,readij); i=readij[0]; j=readij[1];

if(p->top==p->base) {printf(\"找不到出口\\n\");return 0;} //涵数出口. }

//无路走时出栈并原路返回.

Judgment(p,Maze,i,j,Exportsi,Exportsj); }

三、主程序模块 main() {

6

struct Stack *p; struct Stack S; int Maze[9][8];

int m,n,data1[1],data2[1]; int Entrancei,Entrancej; int Exportsi,Exportsj; int sum=0; p=&S;

initMaze(Maze);

printf(\"迷宫图(1代表墙不通的意思,0代表路)\\n\");

printf(\"************************************************\\n\"); for(m=0;m<=9;m++) {

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

printf(\"%4d\ if(sum%9==0) printf(\"\\n\"); } }

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

//打印迷宫图.

printf(\"请输入入口坐标:\"); scanf(\"%d\scanf(\"%d\

Entrancei=data1[0];Entrancej=data1[1]; //迷宫入口坐标.

printf(\"请输入出口坐标:\"); scanf(\"%d\scanf(\"%d\

7

Exportsi=data2[0];Exportsj=data2[1]; //迷宫出口坐标.

if(data1[0]>9||data1[1]>8||data2[0]>9||data2[1]>8|| data1[0]<0||data1[1]<0||data2[0]<0||data2[1]<0) {printf(\"ERROR!!!数据异常!!\\n\");} else

{ printf(\" 过程:\\n\"); initStack(p);

Push(p,Entrancei,Entrancej);

Judgment(p,Maze,Entrancei,Entrancej,Exportsi,Exportsj); } }

6 调试分析

在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。在迷宫中用‘1’表示墙，用‘0’表示通道；探索过的路径用‘.’表示可通过，用‘#’表示死胡同。定义了一个二维字符数组来表示迷宫，将迷宫的入口位置的坐标，在路径中的序号及该位置走到下一个位置的方向放入栈中。在设计程序的过程中由于没有注意到行列都是从0开始的，导致输出时少了一行和一列，后来行数和列数都加1后就正确了。虽然这个程序运行后可以得到正确的实验结果，但是有时还会显示存在着一个警告（warning C4715: 'nextDir' : not all control paths return a value）就是说不是所有的控制路径都能返回一个真值。我上网查了许多的资料还是不能解决这个问题，是做这个程序设计留下的一个遗憾。通过这次的程序设计我学习到了很多的东西，明白了做一个大的程序题要用到以前学到过的很多知识，就说我的程序用的是栈的知识，还用了Switch语句和for语句这两个循环语句，用了二维字符数组的知识。迷宫问题还有许多其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。

8

7 测试结果

任意输入入口坐标和出口坐标，将会得到一条路径或者是找不到路径。 例如输入入口坐标2、3，出口坐标4、6，在坐标2、3和4、6间便会得到一条路径。如图1

图1 存在路径

9

输入入口坐标5、6，出口坐标7、8,在这两点间便没有路径。如图2

图2 不存在路径

10

参考文献

[1].《数据结构》，严蔚敏，吴伟民，清华大学出版社，2002 [2]《C++程序设计教程（第二版）》，钱能，清华大学出版社，2005

[3]《C++实用教程（第一版）》，杨明军、董亚卓、汪黎，人民邮电出版社，2002. [4]《C程序设计（第二版）》，谭浩强，北京，清华大学出版社，1999

[5]《Visual C++实用教程（第一版）》，张荣梅、梁晓林，冶金工业出版社，2004

11

心得体会

通过本次课程设计，增强了我对栈、数组等数据结构的理解和应用，了解了数学建模的基本方法。进一步掌握了栈、二维数组的定义、基本操作和存储结构，并掌握了栈、二维数组的C语言的实现。 在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

12