《数据结构》课程设计报告迷宫求解

枣庄学院信息科学与工程学院课程设计任务书题目：迷宫设计学号：0315姓名：王宇专业：网络技术课程：数据结构指导教师：刘彩霞职称：讲师完成时间：2013年12月----2014年1月枣庄学院信息科学与工程学院制1年月日课程设计任务书及成绩评定实验任务：通过数据结构运用c语言写迷宫算法，实验目的：通过综合性课程设计题目的完成过程，运用所学数据结构知识，解决生活中遇到的实际问题，达到活学活用，所学所用的目的，进一步理解数据结构的学习目的，提高实际应用水平指导教师签字：、日期：2成绩：指导教师签字：日期：联想笔记本win7系统，win-tc课程设计进度计划起至日期工作内容备注313年12月初13年12月中旬13年12月下旬选择题目制定方案制作设计参考文献、资料索引序号文献、资料名称编著者出版单位[1]蒋秀英燕孝飞等，数据结构.东营：中国石油大学，2011[2]严蔚敏.数据结构（c语言版）.北京：清华大学出版社，20074目录一．迷宫求解································（1）问题描述···········································（2）需求分析及设计思路·································（3）数据结构定义········································（4）系统功能模块介绍····································（5）源代码··············································（6）运行结果及调试分析································（7）课程设计总结·····························5一．迷宫求解（1）问题描述输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。（2）需求分析及设计思路从入口出发，按某一方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到一条通路，或无路可走又返回入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈（递归不需要）保存所能够到达的每一点的下标及从该点前进的方向。设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1；其中：0表示通路，1表示不通，当从某点向下试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他边缘点有三个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个。（3）数据结构定义#definem6#definen8#defineMAXSIZE100//四周为1代表围墙,0为可走路径intmaze[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）typedefstruct{intx,y;/*试探方向*/}item;itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};typedefstruct/*栈的设计*/6{intx,y,d;/*纵横坐标及方向*/}DataType;（3）系统功能模块介绍创建一顺序栈：PSeqStackInit_SeqStack(void)判断栈是否为空：intEmpty_SeqStack(PSeqStackS)在栈顶插入一新元素x：intPush_SeqStack(PSeqStackS,DataTypex)删除栈顶元素并保存在*x：intPop_SeqStack(PSeqStackS,DataType*x)销毁栈：voidDestroy_SeqStack(PSeqStack*S)利用栈的非递归算法求迷宫路径：intmazepath(intmaze[][n+2],itemmove[],intx0,inty0)递归算法求迷宫路径：intmazepath1(intmaze[][n+2],itemmove[],intx,inty)主函数：intmain(){出口坐标已定，利用while循环多次输入入点坐标，调用mazepath(intmaze[][n+2],itemmove[],intx0,inty0)输出可走的路径}（5）源代码#includestdio.h#includestdlib.h#definem6#definen8#defineMAXSIZE100intmaze[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）7typedefstruct{intx,y;/*试探方向*/}item;itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};typedefstruct/*栈的设计*/{intx,y,d;/*纵横坐标及方向*/}DataType;typedefstruct/*栈*/{DataTypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;PSeqStackInit_SeqStack(void){/*创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败*/PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S-top=-1;returnS;}intEmpty_SeqStack(PSeqStackS){/*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/if(S-top==-1)return1;elsereturn0;}intPush_SeqStack(PSeqStackS,DataTypex){/*在栈顶插入一新元素x，入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/if(S-top==MAXSIZE-1)return0;/*栈满不能入栈*/else{S-top++;S-data[S-top]=x;8return1;}}intPop_SeqStack(PSeqStackS,DataType*x){/*删除栈顶元素并保存在*x，入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/if(Empty_SeqStack(S))return0;/*栈空不能出栈*/else{*x=S-data[S-top];S-top--;return1;}}voidDestroy_SeqStack(PSeqStack*S){if(*S)free(*S);*S=NULL;return;}/*利用栈的非递归算法*/intmazepath(intmaze[][n+2],itemmove[],intx0,inty0){/*求迷宫路径,入口参数：指向迷宫数组的指针，下标移动的增量数组，开始点（x0，y0），到达点（m，n）,返回值：1表示求出路径，0表示无路径*/PSeqStackS;DataTypetemp;intx,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(d4)/*存在剩余方向可以搜索*/{9i=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)-,temp.x,temp.y);/*打印可走的路径*/}Destroy_SeqStack(&S);/*销毁栈*/return1;}elsed=0;/*方向复位，从第一个方向开始试探*/}elsed++;/*试探下一个方向*/}/*while(d4)*/}/*while*/Destroy_SeqStack(&S);/*销毁栈*/return0;/*迷宫无路*/}/*递归算法*/intmazepath1(intmaze[][n+2],itemmove[],intx,inty){/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点（x，y），以及开始点对应的步数step，（m,n）是终点，返回值：1表示求出路径，0表示无路径*/inti;intstep=0;step++;maze[x][y]=step;if(x==m&&y==n)return1;/*起始位置是出口，找到路径，结束*/for(i=0;i4;i++){if(maze[x+move[i].x][y+move[i].y]==0)if(mazepath(maze,move,x+move[i].x,y+move[i].y))10return1;/*下一个是出口，则返回*/}step--;maze[x][y]=0;return0;}intmain(){inti,j,k;charu;intx,y;printf(*****欢迎进入迷宫游戏*****\n);printf(下图为一个6*8的迷宫：\n);printf(****************************\n);for(i=0;im+2;i++){printf(****);for(j=0;jn+2;j++){printf(%-2d,maze[i][j]);}printf(****);printf(\n);}printf(****************************\n);printf(现在开始游戏？（y/n）:);scanf(%c,&u);while(u!='n'){printf(请输入迷宫入口坐标(x,y)：);scanf(%d,%d,&x,&y);printf(出口：(6,8)-);k=mazepath(maze,move,x,y);printf(：入口\n);if(k==1)printf(恭喜！走出迷宫\n\n);elseprintf(迷宫无路\n\n);printf(继续游戏:);scanf(%c,&u);printf(\n);}return0;}11（6）运行结果及调试分析运行结果达到预期结果达到，递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出，并实现多次输入入口点来验证程序的可行