数据结构实验报告-迷宫问题-葛晨阳

数据结构课程设计设计题目：迷宫问题学院：信息技术学院专业：网络工程班级：B1204学号：0913120419姓名：葛晨阳指导老师：戴玉洁2013年7月20日—2013年8月1日课程设计日期：

实验题目一、问题描述输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。二、实现目标综合运用递归、栈等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力三、主要功能模块及实现功能（创建一顺序栈：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)输出可走的路径}四、主要模块流程图初始化初始化开始游戏开始游戏nn，结束，结束y，继续y，继续输入数据输入数据系统调用运算系统调用运算生成路径无解生成路径无解五、实验结果及测试数据初始界面游戏界面游戏界面附录:源代码#include<stdio.h>#include<stdlib.h>#definem6#definen8#defineMAXSIZE100intmaze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},//四周为1代表围墙,0为可走路径{1,0,0,1,1,0,0,0,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,0,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/*栈的设计*/{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;return1;}}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(d<4)/*存在剩余方向可以搜索*/{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)<-",temp.x,temp.y);/*打印可走的路径*/}Destroy_SeqStack(&S);/*销毁栈*/return1;}elsed=0;/*方向复位，从第一个方向开始试探*/}elsed++;/*试探下一个方向*/}/*while(d<4)*/}/*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;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)) return1;/*下一个是出口，则返回*/ } step--; maze[x][y]=0; return0;}intmain(){inti,j,k;charu;intx,y;printf("*****欢迎进入迷宫游戏*****\n");printf("~~~~~~~~游戏快乐~~~~~~~~~\n");printf("这是6*8的迷宫\n");printf("****************************\n");for(i=0;i<m+2;i++){printf("****");for(j=0;j<n+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