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

课程设计课程设计名称：迷宫求解专业班级：学生姓名：学号：指导教师：课程设计时间： 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个方块均不可通，则应从当前路径上删除该通道块.设以栈记录当前路径，则栈顶中存放的是当前路径上最后一个通道块.由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的才操作即为出栈.设顶当前位置的初值为入口位置；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. 存储结构：堆栈结构：坐标结构：定义：#define MAXNUM 100/* 栈中最大元素个数 */#define N 11 /*地图的第一维长度*/#include#includetypedef 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 <stdio.h>#include <malloc.h>#define STACK_INIT_SIZE 1000int 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;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;}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",sumN,i,j);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(){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",Maze[m][n]);sum++;if(sum%9==0) printf("\n");}}printf("************************************************\n");//打印迷宫图.printf("请输入入口坐标:");scanf("%d",&data1[0]);scanf("%d",&data1[1]);Entrancei=data1[0];Entrancej=data1[1];//迷宫入口坐标.printf("请输入出口坐标:");scanf("%d",&data2[0]);scanf("%d",&data2[1]);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 调试分析在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。