课程设计任务书
题目： 迷宫设计
学 号：
姓 名：
专 业： 网络技术
课 程： 数据结构 指导教师： 职称： 讲师
完成时间： 2013年 12 月----2014 年 1 月
年 月 日
课程设计任务书及成绩评定
实验任务：通过数据结构运用c语言写迷宫算法， 实验目的：通过综合性课程设计题目的完成过程，运用所学数据结构知识，解决生活中遇到的实际问题，达到活学活用，所学所用的目的，进一步理解数据结构的学习目的，提高实际应用水平 指导教师签字： 、 日期： 成绩： 指导教师签字： 日期：
1
联想笔记本win7系统，win-tc 课程设计进度计划 起至日期 工作内容 备注 13年12月初 13年12月中旬 13年12月下旬 选择题目 制定方案 制作设计 参考文献、资料索引 序号 文献、资料名称 编著者 出版单位 [1]蒋秀英 燕孝飞等，数据结构. 东营：中国石油大学，2011 [2]严蔚敏.数据结构（c语言版）.北京：清华大学出版社，2007 2
3
目 录
一． 迷宫求解································ （1） 问题描述··········································· （2） 需求分析及设计思路································· （3）数据结构定义········································ （4）系统功能模块介绍···································· （5）源代码·············································· （6）运行结果及调试分析 ································ （7）课程设计总结 ·····························
4
一．迷宫求解
（1） 问题描述
输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。
（2）需求分析及设计思路
从入口出发，按某一方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到一条通路，或无路可走又返回入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈（递归不需要）保存所能够到达的每一点的下标及从该点前进的方向。设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1；其中：0表示通路，1表示不通，当从某点向下试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他边缘点有三个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个。
（3）数据结构定义 #define m 6 #define n 8
#define MAXSIZE 100
//四周为1代表围墙,0为可走路径 int maze[m+2][n+2]={
{1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,0,0,0,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,0,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1} }; //入口坐标为（1，1），出口坐标为（6，8） typedef struct
{ int x,y;/*试探方向*/ }item;
item move[4]={{0,1},{1,0},{0,-1},{-1,0}}; typedef struct/*栈的设计*/
5
{int x,y,d; /*纵横坐标及方向*/ }DataType;
（3） 系统功能模块介绍 创建一顺序栈：
PSeqStack Init_SeqStack(void) 判断栈是否为空：
int Empty_SeqStack(PSeqStack S) 在栈顶插入一新元素x：
int Push_SeqStack (PSeqStack S, DataType x) 删除栈顶元素并保存在*x ：
int Pop_SeqStack(PSeqStack S ,DataType *x) 销毁栈 ：
void Destroy_SeqStack(PSeqStack *S) 利用栈的非递归算法求迷宫路径：
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0) 递归算法求迷宫路径：
int mazepath1(int maze[][n+2],item move[],int x,int y) 主函数： int main()
{ 出口坐标已定，
利用while循环多次输入入点坐标，
调用mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0) 输出可走的路径 }
（5）源代码
#include #include #define m 6 #define n 8#define MAXSIZE 100 int maze[m+2][n+2]={
{1,1,1,1,1,1,1,1,1,1},//四周为1代表围墙,0为可走路径 {1,0,1,1,1,0,1,1,1,1}, {1,0,0,0,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,0,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1} }; //入口坐标为（1，1），出口坐标为（6，8）
6
typedef struct {
int x,y;/*试探方向*/ }item;
item move[4]={{0,1},{1,0},{0,-1},{-1,0}};
typedef struct/*栈的设计*/ {
int x,y,d; /*纵横坐标及方向*/ }DataType;
typedef struct/*栈*/ {
DataType data[MAXSIZE]; int top;
}SeqStack,*PSeqStack;
PSeqStack Init_SeqStack(void)
{ /*创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败*/ PSeqStack S;
S=(PSeqStack)malloc(sizeof(SeqStack)); if (S)
S->top= -1; return S; }
int Empty_SeqStack(PSeqStack S)
{ /*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/
if (S->top== -1) return 1; else
return 0; }
int Push_SeqStack (PSeqStack S, DataType x)
{ /*在栈顶插入一新元素x， 入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/
if (S->top==MAXSIZE-1)
return 0; /*栈满不能入栈*/ else {
S->top++;
S->data[S->top]=x;
7
return 1; } }
int Pop_SeqStack(PSeqStack S ,DataType *x)
{ /*删除栈顶元素并保存在*x， 入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/
if (Empty_SeqStack ( S ) )
return 0; /*栈空不能出栈 */ else {
*x= S->data[S->top]; S->top--; return 1; } }
void Destroy_SeqStack(PSeqStack *S) {
if(*S)
free(*S); *S=NULL; return; }
/*利用栈的非递归算法*/
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0) { /*求迷宫路径, 入口参数：指向迷宫数组的指针，下标移动的增量数组，开始点（x0，y0），到达点（m，n）, 返回值：1表示求出路径，0表示无路径*/
PSeqStack S ; DataType temp ; int x, y, d, i, j ;
temp.x=x0 ;temp.y=y0 ; temp.d=-1 ; S=Init_SeqStack(); /*初始化栈*/ if (!S)
{ printf(\"栈初始化失败\"); return(0); }
Push_SeqStack (S,temp) ; /* 迷宫入口点入栈 */ while (! Empty_SeqStack (S ) ) {
Pop_SeqStack(S,&temp);
x=temp.x ; y=temp.y ; d=temp.d+1 ;
while (d<4) /*存在剩余方向可以搜索 */ {
8
i=x+move[d].x ; j=y+move[d].y ; if( maze[i][j]==0 ) /*此方向可走*/ {
temp.x=x;temp.y=y; temp.d=d;
Push_SeqStack ( S, temp ) ;/*点{x,y}可以走，用栈保存可以走的路径*/
x=i; y=j; maze[x][y]= -1; if (x==m&&y==n) /*迷宫有路*/ {
while( !Empty_SeqStack(S) ) {
Pop_SeqStack (S,&temp) ; printf(\"(%d,%d)<- \;/*打印可走的路径*/
}
Destroy_SeqStack(&S); /*销毁栈*/ return 1 ; }
else d=0 ;/*方向复位，从第一个方向开始试探*/ }
else d++ ;/*试探下一个方向*/ } /*while (d<4)*/ } /*while */
Destroy_SeqStack(&S); /*销毁栈*/ return 0 ;/*迷宫无路*/ }
/*递归算法*/
int mazepath1(int maze[][n+2],item move[],int x,int y)
{/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点（x，y），
以及开始点对应的步数step，（m,n）是终点，返回值：1表示求出路径，0表示无路径*/ int i;
int step=0; step++;
maze[x][y]=step; if(x==m&&y==n) return 1; /*起始位置是出口，找到路径，结束*/
for(i=0;i<4;i++) {
if(maze[x+move[i].x][y+move[i].y]==0)
if(mazepath(maze,move,x+move[i].x,y+move[i].y))
9
return 1; /*下一个是出口，则返回*/ }
step--;
maze[x][y]=0; return 0; }
int main() { int i,j,k; char u; int x,y;
printf(\"*****欢迎进入迷宫游戏*****\\n\"); printf(\"下图为一个6*8的迷宫：\\n\");
printf(\"****************************\\n\"); for(i=0;iprintf(\"%-2d\ }printf(\"****\"); printf(\"\\n\"); }
printf(\"****************************\\n\"); printf(\"现在开始游戏？（y/n）:\"); scanf(\"%c\ while(u!='n') {
printf(\"请输入迷宫入口坐标(x,y)：\"); scanf(\"%d,%d\
printf(\"出口：(6,8)<-\"); k=mazepath(maze,move,x,y); printf(\"：入口\\n\");
if(k==1)printf(\"恭喜！走出迷宫\\n\\n\"); else printf(\"迷宫无路\\n\\n\");
printf(\"继续游戏:\"); scanf(\"%c\ printf(\"\\n\"); }
return 0; }
10
（6）运行结果及调试分析
运行结果达到预期结果达到，递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出，并实现多次输入入口点来验证程序的可行性。
（7）课程设计总结
在这次实践中遇到了各种问题，碰到问题有时总是百思不得其解经过反复测试，最终确定原因，导致数据无法更新。
迷宫问题：是加深对栈运用的好程序。这个程序又加了个递归的算法，相同的程序不同的算法。我结合老师提过的思想与教材上的例子，很顺利的完成了这个程序。其实在写完这个程序后。
皇天不负有心人，按照步骤，忙碌了两周，在不断地努力下，总算将此程序设计出来。尽管不完全是自己完成，但仍然很欣慰，因为在设计的过程中，让我了解到要设计一个大型程序，查找资料是至关重要的，在他人的基础上，再根据自己所学进行修改与调试，最后设计出自己想要的程序，这过程艰辛，但只要你持之以恒，定可将问题解决。 通过本次实验巩固了课本的基本知识，熟练运用课程知识。提高我的组织数据及编写程序的能力，使我能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的问题在计算机内部表示出来并用软件解决问题，本次实验大大提高了对编程的爱好，发现，只要认认真真的去思考，没有办不到的事情。
11
