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

1、课程设计任务书题目迷宫设计学号：姓名：专业：网络技术课程：数据结构指导教师：职称：讲师完成时间：2013年12月-2014年1月年月曰课程设计任务书及成绩评定实验任务：通过数据结构运用c语言写迷宿算法,实验目的：通过综合性课程设计题目的完成过程，运用所学数据结构知识,解决生活中遇到的实际问题，达到活学活用，所学所用的目的，进一步理解数据结构的学习目的，提高实际应用水平日期:指导教师签字:成绩：指导教师签字：日期:联想笔记本win7系统，win-tc课程设计进度计划起至日期工作内容备注13年12月初选择题目13年12月中旬13年12月下旬制定方案制作设计参考文献、资料索引序号文献、资料名称编者者

2、出版单位蒋秀英燕孝飞等，数据结构.东营：中国石油大学，2011严蔚敏.数据结构（c语言版）.北京：清华大学出版社，2007目录?迷宿求解（1）问题描述2）需求分析及设计思路3）数据结构定义4）系统功能模块介绍5）源代码6）运行结果及调试分析7）课程设计总结迷宫求解(1) 问题描述输入一个任意大小的迷宿数据，用递归和非递归两种方法求出一条走出迷宿的路径，并将路径输出。(2) 需求分析及设计思路从入口出发，按某一方向向前探索，若能走通并且未走过，即某处可以到达，则到达新点，否则试探下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到找到一条通路，或无路可走又返回入口

3、点。在求解过程中，为了保证在到达某一点后不能向前继续行走(无路)时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈(递归不需要)保存所能够到达的每一点的下标及从该点前进的方向。设迷H为m行n列，利用mazemn来表示一个迷H,mazeij=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有四个方向可以试探，而四个角点有两个方向，其他边缘点有三个方向，为使问题简单化，用mazem+2n+2来表示迷宿，而迷宿的四周的值全部为1,这样做使问题简单了，每个点的试探方向全部为4,不用再判断当前点的试探方向有几个。数据结构定义#definem6#definen8#define

4、MAXSIZE100/四周为1代表围墙,0为可走路径intmazem+2n+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)typedefstructintx,y;/*试探方向*/item;itemmove4=0,1,1,0,0,-1,-1,0;typedefstruct/*栈的

5、设计*/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(intmazen+2,itemmove,i

6、ntx0,inty0)递归算法求迷!路径：intmazepath1(intmazen+2,itemmove,intx,inty)主函数：intmain()出口坐标已定，利用while循环多次输入入点坐标，调用mazepath(intmazen+2,itemmove,intx0,inty0)输出可走的路径(5)源代码#include<stdio.h>#include<stdlib.h>#definem6#definen8#defineMAXSIZE100intmazem+2n+2=1,1,1,1,1,1,1,1,1,1,/四周为1代表围墙,0为可走路径1,0,1,1,1,

7、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)typedefstructintx,y;/*试探方向*/item;itemmove4=0,1,1,0,0,-1,-1,0;typedefstruct/*栈的设计*/intx,y,d;/*纵横坐标及方向*/DataType;typedefstruct/*栈*/DataTypedataMAXSIZE

8、;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,D

9、ataTypex)/*在栈顶插入一新元素x,入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/if(S->top=MAXSIZE-1)return0;/*栈满不能入栈*/elseS->top+;S->dataS->top=x;return1;intPop_SeqStack(PSeqStackS,DataType*x)/*删除栈顶元素并保存在*x,入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/if(Empty_SeqStack(S)return0;/*栈空不能出栈*/else*x=S->dataS->top;S->top-;retur

10、n1;voidDestroy_SeqStack(PSeqStack*S)if(*S)free(*S);*S=NULL;return;/*利用栈的非递归算法*/intmazepath(intmazen+2,itemmove,intx0,inty0)(/*求迷宿路径,入口参数：指向迷宿数组的指针，下标移动的增虽数组，开始点(x0,yO),到达点(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)(pri

11、ntf("栈初始化失败");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)/*存在剩余方向可以搜索*/(i=x+moved.x;j=y+moved.y;if(mazeij=0)/*(此方向可走*/temp.x=x;temp.y=y;temp.d=d;Push_SeqStack(S,temp);/*走的路径*/点x,y可以走，用栈保存可以x=i;y=j;

12、mazexy=-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(d<4)*/*while*/Destroy_SeqStack(&S);/*销毁栈*/return0;/*迷宿无

13、路*/*递归算法*/intmazepath1(intmazen+2,itemmove,intx,inty)/*求迷宿路径，入口参数：迷宿数组，下标移动的增虽数组，开始点(x,y),以及开始点对应的步数step,(m,n)是终点，返回值：1表示求出路径，0表示无路径*/inti;intstep=0;step+;mazexy=step;if(x=m&&y=n)return1;/*起始位置是出口，找到路径,结束*/for(i=0;i<4;i+)if(mazex+movei.xy+movei.y=0)if(mazepath(maze,move,x+movei.x,y+movei.

14、y)return1;/*下一个是出口，则返回*/step-;mazexy=0;return0;)intmain()(inti,j,k;charu;intx,y;printf("*欢迎进入迷!游戏图为一个6*8的迷宿：n");printf("ffor(i=0;i<m+2;i+)(printf("*");for(j=0;j<n+2;j+)(*n");printf("下*n);printf("%-2d”,mazeij);)printf(");printf("n");printf(

15、"f*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("恭喜！走出迷Hnn");elseprintf(

16、"迷宿无路nn");printf("继续游戏:");scanf("%c”,&u);printf("n");return0;(6)运行结果及调试分析11111tCJCXWI1111r>£rx1111*ww111*Tj1inBillB0(I1111«*«r/tu*Vym：4mlHEIt000111101180wwirilr且以wjy竺*睥b*j<wk仁j,i>-；入口jy：31迷富尢路运行结果达到预期结果达到，递归和非递归两种方法求出一条走出迷宿的路径，并将路径输出，并实现多次输入入口点来验证程序的可行性。(7)课程设计总结在这次实践中遇到了各种问题，碰到问题有时总是百思不得其解经过反复测试，最终确定原因，导致数据无法更新。迷宿问题：是加深对栈运用的好程序。这个程序又加了个递归的算法，相同的程序不同的算法。我结合老师提过的思想与教材上的例子，很顺利的完成了这个程序。其实在写完这个程序后。皇天不负有心人，按照步骤，忙碌了两周，在不断地努力下，总算将